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

которые пересылаются по этим каналам. При разбиении данных определение
коммуникаций между ЭЗ является сложной задачей, так как существует
достаточно много вариантов, из которых надо выбрать наиболее
оптимальный. Наоборот, при разбиении по операциям определение
коммуникаций достаточно простая задача, так как коммуникации
соответствуют потоку данных между ЭЗ.
      В общем случае можно произвести классификацию коммуникаций по
следующим признакам: - локальная или глобальная; -структурированная
(регулярная) или неструктурированная (нерегулярная); - статическая или
динамическая; - синхронная или асинхронная.
      При локальной коммуникации каждая ЭЗ взаимодействует с
небольшим числом задач (ее «соседями»), а при глобальной со многими
задачами (в пределе с каждой). При структурированной коммуникации
каждая ЭЗ и ее соседи образуют регулярную структуру (например «дерево»
или «сетка»), а при неструктурированной нерегулярную структуру
(произвольный граф). При статической коммуникации взаимосвязи
определяются «раз и навсегда» и не меняются при выполнении алгоритма, а
при динамической могут меняться. При синхронной коммуникации есть
синхронизирующие сигналы между источником и приемником, а при
асинхронной нет. Результаты определения коммуникаций также необходимо
сверить со следующими рекомендациями для оценки их качества.
      1) Если не все элементарные задачи выполняют одинаковые
коммуникации, то такая несогласованность дает немасштабируемый
алгоритм.
      2) Если каждая элементарная задача связана с большим числом
соседей, то следует исследовать возможность преобразования глобальных
коммуникаций в локальные.
      3) Если все коммуникации не могут выполняться параллельно
(одновременно), то алгоритм не масштабируем и не эффективен.

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

                                                                    208