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

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

Дунаев Антон Валентинович

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 2 ДЕН 2008

Санкт-Петербург — 2008

003457328

Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики

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

Бухановский А.В.

Официальные оппоненты:

Заслуженный деятель науки РФ, доктор технических наук, профессор Нечаев Ю.И.

кандидат физико-математических наук, доцент Хоружников С.Э.

Ведущая организация:

ФГУ «Государственный научно-исследовательский институт информационных технологий и телекоммуникаций»

Защита состоится 24 декабря 2008 г. в 14:00 часов на заседании диссертационного совета Д212.227.06 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, г. Санкт-Петербург, Кронверкский пр., д. 49.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан 24 ноября 2008 г.

Ученый секретарь диссертационного совета, # . . доктор технических наук, профессор I (Л/ Тарлыков В.А.

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

Актуальность темы. Грид — географически распределенная, согласованная, открытая и стандартизованная среда разделения вычислительных и информационных ресурсов1. В нашей стране существенный вклад в развитие и применение технологий Грид внесли работы В.А. Ильина, В.М. Котова, В.Г. Хорошевского, А.П. Афанасьева, Л.Б. Соколинского и др, В отличие от Грид-систем I поколения, акцентирующихся, в первую очередь, на предоставлении доступа к вычислительным ресурсам, современная концепция Грид II поколения допускает гораздо более широкую интерпретацию. В частности, допустимо рассматривать Грид как специфическую («мягкую», soft) среду параллельных вычислений, наряду с более традиционными (например, кластерными) параллельными архитектурами. При этом проблема эффективной организации параллельных вычислений в среде Грид связана с необходимостью объединения и синхронизации большого количества вычислительных систем для решения общей задачи. Это обусловлено рядом специфических факторов, в общем случае отрицательно влияющих на параллельную производительность. К ним относятся неоднородность вычислительных ресурсов и сетевых каналов связи, а также стохастическая изменчивость параметров коммуникационных сетей и вычислительных систем за счет коммунального режима их использования. Как следствие, принципы проектирования эффективных параллельных вычислительных приложений в Грид существенно отличаются от традиционных подходов, характерных, например, для кластерных систем. «Ручной» процесс создания таких приложений является весьма трудоемким и требует высокой квалификации разработчиков, что привело к развитию специализированного инструментария — интеллектуальных систем поддержки принятия решений разработчика приложений в среде Грид2. Принцип работы таких систем основывается на интерпретации знаний о параллельной производительности компонентов распределенного приложения в Грид — прикладных Грид-сервисов, создание которых требует использования соответствующих методов инженерии знаний. Важные результаты в области интеллектуальных систем и инженерии знаний были получены Д.А. Поспеловым, Г.С. Осиповым, B.JI. Стефанюком, Т.А. Гавриловой, Ю.И. Нечаевым, L. Zadeh, P. Winston и др. Однако применительно к такой специфической области, как среда Грид, с большим и непрерывно растущим количеством размещаемых в ней прикладных сервисов, использование традиционной стратегии получения знаний путем взаимодействия инженера по знаниям с экспертами и специализированной литературой становится затруднительным.

1 Данное определение является обобщением частных определений, независимо сформулированных I. Foster и С. Kesselman, а также М. Livny.

2 Инструментальная оболочка проектирования высокопроизводительных приложений в Грид. Часть I: Базовая концепция / A.B. Ларченко, A.B. Дупаев, A.B. Бухановский // Научно-технический вестник СПбГУ ИТМО' Технологии высокопроизводительных вычислений и компьютерного моделирования. — СПб.: Изд-во СПбГУ ИТМО, 2008. — Вып. 54 — С. 2936.

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

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

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

Задачи исследования. Для достижения цели работы были поставлены и решены следующие задачи:

• разработка и обоснование семейства аналитических моделей параллельной производительности приложений в среде Грид на основе формализма детерминированной функции случайного аргумента;

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

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

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

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

Научная новизна результатов работы заключается в том, что:

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

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

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

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

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

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

На защиту выносятся следующие положения:

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

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

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

Внедрение результатов работы. Результаты, полученные в ходе диссертационной работы, были использованы при выполнении НИР в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 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с. текста (из них 110 основного текста и 1 приложений), включая 44 рис. и 6 табл.

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

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

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

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

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

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

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

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

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

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

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

