Виды параллелизма
Результатом команды считается результат участника, пришедшего последним.
(из правил соревнований по военно-прикладным видам спорта)
- Доктор, а чем я болен?
- Не волнуйтесь, больной, вскрытие покажет.
(русский анекдот)
Тот из видов параллелизма, который возникает при перемножении матриц, естественен для структурного программирования, но на самом деле параллелизмом не является. В структурном программировании данные организованы в сеть, по которой движется программа. Эта сеть является частичным порядком, и если в сети можно выделить несколько подсетей, слабо связанных друг с другом и проходящих через некоторый сегмент исходной сети с начала до конца, то эти подсети можно исполнять на независимых вычислителях, которые в критические моменты времени взаимодействуют между собой. Обычно такое разбиение сети данных не единственно, и поэтому можно один и тотже алгоритм исполнять на параллельных системах разной архитектуры.
Пример 15.2.1. Пусть сеть данных имеет следующий вид (рис. 15.1)
Рис. 15.1. Развилка
Тогда ее естественно исполнять на одно-, двух- либо трехпроцессорной машине. В случае многопроцессорной машины в начале и на заключительном этапе вычисление идет последовательно, а три ветви распределяются между процессорами. В частности, если две боковые ветви занимают меньше времени счета, чем главная, можно на двухпроцессорной машине распределить их обе на один и тот же процессор.
В распараллеленной программе заключительный этап исполнения начинается лишь после того, как завершатся все три ветви, дающие для него исходные данные. Такой параллелизм, когда для завершения блока параллельных процессов нужно успешно завершить все параллельные ветви, стандартно возникает в вычислительных задачах и носит название &-параллелизма. Насколько успешен будет результат распараллеливания, зависит от равномерности распределения вычислительной нагрузки между ветвями (см. первый эпиграф).
Другой вид параллелизма был впервые осознан на задачах поиска. Например, если нам известно, что сбежавший из зоопарка лев находится в одном из четырех кварталов и никак не может перебраться из одного в другой, для ускорения поиска можно (если у нас есть достаточное количество поисковых команд) послать по команде в каждый из кварталов, и закончить поиск, как только одна из команд найдет беглеца.
Таким образом, возникает
Рассмотрим теперь, каковы же общие условия применимости
if Лев в квартале1
Но беда в том, что для выяснения истинности охраны нужно выполнить охраняемую команду, т.е. найти льва. Таким образом, данный условный оператор может служить лишь призраком.
Далее, имеется еще одно неявное условие, которое иллюстрируется вторым эпиграфом. Если исполнение охраняемой команды с неподходящей охраной может навредить (ресурсы-то оно займет, вред - это нечто более существенное, наподобие лечения согласно неверному диагнозу), то мы скорее всего будем вынуждены производить вскрытие программы после внезапной и мучительной ее кончины.
Таким образом,
- проверить охрану ничуть не проще, чем выполнить соответствующую охраняемую команду;
- выполнение команды из неверной альтернативы ничем, кроме растраты ресурсов, повредить не может.
Тогда можно запустить различные варианты параллельно на разных процессорах и посмотреть, какой первый придет к удаче.
В качестве примера задачи, естественно допускающей >
Третий вид параллелизма на самом деле параллелизмом не является, и, пожалуй, шире всего распространен в практике программирования. Это квазипараллелизм. Вы встречаетесь с ним в программах, когда порождаете подпроцесс командой типа thread. В этом случае несколько процессов исполняются как один процесс, в котором перемешаны шаги подпроцессов, так что у программиста создается впечатление, что процессы исполняются параллельно. Квазипараллелизм может с внешней стороны выглядеть как любой из двух рассмотренных ранее видов параллелизма. В первом приближении квазипараллелизм дает лишь чистый проигрыш, но фактически он позволяет занять естественно образующиеся в одном из процессов промежутки ожидания (например, ввода или вывода данных) работой других процессов. Именно так работает Ваш плейер, пока Вы ломаете голову над ошибками в своей программе.
Поскольку здесь все управление на самом деле сосредоточено в одном месте, методы работы с квазипараллельными процессами наиболее развиты.
И, наконец, последний случай параллелизма, когда процессы не просто идут параллельно друг с другом, они идут на разных, часто плохо связанных друг с другом, вычислителях. Например, на сервере работает поиск в базе данных, а у Вас работает основная программа. Это распределенное исполнение. В последнее время такой случай также неплохо разработан, потому что в столь тяжелой ситуации любая недоделка может привести к агонии программы.
Пример 15.2.2. Классическим примером эффективного использования
