Каковы канонические примеры параллельных вычислений?

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

Мой первый пример — это параллельное вычисление pi. В идеале мне бы хотелось пример, в котором каждая итерация занимает очень много времени (из-за дополнительных накладных расходов, связанных с распараллеливанием); Моя первая мысль — байесовское моделирование с выборкой MCMC и Гиббса.

Какие еще проблемы обычно обсуждаются в этом контексте? Каковы хорошие примеры больших поразительно параллельных задач?


parallel-processing mpi
person Shane    schedule 19.07.2010    source источник
comment
Статья в Википедии, которую вы даете, содержит набор примеров. Что с ними не так?   -  person Jens    schedule 19.07.2010
comment
С ними все в порядке, хотя я не думаю, что их можно рассматривать как стандартный набор примеров (например, пример pi туда не включен). Мне нужны не просто примеры: мне нужны самые известные примеры.   -  person Shane    schedule 19.07.2010
comment
@Shane: Так почему ты попросил хорошие примеры в последнем предложении? Хорошие не всегда могут быть знаменитыми.   -  person Jon Skeet    schedule 19.07.2010
comment
@Jon: Справедливое замечание; вот почему я включил канонический в название, что должно подразумевать известный/важный.   -  person Shane    schedule 19.07.2010
comment
С чего вы взяли, что есть какие-то канонические примеры?   -  person David Thornley    schedule 19.07.2010
comment
@David: Тот факт, что это большая область исследований, и сравнение методов требует некоторой стандартизации. В исследовательских работах часто используются одни и те же примеры (например, набор данных по радужной оболочке для задач классификации).   -  person Shane    schedule 19.07.2010

Ответы (9)


arrow_upward
6
arrow_downward

еще немного -

  • Умножение матриц
  • Инвертирующие матрицы
  • БПФ
  • Сопоставление строк
  • Рендеринг 3D-сцен (через преобразование строк сканирования или трассировку лучей)
person shoosh    schedule 19.07.2010

arrow_upward
5
arrow_downward

Один из примеров, который я использовал в прошлом, для решения досадно параллельной задачи — это визуализация множества Мандельброта. Каждый пиксель можно вычислить независимо.

Conway's Life также интересна тем, что каждое значение «следующей» доски может быть вычислено независимо, но будет зависеть от того, какие соответствующие биты «текущей» доски уже сделаны.

person Jon Skeet    schedule 19.07.2010

arrow_upward
5
arrow_downward

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

На вашем месте я бы посмотрел на эти (не совсем оригинальный список):

  • линейная алгебра на больших плотных матрицах, как прямой, так и итерационный подходы;
  • линейная алгебра на огромных разреженных матрицах
  • подходы ветвей и границ к задачам линейного программирования (и родственным);
  • сопоставление последовательностей для биоинформатики (за пределами моей области, возможно, я неправильно выразился);
  • постоянная оптимизация.

Я ожидаю, что есть еще много.

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

person High Performance Mark    schedule 19.07.2010
comment
+1 Спасибо за этот список. Я думаю, что смущающий действительно подразумевает вещи, которые легко разделить (т. е. нет никаких зависимостей между итерациями), а не то, что они сами по себе являются трудными проблемами. - person Shane; 19.07.2010
comment
@Shane: я позволю себе не согласиться, их называют смущающими, потому что те из нас, кто работает с параллельными вычислениями, были бы смущены, работая над такими простыми проблемами; еще хуже, работая над собой и делая ошибки. Может быть, их так легко распараллелить, потому что между задачами нет зависимостей, но это другой вопрос. - person High Performance Mark; 19.07.2010
comment
+1 за ссылку на PRACE Benchmark Suite. По той же причине я бы также добавил тесты SpecMPI: spec.org/mpi - person Stan Graves; 21.07.2010

arrow_upward
4
arrow_downward

Моделирование молекулярной динамики позволяет вам изменять размер задачи до тех пор, пока ресурсы вашего компьютера не будут исчерпаны (т.е. 256 частиц против 256 000 000 частиц). Это действительно «канонический» пример, если вы запускаете моделирование MD в условиях NVT ;-)

person Jess    schedule 19.07.2010

arrow_upward
2
arrow_downward

Мой любимый пример — симуляция методом Монте-Карло.

person Matt    schedule 19.07.2010

arrow_upward
1
arrow_downward

Подсчет слов кажется каноническим примером для MapReduce.

http://en.wikipedia.org/wiki/MapReduce#Example

person Donald Miner    schedule 19.07.2010

arrow_upward
1
arrow_downward

Поиск коллизий в хэш-функциях с использованием метода Пола К. ван Оршота и Майкла Дж. Вайнера (PDF) часто встречается в различных криптографических настройках.

person Jan Gorzny    schedule 19.07.2010

arrow_upward
1
arrow_downward

Вы можете просмотреть оглавление Параллельное программирование на C с использованием MPI и OpenMP

person claws    schedule 20.07.2010

arrow_upward
1
arrow_downward

Я использовал демонстрацию набора Мандельброта, чтобы объяснить маме, что такое параллельное программирование: http://www.ateji.com/px/demo.html

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

person Patrick Viry    schedule 28.07.2010