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

УДК 519.6

А.П.Карпенко, МГТУ им. Н.Э. Баумана

С.А.Чернецов, МГТУ им. Н.Э. Баумана

Введение

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

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

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

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

            Технология GRID обычно используется для создания географически распределенной гетерогенной вычислительной инфраструктуры и организации коллективного доступа к ресурсам этой структуры. При этом используются сетевые технологии и специальное программное обеспечение промежуточного уровня (между базовым и прикладным программным обеспечением) [4].

            Наиболее известным из проектов Grid является проект Globus. Инструментальные средства проекта Globus (Globus Toolkit) состоят из следующих основных компонентов [5], [6]:

·       GRAM (Globus Resource Allocation Manager), отвечающий за создание/удаление процессов;

·       MDS (Monitoring and Discovery Service), обеспечивающий различные способы представления информации о Grid-системе;

·       GSI (Globus Security Infrastructure), реализующий защиту данных, включая их шифрование, а также аутентификацию и авторизацию;

·       GASS (Global Access to Secondary Storage), предоставляющий возможность хранения массивов данных в распределенной среде Grid, а также доступа к этим данным;

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

            Распределение задач по доступным ресурсам среды Grid реализует низкоуровневый компонент Globus Toolkit - GRAM, который является интерфейсом между высокоуровневым менеджером ресурсов и локальной системой управления ресурсами вычислительного узла среды Grid. В настоящее время GRAM может взаимодействовать со следующими локальными системами управления ресурсами (диспетчерами ресурсов):

·       PBS (Portable Batch System);

·       LSF (Load Sharing Facility);

·       NQE (Network Queuing Environment);

·       LoadLeveler;

·       Condor;

·       Easy-LL.

            Все перечисленные диспетчеры достаточно близки между собой по функциональности. Наиболее популярным из этих диспетчеров является диспетчер LSF, являющийся коммерческим продуктом компании Platform Computing Inc. [4]. Именно использование диспетчера LSF для балансировки загрузки рассматривается в данной работе.

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

            В п. 1 работы приводится информационная и программная модели А-задачи. В п. 2 – методика распараллеливания вычислений и балансировки загрузки с помощью диспетчера ресурсов LSF. В п. 3 дается пример использования диспетчера LSF для распараллеливания вычислений при тестировании программы-трассировщика печатных плат.

1. Информационная и программная модели А-задачи.

2. Постановка задачи балансировки загрузки

            Пусть имеется  вычислительных процессов  информационно связанных между собой по схеме «master - slave» (см. Рис. 1):

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

·       процесс ,  обрабатывает исходные данные  и по завершении обработки посылает результирующие данные  процессу ;

·       процесс  получает от процессов ,  все результирующие данные , выполняет их обработку и завершается.

Рис. 1. Информационная модель А-задачи

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

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

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

            Вариант 1. Объем данных  мал, и эти данные могут быть переданы через аргументы командной строки при запуске программ  (см. Рис. 3)

            Вариант 2. Объем данных  не нас только мал, чтобы эти данные было удобно передавать через аргументы командной строки, как в варианте 1. В таком случае в программе  данные  записываются в переменные среды, а программы  считывают их значения (см. Рис. 4).

Рис. 2. Схема вычислительной системы

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

Рис. 3. Вариант 1 программной модели А-задачи.

Рис. 4. Вариант 2 программной модели А-задачи.

Рис. 5. Вариант 3 программной модели А-задачи.

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

         На Рис. 3 – 5 приняты следующие обозначения: ,  - имена файлов, содержащих данные , , соответственно; .

            Возможны две реализации каждого из рассмотренных вариантов организации решения А-задачи.

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

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

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

3. Методика решения А-задачи с помощью диспетчера ресурсов LSF

            Диспетчер ресурсов LSF реализует динамическую балансировку загрузки в условиях многопользовательской гетерогенной среды и требует, чтобы вычислительный узел среды Grid, на котором он функционирует, был под его полным контролем. Балансировка загрузки вычислительных узлов Grid-системы осуществляется диспетчером LSF на основе формируемой им итоговой очереди задач – LSF запускает очередную задачу из итоговой очереди, как только освобождаются необходимые ей ресурсы. Итоговая очередь задач формируется диспетчером LSF на основе четырех предопределенных очередей:

·       очередь для коротких (до 15 минут) задач (short);

