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

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

  2) Каждая элементарная задача связана с небольшим числом соседей? Если нет, то
   следует исследовать возможность преобразования глобальных коммуникаций в ло-
   кальные.

  3) Все ли коммуникации могут выполняться параллельно (одновременно)? Если нет,
   то алгоритм не масштабируем и не эффективен. В этом случае можно использовать
   технологию “разделяй и властвуй” для создания параллельности.

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

      2.3 Выбор модели аппаратной реализации параллельных вычислений
     На этом этапе необходимо определить наиболее подходящую модель аппаратной
реализации параллельных алгоритмов из числа следующих: - сетка процессоров; - объе-
динение процессоров через общую шину; - взаимодействие процессоров через общую
память.




                                          13