Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Многофункциональный балансер загрузки для решения одного класса вычислительных задач

# 7, июль 2008
DOI: 10.7463/0708.0096191

УДК 519.6

 

А.П.Карпенко, А.Н.Уторов, В.Г.Федорук

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

 

 

 

 

 

Введение

При оптимизации сложных технических систем возникают задачи непрерывной многокритериальной оптимизации (МКО-задачи), имеющие следующие особенности [1]:

·            высокая размерность вектора альтернатив X;

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

·            высокая размерность критериальной вектор-функции;

·            высокая сложность математических моделей оптимизируемых технических систем, приводящая к высокой вычислительной сложности частных критериев;

·            сложная топология частных критериев оптимальности (овражность, многоэкстремальность и пр.).

 

Указные особенности современных МКО-задач делают необходимым использование для их решения многопроцессорных вычислительных систем (МВС), в качестве которых в работе рассматриваются вычислительные кластеры.

Методы решения МКО-задач чрезвычайно разнообразны (что является, в конечном счете, следствием плохой формализуемости таких задач). По одной из распространенных классификаций выделяются следующие классы этих методов [2]:

·            методы зондирования;

·            априорные методы;

·            апостериорные методы;

·            адаптивные методы.

Методы всех этих классов, кроме первого, сводят, в конечном счете, решение МКО-задачи к решению однокритериальной задачи глобальной условной оптимизации (ОКО-задачи). Наиболее распространенные подходы к решению ОКО-задачи основаны на сочетании локальных детерминированных поисковых методов и методов случайного поиска [2].

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

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

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

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

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

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

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

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

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

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

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

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

4)          динамическая децентрализованная балансировка диффузным методом с перераспределением загрузки по инициативе получателя - диффузная балансировка.

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

 

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

Пусть - n-мерный вектор варьируемых параметров и , где - n-мерное арифметическое пространство. Вектор определен в непустом «технологическом» параллелепипеде

.

На вектор Xможет быть дополнительно наложено некоторое количество ограничений, формирующих множество

.

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

Положим, что - векторный критерий оптимальности, определенный на параллелепипеде П, со значениями в пространстве . Лицо, принимающее решения (ЛПР), стремится минимизировать каждый из частных критериев оптимальности .

Во введенных обозначениях рассматриваемая МКО-задача условно записывается в виде

, (1)

где - искомое решение этой задачи.

Тем или иным методом сведем решение задачи (1) к решению ОКО-задачи

, (2)

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

Чаще всего задачу глобальной условной оптимизации (2) сводят с помощью метода штрафных функций к задаче глобальной безусловной оптимизации

, (3)

где - функция, которая возрастает вблизи границ области допустимых значений и тем быстрее, чем больше значение параметра штрафной функции ; В качестве приближенного решения задачи (2) принимается решение вспомогательной задачи (3) при достаточно большом .

Схему приближенного решения задачи (2) комбинацией какого либо локального детерминированного поискового метода и метода случайного поиска можно представить в следующем виде:

·            покрываем параллелепипед П случайной сеткой с узлами ;

·            проверяем принадлежность узла , множеству ;

·            если , то, исходя из этой точки методом локального поиска решаем задачу (3) – находим точку ;

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

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

 

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

 

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

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

, . (4)

Задачи (4) решаются, вообще говоря, разными методами локальной оптимизации и на разных сетках, покрывающих параллелепипед П: при задача решается на сетке с узлами ,,…, ; . Такая схема решения очевидным образом сводится к последовательному применению рассмотренной выше схемы. Однако при этом теряется значительная часть параллелизма. Поэтому для решения задач (4) целесообразно использовать схему решения, которой соответствует граф потока данных в виде несколько более сложного по сравнению с дерева (см. Рис. 2).

 

 

Рис. 2. Граф потока данных ОКО-задач (4).

 

Объединим в графе вершины так, как показано на Рис. 2, и введем обозначения ,…, ,…,, где . В результате получим граф потока данных , представленный на Рис. 3, который в работе используется в качестве информационной модели задачи.

 

 

Рис. 3. Граф потока данных – информационная модель задачи.

 

 

2.              Схемы используемых методов балансировки

В качестве МВС рассматривается однородная вычислительная система, состоящая из процессоров и host-процессора.

2.1. Статическая балансировка

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

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

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

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

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

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

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

Шаг 4. Host-процессор находит приближенное решение задачи.

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

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

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

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

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

Шаг 5. Host-процессор находит приближенное решение задачи.

2.4 Диффузная балансировка

Шаг 1. Host-процессор строит сетки , и разбивает их узлы на N множеств не более чем по узлов в каждом.

Шаг 2. Процессор принимает от host-процессора координаты узлов множества .

Шаг 3. Процессор выполняет следующие действия. 1) Выполняет обработку распределенных ему узлов, и после завершения обработки передает host-процессору результаты обработки. 2) Посылает запрос нескольким ближайшим процессорам . 3) Получает в ответ от каждого их этих процессоров количество еще необработанных узлов. 4) Посылает запрос тому из указанных процессоров, который имеет наибольшее количество необработанных узлов. 5) Получает от этого процессора -ю часть его необработанных узлов и начинает их обработку .

