Вводные примечания по распараллеливанию, в частности, схемы задач и алгоритмы

10

Я ищу в Интернете доступные лекционные заметки или другие ресурсы, которые дают хорошее введение в параллельное программирование, подобно параллельным аналогам базовых классов по информатике.

Я сосредоточен на следующем: пока я могу говорить о «разделяй и властвуй», жадных алгоритмах, динамическом программировании и т. П., То есть об основных шаблонах последовательных алгоритмов (и проблем), и у меня нет подходящего языка для классификации подходов в параллельных алгоритмах.

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

  1. установка массива целых чисел все ноль (отлично масштабируется.)
  2. суммирование массива целых чисел (чем больше потоков вы используете, тем больше накладных расходов.)
  3. Для данного массива перечислите продукты каждой записи вместе с каждой другой записью (если мы распараллелим канонический двойной цикл, время выполнения масштабируется до sqrt числа процессоров.)

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

shuhalo
источник
Можете ли вы переформулировать это предложение: «Например, я хотел бы получить формулировку, почему очевидный параллельный подход к следующим проблемам имеет разное качественное поведение»
Гопи,
Выполнено. Я надеюсь, что это более остро.
Шухало

Ответы:

6

Для вводной книги по параллельному программированию (я не знаю об онлайн-материалах) я изучал ее с помощью параллельных алгоритмов Казановы, Леграна и Роберта, что очень полезно для начала в теоретической параллельной алгоритмике.

Кроме того, в SPAA'11 шла дискуссия о том, что должен знать ученик по параллельному алгоритму и распределенным вычислениям и чему следует учить. Эта Инициатива Учебного плана по Параллельным и Распределенным Вычислениям поможет вам найти не курс, а список другой темы, которая должна быть затронута во время курса бакалавриата. Тогда, я полагаю, легче найти документацию по каждой конкретной теме.

Гопи
источник
1
Термин «язык» относится к естественному языку, а не к языку программирования или подобному. Точно так же, как математика является языком, и, например, теория категорий или теория групп, как говорят, предоставляют «язык» для определенных структур, отношений и фактов. Но все равно спасибо.
Шухало
действительно мой плохой :). Тогда для трех вопросов, которые у вас были, я действительно рекомендую книгу, которую я связал, которая является очень теоретической. Они изучают все виды параллельных алгоритмов и методов на различных видах параллельной архитектуры. Тогда часть, которая может ответить на ваши три вопроса, будет частью « Унифицированные петли» .
Гопи
+1 для Инициативы по разработке учебных программ NSF / IEEE-TCPP, но я предлагаю вам удалить OpenMP и MPI, так как они здесь не очень актуальны.
Юкка Суомела
Действительно, я забыл удалить его после комментария @Martin. Спасибо.
Гопи
7

Если вы не хотите вдаваться в подробности, очень хорошее введение в шаблоны проектирования распараллеливания можно найти в книге « Шаблоны параллельного программирования», написанной Mattson, Sanders and Massingill.

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

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

Массимо Кафаро
источник
1

MPI_RUBY ... нужно найти мою последнюю стабильную сборку. Я бы предложил добавить параллельный префикс (сканирование) в список. Я просто научил бы параллельному префиксу и показал бы им, как использовать кривую заполнения пространства для повышения эффективности кэширования при решении всех пар.

Чад Brewbaker
источник