Технология исполнения экстренных композитных приложений на основе гибридных методов планирования тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Бутаков Николай Алексеевич

• Бутаков Николай Алексеевич
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Бутаков Николай Алексеевич

Термины и обозначения

Введение

1. Технологии экстренных вычислений

1.1. Основные понятия экстренных вычислений

1.2. Вычислительная среда исполнения экстренных вычислений

1.3. Методы планирования экстренных композитных приложений

1.4. Выводы по главе

2. Методы планирования экстренных композитных приложений в гетерогенных распределенных вычислительных средах

2.1. Математическая модель распределенной вычислительной среды

2.1.1. Модель распределенной гетерогенной вычислительной среды

2.2. Математическая модель композитных приложений

2.2.1 Модели производительности задач ЭКП и их расширение

2.3. Постановка задачи планирования экстренного композитного приложения

2.2.2 Цели и ограничения задачи планирования

2.2.3 Формальная постановка задачи планирования как проблемы комбинаторной оптимизации

2.4. Гибридные методы планирования экстренных композитных приложений

2.4.1. Планирование с учетом надежности

2.4.2. Метод планирования МНСН на основе разделения времени

2.4.3. Коэволюционное расширение метода МНСН для повышения эффективности планирования за счет управления инфраструктурой

2.4.4. Повышение эффективности планирования за счет применения элементов эволюционной динамической оптимизации

2.4.5. Планирование структуры ЭКП для соблюдений ограничений времени выполнения

2.5. Выводы по главе

3. Технология исполнения экстренных композитных приложений

3.1. Особенности вычислительной среды исполнения ЭКП и взаимодействие моделей . 85 3.1.1. Общая характеристика среды исполнения ЭКП

3.2. Общая архитектура вычислительной среды исполнения ЭКП

3.3. Организация процесса сбора данных о процессе исполнения. Способы усвоения данных в модели производительности сложных приложений

3.4. Симулятор вычислительной среды

3.5. Выводы по главе

4. Применение экстренных вычислений для задач поддержки принятия решений и

оптимизации

4.1. Экспериментальное исследование гибридных методов планирования ЭКП

4.1.1. Исследование обеспечения надежности исполнения ЭКП за счет использования пула внешних вычислительных ресурсов

4.1.2. Планирование с разделением по времени в условиях нарушения процесса исполнения КП

4.1.3. Исследование применения коэволюционного подхода для повышения эффективности планирования

4.3. Экспериментальные ЭКП для поддержки принятия решения

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

4.5. Выводы по главе

Заключение

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ

Термины и обозначения

ЭВ - Экстренные вычисления

ВС - Вычислительная среда

ОС - Операционная система

КЗС - Комплекс защитных сооружений

МПКВ - Модель производительности качества выполнения

КП - Композитное приложение

ЭКП - Экстренное композитное приложение

СУ ЭКП - Система управления экстренными композитными приложениями

СРП - Система раннего предупреждения

КС - Критическая ситуация

ЯП - Язык программирования

ЛПР - Лицо принимающее решение

ММП - Математическая модель приложения

ММСП - Математическая модель базового приложения

ММПРВ - Математическая модель приложения реального времени

ММБП - Математическая модель базового приложения

СКО - Средне квадратичное отклонение

API - Application Programming Interface

IaaS - Infrastructure-as-a-Service

SLA - Service Level Agreement

SOA - Service Oriented Architecture

AaaS - Application as a Service

CPU - Central Processing Unit

DOP - Dynamic Optimization Problem

Введение диссертации (часть автореферата) на тему «Технология исполнения экстренных композитных приложений на основе гибридных методов планирования»

Введение

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

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

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

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

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

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

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

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

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

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

