Чрезвычайная параллельность

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

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

Типичным примером чрезвычайно параллельной задачи является работа графического процессора (GPU) при расчёте 3D проекций, когда каждый пиксель на экране может рассчитываться самостоятельно.

Примеры

Некоторые примеры чрезвычайно параллельных задач:

• Обслуживание статических файлов на веб-сервере.
• Расчёт элементов множества Мандельброта и других фракталов, когда каждая точка может быть вычислена независимо.
• Рендеринг в компьютерной графике. В трассировке лучей каждый пиксель может быть проработан самостоятельно. В компьютерной анимации каждый кадр может быть обработан независимо.
• Полный перебор или «поиски грубой силы» — поиск в криптографии последовательным перебором возможных комбинаций. Ярким примером является сеть распределённых вычислений distributed.net.
• BLAST-поиски в биоинформатике.
• Крупномасштабные системы распознавания лица, предусматривающие сравнение тысяч входных изображений (например снимков лиц по системам безопасности или видеонаблюдения) с большим количеством сохраненных изображений определённых лиц (например, портретов преступников).
• Компьютерное моделирование сравнения многих независимых сценариев, таких как климатические модели.
• Генетические алгоритмы и другие эвристические алгоритмы.
• Статистический ансамбль с численного прогноза погоды.
• Моделирование и реконструкция событий в физике элементарных частиц.
• Этап сбора отношений в вариации кратных многочленов метода квадратичного решета — алгоритм в факторизации целых чисел (MPQS).
• При генерировании Bitcoin хеширование для одного и того же блока, но с разной служебной информацией в заголовке, может выполняться параллельно.

Реализации

• В языке программирования R пакет «Snow» (Simple Network of Workstations — простая сеть рабочих станций) реализует простой механизм для использования коллекции рабочих станций или кластера Beowulf для чрезвычайно параллельных вычислений.

См. также

• Закон Амдала
• MapReduce

Примечания

1. Designing and Building Parallel Programs, by Ian Foster. Addison-Wesley, 1995. (ISBN 978-0-201-57594-1) Архивная копия от 11 марта 2009 на Wayback Machine Section 1.4.4

Ссылки

• Embarrassingly parallel Архивная копия от 9 июня 2011 на Wayback Machine, Parallel algorithms
• Embarrassingly Parallel Computations Архивная копия от 25 сентября 2013 на Wayback Machine, Engineering a Beowulf-style Compute Cluster
• «Star-P: High Productivity Parallel Computing» Архивная копия от 2 июня 2013 на Wayback Machine