Шаг 4. Если процессор еще не закончил обработку распределенных ему узлов и получил первый запрос от процессора , то он посылает ему в ответ количество еще необработанных узлов.

Шаг 5. Если процессор получил повторный запрос от процессора , то он посылает в ответ этому процессору -ю часть своих еще необработанных узлов (но не менее, чем узлов).

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

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

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

Шаг 9. Если процессор получил от host-процессора сигнал окончательного завершения работы, то он завершается.

Шаг 10. Host-процессор находит приближенное решение задачи.

 

3.              Состав и общая схема функционирования балансера

Балансер состоит из модулей статической, динамической равномерной, динамической экспоненциальной и динамической диффузной балансировки. Каждый из этих модулей поддерживает две группы функций: 1) функции, отвечающие за работу hostпроцессора; 2) функции, отвечающие за работу slaveпроцессора.

Как на host-процессоре, так и на каждом из slave-процессоров запускается по два процесса – пользовательский (вычислительный) процесс и управляющий процесс, реализующий функции балансера. Полагается, что host-пользовательский процесс реализует функции , , а slave-пользовательские процессы – функции , (см. Рис. 2). Host- и slave-пользовательские процессы средствами балансера смогут взаимодействовать только со «своими» управляющими процессами (см. Рис. 2). В первых трех модулях балансера, возможны только двунаправленные обмены данными между host- и slave-управляющими процессами, а в четвертом модуле – также и обмены между slave-управляющими процессами.

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

 

Рис. 4. Взаимодействие процессов в МВС, содержащей host-процессор и 3 подчиненных процессора: окружность – вычислительный процесс; квадрат – управляющий процесс.

 

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

·                 используемый метод балансировки;

·                 общее количество Zрасчетных сеток ;

·                 значения величин n, m, , K, , , ;

·                 максимально допустимое время обработки одного узла [с];

·                 значения l компонентов вспомогательного вектора параметров Y;

·                 общее количество узлов (ситуация , интерпретируется как сигнал завершения вычислений);

·                 для каждого из указанных узлов - номер iсоответствующей расчетной сетки , номер узла, n его координат.

Замечание. Пример использования вектора Y приведен в п. 13.

Host-балансер в соответствии с заданным методом балансировки рассчитывает для каждого из slave-процессоров количество узлов, которые должна обработать соответствующая slave-пользовательская программа. Затем host-балансер передает необходимые данные, включая компоненты вектора Y, каждому из slave-балансеров. Slave-балансеры получают от host-балансера эти данные и передает их «своим» slave-пользовательским программам (за исключением используемого метода балансировки).

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

·                 общее количество узлов, исходя из которых пользовательской программе удалось получить решение задачи;

·                 для каждого из таких узлов: номер расчетной сетки; номер узла; n компонентов вектора , соответствующего найденному решению; m компонентов этого решения; оценку вычислительной сложности полученного решения (которая может быть использована для оптимизации вычислительного процесса ).

Host-балансер передает host-пользовательской программе следующие данные:

·                 общее количество узлов, в которых slave-пользовательским программам удалось получить решение задачи;

·                 для каждого из таких узлов: номер расчетной сетки; номер узла; n компонентов вектора X, соответствующего найденному решению; m компонентов этого решения; оценку вычислительную сложность полученного решения.

Входные данные балансера объединены во входные файлы: 1) файл параметров балансировки; 2) входной файл. Выходные данные объединены в выходные файлы: 1) файл количества результирующих точек; 2) выходной файл; 3) файл «дефектных» узлов; 4) файл отчета; 5) файл ошибок задания.

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

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

 

4.              Входные файлы

4.1. Файл параметров балансировки. Данный файл является текстовым и содержит набор параметров в формате: <имя> = <значение> - см. Табл. 1, где означает некоторое натуральное число, b – некоторое вещественное число; c - строку. Параметры в файле могут быть расположены в произвольном порядке. Любая строка в файле, которую не удается интерпретировать, как описание параметра, считается комментарием и игнорируется.

 

 

Таблица 1. Структура файла параметров балансировки.

Имя

Значение

Описание

Method

stat

Статическая балансировка

dyn

Динамическая равномерная

exp

Динамическая экспоненциальная

dif

Динамическая диффузная

Z

a

Количество расчетных сеток

Общее количество узлов в расчетных сетках

n

Размерность вектора

m

Размерность вектора

l

Размерность вектора Y

Param

См. ниже

Параметры метода балансировки

Максимально допустимое время обработки одного узла [с]

Y

b

Компоненты вектора Y

Lib

c

Путь к программе пользователя

file_in

c

Имя входного файла

file_count

c

Имя файла с количеством результирующих узлов

file_out

c

Имя выходного файла

 

Параметр Param в Табл. 1 для разных методов балансировки имеет различный смысл (см. Табл. 2).

 

Таблица 2. Значения параметра Paramв Табл. 1.

Метод

Параметр

Значение

stat

-

-

dyn

exp

dif

dif

 

4.2. Входной файл. Файл содержит следующих наборов: номер расчетной сетки ; номер узла; nкоординат узла.

 

 