Ценность диссертационной работы заключается в расширении алгоритмического и программного инструментария для решения практически значимых задач управления исполнением экстренных композитных приложений для систем раннего предупреждения и поддержки принятия решений в критических ситуациях. Ценность работы подтверждается участием в 5 международных и всероссийских конференциях, семинарах, симпозиумах, наличием свидетельства о государственной регистрации программ для ЭВМ и 6 статей (все в рецензируемых научных журналах и изданиях, индексируемых международными системами научного цитирования SCOPUS или Web of Science).

1. Технологии экстренных вычислений

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

1.1. Основные понятия экстренных вычислений

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

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

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

г1р8Ы8 РсакУа1Са1сОкауа г1рР5А

Рисунок 1.1.1 - Композитное приложение для оценки последствий землетрясений СуЬегБЬаке [6].

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

КП, условия исполнения которых удовлетворяют описанным выше положениям, будем называть экстренными композитными приложениями (ЭКП).

Экстренные композитные приложения. Кроме специфики применения, ЭКП выделяются следующими особенностями:

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

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

- отсутствие знаний о точном моменте запуска;

- требования к надежности процесса исполнения ЭКП.

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

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

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

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

- варьируемые объем и структура ЭКП.

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

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

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

Изменения вносимые в объем и структуру ЭКП можно классифицировать следующим образом:

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

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

- изменение времени обработки и вычислений за счет изменения структуры ЭКП или структуры суб-КП, входящих в ЭКП

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

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

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

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

- загрузка необходимых для выполнения данных на вычислительные ресурсы (StageIn). В случае если ресурсы уже содержат необходимые данные (подход Code-to-Data), то выполняется просто проверка их доступности;

- исполнение ЭКП. Сам процесс исполнения, который также может включать изменение пула вычислительных ресурсов;

- предоставление результатов (81а§еОи1;).

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

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

Таблица 1.1 - СРП и фреймворки экстренных вычислений

Название системы Год Тип инфраструктуры Возможности планирования Тип приложения Особенности экстренных вычислени

North Carolina Forecast System 2012 Кластер нет статичное приложение (не требует планирования) Выделенный пул ресурсов

Clavire 2013 Система облачных вычислений второго поколения: кластера, гриды, облачные ресурсы Эвристик с моделями производительности вычислительных задач КП критический приоритет, модели производительнос ти

UrbanFlood 2011 Облачные ресурсы Динамическое выделение ресурсов по необходимости КП Приостановка выполнения, использование ресурсов внешних провайдероы

Japan EarthQuake System 2012 кластер нет статичное приложение (не требует планирования) Выделенный пул ресурсов

Spruce 2011 гриды, облачные ресурсы Выбор ресурсов на основании вероятностной оценки времени выполнения, Набор задач критический приоритет, сокращение ресурсов других приложений(там где это возможно)

ISMPO 2015 Облачные ресурсы Оценка требуемого объема вычислительных ресурсов (в виде количсетва вирт. машин) на основе упрщенного представления КП как bag-of-tasks КП модели производительнос ти

Trestle 2012 Кластер Batch-планировщик с учетом зарезервированных зон для особых приложений Набор задач Резервирование специальных зон для определенных приложений, обычные задачи могут исполняться в этих зонах, но будут прерваны при необходимости

Forest Fire Propagation Prediction 2012 Использование других решений для предоставления ресурсов, например SPRUCE Модель определение количества требуемых ресурсов в зависимости от необходимого качества и доступного качества Набор задач Теже, что и у SPRUCE

Как можно видеть из табл 1.1, большинство систем реализуют упрощенный подход к планированию, заключающийся либо в статическом выделении (резервировании) ресурсов или в динамическом выделении на основе текущих характеристик производительности. Лишь небольшое количество систем опирается на процедуры планирования и оценку времени выполнения отдельных вычислительных задач, необходимую для планирования [12,13,8].

