Интеллектуальные технологии и инструментальные средства создания вычислительной инфраструктуры в сети Интернет

Вычислительные технологии

Том 11, Специальный выпуск, 2006

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

В СЕТИ ИНТЕРНЕТ*

С.Н. Васильев, Г. А. Опарин, А. Г. Феоктистов, И. А. Сидоров Институт динамики систем и теории управления СО РАН,

Иркутск, Россия e-mail: snv@icc.ru, oparin@icc.ru

In this work we consider a methodology of construction, architecture and the basic features of the distributed computing environment. The distributed computing environment is created on the basis of a modular programming system. An example of the application of this environment for solving a problem of imitational modeling is demonstrated.

Введение

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

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

* Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант № 04-07-90358).

© Институт вычислительных технологий Сибирского отделения Российской академии наук, 2006.

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

В данной работе представлены интеллектные инструментальные средства для организации распределенной вычислительной среды (РВС) в сети Интернет. В частности, рассматриваются: протокол сетевого взаимодействия вычислительных узлов, основанный на технологии "клиент-сервер"; проблемно-ориентированный язык описания предметной области в виде расширения языка XML; программные средства удаленного запуска вычислительных модулей; способы и алгоритмы обработки параллельных списков данных; способы и алгоритмы планирования загрузки вычислительных ресурсов.

1. Средства реализации

На наш взгляд, можно выделить следующие основные критерии оценки программных средств реализации РВС: возможности графического инструментария, многоплатформен-ность (переносимость на уровне исходного кода), эффективность использования памяти, наличие удобной и мощной среды для разработки приложений и развитые сетевые средства. Исходя из перечисленных выше критериев проведен сравнительный анализ инструментальных сред, таких как QT (Q Toolkit), Java Toolkit, GTK (Gimp ToolKit) и MFC (Microsoft Foundation Class). В качестве программного средства реализации РВС выбрана инструментальная среда QT [3], включающая библиотеку классов С++ и набор инструментальных программных средств, предназначенных для построения много платформенных приложений с графическим интерфейсом. QT представляет собой единую платформу для приложений, которые могут работать под управлением операционных систем Windows 95/98/Ме/2000/ХР, Mac OS X, Linux, Solaris, HP-UX и других версий Unix. В качестве языка спецификации ПО решено использовать расширение языка разметки XML.

2. Планирование распределенных вычислений

Обобщенная схема базы знаний РВС может быть представлена в виде системы KB = (P, T, F, M, Y, IP, in, out, IF, R), где P — множество имен величин (параметров) предметной области; T — множество допустимых типов параметров; F — множество имен аб-

M

дулей, реализующих абстрактные операции из F; Y — множество имен (адресов) узлов

M

но операция / Е F базы знаний KB предполагает возможность вычисления параметров out(/j) по параметрам in(fi) с помощью некоторого модуля m го библиотеки модулей M, установленного в узле y Е Y. Связи между элементами множеств P, T, F, M и Y заданы в базе знаний отношениями IP С P х T, in, out С P х F, IF С F х M, R С M х Y (в общем случае типа многие-ко-многим). T

программирования включает специальный тип par — "параллельный список". Интерпрета-

ция операции f : x ^ y, оде x, y — параметры типа par, выполняется следующим образом: 1) в базе знаний KB осуществляется поиск всех вычислительных ресурсов (модуль+узел), реализующих операцию f; 2) организуется параллельное применение г-го параллельного

ресурса к г-му элементу списка x; 3) результат применения присваивается г-му элементу y

Структуру H = (A0; B0), оде A0, B0 с Z, далее будем называть постановкой задачи для модели M или просто задачей, а множества A0, B0 соответственно входом и выходом задачи. Модули fi и f2 го множества F фактически моделируют условия постановки задачи планирования H = (A0; B0), а именно модель распределенного вычислителя M содержит модули fi(; A0) и f2(B0;), оде A0, B0 с Z. Отсутствие атрибута до или после точки

fi

f2

M

H

из F и/или задача T имеет несколько альтернативных планов решения.

Задача планировщика состоит в том, чтобы, имея описание модели KB, определить,

F

B0

A0

чи H = (A0, B0), представляющий собой последовательность ярусов, каждый из которых

F

параллельно. Параллельные вычисления осуществляются по схеме FORK/JOIN, т.е. модуль (г + 1)-го яруса может быть выполнен, если завершилось выполнение всех модулей г

3. Язык спецификации плана решения задачи

Для построения параллельного плана решения задачи используется проблемно-ориентированное расширение языка разметки XML. Файл спецификации плана решения задачи plan.xml состоит из двух основных секций: описания всех параметров, участвующих в процессе вычислений (<parameters>), и описания процесса вычислений (<process>). Ниже приведены фрагменты файла plan.xml:

Фрагмент 1. Описание параметров:

<parameters> <param>

<id>l</id> <name>cm</name> <type>file</type> <filename>cm.txt</filename> <comment>Computing model</comment> </param> <param>

<id>2</id> <name>vdgm</name> <type>filelist</type> <f ilepattern>vdgm%d.txt</filepattern>

<comment>Variants of data of GPSS modelc/comment> </param> </parameters>