5.              Выходные файлы

5.1. Файл количества результирующих точек. Файл является текстовым и содержит только количество результирующих точек.

5.2. Выходной файл. Файл имеет бинарный формат и содержит множество следующих наборов: номер расчетной сетки ; номер узла , исходя из которого получена результирующая точка ; nкоординат узла ; mкоординат вектора .

5.3. Файла «дефектных» узлов. Файл является бинарным и имеет формат, идентичный формату входного файла. Файл содержит информацию об узлах, исходя из которых по той или иной причине не удалось решить соответствующую ОКО-задачу.

5.4. Файла отчета. Файл является текстовым и содержит набор пар «атрибут-значение», которые сгруппированы по секциям.

Файл содержит одну секцию, соответствующую host-процессору, со следующими атрибутами:

·            N - количество процессоров, используемых для решения задачи;

·            (Totaldotscount) - общее количество исходных узлов;

·            (FailDxdotscount) - общее количество узлов, лежащих вне области допустимых значений ;

·            (Failcalculateddotscount) - общее количество «дефектных» узлов, включая количество узлов ;

·            (Totaltime) - время решения задачи (без учета времени на запуск и остановку системы MPI) [с].

Формат секции host-процессора имеет вид

HOST:<набор пар атрибут-значение>

Файл отчета содержит также по одной секции для каждого из slave-процессоров. Секция, соответствующая slave-процессору с номером i, имеет следующие атрибуты:

·            (Meancalculationtime) - среднее время обработки одного узла [с];

·            (Totaldotscount) - количество узлов, переданных данному slave-процессору;

·            (FailDxdotscount) - количество узлов вне области ;

·            (Failcalculateddotscount) - количество «дефектных» узлов, включая количество узлов .

Формат секции slave-процессора - вид

PROC:<порядковый номер> <набор пар атрибут-значение>

где порядковый номер определяет номер slave-процессора (нумерация ведется, начиная с единицы).

 

Пример 1. Файл отчета.

HOST:

Processors count=4

Total time=7.3

Total dots count=36

Fail Dx dots count=0

Fail calculated dots count=0

PROC:1

Total dots count=12

Fail Dx dots count=0

Fail calculated dots count=0

Mean calculation time=0.41

PROC:2

Total dots count=12

Fail Dx dots count=0

Fail calculated dots count=0

Mean calculation time=0.37

PROC:3

Total dots count=12

Fail Dx dots count=0

Fail calculated dots count=0

Meancalculationtime=0.56

 

Пример 1 показывает следующее: вычисления проводились на 3 slave-процессорах; было успешно обработано 36 узлов; время вычислений составило 7.3 сек. (без учета времени старта и останова библиотеки MPI); каждый из slave-процессоров обработал по 12 узлов; среднее время обработки одного узла на процессорах 1, 2, 3 составило 0.41, 0.37 и 0.56, сек., соответственно.

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

5.5. Файл ошибок задания. Файл является текстовым. Каждая запись фала состоит из маски ошибки и развернутого строковое описание ошибки. Маска ошибки предназначена для автоматической обработки ошибок и имеет формат

<маска>:ERROR

где <маска> - битовая маска, «0» в которой означает, что параметр задан верно, а «1» - неверно.

 

Пример 2. Файл ошибок задания.

0000001000000000:ERROR

The parameter 'user_program' is not found

 

6.              Модуль статической балансировки

6.1. Процедура инициализации. Host-балансер запускается на процессоре с рангом 0, slave-балансеры – на остальных доступных процессорах. Прежде всего, host-балансер считывает файл задания (см. п. 10) и проверяет его на корректность. При обнаружении ошибки или ошибок, host-балансер выводит соответствующие сообщение и завершает свою работу.

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

6.2. Схема функционирования host-балансера.

Шаг 1. Выполнить процедуру инициализации.

Шаг 2. Вычислить для каждого из slave-процессоров количество подлежащих обработке узлов.

Шаг 3. Для каждого из slave-процессоров, начиная с первого, выполнить следующие действия. 1) Выбрать требуемые узлы из файла задания. 2) Переслать данные slave-процессору. 3) Зарегистрировать отложенный прием заголовка сообщения от slave-процессора.

Шаг 4. Пока не приняты результаты обработки всех узлов, выполнять следующие действия.

·                 Ожидать прием заголовка сообщения от slave-процессора.

·                 Если заголовок сообщения принят, то

- извлечь из него размер блока соответствующих данных,

- выполнить синхронный прием блока данных,

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

- записать все полученные значения компонентов векторов , в соответствующий файл,

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

·                 Если не все узлы обработаны, но все slave-процессоры закончили работу, то сгенерировать исключительную ситуацию.

Шаг 5. Отослать всем slave-процессорам сообщения об окончании работы.

Шаг 6. Обработать накопленную служебную информацию.

Шаг 7. Сформировать файла отчета и сохранить его.

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

6.3. Схема функционирования slave-балансера.

Шаг 1. Выполнить процедуру инициализации.

Шаг 2. Пока не принят сигнал окончания работы, выполнять следующие действия.