Целью планирования является составление расписания. Расписание это отображение задач ЭКП на вычислительные ресурсы, при этом каждой из задач сопоставлено время ее начала. Необходимость составления расписания объясняется целесообразностью получения оценки времени выполнения всего ЭКП. Если оценка показывает, что текущая конфигурация ЭКП и вычислительной среды не обеспечивает необходимое время выполнения или не удовлетворяет необходимый резерв по времени, то необходимо произвести реконфигурацию - например, уменьшить объем обрабатываемых данных или (возможность) понизить точность (при этом соблюдая некоторое минимальное допустимое для принятия решений значение). Простейший вариант реакции на нарушение ограничений состоит в информировании человека-оператора системы ЭВ о невозможности выполнения в указанных ограничениях. Оценка времени выполнения может быть получена аналитическим путем, с помощью составления моделей производительности всего распределенного приложения [12,90] однако данный подход может давать сильную ошибку в условиях высокой неоднородности вычислительной среды (как по вычислительным мощностям, так и по каналам передачи данных). Основные способы составления расписаний будут рассмотрены ниже в разделе 1.3

1.2. Вычислительная среда исполнения экстренных вычислений

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

Статический подход подразумевает наличие выделенного пула ресурсов, к

которому имеется постоянный или к которому в кратчайшие сроки может быть

организован монопольный доступ. Сейчас это наиболее распространенный способ

организации вычислительной среды для ЭКП. Данный способ применяется, например, в

японской СРП о наступлении землетрясений [14], German National Meteorological Service

[15], North Carolina Forecast System для предсказания ураганов [9]. Главными

14

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

Второй (динамический) подход подразумевает использование публично-доступных ресурсов - Грид-систем [16, 98, 99], суперкомпьютеров [17], кластеров [18-20], облаков [21]. объединенных сетями общего назначения.

Основная проблема использования этих ресурсов для нужд ЭВ - отсутствие гарантий на время предоставление вычислительных ресурсов для ЭКП и не гарантированная производительность самих предоставляемых ресурсов. Так задача может простоять в очереди больше, чем потребуется на ее выполнение[8]. Для решения проблем связанных с предоставлением такого типа ресурсов, была создана, например, система SPRUCE [7]. Данная система включает в себя web-портал, образующий единую точку доступа к системе для пользователей, адаптеры для интеграции различных систем управления вычислительными ресурсами, такими как Torque, Moa, PBS и позволяет организовывать доступ к вычислительным ресурсам для ЭКП за счет следующих механизмов:

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

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

- прерывание задач и немедленный запуск ЭКП. В этом случае все результаты прерванных задач теряются.

Кроме того, SPRUCE содержит процедуры для подготовки всех необходимых приложений для ЭКП заранее. SPRUCE предоставляет одного из наиболее успешных решений для экстренных вычислений с использованием нескольких ресурсов TeraGrid [93]. Однако при этом SPRUCE ограничен политиками предоставления вычислительных ресурсов провайдеров ресурсов, поэтому часто прерывание и даже приостановка задач не могут быть использованы. Также SPRUCE не работает с композитными приложениями и не составляет расписание, вследствие чего не может гарантировать время выполнения или надежность исполнения отдельных задач ЭКП.

В работе Trebon [8] была предложена модификация платформы SPRUCE. В ней были предложены набор политик ранжирования приоритетов ресурсов в зависимости от их типа (системы с очередями, облачные ресурсы и т.д.), а также набор статистических методов и эвристик для оценки верхней границы времени исполнения экстренных вычислений для разных стадий процесса(загрузки данных, выделения ресурсов и т.д.) исполнения отдельных вычислительных задач. Таким образом, данный шаг является движением в сторону оценки всего времени выполнения, но при этом не является составлением расписания.

В настоящее время все чаще в качестве динамических сред для исполнения ЭКП рассматриваются облачные ресурсы, предоставляемые, например, Amazon, Google, Microsoft. Leong [93] проводил анализ использования публичных облачных ресурсов в условиях специфики экстренных вычислений. Облачные ресурсы идеальны с точки зрения предоставления машин желаемой конфигурации и следованию концепции 'предоставление-по-требованию'. Однако объемы ресурсов, предоставляемых по требованию, могут быть недостаточны для ЭВ, в том числе, и по техническим возможностям. Так, например, облачные ресурсы оказались недостаточным решением для North Carolina Forecast Center [9], из-за невозможности организовать MPI-кластер достаточного для их нужд размера. Также необходимо учитывать аспекты надежности и устойчивости к отказам для специфики облачных вычислений.

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

