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

Question

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

Мой первый пример: the parallel computation of pi. В идеале я хотел бы привести пример, когда каждая итерация занимает очень много времени (из-за дополнительных служебных данных, связанных с распараллеливанием); моя первая мысль - байесовское моделирование с использованием MCMC и Gibbs.

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

Answer 1

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

Жизнь Конвей также интересна тем, что каждое значение «следующей» платы может быть вычислено независимо, но будет зависеть от соответствующих бит текущей платы.

Answer 2

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

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

Answer 3

просто еще несколько -

• Умножение матрицы
• Инвертирование матриц
• FFT
• Строка соответствие
• рендеринга 3D сцены (с помощью преобразования сканирования линии или трассировки лучей)

Answer 4

Мой любимый пример - monte carlo simulation.

Answer 5

Поиск столкновений в хэш-функциях с использованием Paul C. van Oorschot и Michael J. Weiner's method (PDF) часто возникает в различных криптографических настройках.

Answer 6

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

я смотрел бы, если бы я тебя, у них (а не полностью первоначальный список):

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

Ожидает, что их еще много.

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

Answer 7

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

Answer 8

Вы можете посмотреть на оглавлении Parallel Programming in C with MPI and OpenMP

Answer 9

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

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