·            Ожидать приема заголовка сообщения от host-процессора.

·            Определить тип принятого сообщения.

·            Если принят заголовок сообщения с исходными данными, то

- извлечь из этого заголовка размер принимаемого блока данных,

- принять блок исходных данных,

- извлечь из блока данных координаты подлежащих обработке узлов,

- последовательно обработать эти узлы (см. ниже),

- после завершения обработки всех узлов, отправить host-процессору результаты обработки, а также служебную информацию.

·            Если принят заголовок сообщения о завершении работы, то перейти к шагу 3.

Шаг 3. Выполнить процедуру деинициализации.

6.4. Схема обработки узлов slave-балансером.

Шаг 1. Пока обработаны не все узлы, выполнять следующие действия.

·            Запустить slave-программу пользователя как дочерний процесс.

·            Открыть неименованный канал для двунаправленного обмена информацией с программой пользователя через стандартный поток ввода/вывода.

·            Запустить поток обмена информацией с программой пользователя.

·            Если за отведенное время программа пользователя не завершила обработку распределенного ей узла, то

- послать этой программе сигнал безусловного завершения SIGKIL (ситуация интерпретируется как «зацикливание» программы пользователя),

- отменить поток обмена информацией с программой пользователя,

- поместить необработанный узел в набор «дефектных» узлов,

- перейти к началу данного пункта (перезапустить программу пользователя).

·            Если обработка всех узлов завершена, то перейти к шагу 2.

Шаг 2. Определить среднее время обработки одного узла.

 

 

7.              Модуль равномерной динамической балансировки

Процедура инициализации модуля равномерной динамической балансировки аналогична такой же процедуре в модуле статической балансировки.

7.1. Схема функционирования host-балансера.

Шаг 1. Выполнить процедуру инициализации.

Шаг 2. Вычислить для каждого из slave-процессоров количество подлежащих обработке узлов.

Шаг 3. Для каждого из slave-процессоров, начиная с первого, выполнить следующие действия: 1) Выбрать требуемые узлы из файла задания (см. п. 10). 2) Переслать данные slave-процессору. 3) Зарегистрировать отложенный прием заголовка сообщения от slave-процессора.

Шаг 4. Пока не приняты результаты обработки всех узлов, выполнять следующие действия.

·                 Ожидать прием заголовка сообщения от slave-процессора.

·                 Если заголовок сообщения принят, то

- извлечь из него размер блока соответствующих данных,

- выполнить синхронный прием блока данных,

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

- записать все полученные значения компонентов векторов , в соответствующий файл,

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

- вычислить очередное количество узлов, которые должны быть обработаны данным slave-процессором,

- если это количество точек превышает ноль, выполнить действия шага 3.

Шаг 5. Отослать всем slave-процессорам сообщение об окончании работы.

Шаг 6. Обработать накопленную служебную информацию.

Шаг 7. Сформировать файла отчета и сохранить его.

7.2. Схема функционирования slave-балансера. Схема полностью совпадает с аналогичной схемой для модуля статической балансировки.

 

8.              Модуль экспоненциальной динамической балансировки

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

Схема функционирования host-балансера полностью совпадает с аналогичной схемой для модуля динамической равномерной балансировки.

Схема функционирования slave-балансера полностью совпадает с аналогичной схемой для модуля статической балансировки.

 

 

9.              Модуль диффузной балансировки

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

9.1. Схема функционирования host-балансера.

Шаг 1. Выполнить процедуру инициализации.

Шаг 2. Вычислить для каждого из slave-процессоров количество подлежащих обработке узлов.

Шаг 3. Для каждого из slave-процессоров, начиная с первого, выполнить следующие действия. 1) Выбрать требуемые узлы из файла задания (см. п. 10). 2) Переслать данные slave-процессору. 3) зарегистрировать отложенный прием заголовка сообщения от slave-процессора.

Шаг 4. Пока не приняты результаты обработки всех узлов, выполнять следующие действия:

·                 Ожидать прием заголовка сообщения от slave-процессора.

·                 Если заголовок сообщения принят, то

- извлечь из него размер блока соответствующих данных,

- выполнить синхронный прием блока данных,

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

- записать все полученные значения компонентов векторов , в соответствующий файл,

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

Шаг 5. Отослать всем slave-процессорам сообщение предварительного окончания работы.

Шаг 6. Ожидать прием сообщения от каждого из slave-процессоров, подтверждающего готовность к завершению работы.

Шаг 7. Отослать всем slave-процессорам сообщения об окончании работы.

Шаг 8. Обработать накопленную служебную информацию.

Шаг 9. Сформировать файла отчета и сохранить его.

9.2. Схема функционирования slave-балансера.

Шаг 1. Выполнить процедуру инициализации.

Шаг 2. Ожидать прием заголовка сообщения от host-процессора.

Шаг 3. Определить тип принятого сообщения.

Шаг 4. Если принят заголовок сообщения с исходными данными, то выполнить следующие действия. 1)  Извлечь из этого заголовка размер принимаемого блока данных. 2) Принять блок исходных данных. 3) Извлечь из блока данных координаты подлежащих обработке узлов.

