Это старая версия документа!
Содержание
Описание и область применения шаблона
Основные типовые решения в параллельном программировании
- Map
- MapReduce
- TaskBag
- Chain
Map
Map является самой простой схемой вычислений, и применяется, когда есть возможность разбить задачу на независимые потоки вычислений. Например, сложение матриц, при котором каждый поток вычислений складывает определённый заранее набор строк, причём время выполнения заданий легко прогнозировать, что позволяет добиться небольшой разницы длительности выполнения заданий. Схема типового решения Map изображена на рисунке
MapReduce
Применяется когда необходимо согласовать результаты вычислений всех потоков, но на согласование требуется намного меньше времени, чем на сами вычисления. Схема типового решения MapReduce изображена на рисунке
TaskBag
Парадигма параллельных вычислений «портфель задач», называемая также моделью тиражируемых рабочих (replicated workers) или моделью работ по найму (work farm). Принцип организации вычислений по данной схеме иллюстрирует рисунок
Chain
Многие задачи численного моделирования при распараллеливании приводят к структурам, в которых каждый из процессов обрабатывает некоторую локальную информацию и взаимодействует путем отправки сообщений с фиксированным числом соседей. Рассматривают несколько типов регулярных топологий (цепь, кольцо, сетка, тор, куб) и несколько типов алгоритмов работы процессов (систолический и конвейерный). Схема вычислений chain изображена на рисунке
Область применения шаблона TaskBag
Шаблон TaskBag является каркасом приложений, которые обрабатывают множество независимых задач, которые могут добавляться при обработке этих задач. Работа приложения со структурой TaskBag похожа на приложения со структурой Map, но усложняющим фактором является то, что изначально нельзя предсказать сколько заданий необходимо будет обработать.
Примеры задач с динамическим добавлением заданий:
- Адаптивное численное интегрирование
- Методы глобальной оптимизации
- Метод ветвей и границ
- Методы обхода графа в ширину