НАУКА и ОБРАЗОВАНИЕ

УДК 519.6

А.П.Карпенко, В.Г.Федорук, Е.В.Федорук

МГТУ им. Н.Э. Баумана, 105005, Москва, 2-я Бауманская ул., д.5.

Введение

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

Непосредственным стимулом для данной работы явились задачи непрерывной многокритериальной оптимизации (МКО-задачи), которые возникают при оптимизации сложных технических систем и требуют использовать для своего решения высокопроизводительные ЭВМ с распределенной памятью, например, вычислительные кластеры. Подавляющее большинство методов решения МКО-задач сводят, в конечном счете, решение МКО-задачи к решению однокритериальной задачи глобальной условной оптимизации (ОКО-задачи), наиболее распространенные подходы к решению которой основаны на сочетании локальных детерминированных поисковых методов и методов случайного поиска [3]. Граф потока данных алгоритмов решения МКО-задач такими методами как раз может быть представлен в виде указанного выше двухуровневого дерева.

Основная идея метода балансировки загрузки состоит в распределении вычислений по процессорам таким образом, чтобы суммарная вычислительная и коммуникационная загрузки процессоров были примерно одинаковы. При этом не учитываются коммуникационные загрузки процессоров, обусловленные транзитными обменами и конфликты при обменах вследствие перегрузки коммуникационной сети [4]. Часто при балансировке загрузки коммуникационные расходы не учитываются вообще.

Различают статическую и динамическую балансировку загрузки. Статическая балансировка загрузки выполняется однажды, до начала вычислений. Обзор методов статической балансировки загрузки применительно к параллельному решению задач математической физики дан, например, в работе [5].

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

В работе рассматриваются следующие методы балансировки загрузки [1, 2]:

1)          статическая балансировка;

2)          динамическая централизованная балансировка методом равномерной декомпозиции узлов - равномерная балансировка;

3)          динамическая централизованная балансировка методом экспоненциальной декомпозиции узлов - экспоненциальная балансировка.

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

Исследование эффективности указанных методов балансировки выполняется путем имитационного моделирования на языке GPSS [7].

1.              Постановка задачи и ее информационная модель

Пусть - вектор параметров задачи, где - n-мерное арифметическое пространство.

Множество есть множество допустимых значений вектора X. Здесь «технологический» параллелепипед

,

где - заданные константы; множество

.

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

,

где - ограничивающая вектор-функция с непрерывными компонентами.

На множестве определена вектор-функция со значениями в пространстве . Ставится задача поиска значения некоторого функционала .

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

Шаг 1. Покрываем параллелепипед П некоторой сеткой с узлами .

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

Шаг 3. На основе вычисленных значений вектор функции находим приближенное значение функционала .

Такой схеме решения задачи соответствует информационная модель, представленная на Рис. 1.

Рис. 1. Граф потока данных задачи: – вычисление значения функционала ; 2  –вычисление значений функций , .

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

В качестве вычислительной системы рассматривается однородная многопроцессорная вычислительная система с распределенной памятью, состоящая из процессоров и host-процессора, имеющих следующие параметры:

·            – время выполнения одной арифметической операции с плавающей запятой;

·            - диаметр коммуникационной сети;

·            l – длина вещественного числа в байтах;

·            – латентность коммуникационной сети;

·            [с] – время передачи байта данных между двумя соседними процессорами системы без учета времени .

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

2.              Рассматриваемые методы балансировки

2.1. Статическая балансировка выполняется по следующей схеме.

Шаг 1. Host-процессор строит сетку и разбивает ее Z узлов на N множеств не более чем по узлов в каждой. Здесь и далее - символ ближайшего целого большего.

Шаг 2. Процессор принимает от host-процессора координаты узлов множества ; в каждом из узлов вычисляет значение функции и, если этот узел принадлежит множеству , - значение функции ; передает host-процессору результаты вычислений и заканчивает вычисления.

Шаг 3. Host-процессор на основе этих результатов находит приближенное решение задачи и заканчивает вычисления.

2.2. Динамическая равномерная балансировка.

