Основанные на задачах параллельные библиотеки с разделяемой памятью в Scientific Computing

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

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

Примеры таких библиотек:

• КВАРК : Первоначально разработанный для библиотеки параллельной линейной алгебры MAGMA , кажется, также использовался для параллельного быстрого мультипольного метода .

• Cilk : Первоначально проект на основе MIT, который теперь поддерживается Intel, реализован как расширение языка / компилятора для C, используется в компьютерных шахматных программах Cilkchess и экспериментально в FFTW .

• Суперскаляр SMP : Разработан в суперкомпьютерном центре Барселоны, во многом похож на Cilk, на основе #pragmaрасширений.

• StarPU : похожие библиотечные «кодлеты», которые могут быть скомпилированы и запланированы для нескольких различных архитектур, включая графические процессоры.

• Задачи OpenMP: Начиная с версии 3.0, в OpenMP появились «задачи», которые можно планировать асинхронно (см. Раздел 2.7 спецификации).

• Блоки Intel Threading Building Blocks : использует классы C ++ для создания и запуска асинхронных задач, см. Раздел 11 учебного пособия.

• OpenCL : поддерживает основанный на задачах параллелизм на многоядерных процессорах.

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

Итак, вот вопрос: кто-нибудь знает о научных вычислительных кодах, использующих какие-либо из этих библиотек / языковых расширений или аналогичных, для параллелизма совместно используемой памяти?

deal.II использует Threading Building Blocks по всей библиотеке, и в целом мы достаточно довольны этим. Мы рассмотрели несколько альтернатив, в частности OpenMP, так как все, кажется, используют это для более простых кодов, но обнаружили, что их не хватает. В частности, OpenMP имеет огромный недостаток, заключающийся в том, что его модель задач не позволяет вам получить ручку для задачи, которую вы начали, и, следовательно, трудно получить доступ к состоянию задачи (например, дождаться ее завершения) или вернуть значения Функции, которые вы запускаете на отдельную задачу. OpenMP в первую очередь хорош для распараллеливания самых внутренних циклов, но вы получаете параллельную эффективность за счет распараллеливания самых внешних , сложных циклов, и OpenMP не является инструментом для этого, в то время как TBB достаточно хорош для этого.

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

• Наивная перспектива, что параллельные вычисления - это параллелизация вычислений (например, флопс), а не демонстрация локальности памяти и удаление точек синхронизации. Несмотря на то, что некоторые проблемы, такие как алгоритмы с плотной матрицей, по-прежнему ограничены FP, это происходит только после тщательного рассмотрения подсистемы памяти, и большинство вычислительных ядер (особенно в мире PDE) более чувствительны к памяти. Рабочие очереди имеют тенденцию обменивать локальность памяти для лучшего наивного баланса флопов и большего количества атомарных операций с памятью (из-за синхронизации через очередь).
• Опора на чрезмерное разложение для динамического баланса нагрузки за счет высокой масштабируемости. Задачи обычно имеют перекрывающиеся зависимости данных (призрачные значения). По мере того, как размер интерьера уменьшается, соотношение призрак / интерьер увеличивается. Даже если это не означает избыточную работу, это означает увеличение движения памяти. Значительные сокращения требований к пропускной способности памяти могут быть достигнуты с помощью таких подходов, как кооперативная предварительная выборка, с помощью которой несколько потоков совместно используют кэш L1 или L2 путем программной предварительной выборки для своего соседа (что неявно поддерживает группу потоков приблизительно согласованной). Это как раз противоположность чрезмерного разложения.
• Непредсказуемая производительность, в основном из-за проблем, связанных с памятью выше.
• Отсутствие библиотечно-дружественных компонентов. Это можно почти суммировать как отсутствие аналога, MPI_Commкоторый позволяет различным библиотекам выполнять расширенные операции без коллизий, а также передавать контекст между библиотеками и восстанавливать необходимые атрибуты. Абстракция, предоставляемая «коммуникатором», важна для компоновки библиотеки независимо от того, используется ли общая или распределенная память.