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

      - сокращении стоимости инженерной разработки программного
обеспечения.
      Рассмотрим каждую из них.
      Локализация коммуникаций. На этапе разбиения алгоритма на ЭЗ
усилия сосредотачиваются на получении как можно большего числа задач.
Это позволяет рассмотреть широкий круг возможностей для параллельного
выполнения. Однако, следует заметить, что получение большого числа задач
при разбиении не обязательно дает эффективный параллельный алгоритм.
Самое негативное влияние на время выполнения параллельного алгоритма
оказывают коммуникации. На большинстве параллельных систем приходится
останавливать вычисления, чтобы послать или принять сообщения
необходимые для их продолжения. Улучшить скорость вычисления можно
пересылкой меньшего объема данных между задачами, выполняющимися
параллельно. Менее очевидно, но сократить время на коммуникации можно и
при использовании меньшего числа сообщений при тех же объемах данных.
Это объясняется тем, что каждая коммуникация требует время не только
пропорциональное объему пересылаемых данных, но имеет фиксированные
начальные затраты времени по ее установлению. В дополнение к
коммуникационным временным затратам нужно учитывать и стоимость
создания задачи на процессоре (выделение памяти и т.д.).
      Исходя из вышесказанного, объединение взаимодействующих задач в
одну устраняет необходимость их внешних коммуникаций, так как
полученная задача будет выполняться на одном процессоре.
      Можно отметить, что при разбиении по данным эффективен подход
увеличения локальности за счет увеличении размерности «куска»,
обрабатываемых регулярных данных (векторы, матрицы и т.п.). Но если
данные нерегулярны, то задача агломерации становится достаточно трудной.
Можно попытаться использовать размножение данных и/или операций для
сокращения коммуникаций и/или для сокращения времени вычисления.
      Сохранение гибкости. Хорошо разработанный параллельный
алгоритм должен быть гибким по отношению к числу процессоров в системе,
что повышает ее надежность в случае отказа одного или нескольких
процессоров. Гибкость также полезна и при создании программного кода для
отдельного процессора. Если задачи часто блокируются в ожидании данных
от других процессоров, это может быть использовано для назначения
нескольких таких задач на один процессор, с тем, что пока одна задача
ожидает данных, другая может выполняться. Тогда время коммуникации
одной задачи перекрывается временем вычисления другой и таким образом
процессор не простаивает. Третья полезность создания большего числа задач
чем процессоров состоит в обеспечении лучших возможностей при
распределении задач по процессорам (балансировка вычислений ). Хорошее
правило состоит в том, что число задач должно быть на порядок больше
числа процессоров.


                                                                      210