Шаг 1. Host-процессор строит сетку и разбивает ее Z узлов на K множеств не более чем по узлов в каждой.

Шаг 2. Процессор , принимает от host-процессора координаты узлов первого из нераспределенных множеств , обрабатывает их аналогично шагу 2 статической балансировке и передает host-процессору результаты вычислений.

Шаг 3. Если исчерпаны не все множества , то host-процессор посылает, а процессор принимает координаты следующего нераспределенного множества узлов, которое обрабатывается процессором аналогично шагу 2 и т.д.

Шаг 4. Если исчерпаны все множества , то host-процессор посылает всем slave-процессорам сигнал завершения работы, находит приближенное решение задачи и завершает вычисления.

2.3. Динамическая экспоненциальная балансировка.

Шаг 1. Host-процессор строит сетку и полагает , .

Шаг 2. Если исчерпаны не все Zузлов, то host-процессор выделяет среди оставшихся узлов множество , содержащее узлов, и разбивает это множество на N подмножеств , не более чем по узлов в каждом; .

Шаг 3. Пока множество узлов не исчерпано, host-процессор передает, а процессор принимает от него координаты узлов первого из необработанных подмножеств , обрабатывает их аналогично шагу 2 статической балансировке и передает host-процессору результаты вычислений.

Шаг 4. Если множество узлов исчерпано, то host-процессор полагает k=k+1, и переходит к шагу 2.

Шаг 5. Если все Zузлов сетки исчерпаны, то host-процессор посылает всем slave-процессорам сигнал завершения работы, находит приближенное решение задачи и завершает вычисления.

3.              Имитационные модели

Статическая балансировка. Модель статической балансировки (см. Приложение 1) состоит из "последовательной" модели и "параллельной" модели. Используется один обслуживающий аппарат host, который моделирует работу host-процессора. Накопитель proc_posl моделирует работу процессора в "последовательной" модели, а накопитель proc_par- в "параллельной" модели. Время обработки узлов на процессорах задается функциями fnproc_posl, fnproc_par, соответственно. Транзакту, генерируемому оператором 9, ставится в соответствие задача, состоящая в обработке 1024 узлов расчетной сетки. В модели фиксируется время прохождения транзакта по "параллельной" модели и по "последовательной" модели. Отношение этих времен дает коэффициент ускорения, для которого строится гистограмма (таблица tabl_s). В "параллельной" модели транзакт-задача порождает N транзактов-копий (в примере N=64), которые соответствуют группе узлов, обрабатываемых на одном процессоре (оператор 10). Каждая группа состоит из z узлов (в примере z=16). Последовательная обработка этих узлов моделируется циклом proc2. Количество итераций в цикле определяется первым параметром модели (оператор 11).

Динамическая равномерная балансировка. Модель динамической равномерной балансировки (см. Приложение 2) отличается от модели статической балансировки тем, что в ней количество групп не совпадает с количеством процессоров. В примере количество групп равно 256, количество узлов в группе - 4, количество процессоров - 8.

Динамическая экспоненциальная балансировка. Модель экспоненциальной балансировки (см. Приложение 3) отличается от предыдущей модели тем, что в ней количество подгрупп узлов в группе определяется функцией fnwork. В примере количество групп - 5, количество узлов в группе - 64.

4.              Примеры результатов моделирования

С использованием GPSS-программ, рассмотренных в п. 3 и приведенных в Приложениях 1 -3, выполнено исследование эффективности статического, динамического равномерного и динамического экспоненциального методов балансировки при следующих значениях параметров:

·                 ;

·                 ;

·                 ;

·                 [с];

·                 [с];

·                 [с];

·                 .

Заметим, что примерно такими параметрами , обладает коммуникационная сеть, построенная по технологии SCI, в которой для обмена данными используется коммуникационная библиотека MPI [8]. Указанная зависимость соответствует коммуникационной сети с топологией типа квадратная «решетка».

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

