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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

38
количество операций. Дугам графа приписываются веса
Njic
ij
,1,, , отра-
жающие интенсивность информационного обмена между i-й и j- вершинами
(операциями).
Вычислительная система также представляется в виде графа
sss
E,PG . (3.4)
Здесь
s
P - множество процессоров,
s
E - множество дуг, представляющих линии
связи между процессорами. Пропускная способность линий связи характеризу-
ется весами дуг графа
sij
Ej,i,N,j,i,m 1 .
Задается критерий оптимальности отображения
sp
PV:
графа парал-
лельной задачи
ppp
EAG , на структуру вычислительной системы, заданной
графом
sss
E,PG :
sp
PV:QQ
. (3.5)
Если отображение
sp
PV:
представляется матрицей
spij
Pj,Vi:XX
где 1
ij
X , если
ji
и 0
ij
X , если
ji
, то кри-
терий оптимальности отображения, при условии равной производительности
всех процессоров системы, имеет вид
min
1 1 1 1
pjkikp
N
i
N
j
N
p
N
k
ij
XXcmXQ .
В рамках общей проблемы отображения обычно решается одна из двух за-
дач:
1. Для данной параллельной программы выбрать решающее поле.
2. Распределить ветви параллельной программы по процессорам компью-
тера заданной архитектуры.
3.3 Модели сетей передачи данных между процессорами
Для точного отображения алгоритма на архитектуру конкретной вычисли-
тельной системы (ВС) граф алгоритма и граф ВС должны быть изоморфны. К

Страницы