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

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

                                                                     213