Стили и методы программирования
Виды параллелизма
Результатом команды считается результат участника, пришедшего последним.
(из правил соревнований по военно-прикладным видам спорта)
- Доктор, а чем я болен?
- Не волнуйтесь, больной, вскрытие покажет.
(русский анекдот)
Тот из видов параллелизма, который возникает при перемножении матриц, естественен для структурного программирования, но на самом деле параллелизмом не является. В структурном программировании данные организованы в сеть, по которой движется программа. Эта сеть является частичным порядком, и если в сети можно выделить несколько подсетей, слабо связанных друг с другом и проходящих через некоторый сегмент исходной сети с начала до конца, то эти подсети можно исполнять на независимых вычислителях, которые в критические моменты времени взаимодействуют между собой. Обычно такое разбиение сети данных не единственно, и поэтому можно один и тотже алгоритм исполнять на параллельных системах разной архитектуры.
Пример 15.2.1. Пусть сеть данных имеет следующий вид (рис. 15.1)
Рис. 15.1. Развилка
Тогда ее естественно исполнять на одно-, двух- либо трехпроцессорной машине. В случае многопроцессорной машины в начале и на заключительном этапе вычисление идет последовательно, а три ветви распределяются между процессорами. В частности, если две боковые ветви занимают меньше времени счета, чем главная, можно на двухпроцессорной машине распределить их обе на один и тот же процессор.
В распараллеленной программе заключительный этап исполнения начинается лишь после того, как завершатся все три ветви, дающие для него исходные данные. Такой параллелизм, когда для завершения блока параллельных процессов нужно успешно завершить все параллельные ветви, стандартно возникает в вычислительных задачах и носит название &-параллелизма. Насколько успешен будет результат распараллеливания, зависит от равномерности распределения вычислительной нагрузки между ветвями (см. первый эпиграф).
Другой вид параллелизма был впервые осознан на задачах поиска. Например, если нам известно, что сбежавший из зоопарка лев находится в одном из четырех кварталов и никак не может перебраться из одного в другой, для ускорения поиска можно (если у нас есть достаточное количество поисковых команд) послать по команде в каждый из кварталов, и закончить поиск, как только одна из команд найдет беглеца.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий