Возможно ли более быстрое суммирование по 0 в 1?

Question

У меня очень большой массив (например, 10 миллионов элементов), который состоит только из 1 и 0. У меня также есть несколько параллельных потоков (например, 10), и я хотел бы разбить этот большой массив на разные потоки и сделать каждый из них для суммирования части, за которую они отвечают.

Я кодировал проблему в C & pthreads, используя оператор "+". Однако, так как массив состоит только из 1 и 0, мне интересно, может ли быть более быстрый способ реализовать это суммирование? (через побитовые операторы, сдвиг и т. д.?) Поскольку я имею дело с очень большими массивами, наивное суммирование убивает производительность.

Answer 1

Вы добавляете 2 массива из 10 миллионов элементов ... на современный процессор, который может выполнять около 3 МИЛЛИАРДОВ команд в секунду (3GHz).

Даже если каждый отдельный элемент нужно было добавлять отдельно, вы можете добавить два целых массива за 0,003 секунды. (и это действительно наихудший сценарий. На 64-битной машине вы должны иметь возможность добавлять 64 элемента одновременно)

Если это не происходит во внутреннем цикле, это НЕ должно убивать производительность.

Подумайте о том, чтобы описать вашу проблему более полно и показать текущую реализацию.

Answer 2

Если вы можете перейти на использование всех бит вместо 1 на целое, производительность может быть, по крайней мере, увеличена;)

Также протестировано с SSE , __m128i _mm_add_epi32, регистрами , и т. Д. И т. Д. ( eka ), но не получило какого-либо заметного повышения. ( Очень вероятно, что я что-то не так сделал правильно. ).

Все зависит от среды, как создается массив, как он используется в других местах и ​​т. Д., И т. Д. Можно, например, изучить обработку GPU , но это снова становится специализированным и, вероятно, лучше используется при тяжелые вычисления тогда +.

Во всяком случае, вот примерный примерный результат, который я сделал на P4 2,8 ГГц с 2G медленно SDRAM; используя нормальный 1 цикл приращения, разверните 2 и 8 (на одну цифру, например, int) и второй битовый сдвиг из CountBitsSetParallel в сочетании с разверткой. Оба резьбовые и нет. Будьте осторожны с переворотом, если решите объединить его с потоками.

./bcn -z330000000 -s3 -i1
sz_i      : 330000000 * 4 = 1320000000 (bytes int array)
sz_bi     :  10312500 * 4 =   41250000 (bytes bit array)
set every :         3 (+ 1 controll-bit)
iterations:         1

Allocated 1320000000 bytes for ari    (0x68cff008 - 0xb77d8a08)
            1289062 KiB
               1258 MiB
                  1 GiB
Allocated  41250000 bytes for arbi   (0x665a8008 - 0x68cfecd8)
              40283 KiB
                 39 MiB
Setting values ...
--START--
    1 iteration over 330,000,000 values
Running TEST_00 Int Normal    ; sum = 110000001 ... time: 0.618463440
Running TEST_01 Int Unroll 2  ; sum = 110000001 ... time: 0.443277919
Running TEST_02 Int Unroll 8  ; sum = 110000001 ... time: 0.425574923
Running TEST_03 Int Bit Calc  ; sum = 110000001 ... time: 0.068396207
Running TEST_04 Int Bit Table ; sum = 110000001 ... time: 0.056727713

...

    1 iteration over 200,000,000
Running TEST_00 Int Normal    ; sum = 66666668 ... time: 0.339017852
Running TEST_01 Int Unroll 2  ; sum = 66666668 ... time: 0.273805886
Running TEST_02 Int Unroll 8  ; sum = 66666668 ... time: 0.264436688
Running TEST_03 Int Bit Calc  ; sum = 66666668 ... time: 0.032404574
Running TEST_04 Int Bit Table ; sum = 66666668 ... time: 0.034900498

...

  100 iterations over 2,000,000 values
