OpenMP: В чем преимущество вложенных параллелизаций? - PullRequest
Новая
       37

OpenMP: В чем преимущество вложенных параллелизаций?

16 голосов
/ 30 ноября 2010

Из того, что я понимаю, #pragma omp parallel и его вариации в основном выполняют следующий блок во множестве параллельных потоков, что соответствует количеству процессоров.При наличии вложенных параллелизаций - параллели для внутри параллели для, параллельной функции в параллельной функции и т. Д. - что происходит с внутренней параллелизацией?

Я новичок в OpenMP, и случай, который я имею в виду, вероятно, довольно тривиален- умножение вектора на матрицу.Это делается в виде двух вложенных циклов.Предполагая, что количество процессоров меньше, чем количество элементов в векторе, есть ли какая-то польза от попыток запустить внутренний цикл параллельно?Будет ли общее количество потоков больше, чем количество процессоров, или внутренний цикл будет выполняться последовательно?

Ответы [ 3 ]

10 голосов
/ 01 декабря 2010

(1) Вложенный параллелизм в OpenMP: http://docs.oracle.com/cd/E19205-01/819-5270/aewbc/index.html

Вам необходимо включить вложенный параллелизм, установив OMP_NESTED или omp_set_nested, потому что многие реализации отключают эту функцию по умолчанию, даже некоторые реализации этого не сделали.Не поддерживает вложенный параллелизм полностью.Если этот параметр включен, то при каждом достижении parallel for OpenMP будет создавать количество потоков, как определено в OMP_NUM_THREADS.Таким образом, если двухуровневый параллелизм, общее количество потоков будет N ^ 2, где N = OMP_NUM_THREADS.

Такой вложенный параллелизм приведет к переподписке (т. Е. Число занятых потоков больше, чемядра), что может ухудшить ускорение.В крайнем случае, когда вложенный параллелизм вызывается рекурсивно, потоки могут быть раздутыми (например, создавать потоки 1000 с), и компьютер просто тратит время на переключение контекста.В этом случае вы можете динамически контролировать количество потоков, задав omp_set_dynamic.

(2) Пример умножения матрицы на вектор: код будет выглядеть так: 

// Input:  A(N by M), B(M by 1)
// Output: C(N by 1)
for (int i = 0; i < N; ++i)
  for (int j = 0; j < M; ++j)
     C[i] += A[i][j] * B[j];

В общем, распараллеливание внутренних циклов, когда возможны внешние циклы, является плохим из-за разветвления / объединения потоков.(хотя во многих реализациях OpenMP предварительно создаются потоки, все же требуется, чтобы некоторые из них отправляли задачи в потоки и вызывали неявный барьер в конце параллельного потока)

Вас беспокоит случай, когда N <# ЦП,Да, верно, в этом случае ускорение будет ограничено N, и использование вложенного параллелизма определенно принесет пользу.</p>

Однако тогда код вызовет переподписку, если N достаточно велико.Я просто думаю о следующих решениях:

  • Изменение структуры цикла так, чтобы существовал только одноуровневый цикл.(Это выглядит выполнимо)
  • Специализация кода: если N маленькое, тогда делайте вложенный параллелизм, иначе не делайте этого.
  • Вложенный параллелизм с omp_set_dynamic.Но, пожалуйста, убедитесь, что omp_set_dynamic контролирует количество потоков и их активность.Реализации могут отличаться.
8 голосов
/ 30 ноября 2010

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

Вложенный параллелизм предназначен для тех случаев, когда параллелизм не все раскрывается одновременно - скажем, вы хотите сделать 2 одновременных оценки функций, каждая из которых может с пользой использовать 4 ядра, и у вас есть 8-ядерная система. Вы вызываете функцию в параллельном разделе, и в определении функции есть дополнительная, скажем, параллельная функция для.

3 голосов
/ 03 июня 2011

На внешнем уровне используйте предложение NUM_THREADS (num_groups), чтобы установить количество потоков, которые нужно использовать. Если ваш внешний цикл имеет число N, а число процессоров или ядер равно num_cores, используйте num_groups = min (N, num_cores). На внутреннем уровне вам нужно установить количество подпотоков для каждой группы потоков, чтобы общее количество подпотоков равнялось количеству ядер. Поэтому, если num_cores = 8, N = 4, то num_groups = 4. На нижнем уровне каждый подпоток должен использовать 2 потока (так как 2 + 2 + 2 + 2 = 8), поэтому используйте предложение NUM_THREADS (2). Вы можете собрать количество вложенных потоков в массив с одним элементом на каждый поток внешней области (с элементами num_groups).

Эта стратегия всегда оптимально использует ваши ядра. Когда N = num_cores, массив подсчетов подзаписей содержит все 1 с, поэтому внутренний цикл фактически является последовательным.

...