16

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

Еще одним примером системы, основанной на принципах SOA и поддерживающей исполнение ЭКП, является система облачных вычислений второго поколения CLAVIRE [11]. Данная система использовалась для построения СРП для предотвращения наводнений в г. Санкт-Петербурге. Отличительными чертами данной системы являются:

- поддержка формализма связных ЭКП и концепции AaaS;

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

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

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

Несмотря на наличие большего количества систем и достаточно глубокую

проработанность тематики ЭВ, в данной области естественно, имеются определенные

моменты, требующие улучшения. Так, некоторые из описанных выше систем не работают

с формализмом КП, что было указано ранее, а те что работают используют в основном

простейшие методы планирования ЭКП, не имеющие цели произвести оценку времени

17

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

В целом современные потребности технологий ЭВ в решении задачи планирования сводятся к возможностям:

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

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

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

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

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

Стоит отметить, что процесс планирования может включать не только составление расписания для задач ЭКП, но и действия для конфигурации/реконфигурации пула ресурсов. Кроме составления непосредственно расписания по некоторой структуре ЭКП, с целью соблюдения ограничений времени выполнения, возможно изменение самого ЭКП, как пользователем, так и самой системой исполнения ЭКП. Изменения подразумевают:

- изменение состава и связей внутри ЭКП;

- изменение типов вычислительных пакетов;

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

задач ЭВ, рассмотрены ниже.

1.3. Методы планирования экстренных композитных приложений

Список литературы диссертационного исследования кандидат наук Бутаков Николай Алексеевич, 2015 год

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Boukhanovsky A., Bubak M. High Performance Computations for Decision Support in Critical Situations: Introduction to the Third Workshop on Urgent Computing //Procedia Computer Science. - 2014. - Т. 29. - С. 1644-1645.

2. Berg M. A., Borensztein M. E., Pattillo M. C. A. Assessing early warning systems: how have they worked in practice?. - International Monetary Fund, 2004. - №. 4-52.

3. Mostashari F. et al. Dead bird clusters as an early warning system for West Nile virus activity //Emerging infectious diseases. - 2003. - Т. 9. - №. 6. - С. 641.

4. Zou C. C. et al. Monitoring and early warning for internet worms //Proceedings of the 10th ACM conference on Computer and communications security. - ACM, 2003. - С. 190-199.

5. Hong Y., Adler R. F. Towards an early-warning system for global landslides triggered by rainfall and earthquake //International journal of remote sensing. - 2007. - Т. 28. - №. 16. - С. 3713-3719.

6. Workflow Generator [Электронный ресурс] // Pegasus [Офиц. сайт]. URL: https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator (дата обращения: 30.09.2015)

7. Beckman P. et al. SPRUCE: A system for supporting urgent high-performance computing //Grid-Based Problem Solving Environments. - Springer US, 2007. - С. 295311.

8. Trebon N. Enabling urgent computing within the existing distributed computing infrastructure. - University of Chicago, 2011.

9. Blanton B. et al. Urgent computing of storm surge for North Carolina's coast //Procedia Computer Science. - 2012. - Т. 9. - С. 1677-1686.

10. Balis B. et al. The urbanflood common information space for early warning systems //Procedia Computer Science. - 2011. - Т. 4. - С. 96-105.

11. Ivanov S. V., Kovalchuk S. V., Boukhanovsky A. V. Workflow-based Collaborative Decision Support for Flood Management Systems //Procedia Computer Science. - 2013. - Т. 18. - С. 2213-2222.

12. Kovalchuk S. V. et al. Deadline-driven resource management within urgent computing cyberinfrastructure //Procedia Computer Science. - 2013. - Т. 18. - С. 2203-2212.

