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

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

  2) Позволяет ли полученная декомпозиция избежать чрезмерного количества опера-
   ций и/или чрезмерных требований по затратам памяти?. Если нет то результирующий
   параллельный алгоритм не может быть применим при увеличении входной размерно-
   сти данных (в литературе используется понятие "алгоритм не масштабируем").
  3) Одинакового ли размера полученные задачи? Если нет, то при дальнейшем проек-
   тировании будет трудно обеспечить равномерную загрузку процессоров системы.

  4) Число ЭЗ пропорционально размеру исходной задачи? В идеальном случае необхо-
   димо, чтобы увеличение размерности исходной задачи увеличивало число ЭЗ значи-
   тельно быстрее, чем размер самой ЭЗ. Если этого нет, то параллельный алгоритм не
   пригоден при росте размерности задачи и увеличения числа процессоров в системе.

  5) Есть ли наличие альтернативных вариантов декомпозиции. Это может обеспечить
   большее число вариантов на последующих шагах проектирования.

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


                                         12