Несколько уровней параллелизма с помощью OpenMP - Возможный? Умный? Практичный?
Я в настоящее время работаю над C++ редкая библиотека решателя матрицы/математики/повторяющейся для инструмента моделирования, которым я управляю. Я предпочел бы использовать существующий пакет, однако, после обширного расследования, ни один не был найден, которые подходили для нашего средства моделирования (мы посмотрели на пироги с фруктами, это ++, PetSC, собственный, и несколько других). Хорошие новости являются моими решателями, и структуры разреженной матрицы теперь очень эффективны и устойчивы. Плохие новости, я теперь изучаю распараллеливание с помощью OpenMP, и кривая обучения немного крута.
Домен, который мы решаем, может быть поврежден в субдомены, которые объединяются в диагональном блоком формате. Таким образом, наша схема устройства хранения данных заканчивает тем, что была похожа на массив меньших квадратных матриц (блоки []) каждый с форматом, соответствующим субдомену (например, Сжатое устройство хранения данных строки: CRS, Сжатое Диагональное устройство хранения данных: CDS, Плотный, и т.д.), и фоновая матрица (в настоящее время использование CRS), который составляет возможность соединения между субдоменами.
"Горячая точка" в большинстве (все?) повторяющиеся решатели являются Матричной операцией Векторного умножения, и это верно для моей библиотеки. Таким образом я фокусировал свои усилия на оптимизации моих стандартных программ MxV. Для структуры диагонали блока псевдо код для M*x=b был бы следующие:
b=background_matrix*x
start_index = 1;
end_index = 0;
for(i=1:number of blocks) {
end_index=start_index+blocks[i].numRows();
b.range(start_index, end_index) += blocks[i] * x.range(start_index, end_index);
start_index = end_index+1;
}
где background_matrix является фоном (CRS) матрица, блоки являются массивом матриц субдомена, и .range возвращает часть вектора от начального значения индекса до конечного индекса.
Очевидно, цикл может быть (и был), параллелизированный, поскольку операции независимы от других повторений цикла (диапазоны не накладываются). Так как у нас есть 10-15 блоков в типичной системе, 4 +, потоки на самом деле имеют значительное значение.
Другое место, где распараллеливание, как замечалось, было хорошим вариантом в, находится в деятельности MxV для каждой схемы устройства хранения данных субдомена (вызовы в строках 1 и 6 в вышеупомянутом коде). Существует много там при параллелизации CRS, CDS и плотных матричных операций MxV. Обычно хорошее повышение замечено с 2 потоками со значительно убывающей доходностью, поскольку добавляется больше потоков.
Я предполагаю схему, где 4 потока использовались бы в цикле блока для вышеупомянутого кода, и каждый из тех потоков будет использовать 2 потока для субдомена, решает. Однако я не уверен, как с помощью OpenMP можно было бы управлять пулом потоков - действительно ли возможно ограничить количество потоков в openmp для цикла? Этот многоуровневый параллелизм - что-то, что на практике имеет смысл? Любые другие мысли о том, что я предложил здесь, ценились бы (и благодарит читать полностью в конец!)
2 ответа
Обратите внимание, что все, что я описываю, зависит от реализации.
Можно ли ограничить количество потоков в цикле openmp for?
Да. Это можно сделать разными способами. Установите omp_set_nested (1); и используйте что-то вроде #pragma omp parallel для num_threads (4) или аналогичное во внешнем цикле и #pragma omp parallel для num_threads (2) во внутреннем цикле. Это должно дать вам 8 потоков (в зависимости от реализации вам, возможно, также потребуется установить OMP_THREAD_LIMIT , если у вас меньше 8 ядер)
В качестве альтернативы вы можете вручную развернуть свои циклы, например используя что-то вроде
#pragma omp parallel sections {
#pragma omp section
do your stuff for the first part, nest parallel region again
#pragma omp section
and so on for the other parts
}
Вы можете сделать то же самое иногда более эффективно в OpenMP 3.0 с помощью #pragma omp task .
Или вы запускаете 8 потоков и получаете номер текущего потока в параллельном разделе и планируете вручную на основе номера потока.
Наконец, если у вас есть идеально вложенный цикл (цикл идеально вложен, если фактическое присвоение происходит только во внутреннем цикле), вы можете переписать все в один цикл.По сути, упакуйте два итератора i и j в один большой итератор (i, j) . Обратите внимание, что это может уменьшить локальность и, следовательно, снизить производительность
Имеет ли смысл этот многоуровневый параллелизм на практике?
Это зависит от обстоятельств, и вы должны выяснить это сами. В общем, многоуровневый параллелизм делает вашу проблему более масштабируемой. Однако планирование может быть более сложным. Эта статья может быть интересной.
Относительно установки количества потоков вручную: главное преимущество установки количества потоков состоит в том, что вы можете использовать конкретные знания о вашей проблеме при планировании. Таким образом, вы можете уменьшить накладные расходы и получить более высокую локальность выполняемого кода и, следовательно, больше попаданий в кэш и меньше операций ввода-вывода в основную память.
Главный недостаток ручной установки количества потоков во вложенном параллелизме состоит в том, что потоки в самом внутреннем цикле могут бездействовать на неявном барьере, в то время как может выполняться дополнительная работа ( пример ). Кроме того, крупномасштабный параллелизм плохо масштабируется. Поэтому, если у вашего внешнего цикла очень разное время выполнения внутри цикла, вам нужно планировать более гибко, чем просто разделение на 4 потока.
Есть еще какие-нибудь мысли
Думали ли вы о выполнении MxV с SIMD? В зависимости от архитектуры это может дать ускорение в 2-4 раза. Я быстро погуглил для вас эту презентацию .
Для MxV, мозаика цикла , регистр и блокировка кэша и связанные методы могут увеличить локальность данных и уменьшить другие проблемы, напримерложный обмен. Эта книга , глава 11 (вы можете ее предварительно просмотреть), может дать вам некоторые дополнительные идеи о том, как реструктурировать доступ к данным.
Почему бы не спросить экспертов на OpenMP.org
Зарегистрируйтесь и войдите в систему по адресу: http://openmp.org/forum/viewforum.php?f=3