Интеллектуальные технологии проектирования высокопроизводительных композитных приложений в среде Грид основываются на знаниях о параллельной производительности ПГС как предметно-ориентированных вычислительных компонентов, зарегистрированных в Грид и доступных другим приложени-

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

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

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

Аналитические модели в форме зависимости Т = /(Е,П) времени выполнения Тп от характеристик задачи Е и параметров вычислительной системы П, часто используются для исследования характеристик параллельных алгоритмов для традиционных (например, кластерных) архитектур. Учет стохас-тичности набора параметров П позволяет интерпретировать Тп в форме детерминированной функции случайных аргументов и использовать для ее описания и анализа соответствующие методы теории вероятностей.

Одной из наиболее простых моделей производительности вычислений в Грид является сетевой закон Амдала, где случайной величиной является коэффициент деградации вычислений г:

Тр^Щ\ + т-р). (1)

Р

Здесь Т — время вычислений на р вычислителях (целевых системах), Т0 —

время работы ПГС на пользовательской системе (вне Грид). Модель (1) требует однородности целевых систем и коммуникаций между ними. Ее характерной особенностью является гомоскедастичность, выраженная в том, что в зависимости от р изменяется только математическое ожидание М[Тр], а дисперсия времени выполнения остается постоянной.

Построение более сложных моделей параллельной производительности требует конкретизации структуры параллельного алгоритма и входных данных. Это позволяет выразить время выполнения задачи через удельные времена выполнения коммуникационной операции /„ и вычислительной операции tc. Например, для параллельного алгоритма, распределяющего массив из N данных между р вычислителями с целью расчета М величин на каждом и последующим их сбором на одном узле, модель времени выполнения принимает вид:

Tp=(N + PM)tw+-tc, (2)

Р

где t„, tc — случайные величины. Модель (2) описывает однородную вычислительную систему, в которой tw характеризует усредненную пропускную способность коммуникационной среды, которая случайным образом изменяется от запуска к запуску приложения для всех коммуникационных каналов одинаково. В отличие от (1), эта модель является гетероскедастической: с увеличением р дисперсия времени вычислений возрастает.

Выражение (2) является оценкой снизу для времени выполнения приложения, поскольку не учитывает коммуникационного дисбаланса, обусловленного тем, что пропускные способности коммуникационных каналов в Грид могут меняться асинхронно, т.е. t^) =tw+T},, где т], — гауссов случайный шум с заданными математическим ожиданием тц и среднеквадратичным отклонением aq. С учетом этого факта время работы приложения определяется как

Т„ = шах[7] ], где Т, — времй работы с каждым вычислителем. Оно также явля-<=>,/>

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

