Содержание к диссертации
Введение
1 Особенности функционирования интеллектуальных систем поддержки принятия решений разработчика вычислительных приложений в среде Грид Л.. 7
1.1 Анализ современных тенденций в области Грид-вычислений 7
1.2 Интеллектуальный подход к проектированию приложений в Грид 17
1.3 Анализ современных подходов к представлению информации о производительности в Грид 25
1.4 Выводы к главе 1 28
2 Приобретение экспертных знаний в форме параметрических моделей производительности, идентифицируемых на основе обработки данных 30
2.1 Стратегии приобретения знаний :. 30
2.2 Обзор современных моделей производительности параллельных приложений 33
2.3 Методы исследования параллельной производительности на основе моделей кластерной архитектуры 40
2.4 Модели в рамках схем параллельных вычислений с учетом независимой изменчивости пропускной способности сети и производительности вычислительных узлов 58
2.5 Выводы к главе 2 68
3 Приобретение знаний о параллельной производительности на основе имитационного моделирования 70
3.1 Обзор современных имитационных моделей Грид-среды 70
3.2 Особенности реализации программной системы имитационного моделирования вычислительных процессов в Грид : 73
3.3 Верификация имитационной модели 79
3.4 Использование имитационной модели для исследования производительности сервисов Грид 82
3.5 Выводы к главе 3 89
4 Использование знаний о параллельной производительности для построения квазиоптимального расписания 90
4.1 Подходы к составлению расписания 90
4.2 Автоматизированное составление квазиоптимального расписания на основе знаний о параллельной производительности 96
4.3 Расчет ускорения приложения в виде детерминированной функции случайного аргумента
4.4 Выводы к главе 4 103
Заключение 104
Список литературы 106
Приложение А
- Интеллектуальный подход к проектированию приложений в Грид
- Методы исследования параллельной производительности на основе моделей кластерной архитектуры
- Особенности реализации программной системы имитационного моделирования вычислительных процессов в Грид :
- Автоматизированное составление квазиоптимального расписания на основе знаний о параллельной производительности
Введение к работе
Актуальность темы. Грид — географически распределенная, согласованная, открытая и стандартизованная среда разделения вычислительных и информационных ресурсов1. В нашей стране существенный вклад в развитие и применение технологий Грид внесли работы В.А. Ильина, В.М. Котова, В.Г. Хорошевского, А.П. Афанасьева, Л.Б. Соколинского и др, В отличие от Грид-систем I поколения, акцентирующихся, в первую очередь, на предоставлении доступа к вычислительным ресурсам, современная концепция Грид II поколения допускает гораздо более широкую интерпретацию. В частности, допустимо рассматривать Грид как специфическую («мягкую», soft) среду параллельных вычислений, наряду с более традиционными (например, кластерными) параллельными архитектурами. При этом проблема эффективной организации параллельных вычислений в среде Грид связана с необходимостью объединения и синхронизации большого количества вычислительных систем для решения общей задачи. Это обусловлено рядом специфических факторов, в общем случае отрицательно влияющих на параллельную производительность. К ним относятся неоднородность вычислительных ресурсов и сетевых каналов связи, а также стохастическая изменчивость параметров коммуникационных сетей и вычислительных систем за счет коммунального режима их использования. Как следствие, принципы проектирования эффективных параллельных вычислительных приложений в Грид существенно отличаются от традиционных подходов, характерных, например, для кластерных систем. «Ручной» процесс создания таких приложений является весьма трудоемким и требует высокой квалификации разработчиков, что привело к развитию специализированного инструментария — интеллектуальных систем поддержки принятия решений разработчика приложений в среде Грид2. Принцип работы таких систем основывается на интерпретации знаний о параллельной производительности компонентов распределенного приложения в Грид — прикладных Грид-сервисов, создание которых требует использования соответствующих методов инженерии знаний. Важные результаты в области интеллектуальных систем и инженерии знаний были получены Д.А. Поспеловым, Г.С. Осиповым, В.Л. Стефанюком, Т.А. Гавриловой, Ю.И. Нечаевым, L. Zadeh, P. Winston и др. Однако применительно к такой специфической области, как среда Грид, с большим и непрерывно растущим количеством размещаемых в ней прикладных сервисов, использование традиционной стратегии получения знаний путем взаимодействия инженера по знаниям с экспертами и специализированной литературой становится затруднительным.
1 Данное определение является обобщением частных определений, независимо сформулиро
ванных I. Foster и С. Kesselman, а также М. Livny.
2 Инструментальная оболочка проектирования высокопроизводительных приложений в Грид.
Часть I: Базовая концепция / А.В. Ларченко, А.В. Дупаев, А.В. Бухановский // Научно-
технический вестник СПбГУ ИТМО' Технологии высокопроизводительных вычислений и
компьютерного моделирования. — СПб.: Изд-во СПбГУ ИТМО, 2008. — Вып. 54 — С. 29-
36.
4 Для приобретения таких знаний в условиях неопределенности среды Грид необходимо применять косвенные методы, основанные на обработке данных экспериментальных измерений производительности, усвоении их в аналитических моделях, а также использовании индуктивных программ имитационного моделирования. Отсутствие общего подхода к решению этой задачи делает тему диссертации актуальной.
Предметом исследования являются косвенные методы формализации и приобретения знаний о параллельной производительности вычислительных сервисов в среде Грид на основе аналитических и имитационных моделей.
Целью работы является решение задачи, играющей существенную роль в области распределенных вычислений, а именно — исследование и разработка методов формализации и приобретения знаний о параллельной производительности прикладных Грид-сервисов, используемых для наполнения базы знаний интеллектуальной системы поддержки процесса проектирования параллельных вычислительных приложений в Грид.
Задачи исследования. Для достижения цели работы были поставлены и решены следующие задачи:
разработка и обоснование семейства аналитических моделей параллельной производительности приложений в среде Грид на основе формализма детерминированной функции случайного аргумента;
разработка, обоснование и программная реализация метода имитационного моделирования работы параллельного приложения в Грид, позволяющего описывать среды, в которых пропускная способность каналов связи и производительность вычислительных узлов независимо меняются от запуска к запуску по заданным пользователем законам распределения;
приобретение и формализация знаний о производительности приложений в неоднородных корпоративных Грид-средах с использованием аналитических и имитационных моделей;
обоснование метода определения вероятностных характеристик параллельного ускорения с учетом стохастичности времени работы вычислительного приложения в среде Грид.
Методы исследования включают в себя аппарат теории вероятностей и математической статистики случайных величин и функций, методы имитационного моделирования, элементы анализа алгоритмов и программ, модели и методы инженерии знаний, методы вычислительной математики и инженерии программного обеспечения.
Научная новизна результатов работы заключается в том, что:
сформулирован метод приобретения знаний о производительности композитных вычислительных приложений в среде Грид, совокупно учитывающий алгоритмическую специфику Грид-сервисов, условия запуска приложения и изменчивость характеристик вычислительной инфраструктуры;
обоснован метод расчета параллельного ускорения вычислительных приложений в среде Грид на основе нелинейного преобразования детермини-
5 роваиной функции случайного аргумента, определяющей время работы приложения на заданном количестве вычислителей;
предложено использование кортежа величин (заданного ускорения, оптимального количества вычислителей и соответствующей вероятности достижения этого ускорения), позволяющего однозначно охарактеризовать производительность параллельного приложения в Грид. Практическую ценность работы составляют:
семейство аналитических моделей параллельной производительности в Грид для типовых классов приложений, необходимых для идентификации и валидации имитационной модели;
программное средство имитационного моделирования работы параллельного приложения в Грид, позволяющее задавать параметры среды: произвольные сетевые топологии, производительность и загруженность для вычислительных узлов, пропускную способность и загруженность для сетевых каналов; законы распределения шумовой загруженности вычислительных узлов и сетевых каналов.
На защиту выносятся следующие положения:
приобретение знаний о производительности композитных вычислительных приложений в среде Грид целесообразно выполнять посредством процедуры имитационного моделирования, совокупно учитывающей специфику Грид-сервисов, условия запуска приложения и характеристики коммуникационных сетей;
вероятностные характеристики параллельного ускорения приложений в Грид определяются посредством косвенных измерений на основе интерпретации времени работы в форме детерминированной функции случайного аргумента.
Достоверность научных результатов и выводов подтверждается строгостью наложенных ограничений, обоснованностью применения математического аппарата, оценкой адекватности математических моделей, результатами тестирования алгоритмов и программного обеспечения, а также практическим использованием разработанных математических, алгоритмических и программных методов и средств.
Внедрение результатов работы. Результаты, полученные в ходе диссертационной работы, были использованы при выполнении НИР в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы»: «Разработка инструментальной оболочки проектирования высокопроизводительных приложений для Грид-архитектур в целях создания прикладных сервисов компьютерного моделирования и обработки данных» (2007-4-1.4-20-01-025) и «Высокопроизводительный программный комплекс моделирования и прогноза экстремальных гидрометеорологических явлений и расчета воздействий на морские объекты и сооружения» (2007-4-1.4-00-06-108), а также при выполнении ОКР "Разработка высокопроизводительного программного комплекса для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и ком-
плексов"(2008-04-2.4-15-02-003). В процессе работы получено свидетельство о государственной регистрации программы для ЭВМ: «PEG2» (свидетельство №2008614623).
Апробация работы. Изложенные в диссертации результаты обсуждались на 9 международных и российских научных конференциях, семинарах и совещаниях, включая ежегодные Международные научно-практические семинары «Высокопроизводительные параллельные вычисления на кластерных системах» (2006 г., Санкт-Петербург; 2007 г., Нижний Новгород; 2008 г., Казань), ежегодные Всероссийские научные конференции «Научный сервис в сети Интернет» (2007 и 2008 гг., Новороссийск), ежегодную Международную научную конференцию «Параллельные вычислительные технологии (ПаВТ 2008)», XV Всероссийскую научно-методическую конференцию «Телематика 2008», IV и V Межвузовские научные конференции молодых ученых (2007 и 2008 гг., Санкт-Петербург).
Публикации. По теме диссертации опубликовано 10 печатных работ (из них 4 — в изданиях из перечня ведущих рецензируемых научных журналов и изданий ВАК РФ).
Личный вклад автора заключается в разработке семейства аналитических и имитационных моделей работы параллельного приложения в среде Грид и их программной реализации, в сопоставлении областей их применимости, в организации вычислительных экспериментов и интерпретации их результатов, в разработке структуры представления знаний в интеллектуальной системе поддержки принятия решений разработчика приложений в Грид.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (70 наименований) и 1 приложения. Содержит 111с. текста (из них ПО основного текста и 1 приложений), включая 44 рис. и 6 табл.
Интеллектуальный подход к проектированию приложений в Грид
Одним из основных компонентов инструментального средства является система управления знаниями, которая ответственна за хранение знаний об инфраструктуре Грид, опыте предыдущих запусков и пр. Она позволяет извлекать эти знания, производить их обновление и пополнение, проверку целостности, оценку качества и т. п. Этот компонент участвует на всех этапах работы системы и обеспечивает ее функционирование как интеллектуальной вычислительной среды.
У пользователя имеется определенная задача, которую ему необходимо решить путем последовательного применения проблемно-ориентированных модулей к исходным данным, которые имеются у него или содержатся на удаленном хранилище Грид. На первом этапе пользователь осуществляет проектирование, описывая свою задачу в виде MWF с нечетким заданием параметров и характеристик блоков действий и данных, используя термины своей предметной области. Для этого визуальная оболочка, посредством которой осуществляется проектирование, обращается к системе управления базами знаний за информацией о доступных сервисах, их типах и классификации. В результате этого этапа системе передается нечеткое описание задачи пользователя. Помимо этого, пользователь указывает для всего описания в целом критерии, которые ему важны для проведения вычислений. Критериями могут быть: минимизация времени выполнения результирующего сценария, определенная точность, обеспечиваемая устойчивость к сбоям и т.п. Также он может наложить ограничения на отдельные блоки или WF в целом, указав, например, предпочитаемые сервисы или конкретное местоположение данных. Полученное описание не может быть исполнено системой напрямую, поэтому необходим следующий этап — этап интерпретирования и формирования активного набора фактов.
На этом этапе производится перевод схемы пользователя в термины, понятные системе, и формирования набора активных фактов. В него входит информация о текущем состоянии Грид-инфраструктуры, получаемая от компонента мониторинга, а также информация о производительности проблемно-ориентированных сервисов. Производится сбор информации о внешнем мире для последующего построения прогнозов и логического вывода.
Сформированный набор фактов вместе с пользовательским описанием поступает на вход компонента логического вывода, который выполняет основную часть работы по переводу пользовательского описания в конкретный сценарий исполнения, который может быть передан в Грид. Этот этап делится на две стадии: планирование и создание расписания. Планирование представляет собой подбор альтернативных конфигураций частичного сценария выполнения AbstractWorkflow, представляющих сформированные последовательности вызовов конкретных сервисов. Данный сценарий описывает только общую последовательность вызовов сервисов, без указания точного времени вызова. AWF является шаблоном сценария, который может быть далее настроен и уточнен для непосредственного исполнения. При этом реализуется требование совместимости форматов входных и выходных данных для последовательно вызываемых сервисов. На полученном наборе непротиворечивых AWF производится построение альтернативных расписаний, заключающееся в выборе узлов, на которых эти сервисы будут исполняться с учетом критериев, заданных пользователем при проектировании. В результате этого этапа получается набор альтернативных расписаний, среди которых система выбирает наилучший с точки зрения критериев пользователя, либо предоставляет пользователю право выбора. Также производится оценка достоверности знаний, на основе которых были получены данные расписания, а в случае нехватки знаний происходит обращение к пользователю или извлечение дополнительных знаний.
Извлечение дополнительных знаний может быть реализовано за счет использования следующих возможностей: поиск прецедентов — система осуществляет поиск знаний о предыдущих запусках и на их основании делает вывод; имитационное моделирование — система может произвести моделирование процесса вычислений с помощью имитационной модели Грид и основывать свой вывод на результатах моделирования; тестирование и профилирование: данные методы пополнения знаний могут быть применены только путем отдельных запусков программных модулей сервисов с участием эксперта, который по оценкам этих запусков самостоятельно пополнит базу знаний. После того, как конкретное расписание выбрано, происходит его исполнение в Грид с постоянным контролем за счет применения компонента мониторинга исполнения. В случае отклонения от построенного расписания возможно повторное обращение к системе логического вывода для построения нового расписания для еще невыполненной части. Также, происходит сбор данных о выполнении, которые используются для пополнения базы знаний, чтобы в дальнейшем иметь возможность использовать их в аналогичных запусках.
В результате выполнения пользователь получает результат в виде набора данных, которые отправляются в указанное хранилище Грид или на машину пользователя.
Представленная на рис. 1.2 концептуальная схема обобщает результаты работ по развитию программный комплекс инструментальная оболочка семейства PEG (PEG1, PEG2, iPEG), созданного в рамках НИР 2007-4-1.4-20-01-025. Они призваны предоставлять удобные средства для проектирования, создания и выполнения параллельных приложений в среде Грид, а также обеспечивать инструментарий для мониторинга состояния самой Грид-среды, процесса выполнения задач, оповещения о возникающих ошибках, сбора статистических данных по производительности и пр. Задачи, для решения которых предназначен программный комплекс, могут быть охарактеризованы как задачи, требующие значительных вычислительных ресурсов, а не интенсивного обмена данными между вычислительными узлами, использующие алгоритмы, которые допустимо распараллеливать по схеме «master-slave» (или централизованной схеме), в которых большая часть времени тратится на вычисления. Это могут быть, например, серии трудоемких вычислений, обработка статистических данных, системы имитационного моделирования, и пр.
Все перечисленные виды знаний необходимы для функционирования системы, но ввиду того, что основной целью создания системы является разработка высокоэффективных Грид-приложений, знания о производительности сервисов начинают играть решающую роль. Без их наличия система может функционировать и, возможно, будет упрощать процесс проектирования, предоставляя пользователю менее требовательную и сложную среду разработки, но приложения, созданные в такой системе, не будут соответствовать никаким критериям эффективности, надежности, оправданности. Весь процесс проектирования потеряет смысл, так как пользователь передаст системе процесс обоснованного выбора схемы выполнения, а система не будет иметь никаких знаний о том, как именно обосновать тот или иной выбор. Положение усугубляется тем, что Грид-среда по определению является системой с децентрализованной системой предоставления ресурсов и сервисов. Сервисы, распространяемые в среде, не подвергаются никакой регламентации с точки зрения используемых алгоритмов, схем распараллеливания, и других, ввиду чего конечный пользователь может только надеяться на полноту и адекватность предоставленного поставщиком описания. Собирая композитное приложение, которое задействует насколько сервисов (даже однотипных), пользователь не может предсказать времени и характера его работы
Методы исследования параллельной производительности на основе моделей кластерной архитектуры
Существует несколько стратегий получения знаний из источника в зависимости от условий применения. Традиционной является стратегия, в которой инженер по знаниям непосредственно общается с экспертами и собирает разрозненную информацию воедино. В данном случае эксперты предоставляют «обрывочные» и субъективные знания об одном процессе или о его связанных частях. Инженер, вооруженный специальными знаниями по когнитивной психологии, системному анализу, математической логике и прочим, создает целостную систему знаний о процессе. Данная стратегия не применима в Грид в связи с тем, что эксперты обладают знаниями, которые описывают не связанные процессы. Как было сказано в главе 1, из-за быстрого роста числа сред возникает дефицит экспертов, знания которых охватывали бы все процессы в Грид. В результате появляются «дыры» в поле знаний, которые не позволяют получить целостную картину процессов.
Другой стратегией получения знаний является процесс машинного формирования знаний или машинного обучения. Традиционно к задачам формирования знаний, или машинного обучения, относятся задачи прогнозирования, идентификации (синтеза) функций, расшифровки языков, индуктивного вывода и синтеза с дополнительной информацией. Данные системы использую специализированные методы для извлечения знаний из больших массивов сырых данных. Учитывая большое число стохастичных параметров среды Грид, накопление достаточной для проведения анализа базы данных займет длительное время. При условии, что структура среды не будет существенно меняться (а это является одним из частых процессов в Грид), данная стратегия трудно адаптируема к большим и динамичным Грид-средам. Но именно такая стратегия применяется для более статичных распределенных систем с закрытой от внешнего воздействия статичной инфраструктурой (исторические методы оценки производительности, см. раздел 1.3)
Третьей стратегией является приобретение знаний (knowledge acquisition) — процесс получения знаний инженером с использованием специализированных методов и программных средств. Данный метод водится наиболее подходящим для использования в среде Грид для получения знаний о параллельной производительности. Он позволяет совмещать различные механизмы, позволяющие заделывать «дыры» в поле знаний, составленном на основе опроса экспертов. Остальная часть работы будет посвящена исследованию методов приобретения знаний в форме аналитических и имитационных моделей.
Модель параллельных вычислений — это абстрактная модель параллельной вычислительной машины и/или модель оценки производительности параллельного алгоритма, реализованного для этой абстрактной машины. Существует множество моделей параллельных вычислений, но подавляющее их большинство сейчас не находят применения. Это связано с тем, что ранние модели параллельных вычислений были разработаны так, чтобы как можно более точно описать поведение конкретной параллельной машины. Например, модель компьютера СМ-2, которую применяли для определения наиболее подходящего для него алгоритма сортировки [41]. Подобные модели в большинстве случаев не применимы для описания производительности алгоритмов на других вычислительных архитектурах. Наиболее известными на данный момент являются модели: PRAM (1978), BSP (1989), Postal Model (1992), LogP (1993) и x-Model (1997). Они популярны благодаря тому, что применимы для многих реально действующих современных параллельных машин и распределенных систем за счет своей относительной универсальности.
Модель BSP (Bulk Synchronize Parallel) — это модель параллельного программирования [41, 42] для компьютера, состоящего из нескольких одинаковых процессоров, соединенных сетью с постоянной пропускной способностью. У каждого процессора есть своя быстрая память. Процесс выполнения программы разбігваетея на несколько блоков, каждый из которых состоит из трех последовательных во времени частей: вычисления, передача данных, барьер синхронизации. Действия внутри каждого из этапов протекают в параллельном режиме. На рис. 2.2 приведена концептуальная схема выполнения параллельной программы.
На этапе параллельных вычислений на каждом участвующем в блоке процессоре запускается свой вычислительный поток. При этом используются только данные, расположенные в быстрой локальной памяти процессора. Каждый поток работает независимо от других.
На следующем этапе запускаются параллельные независимые потоки обмена данными. Данные могут передаваться как между процессорами, так и между процессорами и хранилищем данных, что характеризует применяемую модель оценки работы этого этапа.
На этапе синхронизации потоки, закончившие необходимый им обмен данными, достигают барьера синхронизации и ожидают окончания работы остальных потоков.
Во многих системах параллельного программирования передача информации состоит из нескольких действий процессоров, таких как передача сообщений или копирование памяти. Так как в параллельной программе много независимых взаимодействий потоков, трудно предположить, сколько времени займет конкретная передача данных. BSP-модель рассматривает все обмены информацией между процессами одновременно. Предполагается, что все сообщения имеют фиксированную длину (длинные сообщения при этом могут быть разбиты на более мелкие с фиксированной длиной) и оценивается время передачи информации для всего блока параллельного алгоритма. Максимальное число сообщений, принимаемых или посылаемых в блоке, обозначается как И.
BSP-модель не предполагает латентности сети. И в случае передачи т сообщений длины 1, и в случае передачи одного сообщения длины т время на передачу полагается равным mg. Параметр g определяется следующими факторами:
На многих параллельных архитектурах барьерная синхронизация — дорогая по времени операция. Стоимость барьерной синхронизации обозначается /. На практике время синхронизации обычно определяется экспериментально. В барьерной синхронизации есть много положительных моментов, так как она не создает циклические зависимости захвата и освобождения ресурсов, не может произойти взаимная блокировка процессов (deadlock). Но для алгоритмов с частыми обменами данных использование принудительного барьера приводит к значительному увеличению времени работы параллельного приложения.
Время выполнения блока параллельного алгоритма в BSP-модели состоит.из трех частей: время работы самого длительного потока вычислений, время передачи информации между процессорами и время барьерной синхронизации в конце блока. Дляр процессоров время работы блока в BSP-модели вычисляется так:
Особенности реализации программной системы имитационного моделирования вычислительных процессов в Грид :
Процесс исследования Грид-среды как среды для параллельных вычислений, выявление в ней особенностей и закономерных процессов, требует проведения большого числа экспериментов, поставленных на различных конфигурациях программно-аппаратного обеспечения, учета большого числа параметров, имеющих сложную динамику изменения. Проведение экспериментов в реальном времени на реально существующем стенде — слишком длительный процесс, отнимающий часы для проведения одного экспериментального запуска; при этом сокращение числа экспериментов отрицательно сказывается на достоверности статистических выводов. Проверка гипотез часто требует проведения экспериментов на различных топологиях среды, на существенно различающихся конфигурациях аппаратного и программного обеспечения, что является трудно выполнимой задачей при ограниченном парке техники. Имитационное моделирование позволяет избежать описанных трудностей, предоставляя исследователю возможность варьировать как конфигурации среды (широта выбора обусловлена используемой имитационной моделью), так и детализованность получаемой в результате моделирования информации.
Помимо сокращения времени экспериментов, использование имитационного моделирования играет важную гносеологическую роль. Она связана с тем, что в силу децентрализации функционирование Грид учитывает влияние большого числа факторов, ни один из которых не имеет лидирующего значеЕіия. Например, даже в рамках PEG используется около 40 базовых сервисов, разработанных различными компаниями. Это усложняет выявление фундаментальных факторов, влияющих на работу параллельной программы в среде Грид. Потому варьирование детализации задачи с помощью имитационного моделирования позволяет измерять характеристики процессов, не поддающиеся прямым измерениям обычными средствами Грид.
Сложность воссоздания актуальных процессов (высокая стоимость компонентов, задействованных в процессе, сложность воссоздания заданной конфигурации и условий протекания процесса, длительность процесса вычислений) является стимулирующим фактором появления новых имитационных моделей. По этой же причине появляется достаточно большое число имитационных систем для Грид-среды. Рассмотрим несколько наиболее известных, имеющих длительный период развития и поддержки [59].
SimJava [60] представляет собой библиотеку классов общего назначения, позволяющую достаточно легко создавать дискретные событийные программные модели имитационного моделирования. Эта библиотека хорошо подходит для реализации на ней имитационных моделей распределенных систем вычислений, включая и Грид-среды. Библиотека состоит из 3 частей. Первая часть библиотеки предоставляет набор классов поддержки разработки ядра имитационной системы и средств взаимодействия с ним. Результаты работы ядра могут быть получены только в текстовом виде. Вторая часть библиотеки, под названием simanim, предоставляет набор шаблонов визуальных аплетов, которые позволяют анимировать текстовые результаты, полученные от ядра системы. Третья часть библиотеки simdiag предоставляет набор JavaBeans визуальных компонентов для настройки и визуализации процесса моделирования. На данный момент система больше не поддерживается, хотя все еще используется во многих других имитационных системах как базовый компонент. Дата последнего обновления 2002 г.
Bricks [61] — имитационная система моделирования производительности, позволяющая сравнивать эффективность работы различных методов балансировки нагрузки и составления расписаний выполнения. Она хорошо подходит для отработки методов, применяемых в брокерах вычислительных ресурсов (Condor, openPBS). Bricks является дискретной событийной системой управления заданиями (jbs) с продвижением виртуального времени. Она состоит из двух компонент: Global Computing Environment, которая моделирует работу распределенной среды (в том числе и среды Грид); компоненты Scheduling Unit, которая управляет поведением среды (задает механизм распределения заданий в системе). Эта система также реализована на языке Java и дополнительно поддерживает специализированный скриптовый язык для описания алгоритмов распределения заданий. Название системы символизирует процесс ее использования. Пользователь, используя скриптовый язык, описывает отдельные блоки поведения системы, собирая из них готовую и функционирующую имитационную модель. На данный момент проект развивается в закрытом режиме.
GridSim [62] — имитационная система, поддерживающая возможность моделировать работы и взаимодействие различных объектов Грид: ресурсов, пользователей, сервисов, серверов, приложений, брокеров ресурсов. Она предоставляет возможность создавать и манипулировать такими сущностями, как: пользовательское приложение, проекция заданий схемы выполнения (workflow) на ресурсы системы, схемы управления поведением различных объ7 ектов системы. Систему можно разбить на слои по уровню детализации и по объектам моделирования. Нижний уровень представлен в виде настроенного внешнего компонента SimJava, который поддерживает базовые возможности имитационной системы (эта система была рассмотрена ранее). На втором уровне представлены базовые элементы среды Грид: ресурсы и информационные сервисы. Далее следует слой агрегаторов ресурсов, которыми являются брокеры и системы создания расписания выполнения. На последнем слое представления сущности высокого уровня, такие, как приложения пользователей, система управления поведением ресурсов и сервисов. Группой разработчиков данной системы разрабатывается также отдельная оболочка визуализации и графического интерфейса Visual Modeler [63], тесно взаимодействующая с ядром имитационной системы. Данная система моделирования является высоко детализированной и требует для своей настройки точного отражения моделируемой среды, что создает дополнительные трудности при ее использовании, так как требует высокого уровня знаний технологий и процессов, протекающих в моделируемой среде. Система активно развивается и доступна для открытого некоммерческого использования. Последний бета-релиз системы состоялся в октябре 2008 г.
Система MicroGrid [64], в отличие от остальных рассматриваемых систем моделирования, не является в полной мере системой имитационного моделирования, так как большая часть моделируемых процессов происходит на специально подготовленной версии стандартных библиотек среды Грид Globus Toolkit. Данная система позволяет достоверно исследовать работу системного программного обеспечения Грид-среды. Также, на базе модернизированных библиотек можно разрабатывать собственные надстройки и исследовать их поведение и влияние в реальных условиях. Систему можно настраивать, создавая имитации различных аппаратных платформ, на которых могли бы существовать стандартные библиотеки. Эта возможность позволяет варьировать формы использования реальной системной библиотеки. Ядро MicroGrid составляет подсистема MaSSF, построенная на базе параллельной дискретной событийной имитационной системы моделирования DaSSF [65] (Dartmouth Scalable Simulation Framework), MicroGrid не имеет графической подсистемы и пользователь должен вручную модифицировать файлы настройки для задания характеристик модели. Последняя версия системы вышла в 2004 году и поддерживала Globus Toolkit 2.2.4. На данный момент система не развивается и быстро теряет свою актуальность в связи с регулярным обновлением стандартных библиотек (последнее обновление было в июне 2008 г., вышла версия 4.2.1).
Ввиду ряда недостатков у рассмотренных систем было принято решение самостоятельно разрабатывать имитационную систему, которая бы могла тесно интегрироваться с оболочками проектирования параллельных Грид-приложений PEG2/iPEG.
Автоматизированное составление квазиоптимального расписания на основе знаний о параллельной производительности
Эта задача формулируется и решается в терминах различных дисциплин: методов оптимизации, искусственного интеллекта и т. д. На данный момент существует несколько традиционных широко применяемых подходов для ее решения:
Эвристический поиск (методы и эвристики искусственного интеллекта). В настоящее время широко распространены такие методы, как Л с локальными эвристиками, эвристические методы поиска Min-min, Max-min, Duplex, Генетические алгоритмы [68].
Поиск экстремума функции критериев оптимальности (методы оптимизации). На данный момент встречается использование таких методов, как Симуляция Отжига (Simulated Annealing) и Tabu [69].
Статические эвристики, устанавливающие правила или принцип распределения задач между ресурсами, который при соблюдении определенных условий работы гарантируют квазиоптимальность получаемого расписания. К ним можно отнести такие простые и широко распространенные стратегии как: OLB (Opportunistic Load Balancing). Каждая следующая задача назначается на первый свободный вычислительный ресурс. о MET (Minimum Executing Time). Каждая следующая задача назначается на свободный вычислительный ресурс, на котором время вычисления данной задачи будет минимальным. о МСТ (Minimum Completion Time). Каждая следующая задача назначается на свободный вычислительный ресурс так, чтобы общее время всего доступного для рассмотрения потока задач было минимально. В этом методе применяются простейшие методы планирования вычислений. В ряде случаев могут быть использованы упрощенные (полуаналитические методы) построения расписаний, основанные, например, на каскадных схемах (подробно рассмотрены в пункте 4.1.4). Они по некоторым критериям могут быть отнесены к статическим эвристическим методам создания расписаний. Каскадные методы достаточно эффективны и просты в применении, но позволяют решать лишь узкий класс задач управления параллельными вычислительными процессами. С точки зрения задач общего плана наиболее перспективными на данный момент методами в данной области признаны Min-Min, Duplex [68] и генетические алгоритмы.
Задача построения расписаний в данной постановке на данный момент находится на стадии активного исследований и обсуждения. Разными группами разработчиков ставятся акценты на различных критериях, по которым необходимо оптимизировать процесс построе ния расписаний. С одной стороны, ввиду появления Грид-систем коммерческой направлен ности, актуальным становится вопрос разработки подходов к построению расписаний с уче том ценовых критериев используемьк ресурсов и максимизации качества предоставляемых После введения WF в активное использование в Грид-средах появилась необходимость пересмотра методов, описанных в предыдущем пункте. Новыми критериями стали: минимизация времени выполнения отдельного WF и минимизация среднего времени выполнения WF [70].
Рассмотрим каскадные методы декомпозиции, основанные на управлении синхронной коммуникационной моделью. Для сравнения приводятся три алгоритма декомпозиции: равномерный (приводимый как алгоритм, работающий на асинхронной модели и не учитывающий параметров среды), каскадная прямая балансировка и каскадная балансировка с барьером. При равномерной декомпозиции данные разбиваются на несколько равных частей, количество которых равно числу вычислителей в системе.
При каскадной балансировке ставится условие, что никакие два потока не должны передавать данные по разделяемому каналу одновременно. В связи с этим можно построить естественную модель, в которой данные разбиваются и отсылаются таким образом, чтобы участки передачи данных на сервер и с сервера не пересекались между собой (см. рис. 4.1).
Преимуществом каскадных методов является также и то, что построение моделей для них является более простым, нежели чем для методов, использующих асинхронные передачи. Это обусловлено тем, что для каждого потока образуется свободный канал, на который не оказывают влияния другие потоки, поэтому для него можно аналитически выписать время его выполнения.
Время работы отдельного потока может быть рассчитано в форме параметрической модели времени работы параллельного приложения, описанной в пункте 2.3: 7} = qtN{Tw. + Tc.) + ЧіШщ, (4.1) где N— объем входных данных, М— объем выходных данных, Tw ,Т„ — соответственно пропускная способность канала до / вычислительного узла и производительность і вычислительного узла, qt — доля данных и вычислений, приходящихся на і вычислительный узел. Основным критерием при каскадной балансировке является то, что передачи данных различных потоков не должны пересекаться (мешать друг другу) на общих каналах передачи данных (для Грид-среды общим будет канал между терминалом пользователя и сервером Грид). В соответствии с этим критерием можно выделить 2 очевидных способа построения каскадной балансировки: прямой и обратный, которые приведены соответственно на рис. 4.16 и 4.1в. Различия между этими двумя методами состоят в порядке возврата данных на терминал пользователя и по принципу аналогичны порядку обработки очередей и стеков. Прямой каскад, как и обыкновенная очередь, руководствуется принципом FIFO («Первым пришел — первым ушел»), т. е. поток, который начнется первым, должен и закончить первым. Обратный каскад, по принципу соответствующий стеку, руководствуется принципом LIFO («Последним пришел — первым ушел»). Таким образом, исходя из выражения (4.1), время работы прямого каскада имеет вид:
Необходимость обрабатывать частично конкретизированные задачи (см. раздел 4.1) порождает ряд трудностей, не характерных для традиционных подходов к построению расписаний. В такой постановке рассматривается идея переноса части работы по принятию решений о формировании задачи, которую обычно выполняет человек, исходя из своих знаний и опыта, на машину. Процесс формирования расписания в такой системе можно разделить на следующие этапы: составление конкурирующих (формально корректных) планов выполнения, анализ конкурирующих планов на основании критериев, указанных пользователем, формирование готового к выполнению расписания.
