Лекции по параллельным вычислениям. Гергель В.П - 42 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

42
Граф вычислительной схемы алгоритма (3.1) совместно с расписанием
(3.4) может рассматриваться как модель параллельного алгоритма:
A
s
(G,H
s
), (3.7)
реализуемого с использованием s процессоров.
Время выполнения параллельного алгоритма определяется максимальным
значением времени, применяемым в расписании:
iss
t
V
i
max
H,GT . (3.8)
Для фиксированного графа вычислений целесообразно строить расписание,
обеспечивающее минимальное время исполнения алгоритма:
ss
s
s
H,GT
H
min
GT
. (3.9)
Часто в ходе построения параллельного вычислительного процесса с це-
лью уменьшения времени реализации алгоритма перебираются также различ-
ные вычислительные схемы. Переход к каждой новой вычислительной схеме,
как правило, ведет к изменению расписания. Такая постановка задачи, в общем
виде, может быть сформулирована следующим образом:
ss
s
s
H,GT
H
min
G
min
T . (3.10)
Точное решение такой задачи возможно лишь в очень немногих простых
случаях. Для большинства же реальных алгоритмов оценить хотя бы прибли-
женно даже число возможных вариантов графа вычислительной схемы вряд ли
удастся. Поэтому сформулированная задача может рассматриваться, как фор-
мальное представление целевой функции, которая может использоваться при
последовательном просмотре вариантов построения параллельного вычисли-
тельного процесса на конкретной многопроцессорной вычислительной системе.
При этом в процессе перебора вариантов оценки
ss
H,GT ,
GT
s
и T
s
могут использоваться при принятии решения о выборе конкретного графа и
расписания вычислительного процесса.

Страницы