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

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

е/

и-

Боченина Клавдия Олеговна

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

Специальность 05.13.11 - Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

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

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

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

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

Официальные оппоненты: Шабров Николай Николаевич,

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

Поляков Андрей Николаевич,

кандидат технических наук Национальный исследовательский центр «Курчатовский институт», начальник лаборатории, г. Москва

Ведущая организация: Институт проблем передачи информации

им. А.А.Харкевича Российской Академии Наук, г. Москва

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

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д.49 и на сайте fppo.ifmo.ru.

Автореферат разослан «_» _2014 года.

Ученый секретарь диссертационного совета Лобанов И.С.

' РОССИЙСКАЯ 'ГОСУДАРСТВЕННАЯ

ЙИВЛИОТЕКЛ 3

?0 '5_______

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

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

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

Предметом исследования являются модели, методы и технологии статического планирования исполнения наборов КП.

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

Задачи исследования: - обоснование требований к алгоритмам статического планирования наборов КП для систем с временными окнами на основе анализа предметной области;

- разработка математической модели неоднородной распределенной вычислительной среды с временными окнами;

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

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

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

- оценка эффективности разработанных алгоритмов на основе вычислительных экспериментов: а) для синтетических наборов КП с различными характеристиками графов задач; б) для типовых наборов научных КП Cybershake, Montage и Genome; в) для задачи калибровки параметров ансамблевого прогноза нагонных наводнений в Санкт-Петербурге.

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

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

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

- алгоритмы позадачного планирования MDW-T (Multiple Deadline-Constrained Workflows - Task-based), планирования с использованием стадийной схемы приоритизации КП MDW-W (Workflow-based), класте-ризационного планирования MDW-C (Clusterization-based), позволяющие формировать статические планы запуска задач набора КП на совокупности неоднородных ресурсов с поддержкой временных окон;

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

' СЬАУШЕ (СЬоис! АррНсаиоп УЖШа! ЕгтгоптегН) - многопрофильная инструмснтально-тсхнологическая платформа создания, разработки и эксплуатации облачных сред второю поколения, разработанная в НИИ НКТ Университета ИТМО в 2010-2012 гг. в рамках проекта «Создание распределенной вычислительной среды на базе облачной архитектуры для построения и эксплуатации высокопроизводительных композитных приложенийвв рамках реализации постановления Правительства РФ№ 218.

На защиту выносятся:

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

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

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

Внедрение результатов работы. Результаты работы использованы при выполнении следующих НИОКР: «Виртуальный полигон для суперкомпьютерного моделирования сложных систем» (соглашение от 17.08.2012 г. № 14.В37.21.0596), «Интеллектуальные суперкомпьютерные технологии е-Science» (соглашение от 20.08.2012 г. № 14.В37.21.0592) в рамках реализации постановления №220 Правительства РФ (договор №11.G34.31.0019), «Предсказательное моделирование экстремальных явлений и оценка рисков устойчивого развития сложных систем» НИР № 713581 (2013-2014 гг.) в рамках реализации постановления № 211 Правительства РФ, проект Российского научного фонда «Суперкомпьютерное моделирование критических явлений в сложных социальных системах» (№ 14-21-00137).

Апробация работы. Полученные результаты обсуждались на международных и всероссийских научных конференциях, семинарах и симпозиумах, включая IX Международную конференцию-семинар «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Владимир, 2009), IX Международный симпозиум «Интеллектуальные системы» (г. Владимир, 2010), II и III сессии научной школы «Технологии высокопроизводительных вычислений и компьютерного моделирования» (Санкт-Петербург, 2009, 2010), XVII Всероссийскую научно-методическую конференцию «Телематика 2010» (Санкт-Петербург, 2010), XIV Международную конференцию «International Conference on Computational Science» (г. Кэрнс, Австралия, 2014).

Публикации. По материалам диссертации опубликовано 13 научных работ, в том числе 3 статьи - в изданиях из перечня ведущих рецензируемых научных журналов и изданий ВАК РФ, 2 статьи - в изданиях, индексируемых SCOPUS, получено два свидетельства о государственной регистрации программ.

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

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

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

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

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

