Технология организации распределенных вычислений в инструментальном комплексе Discomp

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ЗАДАЧАХ ДИНАМИКИ И УПРАВЛЕНИЯ

Сидоров И.А., Опарин Г.А., Феоктистов А.Г.

УДК 519.68+004.272

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

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

В последнее время для решения ресурсоемких задач создаются различные распределенные и параллельные вычислительные среды (см., например, работы В.В. Абасова, В.С. Бурцева, В.А. Васенина, В.В. Воеводина, А.Б. Жижченко, В.Н. Коваленко, В.В. Корнеева, Д.А. Корягина, А.О. Лациса, А.П. Новопашина, В.В. Топоркова и др.). Однако массовое использование таких сред сдерживается рядом нерешенных до конца проблем взаимодействия конечного пользователя (специалиста-предметника) с высокопроизводительными вычислительными установками. В их числе сложность задания параллелизма алгоритма решаемой задачи, анализа результатов счета, управления распределенным процессом решения задачи и др.

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

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

2) Вычислительные модули размещаются в разных узлах РВС. Исполнение схемы решения задачи выполняется в режиме интерпретации.

В данной работе рассматриваются средства инструментального комплекса DISCOMP (DIStributed COmputing system of Modular Programming) для описания предметной области пакета прикладных программ и постановок исследовательских задач, а также способ выполнения схем решения задач в режиме интерпретации. Основные методологические принципы описания предметной области для распределенного пакета прикладных программ приведены в работе [1].

Инструментальный комплекс DISCOMP.

Данный программный комплекс предназначен для инструментальной поддержки основных этапов разработки и применения пакетов прикладных программ, ориентированных на работу в гетерогенной (многоплатформенной) РВС, которая может включать вычислительные кластеры различных видов. РВС характеризуется следующими особенностями: в одном узле РВС может быть установлено несколько вычислительных модулей; допустимо включение в состав функционального наполнения пакета нетиражируемых вычислительных модулей, жестко привязанных к узлам РВС; построение схемы решения задачи осуществляется по процедурной постановке задачи [2]; в качестве входного языка для описания модели предметной области пакета и формирования постановок исследовательских задач используется метаязык XML; процессы решения задач в пакетах прикладных программ требуют проведения мно-

ИРКУТСКИМ государственный университет путей сообщения

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

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

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

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

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

Штта

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

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

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

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

Секция <modules> содержит спецификации, определяющие назначение модуля, атрибуты (идентификатор, имя модуля), команды запуска, а также множество входных и выходных параметров.

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

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ЗАДАЧАХ ДИНАМИКИ И УПРАВЛЕНИЯ

<!-- секция спецификаций параметров --> <рагате!еге>

<рагат 1й=*1* name='model' 1уре='Г11е' fi1ename='mode1.txt'>

<рагат id='2' name='mode1_1ist' type='fi1e1ist' pattern='mode1_e1ement_%1.txt' size='10'/> <param id='3' name='resu1t_1ist' type='fi1e1ist' pattem='resu1t_e1ement_%1.txt' size='10'/> </parameters>

<!-- секция спецификаций модулей --> <modu1es>

<modu1e id='1' name='decompose'> <commands os='Windows'>

<start>decompose.exe</start> </commands> <parameters>

<input><param id='1'/></input> <output><param id='2'/></output> </parameters> </modu1e>

<modu1e id='2' name='so1ve'> <commands os='Linux'>

<start>./so1ver (param_id:2)</start> </commands> <parameters>

<input><param id='2'/></input> <output><param id='3'/></output> </parameters> </modu1e> </modu1es>

<!-- секция спецификаций постановок задач --> <processes>

<process> <stage>

<modu1e id='1'/> </stage> <stage>

<modu1e id='2' 1istParameterId='2'/>

</stage> </process> </processes>

Рис. 1. Фрагмент описания предметной области на языке XML

Управление вычислительным процессом.

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

функций на языке JacaScript [5] и включаются в процедурную постановку задачи.

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

Множество неявных ограничений интерпретатора схемы решения задачи включает:

- ограничения на диапазоны значений параметров предметной области, определяемые типами этих параметров;

