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

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

Лазарев Игорь Валентинович

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

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

АВТОРЕФЕРАТ

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

Москва-2009

003490828

Работа выполнена в Учреждении Российской академии наук Институте системного анализа РАН в Центре Грид-технологий и распределенных вычислений

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

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

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

Сигал Израиль Хаимович

кандидат физико-математических наук Бритков Владимир Борисович

Ведущая организация: Учреждение Российской академии наук

Институт проблем управления им. В.А. Трапезникова РАН

Защита состоится « 15» февраля 2010 г. в 11— часов на заседании диссертационного совета Д 002.086.02 при Учреждении Российской академии наук Институте системного анализа Российской Академии наук, по адресу: 117312, Москва, проспект 60-летия Октября, 9.

С диссертацией можно ознакомиться в научной библиотеке Учреждения Российской академии наук Институте системного анализа Российской Академии наук (г. Москва, проспект 60-летия Октября, 9).

Отзывы на автореферат, заверенные печатью, просим направлять по адресу: 117312, Москва, проспект 60-летия Октября, 9, диссертационный совет Д 002.086.02. ■

Автореферат разослан «12» января 2010 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

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

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

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

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

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

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

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

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

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

В диссертации идет речь о применении методологии сценариев в рамках двух распределенных вычислительных сред — ГАЯле! и МаШС1оис1. Обе эти среды основаны на сервис-ориентированном подходе. В основе архитектуры 1АЯпе1 лежит понятие информационно-алгоритмического ресурса, представляющего собой абстрактный ресурс с четко описанной функциональностью и программным интерфейсом удаленного доступа к этой функциональности, скрывающим за собой один или несколько первичных ресурсов. Отличительными особенностями ЬШпе^ являются высокоуровневая модель программирования и возможность использования различных технологий для удаленного доступа к ресурсам. Среда Ма&С1оис1 является развитием заложенного в 1АКпе1 подхода к интеграции

высокоуровневых информационно-алгоритмических ресурсов на основе Web-технологий и архитектурного стиля REST (Representational State Transfer), являющегося перспективной альтернативой технологиям веб-сервисов.

Цель работы и задачи исследования.

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

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

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

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

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

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

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

• На основе указанного подхода разработана инфраструктура для организации взаимодействия между геометрическими сервисами МаШСоис!, основанными на известном пакете Ап^ргтап.

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на семинарах в Институте системного анализа, а также на конференции «Системный анализ и информационные технологии -2005», конференции «Системный анализ и информационные технологии -2007», на третьей международной конференции "Distributed Computing and Grid-technologies in Science and Education", на конференции «Научный сервис в сети Интернет - 2009», на 52 научной конференции МФТИ и на конференции "Современные информационные технологии и ИТ-образование -2009».

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

Структура и объем работы. Общий объем диссертации состоит из

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

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

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

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

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

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

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

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

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

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

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

• Выбор существующего или разработка собственного графического языка для описания сценариев

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

• Создание среды выполнения распределенных вычислительных процессов (интерпретатор описаний сценариев).

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

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

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

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

Архитектура СУС состоит из следующих частей:

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

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

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

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

Так, первый параграф главы посвящен первой реализации СУС, использующей в качестве языка графического описания скриптово-графический язык BPEL, являющийся стандартом де-факто для описания бизнес-процессов на основе веб-сервисов, и программного пакета Collaxa BPEL (в настоящий момент принадлежит компании Oracle). В этом параграфе описываются основные конструкции языка BPEL и особенности архитектуры данной версии СУС, связанные с выбором этого языка. В частности, вычислительные ресурсы и компоненты службы в данном случае реализованы в виде веб-сервисов, описываемых с помощью языка WSDL. Сам сценарий описывается в графическом редакторе, после чего создается файл в XML-формате языка BPEL.

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

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

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

В начале параграфа описывается архитектура данной реализации СУС, состоящая как из уже готовых встроенных средства Renew, так и из написанных с нуля компонентов. К числу первых относятся:

