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

На правах рукописи

Сухорослов Олег Викторович

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

Специальность 05.13.18 "Математическое моделирование, численные методы и комплексы программ "

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва-2005

Работа выполнена в Институте Системного Анализа РАН

Научный руководитель: доктор физико-математических наук,

профессор Афанасьев Александр Петрович

Официальные оппоненты: доктор физико-математических наук,

профессор Клименко Станислав Владимирович

кандидат технических наук, старший научный сотрудник Васильев Андрей Анатольевич

Ведущая организация: Вычислительный центр РАН

Защита состоится СИЮНчР- 2005 г. в 11е0 часов на

заседании диссертационного в Институте Системного

Анализа РАН по адресу: 117312, г. Москва, пр-т 60-летия Октября, 9.

С диссертацией можно ознакомиться в библиотеке Института Системного Анализа РАН

Автореферат разослан « 2Ь» 2005 г.

Ученый секретарь диссертационного совета

д.т.н., проф._А.И. Пропой.

гоос-Ц

сг 97

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

¿4 4 49 3%

Актуальность темы. Диссертация посвящена разработке целостной

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

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

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

В качестве еще одной задачи, характерной для указанного класса, в диссертации рассматривается

г

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

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

1 . ' ' 2

I * *

Ь ----- -"

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

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

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

Научная новизна. Научная новизна складывается из следующих результатов:

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

• Разработан прототип распределенной информационно-алгоритмической среды, реализующей эгот подход.

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на семинарах в Институте системного анализа, а также на V Всероссийской школе-семинаре "Прикладные проблемы управления макросистемами", II Московской конференции "Декомпозиционные методы в математическом моделировании и информатике", ХЬУИ Научной конференции МФТИ.

Публикации. По теме диссертации опубликовано 5 работ.

Структура и объем работы. Общий объем диссертации состоит из 218 страниц. Диссертация включает в себя введение, четыре главы, заключение, список литературы (119 наименований), приложение и 38 рисунков.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

• Разработка универсальной модели интеграции ресурсов в РВС.

• Разработка набора служб, которые реализуют базовые механизмы, востребованные приложениями и компонентами среды.

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

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

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

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

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

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

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

Во втором параграфе описывается архитектура распределенной вычислительной среды на основе концепции ИАР. Рассматриваются основные уровни данной архитектуры (Рис. 1):

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

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

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

Первичные ресурсы ,

_____J

Рис. 1 Архитектура РВС па основе концепции ИАР.

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

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

£

Приложение

Атнт доступа

Кткнтсют

р—д

5» < , > ? , 1

ППО г прСИЖМ! уМЛФННОЮ £.ОС'уП» к ПАР

1 ¡Г-^! 1

\ жг:

СйЦрВа

Рис. 2 Программная архитектура системы 1АЯпе1

Уровню агентов доступа соответствуют агенты доступа и контейнеры ИАР. Агент доступа в 1АЯпе1 представляет собой программный компонент, реализующий набор операций, через которые осуществляется доступ к функциональности первичного ресурса. Помимо специфической задачи унификации интерфейса первичного ресурса, агент доступа должен решать такие стандартные задачи, как контроль доступа к ресурсу, обеспечение

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

Агент доступа в 1АЯпе1 не решает задачу организации удаленного доступа к ресурсу. Для обеспечения гибкости и расширяемости архитектуры данная задача изолирована в другом компоненте - контейнере ресурсов, который представляет собой среду, в которой развертываются и функционируют агенты доступа. Контейнер обеспечивает удаленный доступ к агентам посредством определенного коммуникационного механизма и технологии ППО. Описывается общая схема устройства контейнера ИАР (Рис. 3) и процедура развертывания агента доступа в контейнере.

Рис. 3 Контейнер ИАР.

Уровень прикладного API образует клиентская библиотека, которая использует для вызова ресурсов так называемые коннекторы. Клиентская библиотека IARnet представляет собой реализацию интерфейса прикладного

программирования (АР1), который соответствует высокоуровневой модели доступа к ИАР.

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

Приложение

Рис. 4 Клиентская библиотека и коннекторы.

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

• Информационная служба, осуществляющая сбор и хранение информации о ресурсах и службах РВС;

