Проектирование параллельных алгоритмов в задачах идентификации. Вашкевич Н.П - 18 стр.

   Так при разбиении по данным используется загрузочно-балансный алгоритм (динами-
ческий загрузочно-балансный алгоритм), обеспечивающий равномерную загрузку про-
цессоров.
   При функциональной декомпозиции используется алгоритм составления расписаний
для задач. Есть централизованный ( в одном месте ) или распределенный ( в нескольких
местах ) набор ( пул ) задач, в который новые задачи помещаются и из которого задачи
берутся для размещения по процессорам.
   Наиболее сложным аспектом при составлении расписания является используемая стра-
тегия при размещении задач по процессорам. В основном выбираемая стратегия пред-
ставляет компромисс между конфликтными требованиями по независимости задач ( что-
бы сократить стоимость коммуникаций ) и полном знании о состоянии вычислений ( что-
бы улучшить балансировку загрузки процессоров ). Рассмотрим централизованный (
manager/workers ), иерархический ( manager/submanager/workers ) и децентрализованный
подходы.
   Централизованный подход. Manager ( управляющий ) отвечает за проблему размеще-
ния. Каждый worker ( исполнитель ) постоянно обращается к мanager с запросами ( на-
пример, сообщение об окончании выполнения задачи ) получает задачу от него и испол-
няет ее. В свою очередь workers могут послать новые задачи мanager, которые затем мо-
гут быть размещены по другим рабочим. Эффективность такой стратегии зависит от чис-
ла workers и относительной стоимости получения задач от manager и их выполнения. Ре-
зультаты могут быть улучшены за счет перекрытия вычислений и коммуникаций, а также
кешированием задач в workers так, чтобы workers связывались с мanager когда нет ло-
кальных ( своих ) задач.
   Иерархический подход. Workers делятся на отдельные группы у которых свой
submanager ( подуправляющий ). Workers из группы связываются только со своим
submanager. Submanager периодически связываются с manager и другими submanager что-
бы обеспечить балансировку загрузки процессоров за которые они отвечают.
   Децентрализованный подход. В полностью децентрализованной схеме нет централь-
ного управляющего. Соответственно отдельный пул задач назначается на каждый процес-
сор и незанятые процессоры требуют задач от других процессоров. В результате пул за-
дач становится распределенной структурой данных, которая доступна различным задачам
асинхронно. При этом определяется какая-либо процедура доступа. Например worker мо-
жет требовать задания только от небольшого числа соседей или выбирать другие процес-
соры по “заданному” случайному закону.
   Гибридный централизованно - децентрализованный подход. В гибридной централи-
зованной/децентрализованной схеме запросы посылаются центральному управляющему
который размещает их по workers, используя круговой "обход-отбор". Нужно отметить,
что хотя в этом случае центральный управляющий будет узким местом в системе при
большом числе процессоров, доступ к нему будет требоваться менее часто чем к управ-
ляющему в централизованном системе и следовательно это более масштабируемая конст-
рукция.
   Доступ к распределенному пулу задач может быть получен несколькими способами.
Workers могут быть назначены ответственными как за вычисления так и за управление
очередью задач. В этом случае каждый workers должен периодически переключаться с
вычислений на проверку ожидающих запросов.
   Обнаружение завершения. Составление расписаний требует механизма для обнару-
жения момента времени когда весь алгоритм будет завершен, в противном случае про-


                                         18