Шаг 5. Запустить поток обмена сообщениями с другими slave-процессорами.

Шаг 6. Пока не принят сигнал предварительного окончания работы, выполнять следующие действия. 1) Последовательно обработать все узлы, распределенные данному slave-балансеру (см. ниже). 2) После завершения обработки всех узлов, отправить host-процессору результаты обработки, а также служебную информацию.

Шаг 7. Ожидать сигнал продолжения вычислений.

Шаг 8. Ожидать завершения потока обмена сообщениями с host-балансером и другими slave-балансерами.

Шаг 9. Выполнить процедуру деинициализации.

9.3. Схема обмена сообщениями с host-балансером и другими slave-балансерами

Шаг 1. Регистрация отложенного приема заголовков сообщений от host- и slave-балансеров.

Шаг 2. Пока не принято сообщение об окончании работы, выполнять следующие действия.

·            Проверить внутренние буферы MPI на наличие заголовка сообщения/

·            Если заголовок принят, то определить тип сообщения и

-если это - сообщение о завершении работы, то перейти к шагу 3,

- если это - сообщение о предварительном завершении работы, то прекратить рассылку запросов другим процессорам и отправить host-балансеру сообщение с подтверждением готовности к завершению работы,

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

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

- если это сообщение есть запрос на пересылку узлов соседнему slave-балансеру, то переслать необходимые данные этому балансеру,

- если это - сообщение, содержащее координаты дополнительных узлов, то принять координаты этих узлов.

·            Если обработка ранее распределенных данному slave-балансеру узлов завершена, результаты обработки переданы host-балансеру, а также получены ответы от slave-балансеров на все ранее отправленные запросы, то выполнить повторную отправку запросов соседним slave-балансерам о количестве доступных узлов.

Шаг 3. Освобождение всех выделенных ресурсов, включая буферы MPI.

 

Замечание. В рассматриваемой реализации балансера сначала соседними slave-процессорами считаются процессоры с рангом ±1 относительно текущего ранга данного slave-процессора. Если на запрос о количестве доступных узлов все соседние процессоры дали ответ 0, то в качестве соседнего выбирается slave-процессор со случайным рангом. В следующей реализации балансера в качестве соседних процессоров планируется использовать сначала процессоры с рангами , затем и т.д.

 

10.          Программа запуска балансера

Запуск балансера выполняется по следующей схеме: 1) загрузка файла конфигурации кластера; 2) загрузка файла текущего использования кластера; 3) анализ файла задания на корректность входных данных; 4) если данные не корректны, то пользователю выдается код ошибки и формируется файл ошибок задания; 5) формирование команд запуска балансера; 6) последовательный запуск сформированных команд на исполнение.

10.1. Файл конфигурации кластера. Файл конфигурации кластера является текстовым файлом с набором пар <ключ>=<значение>.Здесь <ключ> представляет собой строку символов (возможно с пробелами). Пробелы в начале строки и перед символом « игнорируются и не входят в имя ключа. Значение – это строка символов (возможно с пробелами). Пробелы после символа « и в конце строки игнорируются и не входят в значение ключа.

Файл конфигурации может содержать пустые строки и комментарии. Комментарием считается строка, начинающаяся с символа # и заканчивающаяся символом перевода строки. Комментарии программой не анализируются.

Группы параметров разбиваются на секции RUN, METHOD, NODES, признаком которых является символ «:».

Секция RUN содержит макрокоманды, которые должны быть запущены на выполнение программой запуска. Каждая строка может содержать только одну макрокоманду.

Макрокоманда может иметь один или несколько макропараметров, каждый из которых заключается в фигурные скобки. Определены макропараметры {METHOD}, {N}, {NODES}, {TASK}. Макропараметры заменяются соответствующими значениями в момент формирования команды на исполнение. Макропараметр {METHOD} заменяется командой запуска специализированного балансера, которая определена в секции METHOD. Макропараметр {N} заменяется количеством процессоров, на которых должна исполняться запускаемая программа. Макропараметр {NODES} заменяется именами узлов кластера, на которых должна исполняться запускаемая программа. После названия узла в этом случае через пробел указывается число процессоров, используемых в данном узле. Макропараметр {TASK} заменяется именем файла-задания.

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

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

<имя узла>:<количество процессоров>

Имя узла не должно содержать пробелов, символов табуляции и двоеточия. Количество процессоров должно быть целым положительным числом.

 

 

Пример 3. Файл конфигурации кластера.

RUN:

mpimon {METHOD} -- {NODES}

#mpiexec -n{N}{METHOD} # for MPI 2.0

METHOD:

stat=./node_balancer_stat {TASK}

dyn=./node_balancer_dyn {TASK}

exp=./node_balancer_exp {TASK}

dif=./node_balancer_dif {TASK}

NODES:

node-11:2

node-12:2

node-13:2

node-14:2

node-22:2

node-23:2

node-31:2

node-32:2

node-34:2

 