Современные системы исполнения КП (Pegasus, Taverna, Triana и др.) могут использовать различные типы распределенных вычислительных сред. Основная тенденция их развития - создание методов и моделей построения гибридных инфраструктур, объединяющих разнородные ресурсы на основе облачных моделей предоставления услуг. Гибридные среды подразумевают поддержку унифицированного доступа не только к платформам, ПО и инфраструктурам (облачные модели PaaS, SaaS и IaaS), но и к вычислительным сервисам, обеспечивающим сокрытие деталей реализации и исполнения КП от конечного пользователя (модель AaaS), что делает возможной комплексную поддержку интерпретации КП как набора сервисов, связанных по управлению и по данным.

Наиболее общая классификация задач планирования КП в неоднородных средах может быть получена при рассмотрении комбинаций возможных свойств самых КП, инфраструктур их исполнения, а также целей планирования и ограничений, накладываемых на допустимое решение. Этот подход базируется на нотации теоретических проблем планирования a|ß|y (а - свойства вычислительной среды, ß - свойства задач, у - вид целевой функции). В

табл. 1 приведены возможные значения а, р и у, полученные путем анализа наиболее распространенных задач планирования КП.

Таблица 1 - Свойства основных компонент задач планирования КП

Вычислительная среда а Композитное приложение /3

mpvd - число провайдеров ресурсов > I Неоднородность: Н - аппаратная, S -программная, С - коммуникационная, Р -ценовая, сочетание нескольких видов, nded - частичная доступность ресурсов, ondm - возможность выделения ресурсов по запросу, virt - виртуализованные ресурсы musr - число владельцев (пользователей) КП >1, mwf - одновременно планируется более одного КП, dshape - форма графа задач может меняться в ходе выполнения КП, Оценки времени выполнения пакетов: del - детерминированные, stoch - стохастические, unav - недоступны, migr - возможна миграция задач, pempt - возможна временная приостановка задач, сотт - учитывается время передачи данных между задачами, dpar - задачи КП параллельны по данным

Критерии у

Провайдер: Eff - эффективность загрузки ресурсов, Energy - энергоэффективность, Ргос - число используемых вычислительных устройств. Пользователь: Cost - стоимость исполнения КП, Time - время исполнения КП, Wait - время ожидания запуска КП

В табл. 2 приведены сведения об исследованных постановках задач планирования КП в соответствии с нотацией а|Р|у. Анализ исследований в области статического планирования наборов композитных приложений позволяет сделать вывод о том, что на данный момент в открытых источниках не описаны постановки задач вида HS,nded \mwf,det,comm\ MinTime (Time). Вместе с тем анализ типовых случаев практического применения КП позволяет выявить класс задач планирования наборов КП во временных окнах, границы которых определяются как текущей занятостью ресурсов, так и ограничениями пользователей на сроки старта и завершения КП (в качестве примеров можно привести штатный режим функционирования систем экстренных вычислений и пакетное исполнение КП в рамках образовательного процесса).

В целом это определяет совокупность требований к входным данным и области применения алгоритмов решения таких задач: 1) базой исполнения КП является статический набор ресурсов; 2) имеются достоверные оценки времени исполнения планируемых задач вследствие ограниченности базы пакетов, доступных для запуска, и периодичности процессов исполнения КП; 3) специфика предметной области определяет необходимость и возможность единовременного планирования набора КП; 4) при планировании необходимо учитывать данные об имеющемся резервировании вычислительных мощностей; 5) на качество формируемых планов накладываются ограничения, определяемые требованиями пользователей и/или провайдеров ресурсов.

Таблица 2 - Постановки задач планирования КП в нотации a|ß|y

№ п/п Свойства вычислительной среды и КП (а | ß) Целевая функция и ограничения (у) Авторы, год опубликования

] НС \ del MinTime(Proc) Ramamoorthy, Chandy, Gonzalez, 1972

2 НС ¡del, comm MinTime Gerasoulis, Yang, 1992

3 01 del, pempl MinTime Djellab, 1999

4 01 del,dpar MinTime Wang, Cheng, 1991 Radulescu и др., 2001

5 01 det.dshape MinTime Towsley, 1986

6 HSCP,mpvd, nded \ musr, del.com MinCosl(Time), Min Time(Cost) Yu, Buyya, Tam, 2005 Yu, 2007

7 H, nded | mwf,del MinTime Hirales-Carbajal, Tchemykh и др., 2012