• Служба рассылки сообщений, реализующая механизм группового взаимодействия ресурсов и уведомлений;

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

• Служба журналов, позволяющая вести единый системный журнал распределенного приложения.

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

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

Во втором параграфе рассматривается механизм идентификации ресурсов РВС. Для идентификации ресурсов в 1Л11пе1 введено два типа идентификаторов:

• Идентификатор ресурса - уникальный идентификатор ресурса, который не изменяется при перемещении ресурса и изменении способа доступа к нему.

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

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

В третьем параграфе описывается система типов данных IARnet и рассматривается описание интерфейсов (типов) ресурсов.

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

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

Описаны две модели сбора информации о РВС:

• Пассивный сбор или регистрация, при которой информация помещается в репозиторий (публикуется) непосредственно поставщиками информации.

• Активный сбор или опрос, при котором некий механизм производит опрос поставщиков информации, а затем помещает полученную от них информацию в репозиторий.

Рассмотрена целесообразность использования той или иной модели при сборе различной информации о РВС.

Рис. 5 Архитектура информационной службы 1АКпе1.

Описанный подход к управлению информацией о РВС реализован в 1АИпе1 при помощи создания специальной службы - информационной службы. Описана архитектура службы (Рис. 5) и ее унифицированный

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

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

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

• Описание элементарных типовых подзадач, из которых состоит решение исходной задачи;

• Описание ресурсов, которые решают указанные подзадачи;

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

• Описание событий, которые могут влиять на ход выполнения алгоритма, и правил их обработки.

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

У Прикладной API ¡ARnet

Служба управления сценариями

Ресурсы участвующие в выполнении сценария Рис. 6 Архитектура службы управления сценариями.

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

В восьмом параграфе описывается модель прикладного программирования 1АЯпе1 Описывается интерфейс представителя ресурса на

клиентской стороне для языка Java. Приводится пример программы на языке Java, в которой осуществляется поиск ресурса заданного типа и его вызов.

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

• распределенное решение задачи оптимального управления;

• распределенное решение системы обыкновенных дифференциальных уравнений (ОДУ);

• распределенное имитационное моделирование экологической, экономической и социальной динамики.

В первом параграфе рассматривается линейная по управлениям задача оптимального управления со смешанными ограничениями, вида:

Процедура продолжения оптимальных траекторий модифицируется для использования её в распределенной среде. Исходная задача декомпозируется на следующие подзадачи:

• задачи математического программирования (МП) - для получения новых режимов в процессе продолжения оптимальной траектории;

т

