Что такое канонические примеры параллельного вычисления?
Я пишу работу для тестирования нового приложения, которое продемонстрирует преимущества параллелизированного вычисления (по сравнению с традиционной сериализированной версией этого приложения). Я хочу использовать канонические примеры для параллельного вычисления в моей статье.
Моим первым примером является параллельное вычисление пи. Я идеально хотел бы пример, где каждое повторение является очень трудоемким (из-за дополнительных издержек, связанных с параллелизацией); моя первая мысль является Байесовским моделированием с MCMC и Gibbs выборкой.
Что другие проблемы обычно обсуждаются в этом контексте? Что такое хорошие примеры больших, смущающе параллельны проблемам?
9 ответов
Я бы предположил, что канонические примеры параллельных вычислений и досадно параллельные задачи являются если не полностью, то почти непересекающимися множествами. Другими словами, люди, работающие над параллельными вычислениями, не очень-то заинтересованы в неприятно параллельных задачах; мы называем их так, потому что нам было бы стыдно над ними работать.
На вашем месте я бы посмотрел на эти (не совсем оригинальный список):
- линейная алгебра на больших плотных матрицах, как прямой, так и итерационный подход;
- линейная алгебра на огромных разреженных матрицах
- разветвленные подходы к задачам линейного программирования (и родственных),
- сопоставление последовательностей для биоинформатики (за пределами моей области, я, возможно, неправильно выразил это),
- непрерывная оптимизация.
Я полагаю, что их гораздо больше.
РЕДАКТИРОВАТЬ: Вас может заинтересовать этот список проблем , которые были выбраны для тестирования следующего поколения европейских (академических) суперкомпьютеров. Это даст вам некоторое представление о том, куда движется эта ниша.
Поиск коллизий в хэш-функциях с использованием метода Пола К. ван Оршота и Майкла Дж. Вайнера (PDF) часто возникает в различных криптографических настройках.
еще несколько -
- Умножение матриц
- Инвертирование матриц
- БПФ
- Сопоставление строк
- Визуализация 3D-сцен (с помощью преобразования строк развертки или трассировки лучей)
Подсчет слов кажется каноническим примером для MapReduce.
Возможно, вы захотите взглянуть на оглавление Параллельное программирование на C с MPI и OpenMP
Один из примеров, который я использовал в прошлом для решения досадно параллельной задачи, - это визуализация множества Мандельброта. Каждый пиксель можно вычислить независимо.
Жизнь Конвея также интересна тем, что каждое значение «следующей» доски может быть вычислено независимо, но будет зависеть от того, какие соответствующие биты «текущей» доски уже сделаны.
Моделирование молекулярной динамики позволяет изменять размер задачи до тех пор, пока не исчерпаются ресурсы компьютера (например, 256 частиц против 256 000 000 частиц). Это действительно "канонический" пример, если вы проводите MD-симуляцию в условиях NVT ;-)
.Я использовал демонстрацию набора Мандельброта, чтобы объяснить маме, что такое параллельное программирование: http://www.ateji.com/px/demo.html
Все приведенные вами примеры в основном представляют собой тяжелые данные -параллельные коды. Вы, вероятно, захотите упомянуть также ориентированные на задачи коды, такие как серверы, отвечающие на множество запросов параллельно, и примеры потокового или потокового программирования (MapReduce - хороший представитель этого класса).