8 HSCP | mwf, stach, comm MinCost(Time) Afzal и др., 2006

9 HC,nded\mwf del, comm MinTime Zhao, Sakellariou, 2006 Bittencourt, Madeira, 2009

10 HC, nded | mwf, del, comm, dpar MinTime N'Takpe, Suter, 2009

11 HSCP, nded,virt, ondm | del,comm MinTime MaxEff(Time) Lin, Lu, 2011 Zhu и др., 2012

12 HSCP, virt, ondm \ del, comm, dshape, dpar Min Time(Cost) Carón и др., 2012

13 HC \ del, comm MinTime MaxEnergy Ebrahimirad и др., 2010 Durillo и др., 2013

14 HSCP, virt, ondm | del, comm Min Time(Time, Cost) Calheiros, Buyya, 2013

15 CP, virt,ondm | mwf ,det,comm MaxEff(Time, Cost) Malawski и др., 2012

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

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

фикацию способов кластеризации и вариантов структуры алгоритмов класте-ризационного планирования.

Распределенная облачная среда представляет собой множество вычислительных ресурсов Д, представляющее собой набор непересекающихся подмножеств Л/,, / е 1, NT, где NT - число типов ресурсов. К одному и тому же типу относятся ресурсы с одинаковыми техническими характеристиками и функцией утилизации g,(r),Tsr/r (Г - длина периода планирования), причем временем передачи данных между ресурсами одного типа можно пренебречь. Обозначим отдельный ресурс как iel,NT, jеl.NRt,, где NRt, -число ресурсов типа Л/,. Пусть также задана матрица коммуникации Мсотт размера [AYxAV], задающая скорость передачи данных между ресурсами различных типов.

Пусть необходимо спланировать набор композитных приложений WJSet, состоящий из Wfi%i = \,NWF, где NWF - общее число КП в наборе. Каждое КП представляет собой ориентированный ациклический граф вычислительных задач TaskjjJ = \,NWF,j = \,Ntj (М, - число задач /-го КП), для которого дополнительно задана матрица DataiJk объемов данных, передаваемых от j-й к Jt-й задаче i-ro КП. Структура /-го КП задается матрицей смежности (к,, Е;), / = 1, Nwf , где К, - множество задач /' -го КП, £, = | у, к е V, х V,■} - набор ребер, выражающих зависимости между задачами. Для каждой задачи заданы номера типов ресурсов TaskRtijk,k = l, Nn^, на которых может быть выполнена задача (Nrt¡j - число таких типов для j -й задачи /-го КП), и известны оценки времени выполнения задачи tijk для каждого типа ресурса. Также для каждого КП заданы границы временного окна планирования - сроки старта tstarti и завершения deadimej, при этом период планирования устанавливается равным максимальному сроку завершения.

Целью планирования является нахождение отображения множества задач на множество ресурсов с указанием времени запуска каждой задачи: Shedij=Sched(Tasku)=^Desiu,tf/'8^. Штраф для /-го КП рассчитывается как i 0, tend I < deadline j

\tendj - deadline,, tend, > deadline j. ^

Предполагается, что задачи не могут запускаться на исполнение по завершении периода планирования, потому возможно получение неполного плана, содержащего назначения не для всех имеющихся задач: 3/ е 1, NWF, je\,Ntj\ Schedjj = 0. Примерное время окончания для неполного плана /-го КП вычисляется как:

j

tend, = tend I avg t,jk + max AvgComm,^ ,j e\,Nt, -.Destijask^Cd,

(2)

k = \,Nrtu,le\,Nti:etl = \,

где tendf = max. tendi f-m, fin e ], Nr, : Dest{Taski (ln)* 0 - максимальное время за-

fin

вершения среди задач, имеющих назначение на ресурсы в плане, AvgComm1>7 -среднее время передачи данных между j-й и 1-й задачами i-ro КП. Максимальный штраф Finelncomp™'* рассчитывается с использованием выражений

(1), (2) для случая Dest(Taskij)=0 для всех задач i'-го КП, общий - как

_

Fine = 2_,Fine, /Finelncomp™* , а средний - как Fine = Fine/NWF.

/=I

Для учета справедливости распределения ресурсов между разными пользователями/КП введем следующую метрику:

Fairness = 1 - max \ahs{Finej - Fine /)]/ Finelncomp J™" . q)