х(0 = и( О, K(x{tj)u(t) = L(x(tj), M(x(t))u(t)>N{x(t)),

x(t0) = *0

t 6 [f0, Т], T - фиксировано, x(t): R -> R",g(x): R" -> Ru" K(x):R"^>R"*',L(x):Rn-+RM, M(x):R" -+R™», N(x):R" -»Л"*1.

• задача Коши для системы ОДУ - для получения траектории вдоль каждого режима;

• поиск корней нелинейных уравнений - для определения моментов переключения режимов.

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

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

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

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

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

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

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

Проверка условий сохранения режимов Р(Т) <> О

Задача ОУ

Формирование условий сохранения режимов Р(Т)

Рис. 7 Схема распределенного решения задачи оптимального управления.

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

• ресурсы решения задач математического программирования (ЛП и специальных задач);

• ресурс решения задачи Коши указанным методом;

• ресурсы символьного дифференцирования;

• ресурсы решения нелинейных уравнений;

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

Во втором параграфе рассматривается распределенный алгоритм решения системы ОДУ. В качестве примера ситуации, где естественным образом возникает необходимость решения системы ОДУ в распределенной среде, можно указать случай, когда компоненты правой части системы заданы не аналитически, а являются выходами некоторых сложных имитационных моделей или программно-аппаратных комплексов, которые затруднительно переместить из одного места в другое. Для решения системы ОДУ в РВС применен вычислительный алгоритм, который позволяет минимизировать накладные расходы, связанные с сетевым обменом данными между решателями. Описаны необходимые типы ресурсов и приведен сценарий координированного использования указанных ресурсов для решения системы ОДУ в среде на базе 1АЯпй (Рис. 8).

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

t

Информационная служба

Льэс||

Пользователь

1. Поиск ресурсов

--4

0)

...У «—\pMPM

3. в1агЦ...)

-*С*гк-

V

-1- 0. Регистрации-

-|д(0.Рз(0|

Служба рассылки сообщений

V 1«-------------------------^

___Г <—1д(0,д,(0|

Рис. 8 Схема распределенного решения системы ОДУ.

Страны

Модель

Страны

• Модель Страны

< Модель \ Мира /

Информационная база данных

Модель Страны

Рис. 9 Схема распределенной имитационной модели ЭСЕИМ.

При создании распределенной имитационной модели (Рис. 9), минимальные наборы компонентов модели ЭСЕИМ, которые могли быть размещены на одной рабочей станции, рассматривались как единый ИАР. В результате, были выделены три типа ресурсов: модель страны (региона), база демографических данных и модель внешнего мира. Кроме того, был предусмотрен еще один ресурс - информационный сервер. Это программный модуль, задачей которого является общее управление процессом моделирования на заданном интервале времени, а именно, задание начального и финального года модельного интервала; начало/завершение эксперимента; координация работы всех остальных ресурсов при совершении «шага» моделирования и, наконец, отображение результатов моделирования. Приводится сценарий координированного использования указанных ресурсов для проведения имитационного эксперимента в РВС (Рис. 9).

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Описана универсальная модель интеграции ресурсов в распределенную вычислительную среду.

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Афанасьев А.П., Сухорослов О.В. "Использование информационно-алгоритмических ресурсов в Grid-вычислениях". // Прикладные проблемы управления макросистемами. Труды ИСА РАН. Том 8 - М.: УРСС, 2004.

2. Афанасьев А.П., Рогов C.B., Сухорослов О.В., Хуторной Д.А. Реализация процедуры продолжения оптимальных решений в распределённой вычислительной среде. // Фундаментальные основы информационных технологий и систем. Труды ИСА РАН. Том 9 - М.: УРСС, 2004.

3. Сухорослов О.В. "Разработка универсальной вычислительной платформы для распределенного решения научных задач". Труды XLVII Научной конференции МФТИ, Москва, 2004.

4. Афанасьев А.П., Волошинов В.В., Кривцов В.Е., Рогов C.B., Сухорослов О.В. Использование информационно-алгоритмических ресурсов для организации распределенных вычислений. // Проблемы вычислений в распределенной среде: организация вычислений в глобальных сетях. Сборник трудов ИСА РАН, М.: УРСС, 2004.

5. Афанасьев А.П., Волошинов В.В., Рогов C.B., Сухорослов О.В. Развитие концепции распределенных вычислительных сред. // Проблемы вычислений в распределенной среде: организация вычислений в глобальных сетях. Сборник трудов ИСА РАН, М.: УРСС, 2004.

V

f

í

11150

РНБ Русский фонд

Подписано к печати 18 05.2005 г Формат60 x 84/16. О&ьем 1,5 п.л. Тираж 70 эю

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

ГЛАВА 1. ЭВОЛЮЦИЯ ТЕХНОЛОГИЙ ПОСТРОЕНИЯ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕД.

1.1 Концепция распределенных вычислительных сред.

1.2 Современные технологии построения распределенных вычислительных сред.

1.2.1 Промежуточное программное обеспечение.

1.2.2 Организация параллельных вычислений в масштабах глобальной сети.

1.2.3 Сг1(1-вычисления.

1.2.4 Современные средства решения декомпозируемых вычислительных задач в РВС.

1.3 Описание и классификация основных видов ресурсов РВС.

1.3.1 Аппаратные ресурсы.

1.3.2 Программные ресурсы.

1.3.3 Информационные ресурсы.

1.3.4 Сетевые ресурсы.

1.3.5 Инструментальные ресурсы.

1.3.6 Человеческие ресурсы.

1.4 Основные задачи работы.

1.4.1 Проблемы современной программной инфраструктуры РВС.

1.4.2 Основные задачи работы.

ГЛАВА 2. ПРИНЦИПЫ ПОСТРОЕНИЯ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЫ НА ОСНОВЕ КОНЦЕПЦИИ ИНФОРМАЦИОННО-АЛГОРИТМИЧЕСКИХ РЕСУРСОВ.

2.1 Понятие информационно-алгоритмического ресурса.

2.1.1 Интеграция первичных ресурсов на основе агентов доступа.

2.1.2 Модель доступа к информационно-алгоритмическим ресурсам.

2.1.3 Типизация информационно-алгоритмических ресурсов.

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

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

2.2.1 Уровень агентов доступа.

2.2.2 Уровень служб.

2.2.3 Уровень прикладного АР1.

2.3 Основные требования к программной инфраструктуре РВС.

2.3.1 Функциональные требования.

2.3.2 Нефункциональные требования.

2.3.3 Проектные ограничения.

2.4 архитектура системы Ш^ет.

2.4.1 Агент доступа.

2.4.2 Контейнер ИАР.

2.4.3 Клиентская библиотека.

2.4.4 Коннекторы.

2.4.5 Служба.

ГЛАВА 3. ОРГАНИЗАЦИЯ ВЫЧИСЛЕНИЙ В РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЕ НА ОСНОВЕ 1АШЧЕТ.

3.1 Интеграция первичных ресурсов.

3.1.1 Разработка агента доступа.

3.1.2 Организация удаленного доступа к ресурсу.

3.1.3 Задачи, связанные с организацией доступа к ресурсу.

3.2 Идентификация ресурсов.

3.2.1 Постановка задачи.

3.2.2 Идентификатор ресурса.

3.2.3 Ссылка на ресурс.

3.2.4 Отображение идентификатора ресурса в ссылку на ресурс.

3.2.5 Идентификатор типа ресурса.

3.3 типы данных и описание интерфейсов ресурсов.

3.3.1 Постановка задачи.

3.3.2 Система типов данных lARnet.

3.3.3 Нотация для описания интерфейсов ресурсов.

3.4 Информационная служба.

3.4.1 Постановка задачи.

3.4.2 Представление информации о РВС.

3.4.3 Хранение информации о РВС.

3.4.4 Доступ к информации о РВС.

3.4.5 Сбор информации о РВС.

3.4.6 Информационная служба.

3.4.7 Управление информацией о ресурсе в агенте доступа.

3.5 Групповое взаимодействие ресурсов.

3.5.1 Постановка задачи.

3.5.2 Служба рассылки сообщений.

3.5.3 Интерфейс потребителя сообщений.

3.5.4 Дальнейшее развитие подхода.

3.6 Описание и выполнение прикладных вычислительных сценариев.

3.6.1 Постановка задач и.

3.6.2 Описание прикладных вычислительных сценариев.

3.6.3 Служба управления сценариями.

3.7 Другие службы IARnet.

3.7.1 Служба журналов.

3.8 Модель прикладного программирования I ARnet.

3.8.1 Интерфейс представителя ресурса на клиентской стороне.

3.8.2 Интерфейс клиента информационной службы.

3.8.3 Пример использования 1 ARnet API для поиска и вызова ресурса.

ГЛАВА 4. ПРИМЕНЕНИЕ IARNET ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ.

4.1 Распределенное решение задачи оптимального управления.

4.1.1 Процедура продолжения оптимальных траекторий.

4.1.2 Основные вычислительные подзадачи.

4.1.3 Символьное представление задачи Коши для системы ОДУ и алгоритм решения.

4.1.4 Требуемые типы ресурсов.

4.1.5 Схема распределенного решения задачи оптимального управления.

4.2 Распределенное решение системы обыкновенных дифференциальных уравнений.

4.2.1 Схема распределенного решения системы ОДУ.

4.3 Распределенная имитационная модель экологической, экономической и социальной динамики.

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

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

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

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

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

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

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

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

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

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

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

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

• Разработка универсальной модели интеграции ресурсов в РВС.

• Разработка набора служб, которые реализуют базовые механизмы, востребованные приложениями и компонентами среды.

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

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

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

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

Затем рассматривается модель доступа к ИАР. Концепция ИАР позволяет определить на уровне прикладного инструментария высокоуровневую модель доступа к ресурсам РВС, удобную для решения в среде декомпозируемых вычислительных задач.

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

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

Во втором параграфе описывается архитектура распределенной вычислительной среды на основе концепции ИАР. Рассматриваются основные уровни данной архитектуры:

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

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

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

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

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

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

Агент доступа в IARnet не решает задачу организации удаленного доступа к ресурсу. Для обеспечения гибкости и расширяемости архитектуры данная задача изолирована в другом компоненте - контейнере ресурсов, который представляет собой среду, в которой развертываются и функционируют агенты доступа. Контейнер обеспечивает удаленный доступ к агентам посредством определенного коммуникационного механизма и технологии ППО. Описывается общая схема устройства контейнера ИАР и процедура развертывания агента доступа в контейнере.

Уровень прикладного API образует клиентская библиотека, которая использует для вызова ресурсов так называемые коннекторы. Клиентская библиотека IARnet представляет собой реализацию интерфейса прикладного программирования (API), который соответствует высокоуровневой модели доступа к ИАР.

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

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

• Информационная служба, осуществляющая сбор и хранение информации о ресурсах и службах РВС;

• Служба рассылки сообщений, реализующая механизм группового взаимодействия ресурсов и уведомлений;

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

• Служба журналов, позволяющая вести единый системный журнал распределенного приложения.

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

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

Во втором параграфе рассматривается механизм идентификации ресурсов РВС. Для идентификации ресурсов в IARnet введено два типа идентификаторов:

• Идентификатор ресурса - уникальный идентификатор ресурса, который не изменяется при перемещении ресурса и изменении способа доступа к нему.

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

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

В третьем параграфе описывается система типов данных IARnet и рассматривается описание интерфейсов (типов) ресурсов.

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

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

Описаны две модели сбора информации о РВС:

• Пассивный сбор или регистрация, при которой информация помещается в репозиторий (публикуется) непосредственно поставщиками информации.

• Активный сбор или опрос, при котором некий механизм производит опрос поставщиков информации, а затем помещает полученную от них информацию в репозиторий.

Рассмотрена целесообразность использования той или иной модели при сборе различной информации о РВС.

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

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

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

• Описание элементарных типовых подзадач, из которых состоит решение исходной

• Описание ресурсов, которые решают указанные подзадачи;

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

• Описание событий, которые могут влиять на ход выполнения алгоритма, и правил их обработки.

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

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

В восьмом параграфе описывается модель прикладного программирования IARnet. Описывается интерфейс представителя ресурса на клиентской стороне для языка Java. Приводится пример программы на языке Java, в которой осуществляется поиск ресурса заданного типа и его вызов.

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

• распределенное решение задачи оптимального управления;

• распределенное решение системы обыкновенных дифференциальных уравнений

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

АО = "(О,

M(x(t))u(t)>N(x(t)),

ХЮ = *„ t е [/0,Г], Т - фиксировано,x(t): R -> Rn,g(x) : R" -> RUn K(x):R"^Rn*\L(x):R"^Ru\M(x):Rn->Rm*'',N(x):Rn->R'"*1. задачи;

ОДУ); г

Процедура продолжения оптимальных траекторий модифицируется для использования её в распределенной среде. Исходная задача декомпозируется на следующие подзадачи:

• задачи математического программирования (МП) - для получения новых режимов в процессе продолжения оптимальной траектории;

• задача Коши для системы ОДУ - для получения траектории вдоль каждого режима;

• поиск корней нелинейных уравнений - для определения моментов переключения режимов.

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

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

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

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

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

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

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

• ресурсы решения задач математического программирования (ЛП и специальных задач);

• ресурс решения задачи Коши указанным методом;

• ресурсы символьного дифференцирования;

• ресурсы решения нелинейных уравнений;

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

Во втором параграфе рассматривается распределенный алгоритм решения системы ОДУ. В качестве примера ситуации, где естественным образом возникает необходимость решения системы ОДУ в распределенной среде, можно указать случай, когда компоненты правой части системы заданы не аналитически, а являются выходами некоторых сложных имитационных моделей или программно-аппаратных комплексов, которые затруднительно переместить из одного места в другое. Для решения системы ОДУ в РВС применен вычислительный алгоритм, который позволяет минимизировать накладные расходы, связанные с сетевым обменом данными между решателями. Описаны необходимые типы ресурсов и приведен сценарий координированного использования указанных ресурсов для решения системы ОДУ в среде на базе 1А11пе1:.

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

При создании распределенной имитационной модели, минимальные наборы компонентов модели ЭСЕИМ, которые могли быть размещены на одной рабочей станции, рассматривались как единый ИАР. В результате, были выделены три типа ресурсов: модель страны (региона), база демографических данных и модель внешнего мира. Кроме того, был предусмотрен еще один ресурс - информационный сервер. Это программный модуль, задачей которого является общее управление процессом моделирования на заданном интервале времени, а именно, задание начального и финального года модельного интервала; начало/завершение эксперимента; координация работы всех остальных ресурсов при совершении «шага» моделирования и, наконец, отображение результатов моделирования. Приводится сценарий координированного использования указанных ресурсов для проведения имитационного эксперимента в РВС.

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

Основные выводы и результаты диссертационной работы, выносимые на защиту, состоят в следующем:

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

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

3. Описана универсальная модель интеграции ресурсов в распределенную вычислительную среду.

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

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

Научная новизна складывается из следующих результатов:

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

• Разработан прототип распределенной информационно-алгоритмической среды, реализующей этот подход.

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

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

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

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

ЗАКЛЮЧЕНИЕ

1. Афанасьев А.П. Линейные по управляющим воздействиям задачи оптимальногоуправления. М., 1980. (Препринт / ВНИИСИ)

2. Афанасьев А.П. Обобщенная изопериметрическая задача на многограннике //

3. Дифференциальные уравнения, 1993, Т. 29, № 11, с. 1856-1867.

4. Афанасьев А.П., Ваньков А.И, Волошинов В.В., Кривцов В.Е., Попков Е.Ю., Шляев

5. П.Г. // Современные технологии построения распределенных программных систем. Труды ИСА РАН. М.: Эдиториал УРСС, 2001.

6. Афанасьев А.П., Волошинов В.В., Кривцов В.Е., Рогов C.B., Сухорослов О.В.

7. Использование информационно-алгоритмических ресурсов для организации распределенных вычислений. // Проблемы вычислений в распределенной среде: организация вычислений в глобальных сетях. Труды ИСА РАН. M.: РОХОС, 2004, с. 106-144.

8. Афанасьев А.П., Волошинов В.В., Рогов C.B., Сухорослов О.В. Развитие концепциираспределенных вычислительных сред. // Проблемы вычислений в распределенной среде: организация вычислений в глобальных сетях. Труды ИСА РАН. М.: РОХОС, 2004, с.6-105.

9. Афанасьев А.П., Дикусар В.В., Милютин A.A., Чуканов С.А. Необходимое условие воптимальном управлении. М.: Наука, 1990.

10. Афанасьев А.П., Сухорослов О.В. Использование информационно-алгоритмическихресурсов в Grid-вычислениях. // Прикладные проблемы управления макросистемами. Труды ИСА РАН. Том 8. М.: Едиториал УРСС, 2004, с.32-48.

11. Белотелов Н.В., Бродский Ю.И., Оленев H.H., Павловский Ю.Н. Эколого-социальноэкономическая модель: гуманитарный и информационный аспекты // Информационное общество. № 6. 2001. С. 43-51.

12. Бродский Ю. И., Гринберг Я. Р., Павловский Ю. Н. Имитационное моделирование в распределенной информационно-вычислительной среде // Проблемы вычислений в распределенной среде: прикладные задачи. Труды ИСА РАН. М.: РОХОС, 2004, с. 95-110

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

14. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Д. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2001.

15. Коваленко В., Коваленко Е. Пакетная обработка заданий в компьютерных сетях. // Открытые системы, 2000, №7-8.

16. Коваленко В., Коваленко Е., Корягин Д., Любимскнй Э., Хухлаев Е. Управление заданиями в распределенной вычислительной среде. // Открытые системы, 2001, №56.

17. Коваленко В., Корягин Д. Вычислительная инфраструктура будущего. 11 Открытые системы, 1999, №11-12.

18. Коваленко В., Корягин Д. Эволюция и проблемы Grid. // Открытые системы, 2003, №1.

19. Котов В.Е. Сети Петри. М.: Наука, 1984.

20. Кривцов В.Е., Попков Е.Ю. Схема распределенного решения системы дифференциальных уравнений. // Проблемы вычислений в распределенной среде: прикладные задачи. Труды ИСА РАН. М.: РОХОС, 2004, с. 126-134.

21. Лазарев И.В., Сухорослов О.В. Использование workflow-методологии для описания процесса распределенных вычислений. // Проблемы вычислений в распределенной среде. Труды ИСА РАН. М.: УРСС, 2005.

22. Милютин A.A., Дмитрук A.B., Осмоловский Н.П. Принцип максимума в оптимальном управлении. М.: Изд-во Центра прикладных исследований при механико-математическом факультете МГУ, 2004, 168 с.

23. Оленев H.H., Решетцева Е.В., Саранча Д.А. Модель взаимодействия демографических и экономических процессов (рождаемость, образованность, благосостояние). М.: ВЦ РАН. 1997, 26с.

24. Петров A.A., Поспелов И.Г., Шананин A.A. Опыт математического моделирования экономики. М.: Энергоатомиздат, 1996, 558с.

25. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984. Прототип ДИАР, ЕИС РАН,http://uis.isir.ras.ru/win/htm/scientificactivity .html?p=5p6p4

26. Сухорослов О.В. Имитационное моделирование пиринговых систем. // Проблемы вычислений в распределенной среде: прикладные задачи. Труды ИСА РАН. М.: РОХОС, 2004, с.44-94.

27. Сухорослов О.В. Пиринговые системы: концепция, архитектура и направления исследований. // Проблемы вычислений в распределенной среде: прикладные задачи. Труды ИСА РАН. М.: РОХОС, 2004, с.7-43.

28. Цимбал А. Технология CORBA. СПб.: Питер, 2001.

29. Цимбал А., Аншина М. Технологии создания распределенных систем. СПб.: Питер, 2003.

30. Эммерих В. Конструирование распределенных объектов. М.: Мир, 2002.

31. Abramson, D., Sosic, R., Giddy, J., and Hall, B. Nimrod: A tool for performing parameterised simulations using distributed workstations. In Proc. 4th IEEE Symp. on High Performance Distributed Computing. IEEE Computer Society Press, 1995.

32. Apache Axis, The Apache SOAP Project, http://ws.apache.org/axis/

33. Berners-Lee, T., Hendler, J. and Lassila, O. The Semantic Web. Scientific American, 284(5), pp. 34-43, May 2001.

34. Birman, K. P. and van Rennesse, R. Reliable Distributed Computing Using the Isis Toolkit. IEEE Computer Society Press, 1994.

35. Bray, T.; Paoli, J.; Sperberg-McQueen, C. M.; and Maler, E. (eds.). Extensible Markup Language (XML) 1.0 (Second Edition), W3C, 2000.

36. Casanova, H. and Dongarra, J. NetSolve: A Network Server for Solving Computational Science Problems. International Journal of Supercomputer Applications and High Performance Computing, 11 (3). 212-223. 1997.

37. Catlett, C. and Smarr, L. Metacomputing. Communications of the ACM, 35 (6). 44-52. 1992.

38. Chamberlin, D. Xquery 1.0: An XML Query Language. W3C Working Draft 07, 2001.

39. Common Object Request Broker Architecture (CORBA/IIOP). Version 3.0.2. Object Management Group. 2004.

40. Condor Project, http://www.cs.wisc.edu/condor/

41. CORBA Component Model. Revision 3.0. Object Management Group, 2002.

42. CORBA. http://www.corba.org/

43. Czyzyk, J., Mesnier, M.P., and More, J.J. The Network-Enabled Optimization System (NEOS) Server. Preprint MCS-P615-0996, Argonne National Laboratory, Argonne, Illinois, 1996.

44. DAML+OIL Reference Description, Connolly D., van Harmelen F., Horrocks I., McGuinness D.L., Patel-Schneider P.F., Stein L.A., World Wide Web Consortium, 2001.

45. DCE 1.1: Remote Procedure Calls. The Open Group, 1997.49 5051 52 [5354