• графический интерфейс Renew, через который происходит взаимодействие пользователя с СУС;

• интерпретирующие компоненты Renew, посредством которых осуществляется интерпретация сценария.

К числу вторых принадлежат:

• дополнительный модуль Renew WfMS Plugin, добавленный в графический интерфейс Renew обеспечивающий взаимодействие Renew и СУС на стороне Renew;

• реализация СУС Renew-WfMS - часть IARnet, предназначенная для взаимодействия с Renew и реализованная в виде сервиса;

• Сервис сценария, прикрепленный к Renew Simulation Server для того, чтобы сценарий мог принимать и отправлять вызовы через СУС.

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

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

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

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

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

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

Исходя из указанных выше соображений, было решено перейти к разработке собственной СУС, основанной на модели потоков данных и

подходе REST. Данная реализация описывается в третьем параграфе третьей главы.

Несмотря на то, что СУС создается как универсальная система и предназначена для использования в различных распределенных средах, текущая реализация СУС активно используется в распределенной среде Mathcloud и частично опирается на её архитектуру, в частности на REST-интерфейс этой среды.

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

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

Составные части текущей реализации СУС:

• Редактор сценариев предназначен для взаимодействия пользователей с СУС.

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

• Среда выполнения сценариев осуществляет обработку запросов к сервисам-сценариям.

Редактор сценариев СУС реализован в виде веб-приложения на языке JavaScript. Такая конфигурация позволяет сделать пользовательский интерфейс нетребовательным к ресурсам и предельно переносимым.

В данном параграфе дано подробное описание интерфейса этого веб-приложения и принципов его работы.

Основными функциями редактора являются просмотр и редактирование сценариев. Кроме того, созданный с помощью редактора сценарий может быть сохранен и запущен на выполнение на серверной стороне. При этом в редакторе отображается состояние выполнения сценария. Обмен информацией между редактором и остальными частями СУС происходит с помощью AJAX-запросов, производящих обмен данными в формате JSON. Этот формат выбран как наиболее естественно сочетающийся с языком JavaScript и более приспособленный для чтения человеком, чем, к примеру, распространенный язык разметки XML, чаще всего используемый для аналогичных целей.

Далее в диссертации описывается архитектура сервиса управления сценариями СУС. Сервис управления сценариями реализует удаленный программный интерфейс для хранения сценариев, созданных с помощью редактора, а также осуществляет развертывание сохраненных сценариев в виде новых сервисов. Интерфейс сервиса образован совокупностью идентифицируемых при помощи URI ресурсов, поддерживающих стандартные методы протокола HTTP. Структура этих ресурсов и описываемых ими вызовов подробно описана в данном параграфе диссертации.

В конце параграфа описывается среда выполнения сценариев СУС. Среда выполнения сценариев осуществляет обработку запросов к сервисам-

сценариям путем интерпретации описания сценария с заданными значениями входных параметров.

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

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

В частности, речь идет о библиотеке для работы с трехмерными объектами Antiprism, инструменты которой реализованы в виде сервисов среды MathCloud и теперь могут быть легко организованы в сценарии при помощи веб-интерфейса СУС. В результате выполненной работы стало возможным использовать данную библиотеку удаленно, без установки на локальный компьютер. Это избавляет пользователя от необходимости следить за зависимостями данной библиотеки и поддерживать её в рабочем состоянии. Более того, существенно упростилась работа с библиотекой, которая стала возможной для пользователей с минимальной квалификацией благодаря интуитивности веб-интерфейса СУС. Появилась возможность сохранения конфигурации взаимодействия модулей пакета Antiprism, загружать сохраненные конфигурации и оперативно вносить в них необходимые изменения, не покидая веб-браузер.

В дальнейшем планируется создание отдельного полноценного образовательного Интернет-сайта для изучения стереометрии с использованием СУС и сервисов среды MathCloud, созданных на основе