13. Nasonov D., Butakov N. Hybrid Scheduling Algorithm in Early Warning Systems //Procedia Computer Science. - 2014. - Т. 29. - С. 1677-1687.

14. Yamasaki E. What we can learn from Japan's early earthquake warning system //Momentum. - 2012. - Т. 1. - №. 1. - С. 2.

160

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

Demeritt D. et al. The European Flood Alert System and the communication, perception, and use of ensemble predictions for operational flood risk management //Hydrological Processes. - 2013. - T. 27. - №. 1. - C. 147-157.

Foster I., Kesselman C., Tuecke S. The anatomy of the grid: Enabling scalable virtual organizations //International journal of high performance computing applications. - 2001.

- T. 15. - №. 3. - C. 200-222.

Siewiorek D. P., Koopman P. J. The architecture of supercomputers: Titan, a case study.

- Academic Press, 2014.

Henderson R. L. Job scheduling under the portable batch system //Job scheduling strategies for parallel processing. - Springer Berlin Heidelberg, 1995. - C. 279-294.

Hindman B. et al. Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center //NSDI. - 2011. - T. 11. - C. 22-22.

Vavilapalli V. K. et al. Apache hadoop yarn: Yet another resource negotiator //Proceedings of the 4th annual Symposium on Cloud Computing. - ACM, 2013. - C. 5.

Armbrust M. et al. A view of cloud computing //Communications of the ACM. - 2010. -T. 53. - №. 4. - C. 50-58.

Rahman M. et al. Adaptive workflow scheduling for dynamic grid and cloud computing environment //Concurrency and Computation: Practice and Experience. - 2013. - T. 25. -№. 13. - C. 1816-1842.

Arabnejad H. List Based Task Scheduling Algorithms on Heterogeneous Systems-An overview. - 2013.

Topcuoglu H., Hariri S., Wu M. Performance-effective and low-complexity task scheduling for heterogeneous computing //Parallel and Distributed Systems, IEEE Transactions on. - 2002. - T. 13. - №. 3. - C. 260-274.

Singh L., Singh S. A survey of workflow scheduling algorithms and research issues. -2013.

Turnbull J. The Docker Book: Containerization is the new virtualization. - James Turnbull, 2014.

Jakob W. et al. Fast rescheduling of multiple workflows to constrained heterogeneous resources using multi-criteria memetic computing //Algorithms. - 2013. - T. 6. - №. 2. -C. 245-277.

Delavar A. G., Aryan Y. HSGA: a hybrid heuristic algorithm for workflow scheduling in cloud systems //Cluster computing. - 2014. - T. 17. - №. 1. - C. 129-137.

Shen X. N., Yao X. Mathematical modeling and multi-objective evolutionary algorithms applied to dynamic flexible job shop scheduling problems //Information Sciences. -2015. - T. 298. - C. 198-224.

30. Gkoutioudi K. Z., Karatza H. D. Multi-criteria job scheduling in grid using an accelerated genetic algorithm //Journal of Grid Computing. - 2012. - T. 10. - №. 2. - C. 311-323.

31. Nasonov D. et al. Hybrid Evolutionary Workflow Scheduling Algorithm for Dynamic Heterogeneous Distributed Computational Environment //International Joint Conference SOCO'14-CISIS'14-ICEUTE'14. - Springer International Publishing, 2014. - C. 83-92.

32. Bolaji A. L. et al. University course timetabling using hybridized artificial bee colony with hill climbing optimizer //Journal of Computational Science. - 2014. - T. 5. - №. 5. -C. 809-818.

33. Paul P. V. et al. A new population seeding technique for permutation-coded Genetic Algorithm: Service transfer approach //Journal of Computational Science. - 2014. - T. 5. - №. 2. - C. 277-297.

