Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с

152 
Если e
ij
=(T
i
, T
j
) принадлежит E, это означает, что T
j
 информацион-
но зависит от T
i
. Тем самым выполнение T
j
 может начаться только по-
сле того, как задача T
i
 будет завершена, и вся информация, соответст-
вующая данной дуге, будет передана с процессора, исполняющего за-
дачу T
i
, на процессор исполняющий T
j
. 
Для  множества  предшественников  задачи  T
i
  введем  обозначение 
pred(T
i
). 
Во время выполнения каждая из задач исполняется одним процес-
сором  и  не  перемещается  на  другие  процессоры.  После  выполнения 
вычислений,  задача  может  пересылать  информацию  другим,  зависи-
мым  от  нее,  задачам.  Задача  не  может  дважды  передавать  информа-
цию,  производя  вычисления  в  промежутке  между  пересылками – в 
этом случае она должна быть разбита на две. 
 
2.1.2. Модель распределенной системы 
Распределенная  система M={P, 
η, C, θ} представлена как множе-
ство  процессоров P={P
1
, P
2
, …, P
m
},  имеющих  быстродействие 
η(P
i
) 
вычислений в единицу времени, некоторые из которых соединены ка-
налами C={c
ij
=(P
i
, P
j
)} с быстродействием 
θ(c
l
) информации в единицу 
времени.  Каналы  образуют  межпроцессорную  коммуникационную 
сеть. Таким образом, может быть задана гетерогенная система. 
В зависимости от способа передачи информации между процесса-
ми,  аппаратного  обеспечения  передачи  информации,  типа  ОС  и  др. 
причин, выбирается функция send(P
 i
, P
 j
, v), которая равна количеству 
единиц  времени,  необходимых  для  передачи v единиц  информации  с 
процессора  P
i
  на  процессор  P
j
.  В  одном  из  простых  случаев, 
send(P
i
,P
j
,v)=v(c
i
,
p1
+c
p1,p2
+…+c
pk,j
), где P
i
, P
p1
, P
p2
, … ,P
 j
 есть некоторый 
(обычно, минимальный) путь из процессора P
i
 в процессор P
j
. Для кла-
стеров  рабочих  станций  в  простейшем  случае  можно  использовать 
такой вид функции send: send(P
 i
,P
 j
,v)= v*c
i
,
j
, что оправдано для реаль-
ных  систем  вследствие  наличия  большого  числа  практически случай-
ных факторов, влияющих в этом случае на производительность среды 
передачи данных. 
Однако  наиболее  важным  свойством  предлагаемого  в  данной  ра-
боте алгоритма является его независимость от способа представления 
данной  функции.  Если  точности,  задаваемой  таким  представлением 
функции send недостаточно, можно использовать любое другое пред-
ставление  функции,  в  общем  случае  зависящее  не  только  от  объема 

 
153 
пересылаемой информации, но и от нагрузки на сеть. Более того, вели-
чина send(P
  i
, P
  j
,v),  в  общем  случае,  может  зависеть  от  времени.  На-
пример,  имея  полную  информацию о поведении распределенной сис-
темы, способах маршрутизации данных, алгоритмах буферизации дан-
ных и разрешения коллизий, можно построить моделирующую функ-
цию send, наиболее  точно  определяющую  время  передачи  информа-
ции.  Следует  отметить,  что  функция send активно  используется  при 
вычислении  функции  качества,  поэтому  чрезмерное  ее  усложнение 
нежелательно, т.к. это резко отрицательно отразится на скорости рабо-
ты программы. 
 
2.1.3. Представление расписания 
Расписание  выполнения  задач  представляется  в  виде  списка 
S={s
i
=(T
i
, P
i
, 
τ
i
)}, упорядоченного по 
τ
i
, где P
i
 – это процессор, испол-
няющий задачу T
i
, начиная с момента времени 
τ
i
 после старта распре-
деленной программы. Задача T
i
 может исполняться, только если все ее 
предшественники по направленному графу алгоритма завершили свое 
выполнение, и все данные, необходимые для ее выполнения, получены 
процессором P
i
. 
Таким образом,  
 
∀T
i
, 
∀T
j
 e
ij
=(T
i
, T
j
) 
∈E => τ
i
 +
µ (T
i
)+send(P
i
, P
j
, v(e
ij
)) 
≤ τ
j
. 
Если  данный  предикат  верен  для  некоторого  расписания S, гово-
рят, что S – допустимо. Алгоритм не должен выдавать в качестве сво-
его результата недопустимые расписания. 
Длина  расписания length(S)=max{
∀  s
i
∈ S}τ
j
  +
µ (T
i
)  есть  общее 
время  выполнения  распределенной  программы  на  данной  многопро-
цессорной  системе,  при  выполнении  в  порядке,  задаваемым  расписа-
нием S. 

жүктеу/скачать 1,64 Mb.

Достарыңызбен бөлісу: