Стронгин Р.Г. Высокопроизводительные паралленльные вычисления на кластерных системах. 2003

процессоров более заметна, когда число областей, на которые разбивается изображение невелико. Повышение эффективности использования вычислительных ресурсов кластера может быть достигнуто увеличением размеров областей, находящихся на границах и в углах изображения.

Таким образом, возникает задача нахождения такого разбиения исходного изображения, при котором время работы всех процессоров с учетом пересылок сбалансировано.

2. Схема декомпозиции

Рассмотрим случай, когда исходное изображение квадратное X×X, где X – число отсчетов одной стороны изображения. Будем полагать, что для заданных вычислительного алгоритма и вычислительной системы (кластера) известны константы: τp – время расчета при обработке одного отсчета изображения и τn – среднее время, затрачиваемое на передачу информации, необходимой для одного отсчета изображения. При фиксированных значениях указанных величин наибольшее отношение объема вычислений к объему пересылок достигается при форме фрагмента в виде квадрата.

Пусть x – сторона квадратного фрагмента (выраженная числом отсчетов). Потребуем, чтобы величина x удовлетворяла неравенству

(4 δ) x ≤ ∆доп ,

(1)

где δ = τn /τp – отношение отрезков времени, необходимых для пересылки данных к времени обработки в расчете на один отсчет изображения, а ∆доп – допустимая величина отношения времени пересылок к времени обработки внутренней области, задаваемая из условия эффективной загрузки процессоров. Ясно, что неравенство (1) выполняется также для фрагментов, расположенных на границах исходного изображения, т.к. они имеют меньшую длину сопряженных границ. Неравенство только усилится, если размеры этих фрагментов увеличить, не уменьшая размеров внутренних так, как показано на рисунке 1.

Области, находящиеся в углах изображения размером x0×x0, будем называть угловыми, области x0×x (x×x0) – граничными, а области x×x – внутренними. Задача заключается в том, чтобы найти x0 и x такие,

231

чтобы время обработки всех областей с учетом затрат на пересылку

x0

x

x0

x0

x X

x0

X

было одинаковым.

Рис.1. Разбиение квадратного изображения на фрагменты

Если ширина полос на границах областей, которыми они должны обмениваться, мала по сравнению с размерами квадратов, можно в первом приближении считать объем передаваемых данных пропорциональным длине границ (сторон). Тогда суммарное время обработки с учетом пересылок:

а) для внутренней области:

T	= x2 τ	р	+ 4 x τ	п	,	(2)
вн
б) для граничной:
Tгр = x x0 τр + 2 x0 τп + x τп ,						(3)
в) для угловой:	= x02 τр + 2 x0 τп .
Tугл						(4)
Положим	x0 = k x					(5)
где
	1 < k <1,5					(6)
						232

– коэффициент увеличения угловой (и соответственно граничной) области, который необходимо выбрать из условия балансировки процессоров.

Верхний предел для k указывает значение, при котором балансировка невозможна. В частности, уже при k = 1,5 длины сопряженных границ, а, следовательно, и объемы передаваемых данных для внутренних и граничных областей одинаковы, а объем вычислений для граничной области больше.

3. Условия балансировки процессоров

Можно показать, что точная балансировка всех процессоров достигается при δ = 0, k = 1. Поэтому полную балансировку, при одновременном сокращении времени обработки, можно осуществить лишь для части процессоров. При балансировке процессоров, обрабатывающих внутренние и граничные области, вычислительные затраты на обработку угловых областей существенно возрастают. Поэтому потребуем, чтобы выполнялось равенство

Tугл = Твн .	(7)
или
k 2 x + 2 k δ = x + 4 δ .	(8)

Для выбора k, удовлетворяющего равенствам (7), (8), необходимо исключить величину x. Сделаем это исходя из следующих соображений. Предположим, что удовлетворяющее неравенству (1) x = (4 δ) / ∆доп является делителем числа X . Тогда при разбиении исходного изображения на одинаковые квадраты (k = 1) число полос, на которые может быть разбита одна из сторон X равно X / x. При увеличении сторон угловых квадратных фрагментов в k раз для предельного значения k = 1,5, число полос n, на которые может быть разбита сторона квадратного изображения длиной X, определяется равенством

n = (X / x)−1 .	(9)
Соотношение для выбора k, полученное из (8) с учетом (9)
принимает вид
X (k 2 −1) − (4 − 2k)(n +1)δ = 0 ,	(10)
	233

где X – число отсчетов одной стороны исходного изображения. Заметим, что при k, удовлетворяющем (10), неравенство (1) не нарушается. Дело в том, что число полос n, фигурирующее в (10), определяется равенством (9), которое соответствует предельному значению масштабного коэффициента (k = 1,5). Поскольку в действительности k в силу (10) обычно оказывается меньшим, величину стороны внутреннего фрагмента необходимо соответственно увеличить. Ясно, что при этом неравенство (1) лишь усиливается. Для заданного в соответствии с (9) n величина xˆ стороны квадратного внутреннего фрагмента, уточненная (увеличенная по cравнению с x) с учетом найденного из равенства (10) масштабного коэффициента k определяется как

xˆ = X /(n + 2 (k −1)) .

(11)

Остается убедиться, что время обработки граничного фрагмента с учетом пересылок не будет превышать время обработки внутренних и угловых областей:

Tгр <Тугл .

(12)

Подставляя в (12) значения Tгр, Tугл из (3), (4) в области допустимых значений k, определяемых неравенствами (6), получаем дополнительное условие

k > 0,5 + 0,25 + δ xˆ ,

(13)

где xˆ – вычисленная в соответствии с (11) сторона квадратного внутреннего фрагмента.

Для большинства известных итерационных алгоритмов обработки изображений величина δxˆ мала, при этом граница (13) почти

совпадает с левой границей в (6). Следовательно, практически для всех допустимых k время обработки граничных областей не превышает время обработки внутренних и угловых областей, что приведет к полной загрузке соответствующих процессоров.

4. Обсуждение

Соотношения (9), (10), (11) могут использоваться для выбора начального разбиения обрабатываемого изображения. В действительности эффективность загрузки процессоров будет зависеть также от схемы организации вычислительного процесса и

234

характеристик коммуникационной среды. Здесь предполагалось, что коммуникационная среда располагает буферной памятью, исключающей простой процессоров из-за неодновременности завершения обработки областей, а сама обработка организована таким образом, что вычисления на очередной итерации могут быть начаты до завершения получения всех данных от сопряженных областей. Выполнение этих условий является отдельной сложной задачей для программиста. Кроме того, в данном случае мы не учитывали латентность при передаче данных, а также тот факт, что X не обязано делиться без остатка на величину xˆ .

Для преодоления указанных трудностей и более полного учета влияния всех факторов, которые не принимались во внимание в указанной упрощенной постановке, может использоваться технология итерационного планирования распределения ресурсов, описанная в работе [3]. В данном случае ее применение не вызовет дополнительных усложнений по сравнению с вариантом, описанным в указанной работе, поскольку задача выбора k однопараметрическая.

Если исходное изображение не квадратное, то описанный подход может быть применен вначале для разбиения квадратной части изображения со стороной квадрата, равной длине меньшей стороны. Если длина стороны оставшейся части не кратна выбранной величине X, то для декомпозиции остатка также может быть применена технология итерационного планирования распределения ресурсов кластера.

5. Благодарности

Работа выполнена при поддержке Министерства образования РФ, Администрации Самарской области и Американского фонда гражданских исследований и развития (CRDF Project SA-014-02) в рамках российско-американской программы «Фундаментальные исследования и высшее образование» (BRHE, ) и РФФИ (гранты № 01- 01-00097 №03-01-00109)

Литература

1.Методы компьютерной обработки изображений / Под ред. Сойфера В.А. М.: Физматлит, 2001.

235

2.Попов С.Б., Сойфер В.А., Тараканов А.А., Фурсов В.А. Кластерная технология формирования и параллельной фильтрации больших изображений // Компьютерная оптика. № 23, 2002. С. 75-78.

3.Фурсов В.А., Шустов В.А., Скуратов С.А. Технология итерационного планирования распределения ресурсов гетерогенного кластера. Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения».- Труды Всероссийской научной конференции г. Черноголовка , 30 октября–2 ноября 2000 г. С.43-46.

ПАРАЛЛЕЛЬНАЯ ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА С РАСПРЕДЕЛЕНИЕМ ВЫЧИСЛИТЕЛЬНОЙ НАГРУЗКИ

МЕЖДУ УЗЛАМИ КОМПЬЮТЕРНОЙ СЕТИ

Н.Н. Хохлов, Р.К. Кудерметов

Запорожский национальный технический университет [e-mail], [e-mail]

В последнее время для моделирования сложных задач все чаще применяются параллельные алгоритмы. Как правило, реализуются такие алгоритмы на параллельных суперкомпьютерах, таких как CRAY, HP, SUN и др. [7]. Также все большее распространение получают относительно недорогие параллельные системы на базе персональных компьютеров и основанные на сетевых интерфейсах передачи сообщений (MPI, PVM, MPICH и др.) [1,2], аналогов интерфейсов взаимодействия между процессорами суперкомпьютеров. На сегодняшний день имеется достаточное количество реализаций таких суперкомпьютеров, некоторые из них входят в число самых мощных, которые объединяют вычислительные ресурсы нескольких вычислительных машин, соединенных высокопроизводительными сетевыми интерфейсами, такими как Fast Ethernet, Gigabit Ethernet, SCI. Использование унифицированных средств взаимодействия между узлами вычислительного кластера способно обеспечить объединение в единую систему не только подобных вычислителей, но и компьютеров с различными операционными системами, и с различными архитектурами. Для таких суперкомпьютеров остается актуальной проблема оптимального распределения вычислительной нагрузки

236

между вычислителями параллельного кластера. Имеющиеся на сегодняшний день спецификации интерфейсов, объединяющих вычислители в единую систему, не имеют явных средств автоматической балансировки вычислительной нагрузки с учетом мощности каждого из вычислителей, что, в свою очередь, приводит к неэффективности распределения параллельной задачи и снижению производительности кластера в целом.

В докладе предлагается вариант организации параллельной вычислительной системы на базе компьютерной сети с попыткой минимизировать число пересылок между вычислителями кластера и учетом мощности каждого из вычислителей при распределении параллельной задачи. В качестве интерфейса передачи сообщений был выбран стандарт MPI в реализации университета Коимбра (Португалия) на базе платформы Microsoft Windows [2], как наиболее полный аналог данного стандарта платформы Unix (так как стандарт в сетевой реализации изначально появился на базе Unix-систем управляющих суперкомпьютерами).

Сетевая параллельная система состоит из пяти основных частей: терминала заданий, с которого осуществляется взаимодействие с сетевой параллельной системой и, в последствии, получение результатов работы; параллельной модели (задача, оформленная в виде DLL, динамически подключаемая к системе моделей); клиентвычислитель, загружающий в память параллельную модель и осуществляющий обмен данными с сервером параллельной системы; сервер сегмента вычислений, который распределяет параллельные задания между клиентами-вычислителями и осуществляет сбор конечных результатов; контроллер сетевой параллельной вычислительной системы, который осуществляет контроль над всеми серверами (сегментами) параллельной системы и при необходимости распределяет задания между сегментами. Клиент-вычислитель, сервер сегмента вычислений и контроллер сетевой параллельной вычислительной системы загружаются в момент загрузки операционной системы, а параллельные модели – динамически подгружаются по мере надобности.

Таким образом, задача состоит в определении соответствий между долей параллельного алгоритма и мощностью вычислительного узла, которому эта доля будет предназначена.

237

Проблеме оптимального распределения вычислительной нагрузки в параллельной системе посвящено большое количество научных работ [3, 4, 5], однако большинство из них имеют достаточно сложные алгоритмы, которые по своим вычислительным затратам сравнимы, а то и превосходят вычислительные затраты на решение самой параллельной задачи. Данный факт также нужно учитывать при построении модели оптимального распределения вычислительной нагрузки между узлами кластера.

При решении данной задачи необходимо иметь полную картину топологии данной вычислительной системы с учетом производительности каждого из входящих в кластер компьютеров. Для этого необходимо иметь информацию о производительности процессоров, объема оперативной памяти, объема свободного дискового пространства, удаленности от других узлов, скорости обмена данными между ними и др. Также следует учитывать и текущую загруженность данного узла системы.