В данном примере рассмотрены два основных типа параметров: файл и параллельный список. Каждый из параметров должен обладать уникальным идентификатором, именем, типом и комментарием. Остальные свойства зависят от конкретного типа параметра. Для типа "файл" необходимо явно указывать имя файла, которое будет передано модулю при запуске. Для параллельного списка указывается шаблон имени файла, в данном примере "vdgm%d.txt", где %d будет заменено на числовое значение порядкового номера элемента в списке.

Фрагмент 2. Описание процесса вычислений, включающее инициализацию значений входных параметров и исполнение модулей:

<?xml version="1.0" encoding="UTF-8"?> <plan>

<process>

<!-- init input parameters --> <stage type='init'>

<parameters action='load'> <param>

<id>l</id>

<file>in/cm.txt</file> </param> <param>

<id>5</id>

<file>in/gm.gps</file> </param> </parameters> </stage>

<stage type='modules'> cmodule id='l'/> <module id='3'/> <module id='4'/> </stage>

</process>

В данном примере инициализируются значения двух входных параметров с идентификаторами 1 и 5, значения которых считывайпся из файлов in/cm.txt и in/gm.gps соответственно. Запуск модулей 1, 3 и 4 будет осуществлен по мере освобождения вычислительных ресурсов.

4. Архитектура распределенной вычислительной среды

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

Пользовательский web-интерфейс. Решение задачи многоуровневой обработки данных с помощью распределенных и многократно используемых специализированных прикладных программ предполагает создание специального web-интерфейса к распределенным программным средствам. При этом пользователь задает свои входные данные (заполняет определенные формы), не заботясь о том, где и как реально осуществится обработка данных. Примерами таких систем являются UNICOEE, PowerBuilder, Javelin и др. Проведенный анализ архитектуры клиентского интерфейса для распределенных систем показал, что наиболее оптимальным вариантом при реализации пользовательского интерфейса является связка \геЬ-сервер шлюз DataBase. Наиболее оптимальный вариант для реализации данной архитектуры — Apache XMI. XSI.T Perl MySQI.. Связка XML/XSLT позволяет отказаться от жесткой привязки к дизайну интерфейса и манипулировать более гибкими структурами данных.

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

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

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

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

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

5. Централизованная очередь процессов

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

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

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

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

1. Алгоритм планирования, основанный на приоритетах. Данный алгоритм подразумевает наличие у каждого процесса дополнительной характеристики — приоритета привилегированности процесса по отношению к другим процессам.

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

3. Смешанные алгоритмы планирования. Планирование основывается на концепции как приоритетов задач, так и запрашиваемых вычислительных ресурсов.

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

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

Ниже приведена циклическая процедура опроса очереди задач.