Running TEST_00 Int Normal    ; sum = 666668 ... time: 0.373892700
Running TEST_01 Int Unroll 2  ; sum = 666668 ... time: 0.270294678
Running TEST_02 Int Unroll 8  ; sum = 666668 ... time: 0.260143237
Running TEST_03 Int Bit Calc  ; sum = 666668 ... time: 0.031871318
Running TEST_04 Int Bit Table ; sum = 666668 ... time: 0.035358995

...

    1 iteration over 10,000,000 values
Running TEST_00 Int Normal    ; sum = 3333335 ... time: 0.023332354
Running TEST_01 Int Unroll 2  ; sum = 3333335 ... time: 0.011932137
Running TEST_02 Int Unroll 8  ; sum = 3333335 ... time: 0.013220130
Running TEST_03 Int Bit Calc  ; sum = 3333335 ... time: 0.002068979
Running TEST_04 Int Bit Table ; sum = 3333335 ... time: 0.001758484

---

Темы ...

 4 threads, 1 iteration pr. thread over 200,000,000 values
Running TEST_00 Int Normal    ; sum = 66666668 ... time: 0.285753177
Running TEST_01 Int Unroll 2  ; sum = 66666668 ... time: 0.263798773
Running TEST_02 Int Unroll 8  ; sum = 66666668 ... time: 0.254483912
Running TEST_03 Int Bit Calc  ; sum = 66666668 ... time: 0.031457365
Running TEST_04 Int Bit Table ; sum = 66666668 ... time: 0.036319760

Snip ( Извините за короткое наименование ):

/* I used an array named "ari" for integer 1 value based array, and
   "arbi" for integer array with bits set to 0 or 1.

   #define SZ_I : number of elements (int based)
   #define SZ_BI: number of elements (bit based) on number of SZ_I, or
      as I did also by user input (argv)
 */

#define INT_BIT     (CHAR_BIT * sizeof(int))

#define SZ_I    (100000000U)
#define SZ_BI   ((SZ_I / INT_BIT ) + (SZ_I / INT_BIT  * INT_BIT  != SZ_I))

static unsigned int sz_i  = SZ_I;
static unsigned int sz_bi = SZ_BI;

static unsigned int   *ari;
static unsigned int   *arbi;

---

/* (if value (sz_i) from argv ) */
sz_bi = sz_i  / INT_BIT + (sz_i / INT_BIT  * INT_BIT  != sz_i);

...
#define UNROLL  8


static __inline__ unsigned int bitcnt(unsigned int v)
{
    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}

unsigned int test_03(void)
{
    unsigned int i   = 0;
    unsigned int sum = 0;
    unsigned int rep = (sz_bi / UNROLL);
    unsigned int rst = (sz_bi % UNROLL);

    while (rep-- > 0) {
        sum += bitcnt(arbi[i]);
        sum += bitcnt(arbi[i+1]);
        sum += bitcnt(arbi[i+2]);
        sum += bitcnt(arbi[i+3]);
        sum += bitcnt(arbi[i+4]);
        sum += bitcnt(arbi[i+5]);
        sum += bitcnt(arbi[i+6]);
        sum += bitcnt(arbi[i+7]);
        i += UNROLL;
    }

    switch (rst) {
    case 7: sum += bitcnt(arbi[i+6]);
    case 6: sum += bitcnt(arbi[i+5]);
    case 5: sum += bitcnt(arbi[i+4]);
    case 4: sum += bitcnt(arbi[i+3]);
    case 3: sum += bitcnt(arbi[i+2]);
    case 2: sum += bitcnt(arbi[i+1]);
    case 1: sum += bitcnt(arbi[i]);
    case 0:;
    }

    return sum;
}

Answer 3

Сначала преобразуйте в векторную сумму SIMD и уменьшите элементы векторного регистра до единой суммы в конце, вне вашего цикла. Это должно дать вам тот же результат в 1/4 операций. Затем разверните этот векторизованный цикл с суммированием каждой развернутой итерации в отдельном векторе, чтобы раскрыть больший параллелизм на уровне команд, и объедините частичные суммы в конце. При этом вам достаточно легко будет максимально использовать пропускную способность памяти.

Answer 4