mT ={tw + mn\^ + M

N

+ tc — , crT = Р

N

— + М \Р

(3)

соответственно. Тогда закон распределения величины Тр (как максимума случайной выборки) асимптотически (при значительных р) является предельным распределением I типа (Гумбеля, или Фишера-Типпета):

/у(*) = ехр[-ехр[-а (л-6)Ц , (4)

где коэффициенты

л/21п {р)

и Ь„

v^Jn(ln(p)) + ln(4.)

2j¿Hp)

crT + mT

(5)

зависят от количества рабочих узлов р.

Т, сек.

: i б 5 lo i: 14 £

Количество вычислителей ^

Рис. 1. Сопоставление аналитических моделей параллельной производительности в Грид: 1 — сетевой закон Амдала (1); 2 — параметрическая модель (2); 3 — модель на основе теории экстремальных значений (4); 4 — экспериментальное распределение для настройки параметров моделей

На рис. 1 приведены результаты сопоставления аналитических моделей производительности (1), (2) и (4), построенных по результатам измерений производительности тестового приложения на экспериментальном стенде на осно-

ве системы PEG. Для корректности сопоставления при идентификации параметров всех трех моделей использовались только данные измерений Т0 (время работы приложения на одном вычислителе вне среды Грид) и 7} (время работы приложения на одном вычислительном узле среды Грид).

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

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

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

Для описания вычислительной задачи применяется специальная нотация, которая позволяет описывать программы со статической схемой выполнения. В описании используются четыре базовых элемента: send, calc, thread и threadGroup. Первые два задают элементарные операции передачи и обработки данных, а последние позволяют организовывать последовательные и параллельные потоки.

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

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

Далее уточненная схема вычислительной задачи вместе с конфигурацией среды Грид передается в исполнительный блок Ядра системы, который является его организующим элементом. Он интерпретирует схему задачи, и, используя блоки Сетевой канал и Вычислительный узел, производит имитацию работы приложения в среде Грид. Блоки Сетевой канал и Вычислительный узел производят учет работы элементов среды Грид, позволяя рассчитывать время работы операций send и calc. Использование блока Линия времени позволяет при моделировании учитывать процессы разделения элементов инфраструктуры (сетевых каналов, вычислительных узлов, серверов Грид) между несколькими независимыми потоками действий и корректировать расчетное время работы схемы задачи в целом.

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

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

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

Время вычислений Т, мс

Рис. 3. Сопоставление результатов имитационного моделирования с экспериментом: 1 — результаты натурного эксперимента; 2 — результаты имитационного моделирования; крест — 95% доверительный интервал

Из рис. 3 видно, что, хотя имитационная модель достаточно точно описывает процесс вычислений на стенде, она имеет некоторые отклонения от экспе-

3 Spectral wave climate of the North Sea Bouklianovsky A.V, Lopatoukhin L.J., Soares C.G 2007, Applied Ocean Research, Volume 29, Issue 3, July 2007, P 146-154

риментальных результатов. Данные отклонения объясняются тем, что имитационная модель не учитывает влияния таких низкоуровневых эффектов, как:

• работа библиотек шифрования передаваемых между узлами Грид данных;

• задержки при постановке задачи на выполнение;

• задержки при передаче сообщений по протоколу SOAP для обмена данными (в том числе управляющими).

Четвертая глава посвящена рассмотрению важной характеристики масштабируемости приложения — параллельного ускорения Sp в Грид. Классическое определение параллельного ускорения в виде

Sp=TJTp, (6)

не может быть использовано для непосредственного определения производительности в Грид по экспериментальным данным, поскольку значение Тр может изменяться от запуска к запуску. Однако, интерпретируя (6) как детерминированную функцию случайной величины Тр, можно выразить плотность распределения параллельного ускорения через fj(x):

/sW = 4/r

X2'

(7)

В качестве примера на рис. 4 приведены вероятностные характеристики параллельного ускорения, рассчитанного по методике (6-7) для композитного приложения, осуществляющего расчет климатических спектров морского волнения. Для различного количества вычислителей р рассчитывались распределения /т(х) посредством ядерной оценки с гауссовым ядром, по которым на основе (7) вычислялись математическое ожидание и характерные квантили (90%, 10% и 1% обеспеченностей).

Видно, что кривые характеристик параллельного ускорения имеют ярко выраженные максимумы (при рг10-14), которые и определяют оптимальный режим выполнения задачи. При этом стохастическая изменчивость ускорения (выражаемая, например, в размахе распределения) возрастает по мере увеличения количества вычислителей р, достигая максимума в районе максимума математического ожидания ускорения (соответствующего оптимальному в среднем количеству вычислителей). Это связано с тем, что выбор оптимального количества вычислителей р* обусловлен балансом между выигрышем по времени за счет распараллеливания вычислительных операций и влиянием коммуникационных расходов. Как следствие, стохастическая изменчивость характеристик Грид в данном случае приводит к нарушению этого баланса как в одну, так и в другую сторону, что и влияет на степень разброса результатов измерений. По мере дальнейшего увеличения количества вычислителей р » р размах распределений ускорения уменьшается.

Рис. 4. Параллельное ускорение выполнения иллюстративного композитного приложения по обработке 8 тысяч спектров морского волнения в Грид: 1 — средние значения (эксперимент); 2 — математическое ожидание;

3 — квантиль 10%; 4 — квантиль 1 %; 5 — квантиль 90%;

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

Из рис. 4 также следует, что максимумы квантильных кривых ускорения смещаются в сторону большего значения р по мере уменьшения их обеспеченности. Как следствие, для вычислений в Грид понятие оптимального количества процессоров р , по-видимому, лишено смысла, поскольку является случайной величиной, условное распределение которой /¡>(х\ 5) в общем случае зависит от ускорения 5, на достижение которого ориентируется разработчик. Это заставляет перейти от безусловной характеристики р* к вероятностной характеристике ■— усредненному оптимальному количеству вычислителей для заданного уровня ускорения:

Рк

£ Pk\fs(pk)(x)fc

р/ (8)

Величина (8) носит характер условного математического ожидания. По мере повышения уровня 5 величина р'(5) также увеличивается; это связано с тем, что потенциально для получения большего ускорения требуется больше вычислителей р.

С величиной (8) связана вероятность а, определяющая шанс получить ускорение не ниже заданного уровня 5 при выборе оптимального количества вычислителей:

а= ¡fs^pk)Wdx■ (9)