Пример 3 вводит описания следующих сущностей: вычислительная система, состоящая из 9 двух процессорных узлов с именами node-11, node-12, node-13, node-14, node-22, node-23, node-31, node-32, node-34; балансер загрузки, реализующий 4 метода балансировки (stat, dyn, exp, dif); программа балансировки, вызываемая в контексте библиотеки MPI 1.1.

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

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

а) некоторые задачи могут быть отторгнуты из-за ложной загрузки системы;

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

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

Заголовок блока представляет собой строку данных и имеет следующий формат

ID=<ID>:<N>:<TASK_NAME>

Здесь атрибут<ID> - идентификатор выполняемой задачи (целое число). Для новой задачи назначается номер на единицу больший, чем у задачи с максимальным идентификатором. Атрибут<N> - количество процессоров, используемых для решения данной задачи (целое число). Атрибут<TASK_NAME> - имя задачи, являющееся необязательным атрибутом и предназначенное для мониторинга выполняемых задач.

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

Файл текущего использования кластера может содержать комментарии.

 

Пример 4. Файл текущего использования кластера.

ID=1:4:some_task

node-1

node-2

 

ID=3:5:

node-3

node-4

node-5

 

Пример 4 показывает, что в данный момент выполняются две задачи: первая имеет имя some_task, использует 4 процессора и выполняется на узлах node-1и node-2, вторая – использует 5 процессоров и выполняется на узлах node-3, node-4, node-5.

10.3. Файл задания. Файл задания также является текстовым файлом с набором пар «ключ-значение». Каждая строка файла должна содержать только одну такую пару и иметь не более 256 символов. Формат пары «ключ-значение» совпадает с форматом файла конфигурации. Файл задание может иметь комментарии, аналогичные комментариям в файле конфигурации.

Атрибуты файла задания описаны в Табл. 3, где обозначает натуральное число, - вещественное число, c– строку, d – положительное вещественное число.

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

 

Таблица 3. Атрибуты файла-задания.

Атрибут

Обязательный

параметр

Значение

Описание

Z

Да

Количество расчетных сеток

(Total dots count)

Нет

Общее количество узлов

n

Да

Размерность вектора

m

Да

Размерность вектора

l

Да

Размерность вектора Y

(Cfmax)

Нет

Максимально допустимая вычислительная сложность одного узла расчетной сетки

N

Да

Количество процессоров

K

Нет

Параметр динамической равномерной балансировки

Нет

Параметр динамической экспоненциальной балансировки

Нет

Параметр динамической диффузной балансировки

Нет

Параметр динамической диффузной балансировки

Y

Нет

b

Компоненты вектора вспомогательных параметров Y

user_program

Да

с

Команда запуска расчетной программы пользователя *)

file_dots_in

Да

c

Имя входного файла (см. п. 4)

file_dots_succ

Да

c

Имя выходного файла (см. п. 4)

file_dots_fail

Да

c

Имя выходного файла отбракованных узлов (см. п. 4)

file_report

Да

c

Имя файла отчета (см. п. 4)

balance_method

Да

c

Имя метода балансировки

Name

Нет

c

Имя задачи

 

*) Синтаксис команды user_program соответствует синтаксису команд в командной оболочке bash. Команда содержит полное или локальное имя программы пользователя и, возможно, передаваемые программе аргументы.

 

Входной файл должен существовать; размер его должен быть кратным размерности вектора .

Допустимые значения атрибута balance_method определяются в файле конфигурации (секция METHOD).

Синтаксис команды запуска расчетной программы пользователя соответствует синтаксису команд в командной оболочке bash. Команда содержит полное или локальное имя программы пользователя и, возможно, передаваемые программе аргументы, указанные через пробел после имени программы.

 

 

Пример 5. Файл задания.

Z=1

Total dots count=10

n=3

m=3

l=0

N=4

Cfmax=0 #no time limit

#user’s program with arguments

user_program=./user ./test.so func_job

#input files

file_dots_in=in.dat

#output files

file_dots_succ=succ.dat

file_dots_fail=fail.dat

file_report=report.txt

#

balance_method=stat

 

Пример 5 описывает следующее задание для балансера: используется одна расчетная сетка; количество узлов в сетке равно 10; каждый узел имеет 3 координаты; вектор-функция имеет размерность 3; вспомогательные параметры (вектор Y) отсутствуют; время обработки одного узла не ограничивается; для вычисления значений используется функция func_job из библиотеки ./test.so; координаты подлежащих обработке узлов находятся в файле in.dat; результаты расчета должны сохраняться в файлах succ.dat и fail.dat. для успешно обработанных и «дефектных» точек соответственно; отчет должен сохраняться в файле report.txt; для балансировки загрузки должен использоваться метод stat (статическая балансировка).

 

11.          Организация пользовательской программы

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

1.          Прием slave-программой пользователя от slave-программы балансера следующих данных для инициализации взаимодействия: 1) размерность nвектора параметров X(4 байта); 2) размерность mвектор функции Ф(X) (4 байта); 3) размерность вектора вспомогательных переменных Y(4 байта); 3) количество подлежащих обработке узлов (4 байта).

2.          Прием slave-программой пользователя от slave-программы балансера l компонентов вектора Y(по 8 байтов каждая).