- условия допустимости выполнения схемы решения задачи;

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

Множество явных ограничений интерпретатора схемы решения задачи включает:

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

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

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

Ъе/огеБ1аг1 - готовность модуля к запуску;

onFinish - завершение работы модуля;

опЕаН - некорректное завершение работы модуля;

опБ^р - вынужденная остановка модуля;

onTimer - мониторинг результатов вычислений, выполняемый с определенным интервалом времени.

На рис. 2 приведен пример описания условия остановки вычислений при обработке параметра типа список файлов.

После завершения каждого экземпляра модуля module 2 запускается обработчик checkListResult(), который анализирует выходной элемент списка param 3. Если значение выходного элемента отлично от нуля, то производится остановка всех модулей на текущем ярусе, и вычислительный процесс завершается. Применение данной конструкции позволяет избегать избыточных вычислений при решении комбинаторных задач большой размерности, основным назначением которых является поиск результата, удовлетворяющего определенным условиям.

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

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

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

<process> <stage>

<module id='1'/>

</stage> <stage>

<module id='2' listParameter='2'

onFinish='checkListResult()'/>

</stage> </process> <actions>

function checkListResult() {

var res = DiscompAPI.getModuleOuputParam(); if ( res != 0 ) { DiscompAPI.stopCurrentStageModules();

};

};

</actions>

Рис. 2. Включение управляющих конструкций в схему решения задачи

<stage>

<module id='1'

onFinish= 'Discomp API.stopModules( [2,3]);'>

<module id='2'

onFinish= 'Discomp API.stopModules( [1,3]);'>

<module id='3'

onFinish= 'Discomp API.stopModules( [1,2]);'>

</stage>

Рис. 3. Пример задания способа обработки события onFi-nish

Внутреннее представление описания предметной области. Транслятор инструментального комплекса DISCOMP переводит описание предметной области пакета во внутреннюю объектно-ориентированную структуру (рис. 4) и осуществляет проверку целостности модели данной предметной области.

Процесс трансляции во внутреннюю структуру включает в себя следующие этапы. Описание предметной области передается в качестве параметра методу Init объекта Process, который выполняет анализ всех структур, входящих в это описание, и производит разбор схемы решения задачи.

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ЗАДАЧАХ ДИНАМИКИ И УПРАВЛЕНИЯ

Parameter

+id : int +name: siring +iype: int +coniment: suing filename_ siring filepattern : sting

+is_d6flriad

Module

id  int

name ; sting -comment: string iri_par_arr: Parameter -DLit_par_arr. Parameter s1art_crnd : string 5top_cnd" siring -axacjImeJImiL: Int events: EvcntHandler

+lnit(BK\q specstring)1 bool +Start() : bûûl r-$top() : bûûl

Ргцижч

+id : int : int

+rame : siring

-status " int

-stages_air : Stage

-curnent_stage : int

params_arr : Parameter