34. Zhang Y., Koelbel C., Cooper K. Hybrid re-scheduling mechanisms for workflow applications on multi-cluster grid //Cluster Computing and the Grid, 2009. CCGRID'09. 9th IEEE/ACM International Symposium on. - IEEE, 2009. - C. 116-123.

35. Rahman M., Li X., Palit H. Hybrid heuristic for scheduling data analytics workflow applications in hybrid cloud environment //Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on. - IEEE, 2011. - C. 966-974.

36. Yu Z., Shi W. An adaptive rescheduling strategy for grid workflow applications //Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International. - IEEE, 2007. - C. 1-8.

37. Vasile M. A. et al. Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing //Future Generation Computer Systems. - 2014.

38. Mandal A. et al. Scheduling strategies for mapping application workflows onto the grid //High Performance Distributed Computing, 2005. HPDC-14. Proceedings. 14th IEEE International Symposium on. - IEEE, 2005. - C. 125-134.

39. Pooranian Z. et al. Hybrid Metaheuristic Algorithm for Job Scheduling on Computational Grids //Informatica. - 2013. - T. 37. - №. 2.

40. Behnamian J. A parallel competitive colonial algorithm for JIT flowshop scheduling //Journal of Computational Science. - 2014. - T. 5. - №. 5. - C. 777-783.

41. Pendharkar P. C. A multi-agent memetic algorithm approach for distributed object allocation //Journal of Computational Science. - 2011. - T. 2. - №. 4. - C. 353-364.

42. Nayak S. K., Padhy S. K., Panigrahi S. P. A novel algorithm for dynamic task scheduling //Future Generation Computer Systems. - 2012. - T. 28. - №. 5. - C. 709-717.

43. Durillo J. J., Fard H. M., Prodan R. Moheft: A multi-objective list-based method for workflow scheduling //Cloud Computing Technology and Science (CloudCom), 2012 IEEE 4th International Conference on. - IEEE, 2012. - C. 185-192.

162

44. Lee Y. C., Zomaya A. Y. Rescheduling for reliable job completion with the support of clouds //Future Generation Computer Systems. - 2010. - Т. 26. - №. 8. - С. 1192-1199.

45. Bittencourt L. F., Madeira E. R. M. HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds //Journal of Internet Services and Applications. - 2011. - Т. 2. - №. 3. - С. 207-227.

46. Batista D. M., da Fonseca N. L. S. Robust scheduler for grid networks under uncertainties of both application demands and resource availability //Computer Networks. - 2011. - Т. 55. - №. 1. - С. 3-19.

47. de Oliveira D. et al. A provenance-based adaptive scheduling heuristic for parallel scientific workflows in clouds //Journal of Grid Computing. - 2012. - Т. 10. - №. 3. - С. 521-552.

48. Shi X., Zhao Y. Dynamic resource scheduling and workflow management in cloud computing //Web Information Systems Engineering-WISE 2010 Workshops. - Springer Berlin Heidelberg, 2011. - С. 440-448.

49. Deb K. et al. A fast and elitist multiobjective genetic algorithm: NSGA-II //Evolutionary Computation, IEEE Transactions on. - 2002. - Т. 6. - №. 2. - С. 182-197.

50. Gen M., Lin L. Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey //Journal of Intelligent Manufacturing. - 2014. - Т. 25. - №. 5. - С. 849-866.

51. IBM BladeCenter [Электронный ресурс] // IBM [Офиц. сайт]. URL: https://publib.boulder.ibm.com/infocenter/bladectr/documentation/index.jsp?topic=/com.i bm.bladecenter.hs20.doc/bls_hs20_product_page.html (дата обращения: 30.09.2015)

52. Jette M., Auble D. SLURM: Resource Management from the Simple to the Sophisticated //Lawrence Livermore National Laboratory, SLURM User Group Meeting. - 2010.

53. Frey J. et al. Condor-G: A computation management agent for multi-institutional grids //Cluster Computing. - 2002. - Т. 5. - №. 3. - С. 237-246.