Таким образом, введем в систему ряд критериев, описывающих текущую систему с точки зрения имеющихся вычислительных мощностей, при этом критерии можно представить в виде вектора состояния для каждого из узлов Ci = {cj}, i =1…N, j = 1…M, где N – количество узлов данной параллельной системы, а M – количество учитываемых параметров, описывающих каждый узел. Так же для оптимального распределения параллельной задачи между элементами системы необходимо иметь представление о вычислительной сложности данной задачи, в частности о сложности каждой «параллельной ветви» модели. В результате имеем еще один не мало важный вектор, описывающий реализацию текущей задачи Z = {zk}, где k – максимальное разветвление данной параллельной задачи. Решением поставленной задачи распределения будет определение, на каком из узлов вычислительной системы, и какая доля параллельной задачи будет выполняться.

В настоящее время ведется работа над средой параллельных вычислений на базе компьютерной сети с учетом приведенных требований. Разрабатываемая среда позволит обеспечить анализ архитектуры, анализ текущей модели по специально сформированному интерфейсу получения данных о ресурсоемкости каждой из параллельных ветвей, расчет оптимального распределения ветвей между элементами кластера, а также контроль активности

238

каждого из узлов параллельной системы для перераспределения частей задачи вышедшего из строя узла между оставшимися узлами. Сбор и обработку результатов осуществляет сервер сетевого кластера параллельной системы, в дальнейшем результаты передаются терминалу, с которого было получено задание. Также система имеет канал взаимодействия с другими такими же кластерами для объединения их в единую, более крупную параллельную систему. Такая модель параллельной вычислительной системы имеет многоуровневую архитектуру клиент-сервер. В которой взаимодействие между терминалом и сервером вычислительного кластера осуществляется на базе интерфейса сокетов (Sockets) протокола TCP/IP, что позволяет организовать прием заданий на выполнение в параллельной системе через Internet, а также с компьютеров работающих под управлением различными операционными системами. На данном этапе идет поиск и апробация оптимальных путей решения задачи оптимизации распределения параллельной задачи между вычислительными узлами сетевой параллельной системы, а также ведутся работы над оптимизацией процесса обмена служебной информацией между элементами кластера.

Литература

1.MPI: A Massage-Passing Interface Standard Esprit Project P6643 (PPPE), May 5, 1994, 227p.

2.Argonne National Lab MPICH.NT.1.2.2 http://www.pandora.uc.pt:80/ w32mpi.

3.Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. – М.: Радио и связь, 1983.

4.Кременецкий Г.Н., Гуменюк В.А. Применение нейронных сетей для распределения вычислительной нагрузки / Вiсник технологiчного унiверситету Подiлля. Хмельницкий, 2003. № 3. Т.1. С.102–105.

5.Жабин В.И. Динамическое распределение заданий в параллельных вычислительных системах. / Вiсник технологiчного унiверситету Подiлля. Хмельницкий, 2003. № 3. Т.1. С.119-121.

6.Корнеев В.В. Параллельные вычислительные системы. – М.:

Нолидж, 1999. 320 с.

239

7.Наиболее распространенные современные суперкомпьютеры

(http://www.parallel.ru/computers/computers.html).

Согласно описанному выше алгоритму при разделении дерева между 4 процессорами получим следующий результат (рис. 2).

	4	260
		30
	90		140
20	30		40
		40	50 20	50	2
20	10			10
10	10	20	30 30		40
		20			40
	3		1

Рис. 2.

Для улучшения балансировки главный корень дерева клик не фиксируется, а рассчитывается на основе специальных формул.

Произведенные расчеты и замеры показывают относительную эффективность предложенной схемы балансировки нагрузки, однако ожидать масштабируемости от параллельной версии для распределенной памяти алгоритма Junction Tree Inference Engine нельзя в силу ограничений, таких как коэффициент распараллеливания, и из-за ожидания активных сообщений. Поэтому дальнейшие исследования связаны с разбиением клик и, как следствие, увеличением обмена информации между процессорами с целью уменьшения взаимного ожидания между ними.

Литература

1.Cowell R., Dawid A., Lauritzen S., Spiegelhaulter D. Probabilistic networks and expert systems, Springer-Verlag, New York, 1999.

2.Pearl J. Probabilistic inference in intelligent systems, Morgan Kaufman, San Mateo, California, 1988.

240