пакета Апирпвт. Учащиеся и преподаватели получат наглядный инструментарий для работы с трехмерными объектами.

Рис. 1 Сценарий генерации и обработки многогранника, основанный на сервисах АпЬрпвт

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

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

Для решения данной задачи были созданы следующие сервисы среды МаШС1ои±

• Сборщик модели Сепега1ог2. Составляет из исходных данных математическую модель задачи в формате 1р

• Солвер 1р_$о1уе_1р_оп1у. реализует решение задачи линейного программирования симплекс-методом.

• Солвер 1р_во1уе. Реализует решение М1Р-задачи методом ветвей и границ

• Преобразователь 1р2тр$. Преобразует файлы моделей линейного программирования формата 1р в файлы формата трэ.

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

• Альтернативный солвер й1рк. Реализует решение М1Р-задачи методом ветвей и границ

• Сервис постобработки Ро$1Ке<1Ьр. Создает удобный для

восприятия человеком отчет о работе сервисов 1р_Бо1уе и

1р_5оК'е_1р_оп1у на основе их выходных данных.

При помощи СУС было реализовано координированное использование данных сервисов для решения исходной задачи. Графический вид сценария решения этой задачи приведен на Рис. 2

Рис. 2 Сценарий решения задачи о перевозках

И, наконец, в работе описывается использование СУС для построения

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

матриц большой размерности.

Одной из типичных задач вычислительной математики является

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

Ах = у,1бК*, уеК", А=[а \т = 1: Я,п = 1: N .

' ' 1 ' , где матрица А является т.н.

плохо обусловленной.

