81
ресурсов. Степень использования ресурсов кластера (процессоров,
коммуникационных каналов) характеризует показатель – загружен-
ность (процессоров, каналов), значения которого для отдельных ком-
понентов кластера могут быть получены от средств мониторинга сис-
темы.
В общем случае, при назначении на выполнение очередной задачи,
кластер следует рассматривать как неоднородную мультипроцессор-
ную систему, процессоры и каналы которой обладают различными
значениями производительности и пропускной способности в силу
конструктивных различий или в виду различной загруженности.
Предлагается следующая постановка задачи назначения парал-
лельной программы на гетерогенный вычислительный кластер.
С каждым вычислительным узлом (ВУ) b
i
связан описатель –
<
l, p, z
p
> , где
l – тип процессора,
p – производительность процессора
(число команд, выполняемых в единицу времени),
z
p
– текущая загру-
женность процессора.
Коммуникационная подсистема рассматривается на физическом и
логическом уровнях:
• на физическом уровне – как граф G
f
= (B,F), где B={b
i
}– множест-
во ВУ, а F – множество соединяющих вершины физических кана-
лов связи. С каждым каналом связан описатель <
s,
z
s
>, где
s –
пропускная способность канала, а
z
s
– текущая загруженность ка-
нала. Топология коммуникационной подсистемы задается матри-
цей смежности S=||
s
ij
|| графа G
f
;
• на логическом уровне – система рассматривается как полный граф
G
b
, вершинами которого являются ВУ, а ребрами – логические ка-
налы связи. Под логическим каналом понимается путь между
вершинами b
i
и b
j
графа G
f
, обладающий максимальной пропуск-
ной способностью. С каждым логическим каналом связан описа-
тель <
c,z
c
>, где
c – пропускная способность логического канала,
определяемая как минимальная из пропускных способностей фи-
зических каналов, образующих данный логический канал, а
z
c
–
текущая загруженность логического канала.
Параллельная задача представляется в виде графа G
a
= (А,D), где
A={А
i
}- совокупность взаимодействующих процессов, c каждым из
которых связан вектор
a=
l
>. a
l
определяет вычислительную слож-
ность Ai в числе команд процессора l-типа. D= {D
i
} – множество дуг –
83
деления вычислительных ресурсов (процессорное время ВУ, коммуни-
кационные каналы) между различными задачами.
Поскольку задача оптимального назначения является NP-полной,
для ее решения могут быть использованы эвристические алгоритмы,
обеспечивающие субоптимальные решения с заданной точностью.
Достарыңызбен бөлісу: