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

                      ЭЗ1        канал                ЭЗ3


                                              канал
                  канал
                                  ЭЗ2
                            Задачи и каналы


     Пересылка сообщений с использованием стандартных библиотечных
утилит во многом аналогична модели «задачи и каналы», но для посылки и
приема сообщений используются вызовы библиотечных утилит, т.е. есть
существуют определенные ограничения на пересылаемые и получаемые
сообщения по каналам.
     В модели разделяемой памяти с использованием блокировок и
семафоров задачи используют общее адресное пространство, в котором они
читают и записывают данные асинхронно. Механизм блокировок и
семафоров используется для контроля доступа к общей памяти.

     Объединение элементарных задач.
      На этом этапе проектирования производится объединение
(укрупнение) ЭЗ. Комплекс ЭЗ полученных после этапа разбиения и этапа
определения коммуникаций, представляет абстрактный алгоритм в том
смысле, что он не может быть реализован на любой многопроцессорной
системе. Поэтому просматриваются решения по объединению ЭЗ с целью
получения параллельного алгоритма, который эффективно выполнялся бы на
некотором классе многопроцессорных систем. Нужно рассмотреть, где
полезно скомбинировать задачи, полученные на этапе разбиения так, чтобы
обеспечить в результате наименьшее число задач, каждая из которых
имеет наибольший размер.
      При агломерации получаемое число задач сокращается (в идеальном
случае одна задача на процессор), но еще может быть больше числа
процессоров в системе. В этом случае проектирование предусматривает
следующий шаг - распределение задач по процессорам. Соответственно на
этапе агломерации нужно стремиться, чтобы в результате была одна задача
на процессор.
      Как правило, три конфликтующих цели преследуются при агломерации
и размножении данных и/или операций:
      - сокращение стоимости коммуникаций за счет объединения
взаимосвязанных ЭЗ (локализация коммуникаций);
      - сохранение гибкости по отношению к масштабируемости (изменению
размерности задачи) и распределению задач по процессорам;

                                                                     209