54. Toshniwal A. et al. Storm@ twitter //Proceedings of the 2014 ACM SIGMOD international conference on Management of data. - ACM, 2014. - С. 147-156.

55. Thusoo A. et al. Hive: a warehousing solution over a map-reduce framework //Proceedings of the VLDB Endowment. - 2009. - Т. 2. - №. 2. - С. 1626-1629.

56. Olston C. et al. Pig latin: a not-so-foreign language for data processing //Proceedings of the 2008 ACM SIGMOD international conference on Management of data. - ACM, 2008. - С. 1099-1110.

57. Nilsson P. et al. The ATLAS PanDA Pilot in Operation //Journal of Physics: Conference Series. - IOP Publishing, 2011. - Т. 331. - №. 6. - С. 062040.

58. Nilsson P. et al. The PanDA system in the Atlas experiment //ACAT'08 Conference. -2008.

59. Multiphysics C. COMSOL multiphysics user guide (Version 4.3 a) //COMSOL, AB. -2012.

60. OpenNLP [Офиц. сайт] URL: https://opennlp.apache.org/ (дата обращения: 30.09.2015)

61. Dean J., Ghemawat S. MapReduce: simplified data processing on large clusters //Communications of the ACM. - 2008. - Т. 51. - №. 1. - С. 107-113.

62. LIGO application [Электронный ресурс] // Pegasus [Офиц. сайт]. URL: http://pegasus.isi.edu/applications/ligo (дата обращения: 30.09.2015)

63. Streaming Twitter API [Электронный ресурс] // Twitter [Офиц. сайт] URL: https://dev.twitter.com/streaming/overview (дата обращения: 30.09.2015)

64. Pingle Y. et al. Big Data Processing using Apache Hadoop in Cloud System //National Conference on Emerging Trends in Engineering & Technology. - 2012. - С. 475-479.

65. Tickoo O. et al. Modeling virtual machine performance: challenges and approaches //ACM SIGMETRICS Performance Evaluation Review. - 2010. - Т. 37. - №. 3. - С. 5560.

66. Kalyuzhnaya A. V. et al. Synthetic storms reconstruction for coastal floods risks assessment //Journal of Computational Science. - 2015. - Т. 9. - С. 112-117.

67. Wustenhoff E., BluePrints S. Service level agreement in the data center //Sun Microsystems Professional Series. - 2002.

68. Sotomayor B. et al. Virtual infrastructure management in private and hybrid clouds //Internet computing, IEEE. - 2009. - Т. 13. - №. 5. - С. 14-22.

69. Twigg S., Vo H. Resource Revocation in Apache Mesos. - 2012.

70. Amazon EC2 [Офиц. сайт] URL: https://aws.amazon.com/ru/ec2/ (дата обращения: 30.09.2015)

71. Amies A. et al. Infrastructure as a Service Cloud Concepts //Developing and Hosting Applications on the Cloud. - 2012.

72. Google Compute Engine [Офиц. сайт] URL: https://cloud.google.com/compute/ (дата обращения: 30.09.2015)

73. Microsoft Azure [Офиц. сайт] URL: https://azure.microsoft.com/ru-ru/ (дата обращения: 30.09.2015)

74. Golberg D. E. Genetic algorithms in search, optimization, and machine learning //Addion wesley. - 1989. - Т. 1989.

75. Yu J., Buyya R. Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms //Scientific Programming. - 2006. - Т. 14. - №. 3-4. - С. 217-230.

76. Maheswaran M. et al. Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems //Heterogeneous Computing Workshop, 1999.(HCW'99) Proceedings. Eighth. - IEEE, 1999. - С. 30-44.

77. Zimmer C., Emlen D. J. Evolution: Making sense of life. - Greenwood Village : Roberts, 2013.

78. Calegari P. et al. A taxonomy of evolutionary algorithms in combinatorial optimization //Journal of Heuristics. - 1999. - Т. 5. - №. 2. - С. 145-158.

79. Borthakur D. et al. Apache Hadoop goes realtime at Facebook //Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. - ACM, 2011. - С. 1071-1080.

