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

10

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

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

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

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

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

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

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

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

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

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

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

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

Pedro
источник
Вы ищете параллелизм на основе задач? Есть ли причина, по которой вы пропустили OpenCL и Intel TBB? Я должен признать, что не могу точно сказать, что вы ищете здесь.
Арон Ахмадиа
1
@AronAhmadia: Незнание, в основном ... :) Я добавил TBB и OpenCL в список, но вопрос остается тем же: использовались ли они, то есть их компоненты, основанные на задачах, в каком-либо значительном программном обеспечении для научных исследований? вычисления?
Педро
Как мы относимся к тому, чтобы превратить этот вопрос и его ответы в вики сообщества, а не пытаться расширить его?
Арон Ахмадиа
@AronAhmadia: Я немного обеспокоен тем, что если я оставлю формат вопроса, это быстро выльется в длительные дискуссии о преимуществах / недостатках программирования на основе задач и / или общей памяти в целом. Я, однако, был бы за переключение после того, как он получил еще несколько ответов.
Педро
Название не подходит. Этот вопрос о параллелизме задач, а не о разделяемой памяти.
Джефф

Ответы:

8

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

Вольфганг Бангерт
источник
Спасибо за указание на это, я не смотрел на сделку. II! Существует ли какая-либо публикация или документация, в которой рассматривается. II Использование TBB подробно описано?
Педро
Нет публикации, но это может помочь: dealii.org/developer/doxygen/deal.II/group__threads.html
Вольфганг Бангерт,
4

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

  • Наивная перспектива, что параллельные вычисления - это параллелизация вычислений (например, флопс), а не демонстрация локальности памяти и удаление точек синхронизации. Несмотря на то, что некоторые проблемы, такие как алгоритмы с плотной матрицей, по-прежнему ограничены FP, это происходит только после тщательного рассмотрения подсистемы памяти, и большинство вычислительных ядер (особенно в мире PDE) более чувствительны к памяти. Рабочие очереди имеют тенденцию обменивать локальность памяти для лучшего наивного баланса флопов и большего количества атомарных операций с памятью (из-за синхронизации через очередь).
  • Опора на чрезмерное разложение для динамического баланса нагрузки за счет высокой масштабируемости. Задачи обычно имеют перекрывающиеся зависимости данных (призрачные значения). По мере того, как размер интерьера уменьшается, соотношение призрак / интерьер увеличивается. Даже если это не означает избыточную работу, это означает увеличение движения памяти. Значительные сокращения требований к пропускной способности памяти могут быть достигнуты с помощью таких подходов, как кооперативная предварительная выборка, с помощью которой несколько потоков совместно используют кэш L1 или L2 путем программной предварительной выборки для своего соседа (что неявно поддерживает группу потоков приблизительно согласованной). Это как раз противоположность чрезмерного разложения.
  • Непредсказуемая производительность, в основном из-за проблем, связанных с памятью выше.
  • Отсутствие библиотечно-дружественных компонентов. Это можно почти суммировать как отсутствие аналога, MPI_Commкоторый позволяет различным библиотекам выполнять расширенные операции без коллизий, а также передавать контекст между библиотеками и восстанавливать необходимые атрибуты. Абстракция, предоставляемая «коммуникатором», важна для компоновки библиотеки независимо от того, используется ли общая или распределенная память.
Джед браун
источник
Возможно, я неправильно понимаю ваш ответ, но первый пункт в точности противоположен тому, что Буттари, Курзак, Донгарра и другие показали с MAGMA, библиотекой с общей памятью на основе задач для плотной линейной алгебры ... Кроме того, во втором пункте Вы ссылаетесь на перекрывающиеся данные, т.е. значения-призраки и отношение поверхности к объему, но это удержание от схем декомпозиции области распределенной памяти. Я сам работаю с такими методами для кодов, основанных на частицах, и получаю гораздо лучшую производительность, чем параллельные реализации на основе MPI.
Педро
В любом случае, вопрос был другим ... Знаете ли вы какие-либо проекты в области компьютерного программного обеспечения, использующие эти подходы?
Педро
1. Есть несколько проектов, использующих эти системы, но я не думаю, что этот подход можно считать «успешным». 2. Зависимости все еще перекрываются в общей памяти. Посмотрите, как tcmalloc или ядро ​​Linux делают потоки более независимыми, чтобы избежать узких мест, таких как синхронизация через атомные компоненты. Совместное адресное пространство не означает, что вы должны работать так, как если бы у вас была единообразная память, или что вы должны считать, что атомы недороги.
Джед Браун
3. Я не знаю, на какое «честное сравнение» вы собираетесь ссылаться, но PLASMA получает только около 25% пикового значения FPU (например, слайд 5 hpcgarage.org/cscads2012/Luszczek-UTK-PowerTools.pdf ), который будет Вероятно, плохо для той же операции в распределенной памяти, где ожидается не менее 70% пика. Плотная линейная алгебра - это случай, связанный с FPU, который я специально привел в качестве возможного исключения, но, несмотря на огромные размеры матрицы, PLASMA явно далека от того, чтобы быть связанным с FPU.
Джед Браун
Педро, большая часть физики имеет компонент дальнего радиуса действия, поэтому частицы связаны с обновлением, которое подвержено описанному выше эффекту поверхность-раствор (PPPM, вихревая частица и т. Д.)
Мэтт Кнепли,