5

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

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

1. Адаптировано семейство моделей производительности параллельных алгоритмов для применения в условиях стохастичности среды Грид.

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

3. Предложен метод расчета вероятностных характеристик параллельного ускорения в среде Грид на основе формализма детерминированной функции случайного аргумента. '

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

Публикации по теме диссертационной работы

1. Инструментальная оболочка поддержки принятия решений разработчика высокопроизводительных приложений в Грид/ A.B. Дунаев, Л.В. Ларченко, A.B. Бухановский // Научно-технические ведомости СПбГПУ — 2008. — №5,— С. 98-104. (из перечня ВАК) 1. Инструментальная оболочка проектирования высокопроизводительных приложений в Грид. Часть I: Базовые положения / A.B. Ларченко, A.B. Дунаев, A.B. Бухановский // Научно-технический вестник СПбГУ ИТМО: Технологии высокопроизводительных вычислений и компьютерного моделирования. — СПб.: Изд-во СПбГУ ИТМО, 2008. — Вып. 54. — С. 29-36. (из перечня ВАК)

3. Инструментальная оболочка проектирования высокопроизводительных приложений в Грид. Часть II: Архитектура, реализация и применение

/ A.B. Ларченко, A.B. Дунаев, A.B. Бухановский // Научно-технический вестник СПбГУ ИТМО: Технологии высокопроизводительных вычислений и компьютерного моделирования. — СПб.: Изд-во СПбГУ ИТМО, 2008. — Вып. 54. — С. 37-45. (из перечня ВАК)

4. Инструментальная оболочка проектирования высокопроизводительных приложений в Грид. Часть III: Приобретение и формализация знаний

/ A.B. Дунаев, A.B. Ларченко, A.B. Бухановский // Научно-технический вестник СПбГУ ИТМО: Технологии высокопроизводительных вычислений и компьютерного моделирования. — СПб.: Изд-во СПбГУ ИТМО, 2008. — Вып. 54. — С. 46-55. (из перечня ВАК)

5. Инструментальная оболочка проектирования высокопроизводительных приложений для Грид-архитектур / A.B. Ларченко, A.B. Дунаев,

A.B. Бухановский // Высокопроизводительные параллельные вычисления на кластерных системах: Труды конференции / 8-я Междунар. конф. «НРС-2008», Казань, 17-19 ноября 2008. — Казань: Изд-во КГТУ, 2008. — С. 79-81.

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

/ A.B. Ларченко, A.B. Дунаев, A.B. Бухановский // Научный сервис в сети Интернет: решение больших задач: Труды конф. / Всероссийская научная конф. «Научный сервис в сети Интернет», Новороссийск, 22-27 сентября 2008. — М.: Изд-во МГУ, 2008. — С. 163-169.

7. Инструментальная оболочка проектирования высокопроизводительных приложений для Грид-архитектур / A.B. Дунаев, A.B. Ларченко,

A.B. Бухановский // Труды XV Всероссийской научно-методической конференции / 15-я Всероссийская конф. «Телематика 2008», Санкт-Петербург, 23-26 июня 2008. — СПб.: Изд-во СПбГУ ИТМО, 2008. — Том 1—С. 105-106.

8. Моделирование параллельных вычислительных процессов в среде Грид на примере Intel Grid Programming Environment акселераторов

/ A.B. Дунаев, A.B. Ларченко, A.B. Бухановский // Параллельные

вычислительные технологии: Труды конф. / Междунар. научная конф. «ПаВТ 2008», Санкт-Петербург, 28 января - 1 февраля 2008. — Челябинск: Изд. ЮУрГУ, 2008. — С. 383-389.

9. Оптимальная декомпозиция вычислительных задач в корпоративных Грид-системах на основе Intel Grid Programming Environment

