Параллельная сумма для векторов

Question

Может ли кто-нибудь дать несколько советов о том, как можно уменьшить следующее для времени выполнения цикла через многопоточность? Предположим, у меня также есть два вектора с именами «a» и «b».

for (int j = 0; j < 8000; j++){
    // Perform an operation and store in the vector 'a'
    // Add 'a' to 'b' coefficient wise
}

Этот цикл for выполняется много раз в моей программе. Две операции в цикле for уже оптимизированы, но они выполняются только на одном ядре. Тем не менее, у меня доступно 16 ядер, и я хотел бы использовать их.

Я попытался изменить цикл следующим образом. Вместо вектора «а» у меня есть 16 векторов, и предположим, что i-й называется а [i]. Мой цикл for теперь выглядит как

for (int j = 0; j < 500; j++){
    for (int i = 0; i < 16; i++){
        // Perform an operation and store in the vector 'a[i]'
    }
    for (int i = 0; i < 16; i++){
        // Add 'a[i]' to 'b' coefficient wise
    }

}

Я использую OpenMp на каждом из циклов for внутри, добавляя «#pragma omp parallel for» перед каждым из внутренних циклов. Все мои процессоры используются, но время выполнения только значительно увеличивается. Кто-нибудь есть какие-либо предложения о том, как я могу уменьшить время выполнения этого цикла? Заранее спасибо.

Answer 1

omp создает потоки для вашей программы, где бы вы ни вставляли тег pragma, поэтому он создает потоки для внутренних тегов, но проблема в том, что создано 16 потоков, каждый выполняет 1 операцию, а затем все они уничтожаются с помощью вашего метода. создание и уничтожение потоков занимает много времени, поэтому используемый вами метод увеличивает общее время вашего процесса, хотя он использует все 16 ядер. вам не нужно было создавать внутренние форы, просто поместите тег #pragma omp parallel for перед циклом 8000, это omp для разделения значений между ступенями, так что то, что вы сделали для создания второго цикла, это работа omp. таким образом, omp создает потоки только один раз, а затем обрабатывает 500 чисел, используя каждый из этих потоков, и завершает все из них после этого (используя на 499 меньше создание и уничтожение потоков)

Answer 2

На самом деле, я собираюсь поместить эти комментарии в ответ.

Формирование потоков для тривиальных операций просто добавляет издержки.

Сначала убедитесь, что ваш компилятор использует векторные инструкции для реализации вашего цикла. (Если он не знает, как это сделать, вам, возможно, придется самостоятельно кодировать векторные инструкции; попробуйте поискать «SSE instrinsics». Но для такого простого добавления векторов автоматическая векторизация должна быть возможной.)

Предполагая, что ваш компилятор является достаточно современным GCC, вызовите его с помощью:

gcc -O3 -march=native ...

Добавьте -ftree-vectorizer-verbose=2, чтобы узнать, автоматически ли он векторизовал ваш цикл и почему.

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

Answer 3

Does anyone have any suggestions on how I can decrease the runtime of this loop?

for (int j = 0; j < 500; j++){  // outer loop
  for (int i = 0; i < 16; i++){  // inner loop

Всегда старайтесь сделать внешний цикл итераций меньше внутренний цикл Это избавит вас от инициализации внутреннего цикла столько раз.В приведенном выше коде внутренний цикл i = 0; инициализируется 500 раз.Теперь

for (int i = 0; j < 16; i++){  // outer loop
  for (int j = 0; j < 500; j++){  // inner loop

Теперь внутренний цикл j = 0; инициализируется только 16 раз!Попробуйте, изменив свой код соответствующим образом, если он окажет какое-либо влияние.