( 2У/2

соп<1(А) = ||А||||А-1| 1А1 = [Х»..Е!,1(а») ]

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

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

«л- ЧАДи, А, =^ГТ « 1.6-10'5из соображений

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

Пусть М[Ых>1] - невырожденная квадратная матрица. Предположим, что М разбита на четыре блока {А, и, V, В}, как показано ниже.

Дополнением Шура для такого представления называют квадратную матрицу 8 = В-УА 'и.

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

,, , ГА""1 + А^ив^УА"1 -А^ив"1

м = ,1 ,

-в-'УА"1 в"1

Легко заметить, что, проводя вычисления по «отдельным блокам», можно получить более гибкий для дальнейшего распараллеливания «рекурсивный» алгоритм, т.к. вычисления А'1 , Б'1 и всех произведений матриц также поддаются распараллеливанию.

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

ли

УВ

в результате различных «расстановок скобок» в стоящем справа произведении матриц.

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

одинакового размера

N N — х —

2 2 -I; все арифметические операции выполняются с фиксированной ограниченной точностью.

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

4УУ5 4

—; - : 130%, N7 1

W + 2N2 ' 3

А1

YA11[ A'U VA-'U B-V.V'I" S"1

=>Ч)({«/:)')

(PujS7) S-4VA »>11 (.4"fTJ)S 1 =>

pyj^-iT • W') 1 (^Щ^Щ AWYA-' ->

_ ______

AT1 + Л'ЧЙг'УА"11 A ^+A^'VA'1 => -OtfV)

Рис. 3 Схема и оценки трудоемкости сценария блочной декомпозиции

Для реализации данного распределенного алгоритма в качестве сценария в СУ С были созданы следующие сервисы среды MathCloud:

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

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

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

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

. 4 Сценарий безошибочного обращения плохо о^еяовлеииых матриц, реализованный в СУ С

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

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

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

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

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

5. В рамках апробации созданной СУС реализована схема распределенного решения смешанно-целочисленной задачи нелинейного программирования для моделирования железнодорожных перевозок.

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

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

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

[1] Лазарев И.В., Сухорослов О.В. Использование workflow-методологии для описания

процесса распределенных вычислений. // Проблемы вычислений в распределенной среде: Модели обработки и представления данных. Динамические системы. Труды ИСА РАН. Том 14. - М.: КомКнига, 2005, с.26-70.

[2] Лазарев И.В., Сухорослов О.В. Описание и выполнение распределенных

вычислительных сценариев. // Первая международная конференция "Системный анализ и информационные технологии" САИТ-2005 (12-16 сентября 2005г., Переславль-Залесский, Россия): Труды конференции. В 2 т. Т. 2. - М.: КомКнига, 2005, с.211-217.

[3] Сухорослов О.В., Лазарев И.В. Реализация службы управления сценариями в

распределенной вычислительной среде. // Проблемы вычислений в распределенной среде: распределенные приложения, коммуникационные системы, математические модели и оптимизация. Труды ИСА РАН. Т. 25. - М.: КомКнига, 2006, с.77-98.

[4] Лазарев И.В., Сухорослов О.В. Оценка применимости существующих wotkflow-систем

для описания и выполнения распределенных вычислительных процессов. // Вторая международная конференция «Системный анализ и информационные технологии» САИТ-2007 (10-14 сентября 2007 г., Обнинск, Россия): Труды конференции. В2 т. Т.2. -М.: Издательство ЛКИ, 2007, с.166-169.

[5] I. Lazarev, О. Sukhoroslov. On Development of Workflow Management Service for

Distributed Computations. // 3rd International Conference "Distributed Computing and Grid-technologies in Science and Education", GRID'2008, Dubna, Russia, 30 June - 4 July, 2008.

[6] Афанасьев А.П., Сухорослов O.B., Тарасов A.C., Лазарев И.В., Астафьев А.С. Научная

сервис-ориентированная среда на основе технологий Web и распределенных вычислений. // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской научной конференции (21-26 сентября 2009 г., г. Новороссийск). - М.: Изд-во МГУ, 2009, с. 463-467.

[7] Лазарев И.В., Сухорослов О.В. Реализация распределенных вычислительных

сценариев в среде MalhCIoud. // Проблемы вычислений в распределенной среде / Под ред. С.В. Емельянова, А.П. Афанасьева. Труды ИСА РАН. Т. 46.2010. - Принято к публикации.

[8] Лазарев И.В. Разработка службы управления вычислительными сценариями для распределенных сред. // Труды 52-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Часть IX. Инновации и высокие технологии. - М.: МФТИ, 2009, с 22-25.

[9] Лазарев И.В. Разработка редактора вычислительных сценариев для распределенных сред. //Современные информационные технологии и ИТ-образование. Сборник докладов научно-практической конференции: учебно-методическое пособие. Под ред. проф. В. А. Сухомлина - М.:ИНТУИТ.РУ, 2009, с 783-790.

Подписано в печать:

29.12.2009

Заказ № 3228 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

содержание. список сокращений. введение.

глава 1. workflow-методология: обзор основных понятий, подходов и технологий.

1.1 workflow-методология. основные понятия и стандарты.

1.1.1 Основные понятая.

1.1.2 Производственные и научные сценарии.

1.1.3 Стандарты в области систем управления сценариями.

1.2 Способы описания сценариев.

1.2.1 Скриптовые языки.

1.2.2 Представление сценариев в виде графов.

1.2.3 Смешанные подходы.

1.2.4 Модели, ориентированные на потоки данных.

1.3 Обзор существующих workflow-систем.

1.3.1 GridAnt.

1.3.2 Karajan.

1.3.3 Condor DÂGMan.

1.3.4 jFern.

1.3.5 Petri Net Kernel.

1.3.6 Renew.

1.3.7 YAWL.

1.3.8 eXeGrid.

1.3.9 Business Process Execution Language for Web Services.

1.3.10 jOpera.

1.3.11 jBPM.

1.3.12 Triana.

1.3.13 Kepler.

1.3.14 Taverna.

1.3.15 Yahoo! Pipes.

1.4 Обзор научных приложений workflow-методологии.

1.4.1 Проект EMBRACE.

1.4.2 Проект MIASGrid.

1.4.3 Анализ бактерий сибирской язвы.

1.4.4 Измерение характеристик ферментов у дрожжей.

1.5 Задачи работы.

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

2.1 Сервис-ориентированная архитектура.

2.1.1 Концепция SO А.'.

2.1.2 Алгоритмические сервисы.

2.1.3 Базовы s технологии SO А.

2.2 Функциональность службы управления сценариями.

2.3 Архитектура службы управления сценариями.

2.4 Жизненный цикл сценария.

2.4.1 Развертывание сценария.

2.4.2 Запуск сценария на выполнение.

2.4.3 Получение результатов и контроль состояния выполнения сценария.

2.5 Требования к реализации службы управления сценариями.

глава 3. реализации службы управления сценариями.

3.1 Реализация распределенного вычислительного сценария на языке BPEL.

3.1.1 Общие соображения.

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

3.1.3 Перенос алгоритма на BPEL.

3.1.4 Cxe.ua физической реализации тестового прототипа.

3.1.5 Ход эксперимента.

3.1.6 Выводы.

3.2 Реализация прототипа СУС IARnet на основе формализма сетей Петри.

3.2.1 Реализация прототипа СУС IARnet.

3.2.2 Тестирование прототипа СУС IARnet.

3.2.3 Результаты вычислительных экспериментов.

3.2.4 Измерения пропускной способности СУС.

3.2.5 Выводы.

3.3 Текущая реализация СУС.

3.3.1 Архитектура системы.

3.3.2 Редактор сценариев.

3.3.3 Сервис управлен ия сценариями.

3.3.4 Среда выполнения сценариев.

глава 4. применение службы управления сценариями для решения прикладных задач.

4.1 Графическая среда для работы с трехмерными моделями на основе пакета Antiprism.

4.2 Моделирование железнодорожных перевозок.

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

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

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

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

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

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

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

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

В диссертации идет речь о применении методологии сценариев в рамках двух распределенных вычислительных сред — IARnet и MathCloud. Обе эти среды основаны на сервис-ориентированном подходе. В основе архитектуры IARnet лежит понятие информационно-алгоритмического ресурса, представляющего собой абстрактный ресурс с четко описанной функциональностью и программным интерфейсом удаленного доступа к этой функциональности, скрывающим за собой один или несколько первичных ресурсов. Отличительными особенностями IARnet являются высокоуровневая модель программирования и возможность использования различных технологий для удаленного доступа к ресурсам. Среда MathCloud является развитием заложенного в IARnet подхода к интеграции высокоуровневых информационно-алгоритмических ресурсов на основе Web-технологий и архитектурного стиля REST (Representational State Transfer), являющегося перспективной альтернативой технологиям WS-сервисов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Выбор существующего или разработка собственного графического языка для описания сценариев

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

• Создание среды выполнения распределенных вычислительных процессов (интерпретатор описаний сценариев).

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

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

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

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

Архитектура СУС состоит из следующих частей:

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

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

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

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

Так, первый параграф главы посвящен первой реализации СУС, использующей в качестве языка графического описания скриптово-графический язык BPEL, являющийся стандартом де-факто для описания бизнес-процессов на основе WS-сервисов, и программного пакета Collaxa BPEL (в настоящий момент принадлежит компании Oracle). В этом параграфе описываются основные конструкции языка BPEL и особенности архитектуры данной версии СУС, связанные с выбором этого языка. В частности, вычислительные ресурсы и компоненты службы в данном случае реализованы в виде WS-сервисов, описываемых с помощью языка WSDL. Сам сценарий описывается в графическом редакторе, после чего создается файл в XML-формате языка BPEL.

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

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

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

В начале параграфа описывается архитектура данной реализации СУС, состоящая как из уже готовых встроенных средства Renew, так и из написанных с нуля компонентов. К числу первых относятся:

• графический интерфейс Renew, через который происходит взаимодействие пользователя с СУС;

• интерпретирующие компоненты Renew, посредством которых осуществляется интерпретация сценария.

К числу вторых принадлежат:

• дополнительный модуль Renew WfMS Plugin, добавленный в графический интерфейс Renew обеспечивающий взаимодействие Renew и СУС на стороне Renew;

• реализация СУС Renew-WfMS - часть IARnet, предназначенная для взаимодействия с Renew и реализованная в виде сервиса;

• Сервис сценария, прикрепленный к Renew Simulation Server для того, чтобы сценарий мог принимать и отправлять вызовы через СУС.

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

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

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

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

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

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

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

Несмотря на то, что СУС создается как универсальная система и предназначена для использования в различных распределенных средах, текущая реализация СУС активно используется в распределенной среде Mathcloud и частично опирается на её архитектуру, в частности на REST-интерфейс этой среды.

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

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

Составные части текущей реализации СУС:

• Редактор сценариев предназначен для взаимодействия пользователей с СУС.

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

• Среда выполнения сценариев осуществляет обработку запросов к сервисам-сценариям.

Редактор сценариев СУС реализован в виде веб-приложения на языке JavaScript. Такая конфигурация позволяет сделать пользовательский интерфейс нетребовательным к ресурсам и предельно переносимым.

В данном параграфе дано подробное описание интерфейса этого веб-приложения и принципов его работы.

Основными функциями редактора являются просмотр и редактирование сценариев. Кроме того, созданный с помощью редактора сценарий может быть сохранен и запущен на выполнение на серверной стороне. При этом в редакторе отображается состояние выполнения сценария. Обмен информацией между редактором и остальными частями СУС происходит с помощью AJAX-запросов, производящих обмен данными в формате JSON. Этот формат выбран как наиболее естественно сочетающийся с языком JavaScript и более приспособленный для чтения человеком, чем, к примеру, распространенный язык разметки XML, чаще всего используемый для аналогичных целей.

Далее в диссертации описывается архитектура сервиса управления сценариями СУС. Сервис управления сценариями реализует удаленный программный интерфейс для хранения сценариев, созданных с помощью редактора, а также осуществляет развертывание сохраненных сценариев в виде новых сервисов. Интерфейс сервиса образован совокупностью идентифицируемых при помощи URI ресурсов, поддерживающих стандартные методы протокола HTTP. Структура этих ресурсов и описываемых ими вызовов подробно описана в данном параграфе диссертации.

В конце параграфа описывается среда выполнения сценариев СУС. Среда выполнения сценариев осуществляет обработку запросов к сервисам-сценариям путем интерпретации описания сценария с заданными значениями входных параметров.

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

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

В частности, речь идет о библиотеке для работы с трехмерными объектами Antiprism, инструменты которой реализованы в виде сервисов среды MathCloud и теперь могут быть легко организованы в сценарии при помощи веб-интерфейса СУС. В результате выполненной работы стало возможным использовать данную библиотеку удаленно, без установки на локальный компьютер. Это избавляет пользователя от необходимости следить за зависимостями данной библиотеки и поддерживать её в рабочем состоянии; Более того, существенно упростилась работа с библиотекой, которая стала возможной для пользователей с минимальной квалификацией благодаря интуитивности веб-интерфейса СУС. Появилась возможность сохранения конфигурации взаимодействия модулей пакета Antiprism, загружать сохраненные конфигурации и оперативно вносить в них необходимые изменения, не покидая веб-браузер.

В дальнейшем планируется создание отдельного полноценного образовательного Интернет-сайта для изучения стереометрии с использованием СУС и сервисов среды MathCloud, созданных на основе пакета Antiprism. Учащиеся и преподаватели получат наглядный инструментарий для работы с трехмерными объектами.

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

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

Для решения данной задачи был создан ряд REST-сервисов. Организация взаимодействия этих сервисов для решения исходной задачи была организована при помощи СУС.

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

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

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

В ближайшее время, после реализации в виде сервисов среды MathCloud ресурсов системы BNB-Grid [5], станет возможным решение при помощи СУС многих классов задач, решаемых при помощи этой системы, в частности задачи коммивояжера [23].

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

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

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

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

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

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

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

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

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

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

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

2. В качестве сервисной архитектуры выбрана архитектура среды MathCloud, основанная на архитектурном стиле REST.

3. Создана среда выполнения распределенных вычислительных процессов (интерпретатор описаний сценариев).

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

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

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

ЗАКЛЮЧЕНИЕ

1. Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов.//ВМК МГУ.1. Москва, 2000.'

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

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

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

5. Гергель В.П. Теория и практика параллельных систем. // -М.: Интернет-Университет Информационных технологий; БИНОМ; Лаборатория знаний.,2007

6. Коптелов А., Голубев В. Сервис-ориентированная архитектура: от концепции к применению, http://\vww.bytemag.ru/articles/detail.php?ID=12160

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

8. Лазарев И.В., Сухорослов О.В. Реализация распределенных вычислительных сценариев в среде МаШС1оис1//Труды ИСА РАН. Т. 33, 2009 — Принято к публикации.

9. Лестэр Информационные технологии, http://www.lester.ru/

10. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984.

11. Рубцов А.О., Тарасов A.C. Моделирование железнодорожных перевозок на территории России //Труды ИСА РАН. Т. 33, 2009 Принято к публикации.

12. Сигал И. X. Декомпозиционный подход к решению задачи коммивояжера большой размерности и некоторые его приложения // Известия АН СССР. Техническая кибернетика, 1990.

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

14. Сухорослов O.B. Унифицированный интерфейс доступа к алгоритмическим сервисам в Web //Труды ИСА РАН. Т. 33,2009 Принято к публикации.

15. Тарасов A.C. Распределенная математическая среда на основе IARnet. Сб. трудов ИСА РАН, «Проблемы вычислений в распределенной среде: распределенные приложения, коммуникационные системы, математические модели и оптимизация», 2007г.

16. Aleksander Slomiski. On Using BPEL Extensibility to Implement OGSI and WSRF Grid Workflows. GGF 10 Grid Work Flow Workshop, 2004.

17. Antiprism Polyhedron Modelling Software, http://antiprism.com/index.html31 . Apache Ant, http://ant.apache.org/

18. BeanShell Lightweight Scripting for Java, http://www.beanshell.org/

19. BPEL4WS (Business Process Execution Language for Web Services) by Francisco Curbera, Frank Leymann, Rania Khalaf. IBM, 2003.

20. BPWS4J, http://www.alphaworks.ibm.com/tech/bpws4j/

21. Business Process Execution Language for Web Services: Version 1.1. http://www-106.ibm.com/developerworks/webservices/library/ws-bpel/

22. Business Process with BPEL4WS: Summary. http://www-106.ibm.com/developerworks/library/ws-bpelcol.html

23. Cactus, http://www.cactuscode.org/38. caGrid Project, http://cagrid.org/display/cagridhome/Home

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

25. Discovery Net project, http://www.discovery-on-the.net/41. eXeGrid homepage: http://www.exegrid.net/

26. Fielding, R.T. Architectural styles and the design of network-based software architectures. PhD Dissertation. Dept. of Information and Computer Science, University of California, Irvine, 2000.

27. Flux Workflow, http://www.fluxcorp.com

28. Fraunhofer Resource Grid homepage, http://www.fhrg.fhg.de/

29. Fraunhofer-Allianz Grid Computing, http://www.grid.fraunhofer.de/

30. Fraunhofer-Gesellshaft, http://www.fraunhofer.de/en/

31. Freefluo Workflow Enactor, http://freefluo.sourceforge.net/

32. Globus Project, http://www.globus.org/

33. Graph-oriented programming, http://docs.jboss.com/jbpm/v3/userguide/graphorientedprogramming.html

34. Grid Workflow: Karajan, http://www.gridworkflow.org/snips/gridworkflow/space/Karajan

35. GridAnt, http://www-unix.globus.org/cog/projects/gridant/

36. GridLab: Grid Application Toolkit and Testbed. http://www.gridlab.org/

37. Grimshaw, A.S. and Wulf, W.A. The Legion Vision of a Worldwide Virtual Computer. Communications of the ACM, 40 (1). 39-45. 1997.

38. Inputex Field Framework for Web Applications, http://javascript.neyric.coni/inputex/

39. JavaScript Object Notation, http://www.json.org/

40. JBoss jBPM, http://www.jboss.com/products/jbpm58. jOpera, http://www.jopera.ethz.ch/

41. JXTA Project, http://www.jxta.org/

42. Kavantzas, N., et al.: Web Services Choreography Description Language

43. Kepler: An Extensible System for Scientific Workflows, http://kepler.ecoinformatics.org

44. Manchester Centre for Integrative Systems Biology, http://www.mcisb.org/

45. Moteur, http://modalis.polytech.unice.fr/softwares/moteur/start64. myGrid Project, http://www.mygrid.org.uk/65. myGrid Success Stories, http://www.taverna.org.uk/introduction/success-stories/

46. NEOS Server for Optimization, http://www-neos.mcs.anl.gov/

47. Oracle BPEL, http://www.oracle.com/appserver/bpelhome.html

48. Petri Net Kernel, http://www.informatik.hu-berlin.de/top/pnk/index.htmI

49. Petri Nets Tool Database, http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/db.html

50. Production Workflows. Leyman, Roller. Prentice Hall PTR, 1999.

51. Ptolemy II, http://ptolemy.eecs.berkeley.edu/ptolemyII/

52. RaikurajFern, http://sourceforge.net/projects/jfern

53. Renew, http://www.renew.de/

54. SCIRun, Scientific Computing and Imaging Institute, University of Utah. http://software.sci.utah.edu/scirun.html75 76 [77 [78 [798081 82 [83 [84 [8586 87 [88 [89 [9091 92 [93 [94 [95 [96 [97 [98 [99

55. Scitegic Pipeline Pilot, http://www.scitegic.com/productsservices/pipelinepilot.htni SOAP Specifications, http://www.w3.org/TR/soap/ Symphony, http://zuni.cs.vt.edu/symphony/ Taverna Workflow System, http://www.taverna.org.uk/

56. The Application of Petri Nets to Workflow Management. W.M.P. van der Aalst. The Journal of Circuits, Systems and Computers, 1998.

57. The State of Workflow. Tom Baeyens, http://www.theserverside.com/tt/articles/article.tss?l=Workflow

58. The Taverna Project, http://taverna.sourceforge.net/

59. The Yahoo User Interface, http://developer.yahoo.com/yui/

60. Triana, http://www.triana.co.uk/

61. UNICORE, http://unicore.sourceforge.net/

62. User Tools and Languages for Graph-Based Workflows. Andreas Hoheisel, Fraunhofer Institute for Computer Architecture and Software Technology (FIRST), 2004.1. Version 1.0 (2005)

63. Web Service Definition Language, http://www.w3.org/TR/wsdl

64. WfMC Workflow Handbook. Future Strategies Inc, 2002.

65. Wirelt a JavaScript Wiring Library, http://javascript.neyric.com/wireit/

66. Wolfgang Reisig. Elements of Distributed Algorithms: Modelling and Analysis with Petri Nets. Springer-Verlag, 1998.

67. XLANG specification, http://www.gotdotnet.com/team/xmlwsspecs/xlang-c/default.htm Yahoo Pipes, http://pipes.yahoo.com/

68. YAWL:Yet Another Workflow Language, http://www.yawl-system.com/