/ A.B. Дунаев, A.B. Ларченко, A.B. Бухановский // Высокопроизводительные параллельные вычисления на кластерных системах: Материалы конф. / 7-я Междунар. конф.-семинар «Высокопроизводительные параллельные вычисления на кластерных системах», Нижний Новгород, 26-30 ноября 2007. — Нижний Новгород: Изд-во ННГУ, 2007. — С. 138-141.

10.Анализ и моделирование производительности параллельных стохастических алгоритмов, адаптированных к особенностям многоядерных вычислительных архитектур / A.B. Ларченко, A.B. Дунаев, A.B. Бухановский //Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ: Труды конф. / Всероссийская научная конф. «Научный сервис в сети Интернет», Новороссийск, 24-29 сентября 2007. — М.: Изд-во МГУ, 2007. — С. 156.

Тиражирование и брошюровка выполнены в учреждении

«Университетские телекоммуникации»

197101, Санкт-Петербург, Саблинская ул., 14

Тел. (812) 233 4669 объем 1 п.л.

Тираж 100 экз.

Введение.

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

1.1 Анализ современных тенденций в области Грид-вычислений.

1.2 Интеллектуальный подход к проектированию приложений в Грид.

1.3 Анализ современных подходов к представлению информации о производительности в Грид.

1.4 Выводы к главе 1.

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

2.1 Стратегии приобретения знаний.:.

2.2 Обзор современных моделей производительности параллельных приложений.

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

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

2.5 Выводы к главе 2.

3 Приобретение знаний о параллельной производительности на основе имитационного моделирования.

3.1 Обзор современных имитационных моделей Грид-среды.

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

3.3 Верификация имитационной модели.

3.4 Использование имитационной модели для исследования производительности сервисов Грид.

3.5 Выводы к главе 3.

4 Использование знаний о параллельной производительности для построения квазиоптимального расписания.

4.1 Подходы к составлению расписания.

4.2 Автоматизированное составление квазиоптимального расписания на основе знаний о параллельной производительности.9б

4.3 Расчет ускорения приложения в виде детерминированной функции случайного аргумента.

4.4 Выводы к главе 4.

Грид — географически распределенная, согласованная, открытая и стандартизованная среда разделения вычислительных и информационных ресурсов1. В нашей стране существенный вклад в развитие и применение технологий Грид внесли работы В.А. Ильина, В.М. Котова, В.Г. Хорошевского, А.П. Афанасьева, Л.Б. Соколинского и др. В отличие от Грид-систем I поколения, акцентирующихся в первую очередь, на предоставлении доступа к вычислительным ресурсам, современная концепция Грид II поколения допускает гораздо более широкую интерпретацию. В частности, допустимо рассматривать Грид как специфическую («мягкую», soft) среду параллельных вычислений, наряду с более традиционными (па-пример, кластерными, гибридными) параллельными архитектурами. При этом проблема эффективной организации параллельных вычислений в среде Грид связана с необходимостью объединения и синхронизации большого количества вычислительных систем для решения одной задачи. Это обусловлено рядом специфических факторов, в общем случае отрицательно влияющих на параллельную производительность. К ним относятся неоднородность вычислительных ресурсов и сетевых каналов связи, а также стохастическая изменчивость параметров коммуникационных сетей и вычислительных систем за счет коммунального режима их использования. Как следствие, принципы проектирования эффективных параллельных вычислительных приложений в Грид существенно отличаются от традиционных подходов, характерных, например, для кластерных систем. «Ручной» процесс создания таких приложений является весьма трудоемким, требуя высокой квалификации разработчиков, что привело к развитию специализированного инструментария — интеллектуальных систем поддержки принятия решений разработчика приложений в среде Грид. Принцип работы таких систем основывается на интерпретации знаний о параллельной производительности компонентов распределенного приложения в Грид — прикладных Грид-сервисов, а их создание требует использования соответствующих методов инженерии знаний. Важные результаты в области интеллектуальных систем и инженерии знаний были получены Д.А. Поспеловым, Т.А. Гавриловой, Ю.И. Нечаевым, B.JI. Стефанюком, Г.С. Осиповым, L. Zadeh, P. Winston и др. Однако применительно к такой специфической области, как среда Грид, с большим и непрерывно растущим количеством размещаемых в ней прикладных сервисов, использование традиционной стратегии получения знаний путем взаимодействия инженера по знаниям с экспертами и специализированной литературой становится затруднительным. Для приобре