7.1. Статическая балансировка. Результаты исследования в указанных выше условиях эффективности статической балансировки приведены в Табл. 1. Здесь и далее - оценка математического ожидания ускорения, - оценка среднего квадратичного отклонения (СКО) ускорения от его математического ожидания. Табл. 1 иллюстрируют Рис. 2, 3.

Табл. 1. Эффективность статической балансировки.

Рис. 2. Оценка математического ожидания ускорения при статической балансировке:

□ - ; - ; - .

Рис. 3. Оценка СКО при статической балансировке:

□ - ; - ; - .

7.2. Динамическая равномерная балансировка. Результаты исследования эффективности динамической равномерной балансировки приведены в Табл. 2, которую иллюстрируют Рис. 4, 5.

Табл. 2. Эффективность динамической равномерной балансировки.

Рис. 4. Оценка математического ожидания ускорения при динамической равномерной балансировке: □ - ; - ; - .

Рис. 5. Оценка СКО при динамической равномерной балансировке:

□ - ; - ; - .

7.3. Динамическая экспоненциальная балансировка. Результаты исследования эффективности динамической экспоненциальной балансировки приведены в Табл. 3, которую иллюстрируют Рис. 6, 7.

Табл. 3. Эффективность динамической экспоненциальной балансировки.

Рис. 6. Оценка математического ожидания ускорения при динамической экспоненциальной балансировке: □ - ; - ; - .

Рис. 7. Оценка СКО при динамической экспоненциальной балансировке:

□ - ; - ; - .

7.4. Обсуждение результатов. Приведенные результаты показывают, что при невысокой вычислительной сложности математическое ожидание ускорения существенно отличает от N. Как и следовало ожидать, с ростом вычислительной сложности из-за относительного снижения накладных расходов эффективность балансировки повышается. Во всех экспериментах эффективность динамической равномерной и динамической экспоненциальной балансировки существенно выше эффективности статической балансировки. При малой вычислительной сложности зависимость математического ожидания ускорения от количества процессоров имеет максимум, что объясняется ростом коммуникационных расходов с ростом количества процессоров (из-за роста диаметра коммуникационной сети). Положение указанного максимума с ростом вычислительной сложности, как и следовало ожидать, смещается вправо.

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

Заключение

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

Как отмечалось выше, работа является продолжение работ [1,2]. Однако в этих работах рассмотрена также динамическая децентрализованная балансировка диффузным методом с перераспределением загрузки по инициативе получателя - диффузная балансировка. Построить модель этой балансировки средствами GPSS не удалось. В развитии работы предполагается выполнить исследование эффективности диффузной балансировки средствами современных языков имитационного моделирования.

Литература

1.     Карпенко А.П., Федорук В.Г., Федорук Е.В.Исследование эффективности балансировки загрузки многопроцессорной системы при распараллеливании одного класса вычислительных задач //"Наука и образование: электронное научное издание. Инженерное образование", www.technomag.edu.ru (╧ Гос. регистрации 0420700025, ЭЛ ╧ ФС 77-305 69), август, 2007, ╧0420700025/0034.

2.     Карпенко А.П., Федорук В.Г. Балансировка загрузки многопроцессорной вычислительной системы при распараллеливании одного класса вычислительных задач // Труды Всероссийской научной конференции «Научный сервис в ИНТЕРНЕТ: многоядерный компьютерный мир», Издательство МГУ, 2007, с. 48 – 52.

3.     Карпенко А.П., Федорук В.Г. Обзор программных систем многокритериальной оптимизации. Отечественные системы //Информационные технологии, 2008, ╧1, с. 15-22.

4.     Карпенко А.П., Пупков К.А. Моделирование динамических систем на транспьютерных сетях -М.: Биоинформ, 1995.-73 с.

5.     Волков К.Н. Применение средств параллельного программирования для решения задач механики жидкостей и газа на многопроцессорных вычислительных системах // Вычислительные методы и программирование. - 2006, Т.7, с. 69 – 84.

6.     Gubenko G. Dynamic load Balancing for Distributed Memory Multiprocessors //Journal of parallel and distributed computing. – 1989. 7, pp. 279 -301.

