Параллелизм независимых ветвей

Суть параллелизма независимых ветвей состоит в том, что в программе решения большой задачи могут быть выделены программные части, независимые по данным.

В параллельных языках запуск параллельных ветвей осуществляется с по-

мощью оператора FORK M1, M2,..., ML, где M1, M2,..., ML — имена незави-

симых ветвей. Каждая ветвь заканчивается оператором JOIN (R,K), выполнение

которого вызывает вычитание единицы из ячейки памяти R. Так как в R пред-

варительно записано число, равное количеству ветвей, то при последнем сраба-

тывании оператора JOIN (все ветви выполнены) в R оказывается нуль и управ-

ление передается на оператор K. Иногда в JOIN описывается подмножество

ветвей, при выполнении которого срабатывает этот оператор. Рассмотрим при-

мер задачи с параллелизмом ветвей.

Пусть задана система уравнений:

 

Эту систему можно вычислять методом итераций по следующим формулам (n=3):

 

Функции F 1...F 3 из-за их различной программной реализации должны вы-

числяться отдельными программными сегментами, которые можно использо-

вать как ветви параллельной программы. Соответствующая параллельная про-

грамма имеет вид:

 

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. Производится обмен данными (обращение за X i из разных ветвей).

 

Параллелизм вариантов.

Это частный, но широко распространенный на практике случай параллелизма независимых ветвей, когда производится решение одной и той же задачи при разных входных параметрах, причем, все варианты должны быть получены за ограниченное время.

Параллелизм вариантов отличается от идеологии крупнозернистого парал

лелизма. Отличие состоит в том, что в случае крупнозернистого параллелизма

вычисления проводятся внутри одной задачи и требования к скорости обмена

между частями задачи достаточно высокие. В параллелизме вариантов распараллеливаются целые задачи, обмен между которыми в принципе отсутствует.

Системы распределенных вычислений идеальны для решения таких задач.

 

Эффективность параллельных вычислений (закон Амдала)

Закон Амдала. Одной из главных характеристик параллельных систем яв

ляется ускорение R параллельной системы, которое определяется выражением:

R = T 1 / Tn,

где T 1 − время решения задачи на однопроцессорной системе, а T n − время решения той же задачи на n − процессорной системе.

Пусть W = W ск + W пр, где W − общее число операций в задаче, W пр − число операций, которые можно выполнять параллельно, а W cк − число скаляр-

ных (нераспараллеливаемых) операций.

Обозначим также через t время выполнения одной операции. Тогда получаем известный закон Амдала:

 

Здесь a = W ск / W − удельный вес скалярных операций.

Закон Амдала определяет принципиально важные для параллельных вычислений положения:

• Ускорение зависит от потенциального параллелизма задачи (величина а) и параметров аппаратуры (числа процессоров n).

• Предельное ускорение определяется свойствами задачи. Пусть, например, a = 0,2 (что является реальным значением), тогда ускорение не может пре-

восходить 5 при любом числе процессоров, то есть максимальное ускорение определяется потенциальным параллелизмом задачи.

Если система имеет несколько архитектурных уровней с разными формами параллелизма, то качественно общее ускорение в системе будет:

R = r1*r2*r3,

где ri - ускорение некоторого уровня.