3.          Для каждого необработанного узла прием slave-программой пользователя от slave-программы балансера следующих данных: 1) флаг Tготовности к передаче координат узла (1 байт); 2) номер расчетной сетки (4 байта); 3) номера jузла; 4) значения первой координаты узла (8 байтов), значения второй координаты узла (8 байтов) и т.д. до n-ой координаты этого узла.

4.          Для каждого обработанного узла передача slave-программой пользователя slave-программе балансера следующих данных: 1) флаг Rготовности итогов расчета (1 байт); 2) номер расчетной сетки (4 байта); 3) номер kузла (4 байта); 4) значения первой координаты точки (8 байтов), значения второй координаты точки (8 байтов) и т.д. до n-ой координаты этой точки; 5) значения первой компоненты вектора Ф() (8 байтов), значения второй компоненты вектора Ф() (8 байтов) и т.д. до m-ой компоненты этого вектора.

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

Все биты флага R, кроме, возможно, 0-го и 1-го должны быть равны нулю. Если 0-ой бит этого байта установлен в единицу, то обработанный узел не принадлежит области допустимых значений . Если 1-й бит установлен в единицу, то получить значения вектор функции Ф(), соответствующие узлу этому узлу, по некоторой причине не удалось (причина не уточняется)

 

12.          Тестирование и оценка эффективности балансера

Тестирование балансера и оценка его эффективности выполнены на вычислительном кластере МГТУ им. Н.Э.Баумана, который состоит из 12 двухпроцессорный узлов на базе микропроцессора Pentium III 800 Мгц, объединенных коммуникационной сетью в двумерный тор. Требуемая вычислительная сложность вектор-функции моделировалась путем выполнения сложений и умножений вещественных чисел. Величина полагалась случайной величиной, равномерно распределенная в интервале (математическое ожидание такой величины равно, очевидно, ).Рассматривалась однарасчетная сетка (). Было выполнено два эксперимента.

12.1. Эксперимент 1. Количество узлов расчетной сетки равно 36 (). В качестве параметров балансировки используются следующие величины: (каждое из подмножеств (см. п. 3.2) содержит по одному узлу расчетной сетки), , , . Рассматривается три варианта вычислительной сложности : ; ; .

Результаты эксперимента представлены в Табл. 4 – 6 и на иллюстрирующих их Рис. 4 - 6, соответственно. Всюду - количество процессоров, stat– статическая балансировка, dyn– динамическая равномерная балансировка, exp – динамическая экспоненциальная балансировка, dif – диффузная балансировка.

 

Таблица 4. Ускорение при .

Метод балансировки

stat

dyn

exp

dif

2

0.987

0.985

0.990

0.800

3

-

1.575

1.558

-

4

1.739

1.996

1.963

1.472

5

-

2.251

2.069

-

6

2.022

2.251

2.319

1.726

7

-

2.547

2.298

-

8

2.327

2.550

2.707

1.836

9

-

2.718

2.675

-

10

2.316

2.726

2.770

1.824

11

-

2.640

2.370

-

12

2.436

2.640

2.416

1.806

 

Рис. 4. Ускорение, как функция числа процессоров: .

 

Таблица 5. Ускорение при .

Метод балансировки

stat

dyn

exp

dif

2

0.942

0.990

0.993

0.774

3

-

1.734

1.684

-

4

1.982

2.324

2.289

1.564

5

-

2.752

2.566

-

6

2.439

3.059

2.963

2.025

7

-

3.341

3.087

-

8

3.095

3.316

3.356

1.985

9

-

3.804

3.680

-

10

3.138

3.886

3.776

2.329

11

-

3.684

3.366

-

12

3.359

3.804

3.286

2.641

 

Рис. 5. Ускорение, как функция числа процессоров: .

 

 

Таблица 6. Ускорение при .

Метод балансировки

stat

dyn

exp

dif

2

0.995

0.994

0.995

0.779

4

2.144

2.568

2.533

1.692

6

2.766

3.632

3.485

2.313

8

3.834

4.493

4.417

2.656

9

-

4.960

-

-

10

3.906

5.147

5.120

2.589

11

-

5.201

4.311

-

12

4.510

5.438

4.487

3.223

 

12.2. Эксперимент 2. Количество узлов расчетной сетки равно 3000 (); параметры балансировки: (каждое из подмножеств (см. п. 3.2) содержит по 100 узлов), , , ; варианты вычислительной сложности : ; ; .

Результаты эксперимента представлены в Табл. 7 - 9 и на иллюстрирующих эти таблицы Рис. 7 - 9, соответственно.

 

Рис. 6. Ускорение, как функция числа процессоров:.

 

 

Таблица 7. Ускорение при .

N

Метод балансировки

stat

dyn

exp

dif

2

-

0.986

0.990

0.970

3

1.611

-

-

-

4

-

1.952

1.960

1.810

5

2.216

-

-

-

8

-

2.491

2.572

2.027

9

2.610

-

-

-

Рис. 7. Ускорение, как функция числа процессоров: .

 

Таблица 8. Ускорение при .

N

Метод балансировки

stat

dyn

exp

dif

2

-

0,996

0,996

0,991

3