7.     Шрайбер Т.Дж. Моделирование на GPSS. Пер с англ. -M.: "Машиностроение", 1980.

8.     Воеводин В.В., Воеводин Вл., В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2004.

Приложение 1. GPSS-программа для статической балансировки

* * * * * * * * * * * * * * * * * * * *

* N*z (1024=64*16) *

* Единица модельного времениmkc *

* Вычислительная сложность 1e7 *

* Время обработки 0 - 1e5 mks *

* * * * * * * * * * * * * * * * * * * *

* "Параллельная" модель *

* * * * * * * * * * * * * * * * * * * *

1 fnproc_parfunctionrn2,c2; время обработки в "параллельной" модели

2 0,0/1,100001

3 fnproc_poslfunctionrn3,c2; время обработки в "последов-ой" модели

4 0,0/1,100001

5 usvariablep4/p3; расчет коэффициента ускорения

6 tabl_s table v$us,42,0.25,60

7 proc_parstorage 64; число процессоров в "параллельной" модели N=64

8 proc_poslstorage 1; число процессоров в "последовательной" модели N=1

9 generate 1e8,100; транзакт-задача (1024 узла)

10 split 63; N=63+1 - количество групп

11assign 1,16;z=16 - количество узлов в группе

12 queueqhost1_par; очередь на host-процессоре

13 seize host

14 depart qhost1_par

15 advance 5,3; обработканаhost-процессоре

16 release host

17 queue qproc_par

18 enter proc_par; обработкапроцессором

19 depart qproc_par

20 proc2 advance fn$fnproc_par; циклдляобработкигруппы

21loop 1,proc2; число итераций определено в 1-ом параметре транзакта

22 leaveproc_par

23 queueqhost2_par; заключительная обработка на host-процессоре

24 seize host

25 depart qhost2_par

26 advance 5,3

27 releasehost

28 assemble 64; объединение транзактов, относящихся к одной задаче

29 assign 3,m1; фиксация времени прохождения транзакта по модели

* * * * * * * * * * * * * * * * * * * *

* "Последовательная" модель *

* * * * * * * * * * * * * * * * * * * *

31 mark 2

32 split1023;1024 узла (одна задача)

33 queue qhost1_posl

34 seize host

35 depart qhost1_posl

36 advance 5,3

37 release host

38 queue qproc_posl

39 enter proc_posl; обработкапроцессором

40 depart qproc_posl

41 advance fn$fnproc_posl

42 leave proc_posl

43 queue qhost2

44 seize host

45 depart qhost2

46 advance 5,3

47 releasehost

48 assemble1024

49 assign 4,mp2; фиксация времени прохождения транзакта по модели

50tabulatetabl_s; расчет коэффициента ускорения

51 terminate 1

Приложение 2. GPSS-программа для динамической равномерной балансировки

* * * * * * * * * * * * * * * * * * * *

* Z=K*z (1024=256*4) *

* Единица модельного времениmkc *

* Вычислительная сложность 1e7 *

* Время обработки 0 - 1e5mks *

* Число процессоров N=64 *

* ** * * * * * * * * * * * * * * * * * *

* "Параллельная" модель *

* * * * * * * * * * * * * * * * * * * *

1 fnproc_parfunctionrn2,c2; время обработки в "параллельной" модели

2 0,0/1,100001

3 fnproc_poslfunctionrn3,c2; время обработки в "последов-ой" модели

4 0,0/1,100001

5 usvariablep4/p3; расчет коэффициента ускорения

6 tabl_s table v$us,42,0.25,60

7 proc_parstorage 64;число процессоров в "параллельной" модели N=64

8 proc_poslstorage 1; число процессоров в "последовательной" модели N=1

9 generate 1e8,100; транзакт-задача (1024 узла)

10 split255; К=255+1 - количество групп

11assign 1,4; z=4 - количество узлов в группе

12 queueqhost1_par;очередь на host-процессоре

13 seize host

14 depart qhost1_par

15 advance 5,3; обработканаhost-процессоре

16 release host

17 queue qproc_par

18 enter proc_par; обработкапроцессором

