Массив C [] = A [] * B [] в высокопроизводительных вычислениях

Question

Я полагаю, что такой код обычно написан на C ++

for(size_t i=0;i<ARRAY_SIZE;++i)
    A[i]=B[i]*C[i];

Одно из наиболее распространенных вариантов:

double* pA=A,pB=B,pC=C;
for(size_t i=0;i<ARRAY_SIZE;++i)
    *pA++=(*pB++)*(*pC++);

Что мне интересно, так это лучший способ улучшить этот код, поскольку IMO необходимо учитывать следующие вещи:

1. кэш процессора. Как процессоры заполняют свои кэши, чтобы получить наилучшую частоту попаданий?
2. Полагаю, SSE может улучшить это?
3. Другое дело, что если код можно распараллелить? Например. используя OpenMP. В этом случае указатель трюка может быть недоступен.

Любые предложения будут оценены!

Answer 1

Мой g ++ 4.5.2 производит абсолютно идентичный код для обоих циклов (исправив ошибку в double *pA=A, *pB=B, *pC=C;, и это

.L3:
    movapd  B(%rax), %xmm0
    mulpd   C(%rax), %xmm0
    movapd  %xmm0, A(%rax)
    addq    $16, %rax
    cmpq    $80000, %rax
    jne .L3

(где ARRAY_SIZE был 10000)

Авторы компилятора уже знают эти хитрости. Однако стоит изучить OpenMP и другие параллельные решения.

Answer 2

Правило для производительности:

1. еще не

2. получить цель

3. мера

4. получить представление о возможном улучшении и убедиться, что стоит потратить время на его получение.

Это еще более вернодля современных процессоров.О ваших вопросах:

1. Простое сопоставление индекса с указателем часто выполняется компиляторами, и если они этого не делают, у них могут быть веские причины.

2. * Процессоры 1028 * уже часто оптимизированы для последовательного доступа к кешу: простое генерирование кода часто дает наилучшую производительность.

3. SSE может улучшить это.Но нет, если вы уже ограничены в пропускной способности.Итак, мы вернемся к измерению и определим границы стадии

4. распараллеливание: то же самое, что SSE.Использование нескольких ядер одного процессора не поможет, если вы ограничены в пропускной способности.Использование разных процессоров может помочь в зависимости от архитектуры памяти.

5. ручное разматывание петли (предложено в удаленном ответе) часто является плохой идеей.Компиляторы знают, как это сделать, когда это целесообразно (например, если он может выполнять программную конвейерную обработку), и с современными процессорами OOO это не так (это увеличивает нагрузку на кэши инструкций и трассировки во время выполнения OOO, спекуляции надпереходы и переименование регистров автоматически принесут большую пользу от раскрутки и программной конвейеризации).

Answer 3

Первая форма - это именно та структура, которую ваш компилятор распознает и оптимизирует, почти наверняка испуская инструкции SSE.

Для такого рода тривиального внутреннего цикла эффекты кэша не имеют значения, потому что вы перебираете все. Если у вас есть вложенные циклы или последовательность операций (например, g (f (A, B), C)), то вы можете попытаться организовать доступ к небольшим блокам памяти несколько раз, чтобы сделать их более удобными для кэша.

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

OpenMP может помочь, если цикл большой и операции внутри него достаточно сложны, и вы не ограничены памятью.

В общем, пишите свой код естественным и простым способом, потому что именно это ваш оптимизирующий компилятор, скорее всего, поймет.

Answer 4

Когда начать рассматривать SSE или OpenMP? Если оба они верны:

• Если вы обнаружите, что код, похожий на ваш, появляется в вашем проекте 20 и более раз:
  for (size_t i = 0; i < ARRAY_SIZE; ++i)
A[i] = B[i] * C[i];
  или некоторые подобные операции
• Если ARRAY_SIZE обычно превышает 10 миллионов или если профилировщик говорит вам, что эта операция становится узким местом

Тогда

• Сначала сделайте функцию:
  void array_mul(double* pa, const double* pb, const double* pc, size_t count)
{ for (...) }
  
• Во-вторых, если вы можете позволить себе найти подходящую SIMD-библиотеку, измените свою функцию, чтобы использовать ее.
  • Хорошая портативная библиотека SIMD
  • Библиотека SIMD C ++

В качестве примечания: если у вас много операций, которые немного сложнее, например, например, A[i] = B[i] * C[i] + D[i] тогда будет полезна библиотека, которая поддерживает шаблон выражения .

Answer 5

Я думаю, что использование valarrays специализировано для таких вычислений. Я не уверен, что это улучшит производительность.

Answer 6

Вы можете использовать простой метод распараллеливания.Cuda будет зависеть от аппаратного обеспечения, но SSE почти стандартен для каждого процессора.Также вы можете использовать несколько потоков.В нескольких потоках вы все еще можете использовать хитрость указателя, что не очень важно.Эти простые оптимизации могут быть выполнены и компилятором.Если вы используете Visual Studio 2010, вы можете использовать parallel_invoke для параллельного выполнения функций без работы с потоками Windows.В Linux библиотека pThread довольно проста в использовании.