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

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

                                                                     207