Параллелизм независимых ветвей
ЛЕКЦИЯ 3.
Суть параллелизма независимых ветвей состоит в том, что в программе решения большой задачи могут быть выделены программные части, независимые по данным.
В параллельных языках запуск параллельных ветвей осуществляется с по-
мощью оператора FORK M1, M2 , ..., ML, где M1, M2, ..., ML — имена незави-
симых ветвей. Каждая ветвь заканчивается оператором JOIN (R,K), выполнение
которого вызывает вычитание единицы из ячейки памяти R. Так как в R пред-
варительно записано число, равное количеству ветвей, то при последнем сраба-
тывании оператора JOIN (все ветви выполнены) в R оказывается нуль и управ-
ление передается на оператор K. Иногда в JOIN описывается подмножество
ветвей, при выполнении которого срабатывает этот оператор. Рассмотрим при-
мер задачи с параллелизмом ветвей.
Пусть задана система уравнений:
Эту систему можно вычислять методом итераций по следующим формулам (n=3):
Функции F1...F3 из-за их различной программной реализации должны вы-
числяться отдельными программными сегментами, которые можно использо-
вать как ветви параллельной программы. Соответствующая параллельная про-
грамма имеет вид:
L FORK M1, M2, M3
M1 Z1 = F1 (X1, X2, X3)
JOIN (R, K)
M2 Z2 = F2 (X1, X2, X3)
JOIN (R,K)
M3 Z3 = F3 (X1, X2, X3)
JOIN (R, K)
K IF (ABS(Z1-X1)<ε)AND(ABS(Z2-X2)<ε)AND(ABS(Z3-X3)<ε)
THEN вывод результатов; STOP
ELSE X1=Z1; X2=Z2; X3=Z3; GO TO L
Если при выполнении оператора JOIN оказалось, что R ≠ 0, то вычисления в данной ветви останавливаются, но могут быть запущены повторно, если условие в операторе K не выполняется. Этот процесс представлен на рис.
Для приведенного примера характерны две особенности:
1. Присутствует синхронизация процессов, для которой используются
оператор JOIN и ячейка R. Состояние R = 0 свидетельствует об окон-
чании процессов разной длительности.
2. Производится обмен данными (обращение за Xi из разных ветвей).
Параллелизм вариантов.
Это частный, но широко распространенный на практике случай параллелизма независимых ветвей, когда производится решение одной и той же задачи при разных входных параметрах, причем, все варианты должны быть получены за ограниченное время.
Параллелизм вариантов отличается от идеологии крупнозернистого парал
лелизма. Отличие состоит в том, что в случае крупнозернистого параллелизма
вычисления проводятся внутри одной задачи и требования к скорости обмена
между частями задачи достаточно высокие. В параллелизме вариантов распараллеливаются целые задачи, обмен между которыми в принципе отсутствует.
Системы распределенных вычислений идеальны для решения таких задач.
Эффективность параллельных вычислений (закон Амдала)
Закон Амдала.Одной из главных характеристик параллельных систем яв
ляется ускорение R параллельной системы, которое определяется выражением:
R = T1 /Tn ,
где T1 − время решения задачи на однопроцессорной системе, а Tn − время решения той же задачи на n − процессорной системе.
Пусть W = Wск + Wпр, где W − общее число операций в задаче, Wпр − число операций, которые можно выполнять параллельно, а Wcк − число скаляр-
ных (нераспараллеливаемых) операций.
Обозначим также через t время выполнения одной операции. Тогда получаем известный закон Амдала :
Здесь a = Wск /W − удельный вес скалярных операций.
Закон Амдала определяет принципиально важные для параллельных вычислений положения:
• Ускорение зависит от потенциального параллелизма задачи (величина а) и параметров аппаратуры (числа процессоров n).
• Предельное ускорение определяется свойствами задачи. Пусть, например, a = 0,2 (что является реальным значением), тогда ускорение не может пре-
восходить 5 при любом числе процессоров, то есть максимальное ускорение определяется потенциальным параллелизмом задачи.
Если система имеет несколько архитектурных уровней с разными формами параллелизма, то качественно общее ускорение в системе будет:
R = r1*r2*r3,
где ri - ускорение некоторого уровня.