·       очередь для средних (до 1 часа) задач (medium); 

·       очередь для длинных (до 48 час) задач (long); 

·       очередь для неограниченно длинных задач (extralong).

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

            Важным является следующее обстоятельство. При помещении пользователем задачи в одну из указанных предопределенных очередей диспетчер LSF копирует в себя среду исполнения (environment) соответствующего узла GRID-системы (терминала). На основе этой информации диспетчер организует выполнение задачи на любом из выбранных узлов системы в указанной среде исполнения, т.е. так, как будто задача запущена напрямую с терминала. Именно на указанном свойстве диспетчера LSF основан вариант 1 программной реализации распараллеливания А-задачи (см. п. 1). Отметим, что назад (в диспетчер LSF) среда исполнения не копируется, поэтому организовать передачу результатов работы программ  на host-процессор через параметры среды невозможно.

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

            Поскольку в LSF заранее не известно, на каком вычислительном узле и когда будет запущена задача, связь с терминалом, с которого задача была добавлена в очередь, не сохраняется. Поэтому если задача имеет стандартный вывод данных, то эти данные либо пересылаются пользователю, запустившему задачу, по E-mail, либо с помощью опции «-o» команды busb (см. ниже) перенаправляются в файл. Под стандартным выводом понимается текстовый поток вывода на терминал. В LSF также предусмотрена возможность предварительного просмотра стандартного вывода выполняемой в данный момент задачи.

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

            Команда bqueues позволяет просмотреть состояния предопределенных очередей.

            Команда bjobs позволяет получить перечень всех задач, которые в текущий момент находятся в той или иной предопределенной очереди задач, а также вывести информацию об их статусе (см. ниже). Например, команда bjobs -q queue -u all формирует перечень всех задач в предопределенной очереди с именем queue не зависимо от того, каким пользователям они принадлежат. При этом для каждой из задач выводится следующая информация:

·       JOBID – идентификатор задачи (ID задачи);

·       USER – имя пользователя – владельца задачи;

·       STAT – статус задачи (выполняется, находится в очереди и т.д.);

·       FROM_HOST – имя вычислительного узла, с которого была назначена задача;

·       EXEC_HOST – имя вычислительного узла, на котором задача выполняется (только для задач, выполняющихся в данный момент);

·       JOB_NAME – имя задачи;

·       SUBMIT_TIME – время постановки задачи в очередь.

            Команда bsub [options] сommand [args] добавляет задачу в очередь на выполнение. Здесь command – имя задачи, args – аргументы этой задачи, options – опции команды, наиболее употребительными из которых являются следующие:

·       -q queue – добавить задачу в очередь с именем queue;

·       -o file – перенаправлять стандартный вывод в файл с именем file (в режиме дозаписи);

·       -oo file – перенаправлять стандартный вывод в файл с именем file (в режиме перезаписи);

·       -k – управление не возвращать до завершения задачи.

            Заметим, что команда добавление задачи в очередь LSF отличается от команды ее запуска с терминала только префиксом bsub [options].

            Команда bhist job_id выводит подробную информацию о задаче, ID которой есть job_id.

            Команда bpeek job_id позволяет выполнить просмотр содержимого текущего стандартного вывода задачи, ID которой есть job_id. Данная команда используется для задач, которые в текущий момент времени выполняются. Поскольку окончание записи данных стандартного вывода в файл или отправка их по E-mail осуществляются только по завершению исполнения задачи, использование команды bpeek – единственный способ посмотреть содержание стандартного вывода задачи до ее завершения.

            Команда bswitch queue job_id выполняет перенос задачи находящейся в данный момент в очереди на выполнение (то есть выполнение которой еще не началось) с идентификатором job_id в предопределенную очередь с именем queue.

            Команда bkill job_id удаляет из очереди, в которой она находится, задачу с идентификатором job_id.

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

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

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

·       в команде bsub, с помощью которой запускаются задачи , использовать опцию K.

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

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

            Пример 1. Схема реализации программы  (вариант ).

…

<подготовка исходных данных для программ >

`bsub -q short   `;

…

`bsub -q short   `;

…

            Пример 2 Схема реализации программы  (вариант ).

…

<подготовка исходных данных для программ >

<запись исходных данных в переменные среды>

…

`bsub -q short  `;

…

`bsub -q short  `;

…

            Пример 3. Схема реализации программы  (вариант ).

…