Вы можете обнаружить, что индексация массива генерирует лучший код, чем индексация указателя. Посмотрите на ассемблер, сгенерированный компилятором, чтобы быть уверенным. С gcc это опция -S. На моем iMac с использованием gcc v4.2.1 я вижу, как индексирование генерирует более короткий код, хотя, поскольку я не знаю ассемблера x86, я не могу сказать, действительно ли он быстрее.

Кстати, массив int предписан аппаратными или внешними ограничениями?

Answer 5

На большинстве процессоров инструкция добавления является одной из самых быстрых. Логика, связанная с вычислением адреса элемента, извлечением элемента, расширением его по мере необходимости и т. Д., Увеличит фактическое добавление в 4-10 раз (и даже больше, если компилятор вставляет проверки границ массива, точки прерывания и т. Д.).

Первое, что нужно сделать, конечно, - преобразовать индекс массива в приращение указателя. Далее можно развернуть цикл, может быть, 20 раз. Хороший оптимизирующий компилятор может сделать что-то эквивалентное, но в этом случае вы можете (или не можете) сделать это лучше.

Еще одна хитрость, особенно если у вас есть массив байтов, заключается в том, чтобы сделать что-то похожее на то, что предлагает Новелократ (и, видимо, то, что предлагает Алекс) - привести указатель массива к указателю на long и извлечь более одного элемента массива в время, затем добавьте несколько элементов (4 в случае байтов) одновременно с помощью одной операции. Конечно, с байтами вам придется останавливаться по крайней мере каждые 255 итераций и разбивать их на части, чтобы не допустить переполнения одного байта в следующий.

Вам нужно остерегаться хранить слишком много значений "в воздухе" в одной цепочке. Существует только так много регистров процессора, и вы хотите сохранить все свои значения (указатель элемента, счетчик итераций, аккумулятор, регистр очистки для выбранного элемента и т. Д.) В регистрах.

Но очень скоро доступ к хранилищу станет узким местом.

Answer 6

Если, суммируя каждое значение, вы имеете в виду, в основном, подсчет количества единиц, то я думаю, что единственный способ - это добавить каждое значение из массива / чанка ... переопределить инструкцию добавления с помощью побитовых операторов, я думаю, что может быть медленнее, чем при использовании процессора; но, возможно, это может зависеть от процессора.

Кроме того, пропуск 0s не быстрее, чем их добавление (прыжки медленные) ...

Единственное, что приходит мне в голову и может ускорить его, - это упаковать (с самого начала) данные таким образом, чтобы вы могли использовать специальные инструкции вашего целевого процессора. Некоторые процессоры имеют инструкции, которые позволяют легко (и, я полагаю, быстро) получить счетчик чисел в регистре. 32-битный регистр может содержать 32 бита (32 элемента вашего массива), и вы можете «суммировать» их с помощью одной инструкции (для конкретных процессоров ...). Затем вы, конечно, должны суммировать результат с «глобальным частичным» результатом потока; в любом случае, таким образом вы уменьшаете количество операций добавления (32 добавления становятся одной отдельной инструкцией). Это должно работать вместе с ответом Новелократа (например, элемент векторного регистра является результатом подсчета населения).

В последних процессорах "x86" есть инструкция по подсчету населения, см. эту ссылку в википедии .

Answer 7

вы упомянули массив целых чисел, что-то вроде этого: int array [...];

Если вы используете 64-битную ОС + процессор, вы можете захотеть типизировать его на long long (или__int64, в зависимости от вашей платформы) - в основном 8-битные целые числа.Итак, вы делаете это:

int array[...];
...
unsigned long long *longArray;
unsigned long long sum;
for (longArray = &array[number of elements in array]; longArray != array;)
{
    --longArray;
    sum += *longArray;
}

if (the number of elements in original array % 2 == 1)
    sum += array[number of elements in original array - 1];
sum = (sum >> 32) + (sum & 0xFFFFFFFF); // basically add up the first 4 bytes and second 4 bytes
return sum;

Но попробуйте, я не совсем уверен, что это будет быстрее.