Одиночка - паттерн, реализующий одиночный процесс. В рамках указанных выше условий одиночка
представляет собой последовательный процесс (возможно с несколькими потоками выполнения). Этот процесс
имеет интерфейс и осуществляет коммуникацию через порты ввода/вывода посредством обмена сообщений.
В определённом смысле одиночка - наименьшая неделимая абстракция в рамках шаблонов параллельного
программирования. Он играет роль базового строительного блока для других паттернов.
Внешне репликация представляется как одиночка, но её внутренняя структура может
объединять несколько реплик (копий) экземпляра паттерна одиночка. Следовательно, группа реплик
может обрабатывать несколько сообщений одновременно. Набор реплик можно представить в виде дерева
(смотри рисунок 1). В корне находится реплика-оригинал, который играет роль координатора.
Координатор осуществляет взаимодействие через коммуникационные интерфейсы ввода/вывода,
также он перехватывает ввод внешних по отношению к группе реплик данных.
Рисунок 1 - Структура группы реплик
В задачу реплики-координатора входит нахождение реплики для перенаправления ввода внешних данных
для обработки. Для этого используется алгоритм балансировки нагрузки. После того, как реплика
(экземпляр паттерна одиночки) завершит обработку сообщения, происходит возврат результата координатору.
Координатор определённым образом обрабатывает данные результата.
Процесс получения результата выполнения некоторых действий группой реплик представлен на рисунке 2.
Рисунок 2 - Взаимодействие группы реплик при поиске решения задачи
Паттерн конвейер состоит из упорядоченного множества ступеней. Выход одной ступени является входом
ступени-приемника. Структурно конвейер складывается из набора экземпляров паттерна одиночка,
соединённых в цепочку. Выход каждого экземпляра одиночки замыкается на вход другого экземпляра цепочки.
Начальная ступень конвейера играет роль интерфейса ввода, последняя - вывода. Структурная схема шаблона
конвейер представлена на рисунке 3.
Рисунок 3 - Структура паттерна конвейер
Паттерн хозяин/подчинённый носит альтернативное название фабрика задач (task farm).
Структурно паттерн напоминает репликацию. Роль хозяина выполняет реплика-координатор.
Подчинённый - реплика, получающая и выполняющая задания по требованию реплики-хозяина.
Результат обработки задания передаётся обратно реплике-координатору, играющей роль хозяина. В виду
возможности репликации подчинённых может осуществляться одновременное выполнение нескольких
разных запросов.
Паттерн хозяин/подчинённый - пример композиционного паттерна параллельного программирования.
Его основа - паттерны одиночка и репликация. Структура паттерна представлена на рисунке 4.
Рисунок 4 - Структура паттерна хозяин/подчинённый
Паттерн "разделяй и властвуй" представляет собой дерево экземпляров паттерна одиночка.
В процессе выполнения вычислений узел-родитель передаёт задание ниже по дереву своим
потомкам. Когда потомок в результате выполнения задания получает результат, он передаёт его
обратно родителю. При реализации данного паттерна учитываются следующие параметры:
- ширина дерева - количество экземпляров паттерна одиночка на каждом из ярусов
- высота дерева (глубина рекурсии) - количество уровней (ярусов) экземпляров паттерна одиночка
Корень дерева (процесс верхнего уровня) - интерфейсный процесс данного паттерна. Поведение
шаблона "разделяй и властвуй" обеспечивается поддержкой функций передачи задания
процессам-потомкам и сбором результатов от них. Структура данного шаблона представлена на рисунке 5.
Рисунок 5 - Структура паттерна разделяй и властвуй
Паттерн репозиторий (смотри рисунок 6) представляет собой особый случай паттерна репликация.
Особенность состоит в организации централизованном доступе к общим данным и независимой
работе реплик. Причина использования паттерна: необходимость внесения изменений (записи) и чтения
данных из централизованного хранилища данных. Такие операции записи и чтения происходят асинхронно,
и не существует никакого детерминированного алгоритма, определяющего последовательность доступа к данным
со стороны отдельных реплик.
Рисунок 6 - Структура паттерна репозиторий
Характерная организация совместной работы независимых реплик - частые обращения к одним и тем же
централизованным данным в перекрывающихся во времени асинхронных операциях чтения/записи. Чтобы
гарантировать корректность и целостность данных в процессе выполнения их обработки используется
репозиторий, который контролирует доступ к данным со стороны независимых реплик.
Паттерн геометрической декомпозиции используется, когда необходимо организовать вычисления
как множество полунезависимых операций над упорядоченным набором данных. Параллелизм
реализуется множеством реплик, одновременно осуществляющих вычисления. Каждая реплика выполняет набор
операций над подмножеством элементов исходного набора данных. В процессе вычислений реплики обмениваются
частичными результатами, используя существующие коммуникационные каналы.
Никакое подмножество элементов исходного набора данных не может быть напрямую разделено между
репликами. Каждая реплика может осуществлять доступ только к собственному подмножеству элементов
исходного набора данных. Результаты выполняемых репликами операций над элементами данных зависят
от частичных результатов операций, осуществляемых в других репликах. В процессе обмена промежуточными
результатами в сети реплик можно выделить геометрические контуры связанных компонент. Данные на стадиях
коммуникации перемещаются по заранее определённому алгоритмом вычислений правилу, а именно от узла
(реплики) к соседям.
Контуры, которые образуют реплики (узлы вычислительной сети) на различных стадиях коммуникации, могут быть
предсказаны до осуществления своих вычислений. Таким образом, можно организовать такое физическое
расположение реплик по узлам сети, которое позволит свести к минимуму временные затраты на коммуникацию.
Для многих классов вычислительных систем (например, с распределённой памятью) экономия времени на
дорогостоящих вычислениях - желаемый результат. Использование
данного паттерна позволяет достичь такого результата.
На рисунке 7 представлена вычислительная сеть, в узлах которой располагаются осуществляющие вычисления
реплики, и контуры, которые образуют реплики на одной из стадий коммуникации. Параметры данного контура
могут быть использованы для перераспределения реплик по вычислительным узлам сети, цель - снижение
затрат на коммуникацию в процессе выполнения алгоритма.
Рисунок 7 - Контуры геометрической декомпозиции
Представленные паттерны в основном реализуют средне- и крупнозернистые параллельные
вычисления, что особенно способствует их использованию в реализации параллельных вычислений на
основе коммуникационной структуры в виде сети.
Литература:
-
Separation of Concerns in Parallel Patterns / Resources on Parallel Patterns
(PDF,
DOC)
Источник: Resources on Parallel Patterns /
Pattern Collection / Separation of Concerns in Parallel Patterns
-
Geometric Decomposition / Parallel Programming Patterns
Источник:
http://wing.cs.uiuc.edu/group/patterns/patterns/geometric.html
|