Пусть Schedi и Sched2 - два плана, Л' - область допустимых решений (множество возможных планов). Функцию полезности U:X —>[0;l] зададим следующим образом:

U = р, • IV + р2 ■ (l - Fine)+ Pj • Fairness . (4)

Здесь р|,р2>л е[0;']' Р\+ Pi+ Pi =' _ весовые коэффициенты, определяющие сравнительную значимость критериев при принятии решения о предпочтении одного плана другому. Тогда критерий предпочтения для задачи статического планирования наборов КП с ограничениями по крайним срокам завершения может быть сформулирован следующим образом:

Scheil| > х Schedj о U(Schedi) > U(Sched2 ), Sched], Sched2 e X . (5 )

Планирование наборов КП можно выполнять на базе одного из трех основных подходов: 1) позадачное - основано на объединении всех композитных приложений в одно, после чего планирование осуществляется с помощью некоторого алгоритма для одиночных КП; 2) планирование на основе приоритизации КП - приложения набора планируются одно за другим в соответствии с некоторым порядком; 3) планирование на основе кластеризации - все доступные задачи разбиваются на группы (кластеры), после чего планирование осуществляется по каждой группе отдельно.

Формально общая задача кластеризации описывается следующим образом: разбить множество доступных задач Task = {Task/J\, i = \,Nm.,j = \,Nt, на подмножества Clusterk (k = 1, Nc, jVc - число кластеров) таким образом, чтобы каждая задача принадлежала только одному кластеру. Помимо того, на кластеры должно накладываться дополнительное ограничение корректности.

Пусть для некоторой задачи A Parents(A) - множество родительских ж-дач: В е Parents(A), если еВА = 1, т.е. в графе задач существует ориентированная дуга от В к А. Тогда множество предков задачи A Pred(A) может быть определено с помощью рекуррентного соотношения: a) BePred(A), если В е Parents(A); б) BePred(A), если VC е Parents{A) В е Pred{c). Кластеризация

корректна в том, и только в том, случае, когда существует упорядоченный набор номеров кластеров Ord = (k],k2,-,kj,...,kNl kt <e\,Nc (Аг, *kj для / * j) такой, что для любого ie\,Nc выполняется условие:

VA е Clusterk , Vfl е Pred(A) BeC/usterk u...uC/usterk и dusterk . /54

i I i-l i ^ '

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

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

I. Алгоритм позадачного планирования MDW-T (Multiple Deadline-Constrained Workflows - Task-based). Суть процесса планирования заключается в определении порядка доступа задач к ресурсам, т.е. в приоритизации задач с учетом сроков завершения КП. Алгоритм MDW-T включает три этапа.

1. Определение сроков завершения задач

deadline¡jt = deadline¡, weight^ = max weighty,

(7)

deadline ¡j = weight ¡j / weight ¡j. ■ deadline,, j Ф j , где ¡¡j - среднее время выполнения j-й задачи / -го КП:

weight ¡j = tstartj +tiJ,jel,Nti: ekj =0 \/k g 1, ,

weight¡j = tij+max\weightjk+AvgCommjk^\, Taskik s Parents (Task^). ^ ^

2. Построение приоритетной очереди задач с учетом сроков завершения и взаимосвязей задач.

3. Последовательное планирование задач из очереди.

Вычислительная сложность алгоритма <^NWI. -maxM,2 -NT j.

II. Алгоритм стадийного планирования MDW-W (Multiple Deadline-Constrained Workflows - Workflow-based). Для установления порядка доступа КП к ресурсам MDW-W использует критерий приоритизации - метрику, экстремальное значение которой определяет КП, подлежащий планированию. Определение порядка кластеров по этой схеме состоит из NWF стадий.

На стадии 1 определяется набор планов Schedl,...,SchedlN^ независимо для всех

КП в условиях монопольного доступа к ресурсам. После этого приоритетный доступ к ресурсам получает КП с экстремальным значением критерия приоритизации. Затем процесс повторяется итеративно для оставшихся КП. Вычислительная сложность MDW-W 0^f[x\,x2,...,xp\ N^p), где хьх2.....хр - параметры, определяющие сложность алгоритма, выбранного для планирования одиночных КП.