1 Данное определение является обобщением частных определений, независимо сформулированных I. Foster н С. Kesselman, а также М. Livny. тения таких знаний в условиях неопределенности среды Грид необходимо применять косвенные методы, основанные на обработке данных экспериментальных измерений производительности, усвоении их в аналитических моделях, а также использовании индуктивных программ имитационного моделирования. Отсутствие общего подхода к решению этой задачи делает тему диссертации актуальной.

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

• разработка и обоснование семейства аналитических моделей параллельной производительности приложений в среде Грид на основе формализма детерминированной функции случайного аргумента;

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

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

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

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

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

4.4 Выводы к главе 4

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

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

Заключение

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

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

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

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

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

Практическую ценность работы составляют:

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

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

Результаты, полученные в ходе диссертационной работы, были использованы при выполнении НИР в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы»: «Разработка инструментальной оболочки проектирования высокопроизводительных приложений для Грид-архитектур в целях создания прикладных сервисов компьютерного моделирования и обработки данных» (2007-4-1.4-20-01-025) и «Высокопроизводительный программный комплекс моделирования и прогноза экстремальных гидрометеорологических явлений и расчета воздействий на морские объекты и сооружения» (2007-4-1.4-00-06-108). В процессе работы получено свидетельство о государственной регистрации программ для ЭВМ: «PEG2» (свидетельство №2008614623).

Изложенные в диссертации результаты обсуждались на 9 международных и российских научных конференциях, семинарах и совещаниях, включая ежегодные Международные научно-практические семинары «Высокопроизводительные параллельные вычисления на кластерных системах» (2006 г., Санкт-Петербург; 2007 г., Нижний Новгород; 2008 г., Казань), ежегодные Всероссийские научные конференции «Научный сервис в сети Интернет» (2007 и 2008 гг., Новороссийск), ежегодную Международную научную конференцию «Параллельные вычислительные технологии (ПаВТ 2008)», XV Всероссийскую научно-методическую конференцию «Телематика 2008», IV и V Межвузовские научные конференции молодых ученых (2007 и 2008 гг., Санкт-Петербург).

1. Foster I., Kesselman. С. The Grid2: Blueprint for a New Computing Infrastructure (Second edition). Morgan-Kaufman, 2004.

2. Foster I., Kesselman. C. The Grid: Blueprint for a New Computing Infrastructure. Morgan-Kaufman, 1999.

3. Bolt, Beranek, Newman. A History of the ARPANET: The First Decade. 1981.

4. NSFNET: The Partnership that Changed the World. NSFNET. http://www.nsfhet-legacy.org/.

5. Crocker, Steve. RFC 1. IETF Tools. 1969 April 7 http://tools.ietf.org/html/rfcl.

6. SETI@home. http://setiathome.berkeley.edu/.

7. BOINC Homepage. BOINC. http://boinc.berkeley.edu/.

8. Henning M., The Rise and Fall of CORBA: The story behind this once-promising distributed computing technology-why it fell short, and what we can learn from it. ACM Queue. http.7/acmqueue.com/modules.php?name=Content&pa=showpage&pid=396.

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

10. Thain D., Tannenbaum Т., and Livny M. Condor and the Grid // Berman F., (Editor), Fox G. (Editor), Hey J.G. A. (Editor) Grid Computing: Making The Global Infrastructure a Reality. John Wiley, 2003.

11. Stockinger H. Defining the Grid: a snapshot of the current view // Journal of Supercomputing, Springer Science+Business Media, 2007.

12. Foster I., Kesselman C, Tuecke S. The Anatomy of the Grid // Enabling Scalable Virtual Organizations, http://www.globus.oig/alliance/publications/papers/anatomy.pdf.

13. Globus Toolkit Homepage rhttp://globus.org/toolkit/l.14. gLite http://glite.web.cern.ch/glite/.

14. EGEE Homepage http://public.eu-egee.org/.

15. CERN rhttp://www.cern.cli/1.

16. SAGA fhttp ://forge.о gf.ore/sf/proi ects/saga-rof.

17. GPE http://gpe4gtk.sourceforge.net/.

18. Open Grid Forum: http://www.ogf.org/.

19. Соммервилл И. Инженерия программного обеспечения, 6-е изд. / Пер. с англ. — М.:22.