19 depart qproc_par

20 proc2 advance fn$fnproc_par; циклдляобработкигруппы

21loop 1,proc2; число итераций определено в 1-ом параметре транзакта

22 leaveproc_par

23 queueqhost2_par; заключительная обработка на host-процессоре

24 seize host

25 depart qhost2_par

26 advance 5,3

27 releasehost

28 assemble256; объединение транзактов, относящихся к одной задаче

29 assign 3,m1; фиксация времени прохождения транзакта по модели

* * * * * * * * * * * * * * * * * * * *

* "последовательная" модель *

* * * * * * * * * * * * * * * * * * * *

31 mark 2

32 split1023; 1024 узла (одна задача)

33 queue qhost1_posl

34 seize host

35 depart qhost1_posl

36 advance 5,3

37 release host

38 queue qproc_posl

39 enter proc_posl; обработкапроцессором

40 depart qproc_posl

41 advance fn$fnproc_posl

42 leave proc_posl

43 queue qhost2

44 seize host

45 depart qhost2

46 advance 5,3

47 releasehost

48 assemble1024

49 assign 4,mp2 фиксация времени прохождения транзакта по модели

50tabulatetabl_s; расчет коэффициента ускорения

51 terminate 1

Приложение 3. GPSS-программа для динамической экспоненциальной балансировки

* * * * * * * * * * * * * * * * * * * * **

* Z=1024 (8*64 + 4*64 + 2*64 + 64 + 64) *

* Единица модельного времениmkc *

* Вычислительная сложность 1e7 *

* Время обработки 0 - 1e5mks *

* Число процессоров N=64 *

* * * * * * * * * * * * * * * * * * * * *

* "Параллельная" модель *

* * * * * * * * * * * * * * * * * * * * *

1 fnproc_parfunctionrn2,c2; время обработки в "параллельной" модели

2 0,0/1,100001

3 fnproc_poslfunctionrn3,c2; время обработки в "последов-ой" модели

4 0,0/1,100001

5 fnworkfunctionp5,d5

6 1,8/2,4/3,2/4,1/5,1

7 usvariablep4/p3; расчет коэффициента ускорения

8 tabl_stable v$us,42,0.25,60

9 proc_parstorage 64; число процессоров в "параллельной" модели N=64

10 proc_poslstorage 1;число процессоров в "последовательной" модели N=1

11generate 1e8,100; транзакт-задача (1024 узла)

12 split 4,,5; k=4+1 - количество групп

13assign 1,fn$fnwork; первый параметр - количество подгрупп в группе

14 split 63; z=63+1 - количество узлов в подгруппе

14 queueqhost1_par; очередь на host-процессоре

15 seize host

16 depart qhost1_par

17 advance 5,3; обработканаhost-процессоре

18 release host

19 queue qproc_par

20 enterproc_par; обработка процессором

21 departqproc_par

22 proc2 advancefn$fnproc_par; цикл для обработки группы

23loop 1,proc2; число итераций определено в 1-ом параметре транзакта

24 leaveproc_par

25 queueqhost2_par; заключительная обработка на host-процессоре

26 seize host

27 depart qhost2_par

28 advance 5,3

29 releasehost

30 assemble320; объединение транзактов, относящихся к одной задаче

31 assign 3,m1; фиксация времени прохождения транзакта по модели

* * * * * * * * * * * * * * * * * * * *

* "последовательная" модель *

* * * * * * * * * * * * * * * * * * * *

31 mark 2

32 split1023; 1024 узла (одна задача)

33 queue qhost1_posl

34 seize host

35 depart qhost1_posl

36 advance 5,3

37 release host

38 queue qproc_posl

39 enter proc_posl; обработкапроцессором

40 depart qproc_posl

41 advance fn$fnproc_posl

42 leave proc_posl

43 queue qhost2

44 seize host

45 depart qhost2

46 advance 5,3

47 release host

48 assemble 1024

49 assign 4,mp2; фиксация времени прохождения транзакта по модели

50tabulatetabl_s; расчет коэффициента ускорения

51 terminate 1