<подготовка исходных данных для программ >

…

if(!fork())

     `bsub –K -q short   `;

…

if(!fork())

     `bsub -K -q short   `

wait(0);

…

<чтение результатов обработки из файлов>

<обработка результатов>

…

4. Распараллеливание программы для тестирования трассировщика печатных плат с помощью диспетчера LSF

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

В последовательном режиме тестирование выполняется по следующей схеме:

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

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

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

            На современной рабочей станции характерное время выполнения репрезентативного набора тестов составляет от 35 до 52 часов.

            Каждый из тестов имеет значительный объем (от нескольких килобайт до нескольких десятков мегабайт) и хранится на жестком диске. Время обработки трассировщиком каждого из тестов заранее не известно и может варьироваться в очень широких пределах: от нескольких минут до нескольких часов. В результате обработки каждого из тестов трассировщик создает файл, содержащий от 1 до 10 отчетов о результатах разводки. Отчет содержит специальные данные (зависящие от обработанного теста) и общие данные (некоторый показатель качества трассировки, количество конфликтов, количество необработанных соединений, количество переходов между слоями, общее количество соединений и т.д.). Общий объем каждого отчета составляет от 20 до 500 Кбайт.

            Таким образом, рассматриваемая задача тестирования трассировщика печатных плат может быть представлена в виде А-задачи следующим образом:

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

·       программы  одинаковы и представляют собой сам трассировщик (т.е. имеет место частный случай А-задачи);

·       каждое из исходных данных ,  содержит i-й тест;

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

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

            Таким образом, программа  имеет следующий вид:

foreach my $tst (@tests)

{

`bsub -q short testenv $tst`;[SC1] 

}

            Здесь testenv- имя трассировщика; массив tests содержит имена tst входных  и выходных  файлов, где файл  содержит i-й тест, а в файл  тестировщиком будут записаны результаты обработки этого теста. Таким образом, testenv=, tst=&. Конструкция foreach my $tst (@tests) циклически выбирает из массива tests имя файла tst с очередными именами файлов ,  и помещает трассировщик testenv в очередь LSF.

            Тестирование в параллельном режиме выполнено на гетерогенной вычислительной системе, состоящей из 5 узлов, объединенных локальной сетью, и функционирующей под управлением операционной системы Solaris и диспетчера LSF. [SC2] Общее время  обработки одного из наборов из 85 тестов (без учета затрат на обработку и визуализацию его результатов) составило 8.7 часов. Среднее время  прогона тех же тестов в последовательном режиме на одном узле примерно равно 43.4 часа. Таким образом, достигнуто ускорение  и эффективность  [9].

5. Заключение

            В работе приведена информационная и программная модели А-задачи - задачи, имеющей граф информационных связей в виде двухуровневого дерева с априори неизвестными вычислительными сложностями листьев. Рассмотрены варианты А-задачи, отличающиеся объемом исходных данных, которые должны быть переданы от корня указанного дерева к его листьям. Различие в объемах указанных данных приводит к разным программным моделям А-задачи, отличающимся механизмами передачи этих данных: через аргументы командной строки; через переменные среды; через файлы на накопителях на жестких магнитных дисках. Описана методика распараллеливания и балансировки загрузки разных вариантов А-задачи с помощью известной компоненты проекта Grid Globus - диспетчера ресурсов LSF. На примере программы тестирования трассировщика печатных плат показана высокая эффективность использования диспетчера LSF при распараллеливании вычислений и балансировке загрузки гетерогенной вычислительной системы в условиях, когда листья графа информационных связей А-задачи имеют высокие вычислительными сложности.

            Авторы выражают благодарность В.Б. Маничеву за поддержку данной работы.

Литература

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

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

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

4. Кирьянов А.К., Рябов Ю.Ф. Введение в технологию Грид http://window.edu.ru/window_catalog/ redir?id=49689&file=Metodichka-grid.pdf

5. I Foster, C. Kesselman. Globus: A Metacomputing Infrastructure Toolkit. ftp://ftp.globus.org/ pub/globus/papers/globus.pdf

6. I. Foster, C. Kesselman. The Globus Project: A Status Report. ftp://ftp.globus.org/ pub/globus/papers/globus – hcw98.pdf

7. Myers, Glenford J., The art of software testing, New York: Wiley, 1979.

8. PCB software.(Test & Measurement); Wireless Design & Development,  February, 2005

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