III. Алгоритм кластеризационного планирования MDW-C (Multiple Deadline-Constrained Workflows - Clusterization-based) состоит из двух основных этапов.

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

1) каждая задача выделяется в отдельный кластер. Для каждого кластера определяются вес, предполагаемые сроки старта и завершения по формулам (7), (8). После этого кластеры упорядочиваются в порядке возрастания сроков завершения;

2) на каждой итерации (начиная со второго и заканчивая NWF-\ кластером) выполняется попытка слияния текущего кластера: а) с последующим; б) с предыдущим. Пусть SumL - сумма длин кластеров (разностей между сроком завершения и сроком старта), AvgDiffWeight - средняя разность весов кластеров, MaxSumL - сумма длин начальных кластеров, MaxAvgDiffWeight - полусумма весов максимального кластера и кластера нулевого веса. Для вариантов а) и б) вычисляются значения критерия f',f,2 (для i'-й итерации):

AvgDiffWeight SumL MaxAvgDiffWeight MaxSumL' ^ '

Если min(/',.Д2)</,_,, то на ;-й итерации осуществляется слияние текущего кластера с тем из соседних, который при слиянии обеспечивает меньшее значения критерия^;

3) процесс итеративного слияния кластеров продолжается до тех пор, пока при проходе от кластера 2 до Nc -1 происходит хотя бы одно слияние.

2. Планирование кластеров:

1) построение орграфа зависимостей кластеров для каждого КП;

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

3) определение КП Wj\., кластер которого будет спланирован на текущем этапе, в соответствии с минимальным резервным временем:

Ideadline, - шах(ten d(SchClustl)\SchClustl

ReservedTime, = < ^ , (10)

[deadline, - tstart,, SchClust, =0 '

где SchClust, - множество номеров спланированных кластеров / -го КП;

4) выбор кластера для планирования в соответствии с максимальным значением следующей метрики:

М(С) = 0.5. -eight(C)/length(O + 05 deadlinejc)

к ' MaxWL MinD v '

где С - кластер КП / *, MaxWL - максимальное отношение веса кластера к его длине, MinD - минимальный срок завершения кластера для КП /*;

5) планирование задач выбранного кластера в порядке их следования, фиксация занятых временных интервалов, обновление сроков завершения текущего кластера, старта и завершения всех следующих кластеров (шаги 2-5 повторяются до тех пор, пока все кластеры не будут спланированы).

Вычислительная сложность алгоритма кластеризации задач составляет

C^NWh -max. Ntf^,i = \,NWh-, а алгоритма планирования - о(м • /(*,,...,где

хих2,...,хр - параметры, определяющие сложность алгоритма, выбранного для планирования отдельных кластеров.

В четвертой главе экспериментально исследована эффективность разработанных алгоритмов на основе вычислительных экспериментов: а) для синтетических наборов КП с различными характеристиками графов задач; б) для типовых наборов научных КП Cybershake, Montage и Genome; в) для задачи калибровки параметров ансамблевого прогноза нагонных наводнений в Санкт-Петербурге.

I. Синтетические КП генерировались для формирования наборов, содержащих КП с различными формами графов задач, а также параметрами вычислительной и коммуникационной интенсивности. Каждый набор экспериментов выполнялся для КП фиксированного размера (5, 10, 20 или 50) с варьированием числа КП в наборе (от 25 до 400) на одном и том же тестовом наборе ресурсов. Сроки завершения КП были установлены одинаковыми и равными концу периода планирования. Каждый эксперимент проводился дважды для двух различных значений длины периода планирования (TightT и WideT) с целью смоделировать разные степени конкуренции за ресурсы. На рис. 1, 2 представлены значения исследуемых метрик качества расписаний для экспериментального набора, состоящего из 20-задачных КП.

>5 1

о. 0.95

tu

£ 0.9 0.85

'I 08

5 0.75

§ 0.7

6 0.65

0.6

ф

а)

ос 0.8

I ».7

m 0.6 ф

° 0.5

8. 0.4

| 0.3

S-P0.2

0) к | ° 0.1

II о

о 3

а)

Рисунок 2 - Среднее резервное время (доля от Т) для TightT (а) и WideT (б)

к 1

х 1

з 1

| Sj 0.8

О) Q. ig °-6 £ го

го м 0 4

I ш

I

et о

0

50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 350 400

Число КП в наборе б) Число КП в наборе

Рисунок 1 - Интегральный критерий (а) и (б) доля нарушенных сроков завершения (для TightT)

0 50 100 150 200 250 300 350 400 ц$

MDW-T 20 5IDW-W 20 WDW-C 20

100

Z50

150 200

300 350 400

Число КП в наборе

Число КП в наборе

Преимущество MDW-T по значениям интегрального критерия обусловлено более равномерным распределением вычислительных ресурсов между КП (среднее преимущество MDW-T по метрике Fairness составляет 6% по сравнению с MDW-C и 11% по сравнению с MDW-W). Вместе с тем в условиях высокой конкуренции за ресурсы использование MDW-T приводит к резкому возрастанию числа нарушенных сроков завершения КП по сравнению с MDW-W и MDW-C, причем MDW-C предоставляет меньшие значения среднего штрафа и большие значения среднего резервного времени, чем MDW-W.

11. Типовые наборы КП Montage, Cybershake и Genome включали файлы формата DAX, сгенерированные на основании реальных запусков КП в системе управления КП Pegasus. Границы временных окон назначались случайным образом (с учетом ограничения на минимальную длину окна), чтобы смоделировать ситуацию разных требований к срокам старта и завершения задач. В каждый тестовый набор (например, Montage) были включены КП, состоящие из 50, 100, 200-1000 задач. Эксперименты для каждого сочетания размера КП и размера набора проводились с варьированием минимальной длины окна для моделирования различных уровней конкуренции за ресурсы. Итоговые значения метрик для каждого тестового набора были получены усреднением значений для КП разного размера.

Рисунок 3 - Интегральный критерий для наборов Cybershake(a) и Genomc(6)

Рисунок 4 - Среднее резервное время (доля от Т) для наборов Montage(a) и Сепоше(б)

На рис. 3 приведены значения интегрального критерия для тестовых наборов Cybershake и Genome (номера итераций возрастают с увеличением длины окна). Для Cybershake среднее преимущество MDW-C по сравнению с MDW-W и MDW-T составило 7 и 17% соответственно, для Genome - 7 и 14 %. На рис. 4 приведены значения среднего резервного времени для наборов Montage и Genome, также подтверждающие преимущество MDW-C.

III. КП задачи калибровки параметров ансамблевого прогноза нагонных наводнений в Санкт-Петербурге. Эксперименты с использованием разработанных алгоритмов проводились для двух типов предметных КП: 1) ансамблевого прогнозирования нагонных наводнений в СПб - требуется запуск КП в режиме пакетного планирования при решении задачи обратной калибровки параметров ансамблевого прогноза на основе анализа ретроспективных данных; 2) расчета поля морского волнения по акватории Балтийского моря для использования в системе предотвращения угрозы наводнений.

Для первого типа предметного КП среднее преимущество MDW-C по интегральному критерию составило 4,5% по сравнению с MDW-T и 11,5% -по сравнению с MDW-W. На рис. 5а приведено значение интегрального критерия для задачи расчета поля морского волнения (среднее преимущество MDW-C составляет 9% по сравнению с MDW-T и 17% по сравнению с MDW-W). При этом время работы кластеризационного алгоритма (рис. 56, М - параметр, определяющий размер КП) для максимального размера набора (264 20-задачных КП) составило порядка 8 с, что несущественно при длине периода планирования порядка суток.

1

>§ 0.95

& 0.9 £ 0.85

J 0.75 ê 0.7 2.0.65 Si 0.6

^ 0.55 0.5

MDW-T 20 MDW-W 20 MDW-C 20

MDW-T 20 MDW-W 20 MDW-C 20

25 50 100 150 200 Число КП в наборе

Э) Номер периода планирования б)

Рисунок 5 - Интегральный критерий (а) и время работы алгоритмов (б) для задачи расчета поля морского волнения но акватории Балтийского моря

Экспериментальное исследование эффективности разработанных алгоритмов при планировании наборов КП в распределенной облачной среде производилось на базе платформы CLAVIRE. С этой целью был разработан сервис планирования наборов композитных приложений, реализующий алгоритмы MDW-T, MDW-W, MDW-C, и осуществлено внедрение КП Montage в систему управления CLAVIRE. Для проведения экспериментов на двух блейд-серверах конфигурации 32xlntel Xeon Е5-2650 2.00 GHz, 96 Gb ОЗУ

было развернуто 20 идентичных виртуальных машин под управлением Oracle Virtual Box (ОС Windows 7 32-bit).

Результаты экспериментов приведены в табл. 4 (tendri,al - фактическое время завершения исполнения набора, tendSih - время завершения набора в базовом плане). Кластеризационный алгоритм обеспечивает соблюдение крайних сроков завершения для всех размеров тестового набора. Значения среднего резервного времени при этом для всех трех алгоритмов сходны. Несмотря на то что доля задач, опоздавших по сравнению с базовым планом, является стабильно высокой, среднее опоздание КП по сравнению с базовым планом для MDW-C и MDW-W не превышает 7 %.

Таблица 4 - Метрики качества планов (КП Montage, исполнение в CLAVIRE)

NT Интегральный критерий Среднее резервное время (доля от Т) Доля опоздавших задач

MDW-T MDW-W MDW-C MDW-T MDW-W MDW-C MDW-T MDW-W MDW-C

40 1 1 1 0.295 0.415 0.303 0.725 0.518 0.675

60 1 1 1 0.073 0.086 0.09 0.71 0.7 0.7

80 0.93 0.98 1 0 0.004 0.083 0.73 0.65 0.375

100 1 1 1 0.083 0.061 0.07 0.70 0.88 0.74

120 0.99 0.99 1 0.02 0.023 0.083 0.91 0.775 0.83

NТ Среднее время опоздания КП (доля от Т) tend / tendnh tendrml / deadline

MDW-T MDW-W MDW-C MDW-T MDW-W MDW-C MDW-T MDW-W MDW-C

40 0.0297 0 0.001 1.085 0.99 1.00 0.757 0.691 0.699

60 0.03 0 0 0.98 0.94 0.93 0.95 0.91 0.90

80 0.17 0.07 0 1.17 1.07 0.95 1.14 1.04 0.93

100 0.0048 0.049 0.034 1.01 1.05 1.04 0.95 0.95 0.95

120 0.10 0.09 0.07 1.12 1.12 1.11 1.01 1.01 0.93

Заключение. В ходе выполнения диссертационной работы получены

следующие основные результаты:

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

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

- разработаны метод кластеризационного планирования наборов КП и алгоритмы (позадачного планирования МО\\'-Т; стадийного планирования на основе приоритизации КП кластеризационного планирования \1DW-C), реализующие различные техники группировки и упорядочивания задач на его основе;

на основе вычислительных экспериментов для синтетических и предметных наборов композитных приложений, в том числе с использованием облачной платформы СЬАУЖЕ, продемонстрирована работоспособность и эффективность предложенных алгоритмов.

Список публикаций по теме диссертации Публикации в изданиях, рекомендованных ВАК РФ

1. Боченина К.О., Духанов A.B., Медведева О.Н., Павлов A.A. Разработка математического и программного обеспечения поддержки принятия решений в многоэтапном распределении ресурсов с применением параллельных вычислений и методов оптимизации // Информатизация образования и науки. 2011. № 2(10). С. 81-90. Объем: 0.4 п.л. (авторский вклад 0.1 п.л.).

2. Боченина К.О. Математическая модель функционирования динамических систем с ресурсными потоками на базе системного и кибернетического подходов // Динамика сложных систем-XXI век. 2012. Т.6, № 4. С. 42-47. Объем: 0.31 п.л. (авторский вклад 0.31 п.л.).

3. Боченина К.О., Духанов A.B. Особенности планирования загрузки вычислительных ресурсов в облачных средах второго поколения на основе модели отложенных вычислений во временных окнах // Динамика сложных систем-XXI век. 2013. Т. 7, № 3. С. 83-89. Объем: 0.375 п.л. (авторский вклад 0.19 п.л.).

4. Bochenina К.О. A comparative study of scheduling algorithms for the multiple deadline-constrained workflows in heterogeneous computing systems with time windows // Procedía Computer Science. 2014. Vol. 29. P. 509-522. Объем: 0.81 п.л. (авторский вклад 0.81 п.л.).

5. Dukhanov A.V., Karpova М.А., Bochenina К.О. Design Virtual Learning Labs for Courses in Computational Science with use of Cloud Computing Technologies // Procedía Computer Science. 2014. Vol. 29. P. 2472-2482. Объем: 0.625 п.л. (авторский вклад 0.21 п.л.).

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

1. Боченина К.О., Духанов A.B., Аракелян С.М. Система динамического моделирования ресурсных потоков с применением системной динамики и методов оптимизации // Сб. тр. XV Всерос. науч.-метод, конф. «Телематика 2008». 2008. Т. I. С. 205-206. Объем: 0.1 п.л. (авторский вклад 0.033 п.л.).

2. Боченина К.О., Духанов A.B., Медведева О.Н. О распараллеливании алгоритма решения задач многошаговой оптимизации по схеме Беллмана // Сб. матер. IX Междунар. конф. «Высокопроизводительные параллельные вычисления на кластерных системах». ВлГу, 2009. С. 62-63. Объем: 0.1 п.л. (авторский вклад 0.033 п.л.).

3. Боченина К.О., Духанов A.B. Динамическое моделирование систем с ресурсными потоками с применением системной динамики и методов оптимизации // Тез. докл. науч. шк. «Технологии высокопроизводительных вычислений и компьютерного моделирования». СПбГУ ИТМО, 2009. Вып. 7. С. 6. Объем: 0.1 п.л. (авторский вклад 0.05 п.л.).

4. Боченина К.О., Духанов A.B., Медведева О.Н., Новикова O.A. Разработка информационной системы многошаговой оптимизации параметров

динамических систем с применением эвристических алгоритмов и методов распределенных вычислений // Сб. тр. 9-го Междунар. симп. «Интеллектуальные системы». М.: Русаки, 2010. С. 469-472. Объем: 0.1 п.л. (авторский вклад 0.025 п.л.).

5. Боченина К.О., Медведева О.Н., Павлов A.A. Разработка параллельного алгоритма решения задач многошаговой оптимизации деятельности сложных динамических систем с обратными связями // Тез. докл. науч. шк. «Технологии высокопроизводительных вычислений и компьютерного моделирования». СПбГУ ИТМО, 2010. Вып. 5. С. 98. Объем: 0.1 п.л. (авторский вклад 0.033 п.л.).

6. Боченина К.О., Медведева О.Н., Павлов A.A. Система поддержки принятия решений в многоэтапном распределении ресурсов с применением параллельных вычислений и методов оптимизации // Сб. тр. 9-го Междунар. симп. «Интеллектуальные системы». М.: Русаки, 2010. С. 490-493. Объем: 0.1 п.л. (авторский вклад 0.033 п.л.).

7. Боченина К.О., Духанов A.B., Медведева О.Н., Павлов A.A. Информационная система многошаговой оптимизации параметров динамических систем с обратными связями с применением эвристических алгоритмов и методов параллельного программирования // Сб. тр. XVII Всерос. науч.-метод. конф. «Телематика'2010». СПб, 2010. Т. 2. С. 369-370. Объем: 0.1 пл. (авторский вклад 0.033 пл.).

8. Боченина К.О., Медведева О.Н., Павлов A.A., Таравкова Т.В. Разработка распределенной системы динамического программирования нелинейных процессов с применением многошаговой оптимизации // Сб. тр. XVII Всерос. науч.-метод. конф. «Телематика'2010». СПб, 2010. Т. 2. С. 153-159. Объем: 0.1 п.л. (авторский вклад 0.025 п.л.).

9. Свид-во о гос. регистрации программы для ЭВМ № 2010610429 «Система динамического моделирования ресурсных потоков с применением системной динамики и методов оптимизации» / К. О. Боченина, А. В. Духанов. 11.01.2010г.

10. Свид-во о гос. регистрации программы для ЭВМ № 2014613326 «Программная библиотека планирования исполнения композитных приложений в облачной среде» / К.О. Боченина, H.A. Бутаков, П.А. Смирнов. 25.03.2014 г.

15-429

Формат: 60x84 1/16 Печать офсетная.

Бумага офсетная. Гарнитура Times. Тираж: 100 экз. Заказ: 411 Отпечатано: Учреждение «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., д. 14 +7(812) 9151454, zakaz(«jtibir.ru, www.libir.ru

2014250131