void GridServer::doProcess() {

logMessage("Trying to do something");

//search not busy node

for

{

if

{ //if node not busy we give this node to all processes which have jobs //GridProcess check if this node can execute module on current stage

for ( int process_num=0; process_num<(int)processes.size(); process_num++ ) {

if ( processes[process_num]->haveJobForNode(nodes[node_num] ) ) {

int moduleld = processes[process_num]->giveJobToNode( nodes[node_num] );

if ( moduleld ) {

//this node have module which process need to execute //TODO: in the gridProcess nodes [node_num]->busy = true;

nodes [node_num]->process_id = processes [process_num]->id; nodes[node_num]->prepareToStartModule( moduleld );

>;

} else if ( processes[process_num]->completed ) {

logMessage( QString("Process(id:%l) is removed from processes list").

arg(processes[process_num]->id) ); //TODO¡remove this process from processes list

>;

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

6. Запуск модуля на удаленном узле вычислительной сети

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

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

1. На сервере проверяется наличие значений всех входных параметров для запуска модуля m1. Если данное условие соблюдается, то на удаленный узел отправляются значения входных параметров.

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

3. Сервер отправляет команду на запуск удаленного модуля.

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

5. Сервер меняет состояние для данного узла и ожидает завершения выполнения модуля.

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

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

8. На завершающем этапе выполняется очистка состояния вычислительного узла и он помечается свободным.

Если какой-либо из этапов выполнен некорректно, то после последнего шага процедура запуска модуля на удаленном узле прекращается.

7. Протокол передачи данных

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

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

Ниже приведен пример взаимодействия клиента с сервером.

Сервер отправляет запрос на передачу параметров модулю № 4:

<?xml version='1.0' encoding='UTF-8'?> crequest id='120' name='parameter'> cmodule id='4'>

<parameter id='1'><![CDATA[01010101010]]></parameter> </module> </request>

Клиент обрабатывает запрос и в случае успешного получения всех параметров отправляет серверу ответ:

<?xml version='1.0' encoding='UTF-8'?>

<answer id='120' status='1' msg='success' >

cmodule id='4'/> </answer>

В случае сбоя серверу возвращается сообщение об ошибке:

<?xml version='1.0' encoding='UTF-8'?>

<answer id='120' status='2'msg='failed'>

cmodule id='4'/> </answer>

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

<?xml version='1.0' encoding='UTF-8'?> crequest id='130' msg='start'>

cmodule id='4'/> </request>

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

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

На уровне кода взаимодействие узлов в сети организуется с помощью двух основных функций — receiveDataFromFromEemoteNode() и sendDataToRemoteNodeQ. Функция получения данных является слотом (в терминах QT) и вызывается при генерации сигнала ready Read () класса QSocket. Полученное сообщение анализируется и в зависимости от идентификатора назначается функция, выполняющая дальнейшую обработку сообщения. Функция отправки сообщений на удаленную машину принимает два входных параметра — тело сообщения в формате xml, и если тип передаваемого сообщения — запрос, то в качестве второго параметра передается ссылка на функцию, которая будет осуществлять обработку ответа от удаленной машины.

8. Пример решения задачи

Рассмотрим задачу моделирования процесса погрузочно-разгрузочных работ (ПРР) для ООО "Иркутский хладокомбинат".

Система моделирования реализована в виде распределенного пакета имитационного моделирования. Инструментальная среда и пакет имитационного моделирования установлены на "горизонтальном" вычислительном кластере Института динамики систем и теории управления СО РАН, который состоит из одного центрального (управляющего) и четырех вычислительных узлов. Конфигурация узла: процессор Pentium 4 2.8 ГГц, оперативная память 512 Мбайт, жесткий диск IDE 80 Гбайт, сетевая плата Gigabit Ethernet.

Модель зоны ПРР хладокомбината в общем виде может быть представлена в виде структуры M = (Z,W,G, F,Cl,T,Co), оде Z — множество товарных зон; W — множество помещений для хранения товаров; G — множество товарных групп; F — множество

Cl T Co

ство, включающее ограничения па пропускную систему склада, такие как K — количество каров, Lo — количество грузчиков, S — количество кладовщиков, L — количество лифтов и др.

Z W G F Cl T

щем случае типа многие-ко-многим): Я\ С F х Cl — разгружаемые товары; R2 С F х Cl —

отгружаемые товары; R3 С F х Cl х W — хранимые товары; R4 С F х T — температурный

режим товаров; R5 С W х T — температурный режим помещений для хранения товаров; R6 С F х G — товары, составляющие товарные группы; R7 С W х G — помещения, соответствующие товарным группам; R8 С W х Z — размещение помещений для хранения товаров по товарным зонам.

Имитационная модель зоны ПРР автоматически генерируется на основе его описания, хранящегося в базе данных. Эту функцию выполняет модуль GenMod.exe. Этот же модуль генерирует множество файлов с различными вариантами количественных и вероятностно-временных характеристик процесса работы склада (параллельный список данных). Модуль GPSSW.exe (свободно распространяемая студенческая версия системы имитационного моделирования — Minuteman Software GPSS World for Windows) предназначен для прогона имитационной модели зоны ПРР с одним из вариантов исходных данных. Копии модуля GPSSW.exe размещены на вычислительных узлах кластера. Модуль CMchoice.exe предназначен для анализа результатов расчетов на всех вариантах исходных данных и выбора наиболее оптимального из них.

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

Заключение

Представленная в данной работе инструментальная среда разработана на основе принципов создания много платформенных приложений, обеспечивающих переносимость на уровне исходного кода и использование в качестве модулей приложений, разработанных под операционные системы Windows, Unix like systems, MAC OS X.

В плане дальнейшего ее развития планируется доработать отдельные подсистемы с целью улучшения заложенных в них алгоритмов и исправления возникших на данный момент проблем. Во-первых, очередь процессов планируется реализовать в соответствии с алгоритмом BackFill [6], в котором используется принцип обратного заполнения: вначале размещаются задания строго по приоритетам, а в образовавшиеся "дырки" помещаются менее приоритетные задания. Во-вторых, требуется решение проблем с отказоустойчивостью, так как на данный момент отключение вычислительных узлов от распределенной среды может приводить к нарушению выполнения вычислительного процесса. Также планируется доработать протокол передачи данных по сети и включить в инструментальную среду наиболее развитые протоколы передачи файлов: FTP, NFS, NetBIOS (Samba).

Список литературы

[1] Опарин Г.А., Феоктистов А.Г. Инструментальная распределенная вычислительная САТУРН-среда // Программные продукты и системы. 2002. № 2. С. 27-30.

[2] Васильев С.Н., Опарин Г.А., Феоктистов А.Г. Интеллектный подход к автоматизации моделирования сложных управляемых систем // Современные проблемы прикладной математики и механики: Тр. Междунар. конф. 1ШАММ-2001. Новосибирск: I ПН СО РАН, 2001. Т. 6, ч. 2. С. 159-168.

[3] Бланшет Ж., Симмерфилд М. QT3: Программирование GUI на С++. М.: Кудиц-образ, 2005. 448 с.

[4] Лорин Г., Дейтел Х.М. Операционные системы. М.: Финансы и статистика, 1984. 392 с.

[5] Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2003. 544 с.

[6] Feitelson D.G., Weil A.M. Utilization and predictability in scheduling the IBM SP2 with backfilling // Proc. of IPPS/SPDP. IEEE Computer Society. 1998. P. 542-546.

Поступила в редакцию 26 сентября 2006 г.