Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО НАЗНАЧЕНИЯ
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
Seminar 1
| ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО НАЗНАЧЕНИЯ
ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ НА ГЕТЕРОГЕННЫЙ ВЫЧИСЛИТЕЛЬНЫЙ КЛАСТЕР А.В.Киселев, Е.Л. Зверев Институт криптографии, связи и информатики Академии ФСБ России, Москва В работе рассматриваются вопросы оптимального назначения па- раллельных задач на вычислительный кластер, образованный путем объединения нескольких мультипроцессорных вычислительных сис- тем. Эффективность использования вычислительного кластера во мно- гом зависит от оптимальности распределения его ресурсов между по- током параллельных задач. В случае мультизадачного режима исполь- зования кластера, назначение очередной параллельной задачи должно осуществляться с учетом текущего состояния его вычислительных 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 } – множество дуг – 82 описывает взаимодействия процесса: каждой дуге соответствует чис- ло d j , характеризующее передаваемый объем данных. Назначение процесса на вычислительный узел приводит к увели- чению загруженности процессора и коммуникационной подсистемы. Отличную от 0 загруженность процессора (канала) можно интерпрети- ровать как уменьшение его производительности (пропускной способ- ности). В этом случае будем говорить о приведенной производитель- ности p' (пропускной способности c'): p' = (1–z p ) ×p; c'=(1–z c ) ×c. Оценить изменение производительности процессора и пропускной способности канала в случае назначения на ВУ <l, p, z p > процесса A <a, d> можно по формулам: ; ' ; ' ) ( ) ( ∑ ∑ + ≥ ≥ + ≥ ≥ i i i i i i c d p a c d p p p aс dp aс с c 2 2 Пересчет приведенной пропускной способности осуществляется для всех логических каналов, включающих в свой состав физический канал, используемый процессом A i для передачи данных. Обозначим ϕ : A → B , (N = |A|, M = |B|) отображение информаци- онного графа параллельной задачи G a на структуру вычислительной системы, заданной графом G b и представим его матрицей X ϕ = { X ij : i ∈ A, j ∈ B }, где X ij = 1, если ϕ (i) = j, и X ij = 0, если ϕ (i) ≠ j. Опти- мальное отображение доставляет минимум функционалу F(X ϕ) = F 1 (X ϕ) + F 2 (X ϕ), где ∑ ∑ ∑ ∑ = = = = − = ϕ N i M k k j M j i N i i ik p p a a X X F 1 1 2 1 1 1 ; ) ' ' ( ) ( ∑ ∑ ∑ ∑ = = = = = ϕ M i M j N p N k kj pi pk ' ij X X c d ) (X F 1 1 1 1 2 . F 1 (X ϕ) оценивает равномерность загрузки процессоров, а F 2 (X ϕ) оце- нивает загрузку коммуникационной подсистемы. Приведенная выше постановка задачи назначения позволяет ис- следовать вопросы оптимального распределения параллельных про- цессов в гетерогенных мультипроцессорных системах в условии раз- 83 деления вычислительных ресурсов (процессорное время ВУ, коммуни- кационные каналы) между различными задачами. Поскольку задача оптимального назначения является NP-полной, для ее решения могут быть использованы эвристические алгоритмы, обеспечивающие субоптимальные решения с заданной точностью. жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|