1,872

-

-

-

4

-

2,642

2,634

2,570

5

3,332

-

-

-

8

-

4,062

4,946

4,325

9

5,258

-

-

-

 

Рис. 8. Ускорение, как функция числа процессоров: .

 

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

1.               Использование в качестве параметра балансировки (см. п. 2.4) достаточно большой величины (10). Если вычислительные сложности оставшихся необработанными узлов достаточно велики, то это обстоятельство может привести к значительно дисбалансу загрузки процессоров.

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

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

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

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

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

 

13. Пример использования балансера

Рассмотрим задачу о вертикальном подъеме ракеты-зонда [10]. Движение ракеты описывается системой нормированных обыкновенных дифференциальных уравнений

 

(4)

Здесь - масса ракеты, - высота подъема ракеты, - ее вертикальная скорость, V – постоянная, характеризующая величину реактивной тяги двигателя ракеты, , , - постоянные, связанные с силой тяготения, аэродинамическим сопротивлением и убыванием плотности воздуха с высотой, соответственно. Управление определяет режим расхода горючего. Полагается, что , , где множество допустимых управлений ; - известная константа. В качестве начальных значений переменных состояния рассматриваются величины , , . Задача решается при следующих значениях параметров: ; ; ; ; ; .

В постановке [10] задача состоит в определении управления , обеспечивающего максимум критерия оптимальности при условии - задача подъема ракеты за фиксированное время на максимальную высоту при заданном запасе горючего.

Рассмотрим двухкритериальную модификацию этой задачи: нейти управления , которое максимизирует критерий оптимальности и критерий оптимальности . Т.е. рассмотрим задачу подъема ракеты-зонда за фиксированное время на максимальную высоту при максимальном запасе горючего.

Используем для решения поставленной двухкритериальной задачи оптимального управления метод сведения этой задачи к задаче нелинейного программирования. Хорошо известно, что этот метод обладает серьезными недостатками [10]. Однако для наших целей это обстоятельство не существенно.

Покроем интервал сеткой и аппроксимируем на интервале управление кусочно-постоянной функций со следующими значениями: , ; , ; … , .

Введем в рассмотрение n-мерный вектор . Множество допустимых управлений трансформируется при этом во множество , представляющее собой параллелепипед в пространстве .

Таким образом, МКО-задача в данном случае условно записывается в виде

, (5)

где - векторный критерий оптимальности (т.е. ), - искомое приближенное решение задачи.

С помощью аддитивной скалярной свертки сведем задачу (5) к ОКО-задаче

. (6)

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

, (7)

где в качестве штрафной функции используем функцию

.

Здесь

.

Для решения задачи (7) используем комбинацию детерминированного метода локального поиска Нелдера-Мида и метода случайного поиска. Размерность вектора Uположим равной 100 (n=100); весовые множители в аддитивной свертке - l1=0.8, l2=0.2. В случайной сетке, покрывающей параллелепипед , возьмем узлов. Параметры метода Нелдера-Мида положим равными , , . Начальную длину ребра симплекса примем равной (четверть от максимально допустимого значения управления); требуемую точность решения - .

Для случая использования метода динамической равномерной балансировки файл задания имеет представленный ниже вид. Использован вычислительный кластер, содержащий 8 процессоров. Вектор вспомогательных переменных Y использован для передачи параметров , , метода Нелдера-Мида, а также требуемой точности решения p.

 

Пример 6. Файл задания

#dots

n = 100

m= 2

Z = 1000

Cfmax = 0

#user program with arguments

user_program = ./user ./.so func_job

Y = 0.5;0.5;3;0.01

#input files

file_dots_in = in.dat

#output files

file_dots_succ = succ.dat

file_dots_fail = fail.dat

file_report = report.txt

#balance

balance_method = dyn

K = 1

#CPUcount

N = 8

 

Результат решения задачи представлен на Рис. 9. Рисунок показывает, что найденное решение близко к точному решению , полученному в книге [10] для однокритериальной задачи (что объясняется малым весом критерия оптимальности ). Время решения задачи на одном процессоре составило 16 ч 35 [мин], на 8 процессорах – 3 ч 20 [мин]. Таким образом, на 8 процессорах получено ускорение, равное примерно 5.

 

Рис. 9. Точное решение и найденное приближенное решение .

 

Заключение.

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

Тестирование балансера и оценка его эффективности выполнены на 12-ти процессорном вычислительном кластере МГТУ им. Н.Э.Баумана. Тестирование показало работоспособность и высокую надежность балансера.

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

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

 

Литература

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

2.     А.В. Лотов Введение в экономико-математическое моделирование. – М.: Наука, 1984.-392 с.

3.     А.П. Карпенко, Ю.М. Шурайц. Параллелизм методов интегрирования дифференциальных уравнений в частных производных //Автоматика и телемеханика. - 1992, ╧10, c. 3-20.

4.     Э. Танненбаум. Современные операционные системы. – СПб.:Питер.-1038 с.

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

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

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

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

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

10.  Р.П. Федоренко. Приближенное решение задач оптимального управления. –М.: Наука, 1978. -488 с.

 

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2024 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)