80. Kopytov A. SysBench: a system performance benchmark //URL: http://sysbench. sourceforge. net (дата обращения: 30.09.2015).

81. Stallings W. Operating systems. - Englewood Cliffs : Prentice Hall, 1995. - Т. 4.

82. Tirumala A., Dunigan T., Cottrell L. Measuring end-to-end bandwidth with Iperf using Web100 //Presented at. - 2003. - №. SLAC-PUB-9733.

83. Massie M. et al. Monitoring with Ganglia. - " O'Reilly Media, Inc.", 2012.

84. Ryder T. Nagios Core Administration Cookbook. - Packt Publishing Ltd, 2013.

85. Verma A., Kaushal S. Bi-Criteria Priority based Particle Swarm Optimization workflow scheduling algorithm for cloud //Engineering and Computational Sciences (RAECS), 2014 Recent Advances in. - IEEE, 2014. - С. 1-6.

86. Rashedi E., Nezamabadi-Pour H., Saryazdi S. GSA: a gravitational search algorithm //Information sciences. - 2009. - Т. 179. - №. 13. - С. 2232-2248.

87. White T. Hadoop: The definitive guide. - " O'Reilly Media, Inc.", 2012.

88. Borthakur D. HDFS architecture guide //HADOOP APACHE PROJECT http://hadoop. apache. org/common/docs/current/hdfs design. pdf. - 2008.

89. Yang X., Sun J. An analytical performance model of mapreduce //Cloud Computing and Intelligence Systems (CCIS), 2011 IEEE International Conference on. - IEEE, 2011. - С. 306-310.

90. Anil R., Dunning T., Friedman E. Mahout in action. - Shelter Island : Manning, 2011.

91. Evensen G. Data assimilation: the ensemble Kalman filter. - Springer Science & Business Media, 2009.

92. Featured Workflows [Электронный ресурс] // Wings workflows [Офиц. сайт] URL: http://www.wings-workflows.org/node/42 (дата обращения: 30.09.2015)

93. Leong S. H., Kranzlmüller D., Frank A. A data management system to enable urgent natural disaster computing //EGU General Assembly Conference Abstracts. - 2014. - Т. 16. - С. 4699.

94. Афанасьев А. П. и др. Программный комплекс для решения задач дискретной оптимизации на распределенных вычислительных системах //Труды Института системного анализа Российской академии наук. - 2006. - Т. 25. - С. 5-17.

95. Афанасьев А. П. и др. Решение задач глобальной оптимизации большой размерности на многопроцессорных комплексах и грид-системах //Научный сервис в сети Интернет: решение больших задач: Труды Всероссийской научной конференции. - 2008. - С. 122-130.

96. Посыпкин М. А., Хританков А. С. О понятии ускорения и эффективности в распределённых системах //Труды конференции «Научный сервис в сети Интернет. - 2008. - С. 149-156.

97. Кореньков В. В., Кутовский Н. А., Семенов Р. Н. Опыт адаптации прикладных программных пакетов для работы в грид-средах //Компьютерные исследования и моделирование. ISSN. - 2012. - С. 2076-7633.

98. Ильин В. А. и др. Способ запуска и обработки в гриде заданий, подготовленных для различных сред исполнения //Вычислительные методы и программирование. -2008. - Т. 9. - №. 2.

99. Кореньков В. В., Ужинский А. В. На пути к адаптивности grid //Открытые системы. СУБД. - 2009. - №. 9. - С. 18-21.

100. Кореньков В. В., Нечаевский А. В., Трофимов В. В. Моделирование распределенной системы сбора, передачи и обработки данных для крупных научных проектов (мегапроект ника) // Информационные технологии и вычислительные системы. - 2013. - №. 4. - С. 37-44

ПРИЛОЖЕНИЕ

Свидетельство о регистрации программы симулятора процесса исполнения ЭКП в гетерогенной динамической вычислительной среде