Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 212 стр.

      - размещение задач, которые часто взаимодействуют, на одном и том
же процессоре, чтобы уменьшить коммуникационную стоимость.
      Ясно, что эти стратегии конфликтуют и проектирование должно
разрешить эти противоречия. Кроме того, на распределение задач по
процессорам могут влиять доступные ресурсы одного процессора,
ограничивая число задач которые могут быть одновременно размещены на
нем.
      Такая задача распределения известна как NP-задача. Это означает, что
задача трудно разрешима, поскольку для нее нет алгоритма решения с
полиномиальной зависимостью от входной размерности (число задач и число
процессоров). Поэтому при решении таких задач используются
эвристические методы.
      Так при разбиении по данным используется статический или
динамический загрузочно-балансировочный алгоритм, обеспечивающий
равномерную загрузку процессоров.
      При функциональной декомпозиции используется алгоритм
составления расписаний для задач. Есть набор задач - централизованный (в
одном месте) или распределенный (в нескольких местах) куда новые задачи
помещаются и откуда берутся для размещения по процессорам.
      Наиболее сложным вопросом при составлении расписания является
используемая стратегия при размещении задач по процессорам. В основном
выбираемая стратегия представляет компромисс между конфликтными
требованиями по независимости задач (чтобы сократить стоимость
коммуникаций) и полном знании о ходе вычислений (чтобы улучшить
балансировку загрузки процессоров). Рассмотрим централизованный
(управляющий/исполнители), иерархический (главный
управляющий/управляющий/исполнители) и децентрализованный подходы.
      Централизованный подход. При таком подходе управляющий
отвечает за проблему размещения задач по процессорам. Каждый
исполнитель постоянно обращается к управляющему с запросами (например,
с сообщением об окончании выполнения очередной задачи), получает новую
задачу от него и исполняет ее. В свою очередь исполнители могут послать
новые задачи управляющему, которые затем могут быть размещены по
другим исполнителям. Эффективность такой стратегии зависит от числа
исполнителей, относительной стоимости получения задач от управляющего.
Результаты могут быть улучшены кешированием задач у исполнителей так,
чтобы исполнители связывались с управляющим только тогда, когда нет
локальных (своих) задач.
      Иерархический подход. Исполнители делятся на отдельные группы, у
каждой из которых свой управляющий. Исполнители группы связываются
только со своим управляющим. Управляющие периодически связываются с
главным управляющим и другими управляющими, чтобы обеспечить
балансировку загрузки процессоров, за которые они отвечают.

                                                                       212