+1ш[(ввйд xml siring) : bûûl

+tasks Queu e() : bool

-prnoeas_ptr : P'ûcess

Stage

•-status. int »modules_arT : Module events : EventHandler

*1пк(евйд xml:string). bool

EventHandler

-type ill! -function : striig

*CallQ

DiscompAPI

+gelParameter(BeQfi id : int) +setParameter(BHQfl id : int. ввод value : string} +ge4ParameterValue{BBaq, id : int} уе-1М1.0ииРагат(еге>д mid'int. евод pitJlint}

+stopStageModul«n

+stopModiJte

go-1oStage(BBCö stagejium; int) +rastartMüdijl&(&Bi!fl rrtjd: int}

Рис. 4. иМЬ-диаграмма классов объектов для внутреннего представления описания предметной области

Для каждого яруса схемы создается новый объект Stage, инициализируемый фрагментом спецификации. После инициализации каждый объект Stage добавляется в массив stages_arr объекта Process. Модули, которые должны быть выполнены на каждом ярусе, инициализируются по спецификациям, входящим в предметную область, и добавляются в массив modules_arr объекта Stage. Подобным образом инициализируются параметры для каждого из модулей.

Вычислительный процесс предполагает обработку всех ярусов (элементов массива stages _arr объекта Process) для данной схемы решения задачи. При обработке каждого яруса производится инициализация и запуск модулей на доступных узлах распределенной среды. После завершения выполнения всех модулей яруса (элементов мас-

сива modules_arr объекта Stages) производится переход к следующему ярусу и обработка схемы решения задачи продолжается.

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

Инструментальный комплекс DISCOMP использован для создания ряда пакетов прикладных программ в гетерогенной многоплатформенной РВС [6-8]. Схемы решения задач в этих пакетах формируются с использованием описанных в статье языковых средств с применением различных конструкций управления вычислительным процессом.

Работа выполнена при поддержке РФФИ (проект № 08-07-00163) и при частичной поддержке гранта Президента РФ НШ 1676.2008.1.

БИБЛИОГРАФИЯ

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

2. Опарин, Г.А. САТУРН - метасистема для автоматизации конструирования и поддержки функционирования пакетов прикладных программ с автоматическим планированием вычислительного процесса / Г.А. Опарин, Д.Г. Феоктистов // Пакеты прикладных программ. Итоги и применения. - Новосибирск: Наука, 1986. - С. 12-21.

3. Гершуни, Д.С. Планирование вычислений в системах жесткого реального времени (обзор и перспективы) / Д.С. Гершуни // Вычислительная техника. Системы управления. - 1991. -Вып. 6. - С. 4-51.

4. Спенеср, П. XML проектирование и реализация / П. Спенеср. - Изд-во «Лори», 2001. - 510 с.

6. Сидоров, И.А. Распределенная информационно-вычислительная среда модульного программирования / И.А. Сидоров, А.Г. Феоктистов, А.И. Тятюшкин // Параллельные вычисления и

задачи управления: Тр. III Междунар. конф. PACO'2006. - М.: ИПУ РАН, 2006. - C. 505521.

7. Заикин, О.С. Параллельная технология решения SAT-задач с применением пакета прикладных программ D-SAT / О.С. Заикин, А.А. Семенов, А.Г. Феоктистов, И.А. Сидоров // Вестник ТГУ. Приложение. - 2007. - № 23. -С. 83-95.

Опарин, Г.А. Интеллектуальный решатель задач в булевых ограничениях в распределенной вычислительной среде / Г.А. Опарин, В.Г. Богданова, И.А. Сидоров // Информационные и математические технологии в науке и управлении: Тр. XII Байкальской Всерос. конф. Ч. II. - Иркутск: ИСЭМ СО РАН, 2007. - С. 1219.

Сурков А.В.

УДК 517.929.4

ОПТИМАЛЬНОЕ ДЕМПФИРОВАНИЕ В ЗАДАЧАХ СТАБИЛИЗАЦИИ И БЫСТРОДЕЙСТВИЯ СИСТЕМ С ЗАПАЗДЫВАНИЕМ*

1. Введение и постановка задачи. Пусть

п"

Я - п -мерное векторное пространство с евклидовой нормой || • ||, Ст - пространство всех непрерывных функций у/(), определенных на отрезке [—т,0], со значениями в Я" с обычной

sup-нормои

sup_

т<0<0

Работа выполнена при финансовой поддержке СО РАН (интеграционный проект № 85 и междисциплинарный интеграционный проект № 107).

В данной работе исследуются задачи стабилизации и быстродействия применительно к системе (1). Исследование этих задач основывается на понятии управления оптимального по отношению к демпфированию некоторого функционала V : Я х Я"

х CT ^ R.

Рассматривается управляемая система функционально-дифференциальных уравнений в векторной форме

х = /

где х( (•) е Ст - непрерывная функция для каждого ?, определяемая равенством х( (в) = х(? + в), — т<6< 0, и = (и1;...,ит) - вектор управления с ограничением и еи и и сЯт - компактное множество, / : Я х СТх и ^ Я" - непрерывная функция.

Под решением ) системы (1),

соответствующим некоторому управлению и(?, х{) и удовлетворяющим начальному условию Х0 = Ф0 (•), понимается решение в смысле

Филиппова (см. [1]) или в смысле Айзермана-Пятницкого (см. [2]) системы, замкнутой относительно этого управления.

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

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

тривиального решения производного

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

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

с