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

005001325

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

Целищев Алексей Сергеевич

/ / ч

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

ВЫЧИСЛЕНИЯХ

Специальность 05.13.15 - Вычислительные машины, комплексы и компьютерные сети

1 О НО Я 2011

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

Москва -2011

005001325

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Национальный исследовательский университет МЭИ» (ФГБОУ ВПО «НИУ МЭИ») на кафедре Вычислительной техники.

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

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

Абросимов Леонид Иванович - кандидат физико-математических наук, доцент Фуруган Меран Габибуллаевич

Ведущая организация: ОАО «Научно-исследовательский институт вычислительных комплексов им. М.А. Карцева»

Защита состоится 25 ноября 2011 года в 16 часов 00 минут на заседании диссертационного совета Д 212.157.16 при ФГБОУ ВПО «НИУ МЭИ» по адресу: 111250, Москва, ул. Красноказарменная, д. 17, ауд. Г-306.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «НИУ МЭИ».

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 111250, Москва, ул. Красноказарменная, д. 14, Учёный совет МЭИ.

Автореферат разослан «24 » октября 2011 года.

Учёный секретарь

диссертационного совета Д 212.157.16, к.т.н., доцент

Чернов С.А.

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

Актуальность темы исследования

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

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

• Требования пользователей к минимизации времени выполнения и/или стоимости выполнения вычислений;

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

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

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

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

Объектом исследований в представленной диссертации являются распределенные вычислительные среды, а предметом исследований -модели и методы планирования распределённых вычислений.

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

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

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

» Исследованы существующие методы и алгоритмы планирования вычислений в распределенных средах;

• Предложена концепция решения задачи оптимального планирования вычислений на "1товне приложений и потоков заданий;

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

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

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

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

Методы исследования

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

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

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

• Иерархическая структура планирования и вычислительной среды;

• Совмещение методов планирования уровня потоков заданий и методов планирования уровня приложений;

• Использование экономических критериев и модели планирования;

• Распределение ресурсов в два этапа: выбор домена вычислительных узлов и оптимизация выполнения задания с учётом его структуры.

Предложенная модель впервые позволяет одновременно соблюдать интересы пользователей Грид-систем (крайние сроки выполнения заданий), администраторов вычислительных узлов (эффективная загрузка) и организаторов Грид-систем (интегральные характеристики потока заданий) и совмещать преимущества различных методик планирования: Budget- и Deadline-constrained (ограничения на бюджет и на время) планирования, а также Best-effort планирования.

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

• Разработаны алгоритмы генерации заданий в виде информационных графов, а также алгоритмы анализа их структуры;

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

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

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

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

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

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

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

обеспечение зарегистрировано в государственном реестре программ для ЭВМ: свидетельство № 2011611541 от 10.03.2011 г.

Результаты исследования были использованы при подготовке лекционных курсов «Вычислительная техника» на кафедре ВТ НИУ ФГБОУ ВПО «НИУ МЭИ», а также лекционных курсов кафедры АИЛУ МИЭМ (ТУ), о чём имеются соответствующие акты.

На различных этапах проведения исследований работа автора была поддержана грантами РФФИ (№ 06-01-00027, № 09-01-00095), а также Советом по грантам Президента Российской Федерации для поддержки ведущих научных школ (грант НШ-7239.2010.9), Министерством образования и науки (проекты 2.1.2/6718; 2.1.2/13283 в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» и государственные контракты федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 20092013 годы № П2227, 16.740.11.0038) и Комитетом поддержки развития отечественных автоматизированных систем управления имени академика Семенихина (именная премия первой степени). Апробация и публикация результатов работы

Теоретические и практические результаты диссертационных исследований были представлены и обсуждались в рамках многочисленных российских и зарубежных научных конференций в период с 2007 по 2011 гг.

По теме диссертации опубликовано 27 печатных работ, из них 7 в зарубежных изданиях (в том числе глава в монографии в соавторстве) и одна работа в издании, рекомендуемом ВАК. Структура и объем диссертации

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

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

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

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

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

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

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

• Иерархическая струюура вычислительной среды;

• Иерархическая структура планирования;

• Экономические критерии при планировании;

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

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

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

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

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

поставленные задачи. Предлагаемая концепция организации распределенных

вычислений виртуальной организации использует следующие понятия:

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

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

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

• Метапланировщик, который распределяет потоки заданий и ресурсы среды согласно стратегии виртуальной организации, а также менеджеры заданий - планировщики отдельных заданий, оптимизирующие выполнение заданий в интересах пользователей и владельцев ресурсов; Дадим качественное описание предлагаемой модели (по рис. 1):

1. Поток заданий пользователей поступает в очередь системы планирования,

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

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

3. После выбора набора узлов метапланировщик определяет стратегию выполнения каждого задания на этом наборе. Стратегия выполнения задания / с меньшим бюджетом может быть выражена директивой «наискорейшее выполнение», стратегия задания к может быть выражена директивой «выполнение за максимально близкое к крайнему сроку выполнения время». Задания передаются соответствующим менеджерам заданий, каждый из которых настроен на соответствующую стратегию. Начинается планирование на уровне приложений.

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

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

Формализованная постановка задачи планирования в модели: Исходные данные:

А Ртя^ят»! ТТЛ/Ч 1 »ТГЛЧГ'ЛЛ^ПЛ т Ч1Г1Лт»таттг ТТТТ№ ^ЯУЛЛТИЧПЛТПт' П

» 1 лииалопи^ тпилчьиюи иштълп lv<lшliшл у у х и у хулили*. и

вычислениях ЛГдоб={''р} ,р=1,..,М.

• Глобальный поток заданий пользователей - линейно упорядоченное множество ^1ГЛ0Й = {Ц,сиТ0б;, ¿ = 1,..,А0, где для 1-го задания: /; -требуемое количество вычислительных узлов, с,- - максимальный бюджет выполнения задания, Г,- - крайний срок выполнения, б, -информационный граф задания, включающий оценки длительностей выполнения каждой из операций обработки и передачи данных.

• Множество слотов 51глоб(1) - временных отрезков, которые могут быть использованы для выполнения подзадач, входящих в состав задания.

• Набор стратегий выполнения 5Г = {5^-, / = основанных на экономических критериях и выбирающися организаторами Грид-системы.

На уровне потоков заданий для рассматриваемого пакета заданий при заданных ограничениях метапланировщику необходимо выбрать такой набор слотов и стратегию для которого значение частной функции £/¡(5^), определяющей эффективность использования набора 52( слотов для 1-го задания было бы оптимальным. Структура заданий (информационный граф в,) на уровне потоков заданий не рассматривается.

Исходные данные для менеджеров заданий уровня приложений:

• Информационный граф задания С={Р,Е}, где где Р - множество из п вершин, соответствующих подзадачам (атомарным операциям) задания, а Е - множество рёбер, определяющих информационные зависимости (отношение предшествования),

• Набор слотов и соответствующих им ресурсов Я £ йгло6,

• Стратегия составления плана $1,

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

При этих ограничениях для задания требуется получить план = {[^./¿1'^.'- 1.■•."}. (где [5;,/;] - временной интервал, выделенный /-ой подзадаче, - выбранный для выполнения /-ой подзадачи вычислительный узел) для которого значение целевой функции С = fi.SK) будет соответствовать её экстремуму. Направление поиска и вид функции определяется стратегией st. Описание функции, дополнительных ограничений, компонент модели и условий допустимости плана, а также разработанные методы его получения приводятся в тексте второй главы.

Передача заданий и стратегий

Поиск слотов по экономическим критериям

Администратор

Ресурс М

Планирование подзадач по стратегиям Задание / рО-р1-р2-рЗ Задание к рО-рЗ-рг

Рис. 1. Иерархическая модель планирования

____________

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

• Поддержка неоднородных заданий сложной структуры (отсутствующая в большинстве алгоритмов best-effort планирования и лишь ограниченно применимая в алгоритмах QoS-constrained планирования)

• Использование универсальной схемы для решения задачи оптимизации качества обслуживания пользователей: budget- и deadline-constrained планирование.

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

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

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

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

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

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

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

2. Планирование и назначение последовательно выделяемых критических работ по оригинальному обобщённому методу критических работ.

3. Разрешение возникающих коллизий путём изменения назначения соответствующих подзадач.

ТТттгт Ллттплотшл \го/"»^ттт»г» упт^ттшалсшг лч^лт тт<а гтлмпли*

уи^'Ш^Ч/ишт/! 111 Л- КМ

алгоритм, объединяющий в себе элементы алгоритма Форда и алгоритма Йена и состоящий из трёх этапов:

• Рекуррентное построение корневого дерева критических работ графа с вершинами-работами;

• Формирование массива работ путём сокращённого перебора вершин;

• Упорядочивание массива работ

Второй этап (этап масштабирования) предлагается выполнять по следующей схеме:

1. Для каждой подзадачи / работы (щ < и2 < ■■■ < Щп) определяется запас по переменной 21 — X*, где X* — свободная переменная: крайний срок или предельная стоимость завершения задания.

2. Задается диапазон изменения Х( в зависимости от Zi:

£

í i — 1,... ,m — 1, Хт — [хт, Zm]

r=i+l

,xñ- минимально возможные (исходные) значения переменных. Шаг изменения x¡ в диапазоне X¿ не меньше xf, определяемого из ограничений на рост стоимости /-й подзадачи, если xt = т¿ либо из ограничений на увеличение длительности, если x¡= C¿. Экспериментально показано, что на данном шаге x¡ эффективно привязывать к шагу различия в производительности имеющихся экземпляров ресурсов.

3 Функция w¡(x¡) в аддитивно-сепарабельном критерии

т

w(x1...xm) = ^Wt(X¡)

i=1

определена на отрезках X¡, верхние границы которых зависят от значения запаса, и может быть представлена как функция двух переменных w^x^Zi). При этом значение Wi^xitZ{)выбирается как субоптимальное для разных экземпляров j доступных ресурсов:

WiíXi.Zi) = e3p'{wü(xi,Z¡)},xí е ВД)

4. На i-м шаге состояние работы g представляется запасом Z¿, а управление - переменной x¡. Для каждой подзадачи, кроме первой щ, определяется условно оптимальное управление, при котором Wí(xí,Zí) достигает условного оптимума w¿ (ZJ при фиксированном 2V Соответствующее функциональное уравнение имеет вид:

т,

Wg [2l) = extr

wL{xi,Zi)+ ^ <(zr)

r=i+l

r = 2.....m, (1)

Zx = X* = xt, lr - ~ xr-1 ¡=i

Обозначим W1 = Wi(xitZi)+w%, где

m

< = У\ w0r(Zr)

r-i+l

5. Рекуррентное соотношение оптимального управления (по времени или стоимости) есть

х{ = arg extr w1, х\ (Z£) = argextr w1, (2)

Xl

Z( ~ Zi-1 —• (£[•_!), i > 1, Zi — X*. Для вектора (x^, определяется предварительный план: моменты

начала j, выполнения подзадач оптимальной длительности (т^,,,.,!^), а также назначения = arg extr {ufy (^(ZJ.Z;)) в соответствии с (1).

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

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

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

• С течением времени на каждом шаге обновлять информацию о текущем состоянии ресурсов.

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

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

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

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

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

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

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

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

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

Г ,; ^МОДУЛЬ ; пэйетдого режима

* .Модуль задания параметров

. ■ Л'с дуль

; загрузки ; задании

Управляющий модуль

¡- '.-Модуль ; отображения | графов

: > - Модуль

¿'отображения

; диаграмм и - ■-! результатов

^Модуль сбора статистики

[{--.Модуль [ отображения \ коллизий

: МОДУЛЬ

^генерации !" задания и | среды

.... , гЯ-Т '. ,

Граф . Х.,Ч-: " ■ I .„ ______ Г\г:

у Модуль

...... __ :, анализа; . \ " ' ' \/ Г;

Параметры ■

1Г

Загрузка ХМ1 файла задания > ~~ / -

•Ц/? Обработки [__ _ - ' г •

заданий и I параметры*среды> .МоАУль ; поиска "К!™'*"';^,

I критических работ . и

Тоебовэния

Внутренние модули

----------

-Модуль ' \ составления , расписания и | разрешения' коллизий

Внешние модуле

Рис. 2. Структура среды имитационного моделирования

И* ,, •

Рис. 3. Интерфейс среды имитационного моделирования

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

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

• Выявление ключевых параметров модели с целью определения эффективных стратегий планирования

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

I Для достижения поставленных целей проведено шесть групп экспериментов.

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

В серии экспериментов по планированию 2000 случайных заданий (случайное количество подзадач в каждом задании, степень связности подзадач и время выполнения подзадач, случайные ограничения на I временной интервал планирования) метод позволил получить оптимальные I планы в 84% случаев. Остальные 16% для получения оптимальных планов требовали корректировки начальных данных.

Задания, для которых обобщённый метод критических работ не получает оптимальное расписание, также требуют корректировки начальных данных, либо могут быть распределены любым методом best-effort

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

Анализ влияния различных параметров планирования на возникающие в его процессе коллизии.

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

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

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

2 4 б г

Число крусов графа, N

Рис. 4. Коллизии за ресурсы

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

» «Любимый процессор» - ситуация, при которой выделенное планировщиком время может обеспечиваться одним и только одним процессором, на который подзадача и была назначена, но после чего проиграла коллизию за этот процессор. Таким образом, возникает исключительный случай, и алгоритм приостанавливает работу. Подобные ситуации возникают в 1.23% случаев. Для разрешения подобных ситуаций предлагаются следующие механизмы: при нехватке узлов включать в конкуренцию подзадачи, не вступившие в коллизию, но назначенные на необходимые ресурсы в том случае, если эти ресурсы в состоянии выполнить подзадачу за время, отведенное планировщиком. При наличии «любимого процессора» можно оставлять

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

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

Исследование априорной оценки вероятности успеха выполнения задания на заданном наборе ресурсов за заданное время.

I

I

I

Рис. 5 Зависимости доли полученных оптимальных планов от интервала (а) и числа узлов (б)

Анализ зависимости числа успешных составлений расписаний и числа коллизий от уровня наличия экземпляров ресурсов.

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

I

( Статистика загрузки различных типов узлов при различных критериях и параметрах оптимизации.

Серия экспериментов показала возможность реализации стратегий планирования, задаваемых метапланировщиком на уровне потоков заданий. Так, например, при варьировании интервала планирования можно при необходимости задействовать ресурсы различной производительности (см. 1 рис. 6: меньший индекс ресурса соответствует большей производительности)

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

о.б ; , I | ¡Ц | § 09 Г--------7------Г----------

О з 0.8 |-----------

| * 0.7 -!--.#-5---------

04 б а ; / «I--« —% -«»-N=3

>. Я 0.6 ---1-----!

в а I -«-N=5

| § о.5

0.2 .- .,-. -т- .-,.. ¡..„-¡-, ■■.',.,,-!■■ ■,_.., § 0.4 ----(—---:-----------!

1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2 3 4 5

Коэффициент длины отрезка Множитель числа процессоров;

масштабирования, Ь

(а) (б)

6| ел 0( «" 31

(а) - Исходный эксперимент

11 з 1 § 11

(б) - Уменьшение интервала планирования Рис. 6 Зависимость загрузки ресурсов от параметров планирования

Сравнительный анализ эффективности обобщённого метода критических работ с последовательным планированием.

Целью эксперимента было выяснить степень эффективности разработанных методов в масштабе потока заданий. При планировании двух одинаковых потоков из 1000 заданий задания первого потока были распланированы последовательно за 531089 единиц времени, а задания второго потока подавались до окончания времени выполнения предыдущего задания, а именно по прошествии 75% времени, выделенного на выполнение предыдущего задания. При этом эксперимент показал уплотнение потока на 25% по времени до 399465 единиц времени и сохранение стоимости потока. При этом планы каждого отдельного задания также были оптимальными. Таким образом, модифицированный метод критических работ позволяет проводить и оптимизировать планирование одновременно на уровне приложений и уровне потоков заданий.

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

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

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

3, При создании модели планирования решён ряд задач, связанных с разработкой оригинальных методов и алгоритмов:

• Представление разнообразных сценариев распределённой обработки данных в виде информационных графов с использованием

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

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

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

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

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

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

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

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

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

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

6. Теоретические результаты и разработанное программное обеспечение нашли применение в учебном процессе и научной работе ФГБОУ ВПО «НИУ МЭИ», а также получили положительную оценку экспертов по Грид-вычислениям Европейской организации по ядерным исследованиям (ЦЕРН).

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. Топорков В.В., Целищев А. С. Метод критических работ как перспектива эффективной организации распределённых вычислений И Информационные технологии. 2011. № 6. С. 13-17.

Избранные публикации в других изданиях

2. Toporkov V.V., Tselishchev A. Safety Scheduling Strategies in Distributed Computing // International Journal of Critical Computer-Based Systems, Vol. 1, No. 1/2/3,2010. P. 41-58.

3. Tselishchev A., Toporkov V.V. Compound job scheduling and job-flows management in distributed computing // Proc. of the 54 Int. Colloquium, Ilmenau, Germany, 2009. P. 21 - 26.

4. Toporkov V. V., Tselishchev A. Safely Strategies of Scheduling and Resource Co-allocation in Distributed Computing // Proc. of the 3rd International Conference on Dependability of Computer Systems. - Los Alamitos: IEEE CS Press, 2008.-P. 152-159.

5. Toporkov V. V., Toporkova A., Tselishchev A., Yemelyanov D., Bobchenkov A. Economic Models of Scheduling in Distributed Systems // In: T. Walkowiak, J. Mazurkiewicz, J. Sugier, and W. Zamojski (eds.), Monographs of System Dependability. Dependability of Networks (Vol. 2). - Wroclaw: Oficyna Wydawnicza Politechnki Wroclawskiej, 2010. -P. 143-154.

6. Целищев А. С., Топорков B.B. Модификация метода критических работ с учетом динамически обновляемого состава ресурсов в распределенных вычислениях // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции.- М.: Изд-во МГУ, 2009. С. 340 - 345.

' 7. Топорков В.В., Топоркова А.С., Бобченков А.В., Емельянов Д.М., Целищев А. С. Организация распределенных вычислений на основе экономических принципов // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'10», Сентябрь 2010 г. М.: ФИЗМАТЛИТ, 2010. Т. 1. С. 563-570.

8. Toporkov V.V., Bobchenkov A. Toporkova A., Tselishchev A., Yemelyanov D„ Slot Selection and Co-allocation for Economic Scheduling in Distributed Computing // Parallel Computing Technologies: Lecture Notes in Computer Science 2011, vol. 6873/2011,368-383, Springer Verlag 2011,

9. Toporkov V.V., Yemelyanov D., Toporkova A., and Tselishchev A. Scalable co-scheduling strategies in distributed computing // Proc. of the ACS/IEEE International Conference on Computer Systems and Applications - AICCSA 2010 (AJCCSA !10). IEEECS, Washington, DC, USA, P 1-8

Подписано в печать & IС' Xi-.f-j Г Зак. ¿6$ Тир. ! СО Пл. !, Z&

Полиграфический центр МЭИ

Москва, ул. Красноказарменная, д. 13

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

Вопросы, связанные с распределением трудоемких, вычислений, поднимаются уже не один десяток лет. Современные требования и научный прогресс влияют как на-объёмы обрабатываемых данных, так и на способы их обработки. Сегодня уже невозможно справиться с тем потоком информации, с которым необходимо работать различным организациям, имея под рукой лишь персональный компьютер, а в некоторых случаях даже целый вычислительный центр. Будь то петабайты данных, получаемых физиками на Большом Адронном Коллайдере [1], или огромное число комбинаций при поиске лекарства от тяжелой болезни [2] - современные реалии таковы, что не позволяют осуществить выполнение поставленных задач в рамках одной, сколь угодно большой или влиятельной организации, и требуют совершенно иного подхода к их решению.

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

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

Объектом исследований в представленной диссертации являются распределенные вычислительные среды, а предметом исследований — модели и методы планирования распределённых вычислений.

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

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

Исследованы существующие методы и алгоритмы планирования вычислений в распределенных средах

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

• Совмещение методов планирования уровня потоков заданий и методов планирования уровня приложений;

• Использование экономических критериев и модели планирования;

• Распределение ресурсов в два этапа: выбор домена вычислительных узлов и оптимизация выполнения задания.

Предложенная модель впервые позволяет одновременно соблюдать интересы пользователей Грид-систем, администраторов вычислительных узлов и организаторов Грид-систем и совмещать преимущества различных методик планирования: Budget- и Deadline-constrained (ограничения на бюджет и на время) планирования, а также Best-effort планирования:

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

• Разработаны алгоритмы- генерации' заданий в виде информационных графов, а• также алгоритмы анализа их структуры;

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

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

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

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

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

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

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

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

Практическая значимость работы заключается в том, что на основе среды имитационного моделирования были разработаны программные модули, оптимизированные с точки зрения производительности, которые возможно положить в основу реализации реальной системы управления ресурсами Грид-системы. Программное обеспечение зарегистрировано в государственном реестре программ для ЭВМ: свидетельство № 2011611541 от 10.03.2011 г. ([119]). Результаты исследования нашли применение в учебном процессе кафедры ВТ ФГБОУ ВПО «НИУ МЭИ» и были использованы при подготовке лекционных курсов «Вычислительная техника», о чём имеются соответствующие акты.

На различных этапах проведения исследований работа автора была поддержана различными грантами:

• «Разработка моделей и методов согласованного выделения ресурсов для организации распределенных вычислений на основе опорных планов» РФФИ № 06-01-00027;

• «Стратегии диспетчеризации потоков заданий в виртуальных организациях распределенных вычислительных сред» РФФИ № 0901-00095);

• «Планирование масштабных вычислений и управление ресурсами распределенных вычислительных сред», Совет по грантам Президента Российской Федерации для поддержки ведущих научных школ НШ-7239.2010.9

• «Стратегии организации и поддержки крупномасштабных вычислений в распределенных средах» проекты 2.1.2/6718 и 2.1.2/13283 аналитической ведомственной целевой программы Министерства Образования и Науки РФ "Развитие научного потенциала высшей школы (2009-2010 годы)"

• "Программные модели и системы планирования распределённых вычислений", государственные контракты № П2227, 16.740.11.0038 федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы

• Именная премия первой степени комитета поддержки развития отечественных автоматизированных систем^ управления имени академика, Семенихина (2008г).

По теме диссертации было опубликовано 27 печатных работ (в том числе 7 в зарубежных изданиях), из них 4 в периодических научных изданиях, одна глава в монографии в соавторстве и одна в издании, рекомендованном ВАК ([82],[84],[87],[89],[91-97],[108-109],[117-130]). Результаты исследований были апробированы на многочисленных российских и зарубежных научных конференциях в период с 2007 по 2011гг. Во время выполнения исследований автор прошёл стажировку в Европейской Организации по Ядерным Исследованиям CERN (Швейцария) и ознакомился с принципами организации вычислений в крупнейшем на сегодняшний день проекте распределенных вычислений в мире - LHC Computing Grid.

Автор выражает благодарность своему научному руководителю В.В. Топоркову, своим коллегам A.B. Бобченкову и Д.М. Емельянову за помощь и сотрудничество в проведении исследований.

12

3.2 Результаты работы имитационной модели

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

Исходные данные'.

1. Сложноструктурированное задание, представленное ориентированным ациклическим взвешенным информационным графом G, состоящим из 11 вершин и 13 ребер, определяющих подзадачи и информационные зависимости между ними (рис. 3.3). Для каждой из вершин задан соответствующий её подзадаче условный объём вычислений в условных единицах. Граф сгенерирован с помощью функции среды моделирования Generate (см. приложения С и D).

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

Условные объёмы вычислений для подзадач: рО V:21 pi V:27 р2 V:ll рЗ V:19 р4 V:19 р5 V:12 рб V:25 р7 V:22 р8 V:18 Р9 V:21 plO V:16 в списке работ, представленном ниже, нет повторяющихся элементов. Подобная фильтрация делается заранее, чтобы минимизировать объём s вычислений для модуля планировщика. Действительно, если какая-либо вершина или ребро присутствуют в более длинной критической работе, процесс последовательной обработки критических работ исключит эти i вершины из рассмотрения как уже распределенные. В результате работы* алгоритма, предложенного в подразделе 2.3.2., получены следующие данные, готовые к подаче в модуль планировщика:

Job 1: р0-рб-р5, суммарное время 7,=72+60+72+5+5=214 ед.вр. (здесь и далее обозначение ед.вр. соответствует условным единицам времени)

Job 2: (р0-р6)-р8. Вторая по длительности критическая работа для заданного графа полностью выглядит как р0-р6-р8, 7,=72+60+60+5+5=209 ед.вр., однако вершины рО и рб с соединяющим их ребром уже присутствуют в работе Job 1. Таким образом, в планировщик работа поступает как р8 и инцидентное ей входящее ребро. Принятая нотация — в скобках указываются вершины и рёбра, встреченные ранее и не подаваемые планировщику.

Job 3: р9-(рб-р8). Т=60+60+67+5+5=197 ед.вр.

Job 4: (р9)-р7-(р5). Т=60+54+72+5+5=196 ед.вр.

Job 5: р4-(р7-р5). Т=60+54+72+5+5=196 ед.вр.

Job 6: pl-(p7-p5). Т=57+54+72+5+5=193 ед.вр.

Job 7: (р9-р7)-(р8). Т=60+54+67+5+5=191 ед.вр. (для планировщика эта работа будет состоять лишь из одного ребра р7-р8)

Job 8: (р9-р7)-р10. Т=60+54+62+5+5=186 ед.вр.

Job 9: р2-(р8). Т=73+67+5=145 ед.вр.

Job 10: (pl)-(p5). Т=57+72+5=134 ед.вр.

Job 11: (pl)-(p8). Т=57+67+5=129 ед.вр.

Job 12: рЗ Т=54 ед.вр. (работа состоит из одной изолированной вершины)

Легко проверить, что в этом списке вершины и ребра встречаются вне скобок всего лишь один раз, то есть сам список включает в себя все t 110 компоненты графа. По полученным значениям длительностей выполнения критических работ на основе закона Амдала можно сделать вывод, что отрезок планирования для всего графа не может быть меньше, чем длительность работы Job 1 (см. рис. 3.3 — р0-р6-р5), равной 214 ед.вр. Работа Job 1 - не что иное как наиболее длительный последовательный участок графа, не подлежащий распараллеливанию.

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

3.2.2. Масштабирование

На втором этапе решения задачи происходит получение планов по стратегии, заданной в условии задачи, а именно планирование подзадач критических работ и определение выделенных каждой подзадаче времен таким образом, чтобы максимизировать среднюю загрузку всех вычислительных узлов. Планирование начинается после запуска процедуры Distribute (подробное описание всех компонентов и методов модели см. в приложениях С и D) с предварительным указанием значения в 300 ед.вр. в параметре Timespan и номера критериальной функции 1 в параметре Criterion. После окончания работы планировщик выдаст результаты и информацию о ходе распределения в файле Log.html. Рассмотрим их подробнее.

В данном примере механизм прямого и обратного прохода по критическим работам (см. подразделы 2.2.4 и 2.3.3) будет применён только для критической работы Job 1, так как только она с точки зрения планировщика содержит более одной нераспределённой вершины. Процесс проходов иллюстрируется планировщиком следующим образом:

Первая строка таблицы Layer 1-290 заполняется возможными временами выполнения первой подзадачи работы рО при условии соблюдения ограничения на запас по времени (если оставшегося запаса времени после выделения времени первой подзадаче не хватает на выполнение оставшихся подзадач на самых быстрых процессорах, подобные назначения не рассматриваются). Как показали эксперименты, подтверждающие гипотезу, предложенную в подразделе 2.2.4, эффективно» проводить поиск, рассматривая времена, соответствующие оценкам времени выполнения подзадачи на каждом их процессоров. Промежуточные значения не вносят в результирующий список стратегий новые планы. Таким образом, на процессоре ргО подзадача рО будет выполнена за 72 ед.вр., на prl — за 78 ед.вр., и так далее. Последний столбец соответствует максимально возможному времени, которое можно отвести на выполнение рО (время рассчитывается как разность между запасом и суммой времен выполнения, остальных подзадач рб и р5 на самых быстрых процессорах Z=290-72-60=l>58 ед.вр.). Повторим, что выделять и рассматривать другие времена, для выполнения рО не имеет большого смысла, так как они в итоге будут сводиться к выбору одного из представленных семи вариантов. При желании модуль планировщика можно модифицировать и соблюдать другую дисциплину выбора времен. Подробнее об этом в приложении В.

Вторая строка Layer 1-290 определяет запасы по времени для вершин дерева следующего яруса, которые будут соответствовать разным вариантам распределений операции рО. Z2(p6)=T-tl(p0)=290-72=218 ед.вр. для ргО, Т=212 ед.вр. для prl и так далее. Индекс у Z2 соответствует ярусу запаса, индекс у tl — рассматриваемому ярусу. Число ярусов дерева возможных распределений равно числу подзадач, входящих в критическую работу с точки зрения планировщика. Таблицы для последнего яруса не строятся, так как для последней вершины выделенное время однозначно определяется запасом, оставшимся с предыдущего

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

3.2.3. Составление расписания и разрешение коллизий

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

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

Связность ¿/=15

Объемы вычислений v, £ [100,300] Время выполнения гг е [50 ед. вр. ,100 ед. вр.] Время информационных передач 5 = 5 ед.вр. Число процессоров /=10 Число экспериментов Е = 2000 Масштабирование: по времени Критерий: максимизация средней загрузки узлов Отрезок масштабирования Ь= 1.5*/.

В 93.44% случаев коллизии при таком переназначении были успешно разрешены, причем среднее значение средней загрузки вычислительных узлов ухудшилось с 36.96% до 35.45%, что является неплохим результатом (для сравнения эффективности такого подхода по другому критерию см. эксперимент Эффективность эвристик коллизий). В оставшихся 6.56% случаев коллизии разрешить не удалось, причем в таких ситуациях наблюдались два варианта:

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

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

Подобные ситуации возникают в 1.23% случаев.

148

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

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

Эффективность эвристик коллизий

Число ярусов графа N=5

Максимальное число вершин в ярусе М= 5

Связность d= 15

Объемы вычислений v, £ [100,300]

Время выполнения г,- £ [50 ед. вр. Д00 ед. вр. ]

150

Время информационных передач 5 = 5 ед.вр. Число процессоров ./= 17 Число экспериментов Е = 1000 Масштабирование: по времени Критерий: максимизация стоимости Отрезок масштабирования Ь= 1.3*/.

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

4.1.3. Эксперименты с величиной интервала масштабирования

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

Возможные временные диапазоны (здесь и далее речь идет о масштабировании по времени, однако выкладки для масштабирования по стоимости будут аналогичны), в рамках которых можно составить расписание для задания сложной структуры, можно определить как где ТК1т.п — минимальное время выполнения самой длинной (по сумме весов вершин и рёбер графа) критической работы на определённом наборе ресурсов, а £у - сумма времён выполнения всех подзадач и информационных обменов. Иными словами, при отсутствии параллелизма время выполнения всего сценария равно сумме времён выполнения каждой из подзадач и обменов (верхняя граница), а при максимально возможном параллелизме время выполнения сценария ограничено длиной максимальной критической работы (нижняя граница), то есть самым длинным последовательным участком графа. Проблема выбора интервала планирования объясняется тем, что для случайно генерируемых сценариев сложно дать оценку необходимого времени планирования' ввиду абстрактности самого сценария, тогда как в реальной ситуации это прерогатива пользователя, инициирующего задание. Однако, предложенный' критерий сразу позволит отклонить запросы пользователей с заведомо некорректными требованиями к интервалу выполнения сценария (в том случае, когда предлагаемый интервал будет короче [0; Тштт]), а также дать вероятностную оценку успеха распределения ещё до его начала. Рассмотрим следующий эксперимент: меняя длину отрезка масштабирования, оценим долю успешно составленных планов. В данном случае абсолютные значения не так важны (эксперименты, касающиеся показателей успеха, были рассмотрены в предыдущих подразделах), обратим внимание на тенденции, проглядывающиеся в ходе осуществления процесса планирования.

Анализ графика, изображённого на рис. 4.3 показывает, что увеличение длины отрезка масштабирования относительно времени выполнения самой длинной критической работы на самом быстром процессоре сопровождается существенным ростом числа успешно распределённых заданий. Данная зависимость явно проявляется для критерия максимизации средней загрузки вычислительных узлов, а в общем случае обусловлена приоритетами выбора узлов той или иной производительности. Подробнее о влиянии типов и количества ресурсов см. эксперименты подразделов 4.1.4 и 4.1.5. Очевидно, что не для каждого сценария возможно' составить близкое к оптимальному расписание и обеспечить его выполнение, однако предлагаемые подходы позволяют вплотную подойти к решению этой задачи, а также дать априорные оценки вероятности успешного распределения.

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

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

Число ярусов графа N=6 Максимальное число вершин в ярусе М= 5 Связность й= 15

Объемы вычислений V, £ [100,300]

Время выполнения г, 6 [20 ед. вр. ,200 ед. вр. ]

Время информационных передач е [5 ед. вр. Д 5 ед. вр. ]

Число процессоров15

Число экспериментов Е = 9 прогонов по 200 заданий)

Масштабирование: по времени

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

Отрезок масштабирования Ь= 1*1г, 1г=1.2.6 с шагом 0.2

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

• Требования пользователей распределённых вычислительных сред к срокам и/или стоимости выполнения подаваемых ими заданий

• Требования владельцев вычислительных ресурсов среды к загрузке конечных узлов1 и/или требования к соблюдению их экономических интересов.

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

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

168

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

Основным практическим результатом диссертационных исследований является построение и реализация сложной имитационной модели уровня приложений ([84], [120]), которая позволяет получать планы выполнения распределённых вычислений на уровне приложений с оптимизацией заданных критериев и соблюдением различных требований. Новизна полученных результатов заключается в том, что реализованная модель впервые позволяет обеспечить совмещение требований и экономических интересов участников вычислений и> дополнительных ограничений- при составлении планов и расписаний, являющихся важнейшими компонентами реальных систем распределённых вычислений. В диссертации последовательно рассмотрены все этапы получения планов выполнения заданий по заданным стратегиям, функционал и параметры имитационной модели, проведены многочисленные эксперименты, доказывающие эффективность разработанных методов. Исследование результатов работы модели, которые показывают, что разработанные методы позволяют получать оптимальные или близкие к оптимальным планы для случайных заданий, подтвердило приемлемость применения предложенной концепции в реальных системах.

В процессе работы над диссертацией автору удалось показать, что разработанная модель планирования на уровне приложений годится для интеграции в предложенную комплексную иерархическую концепцию планирования, так как позволяет получать планы выполнения широкого спектра сценариев распределённых вычислений при различных стратегиях организации вычислений. Несмотря на то, что представленные исследования методов планирования являются- завершённой' научным работой, разработанные методы и модель уровня приложений1 может использоваться в дальнейшем для исследований' по следующим^ направлениям:

Исследование методик интеграции модели. Разработанные на основе результатов работы имитационной модели оптимизированные приложения могут быть интегрированы в реальные системы Грид-вычислений, что в совокупности с использованием методов уровня планирования потоков заданий (исследования с участием автора [118], [121], [122], [123] и [126]) позволит повысить эффективность использования ресурсов- в Грид-системах.

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

175

Построение комплексной модели уровня потоков заданий и уровня приложений. Интеграция разработанной модели на уровне потоков заданий позволит провести моделирование и получить оценки качества обслуживания всех участников распределённых вычислений, а также значения интегральных характеристик потока (на примере эксперимента, приведённого в разделе 4.3). Исследования в данном направлении позволят проработать дополнительные аспекты комплексной концепции и, тем самым, вплотную подойти к возможности её реализации в-реальных системах распределённых вычислений. Принимая-участие в параллельных исследованиях методов планирования на уровне потоков заданий, автор учитывал, их результаты» при разработке представленных алгоритмов, что позволило создать модель, готовую к сопряжению с алгоритмами более высокого уровня.

Применение методов планирования распределённых вычислений в других областях науки и промышленности. Изучая различные подходы- к планированию распределённых вычислений, автор- обнаружил необходимость решения задачи составления1 расписаний- и в других областях, напрямую не относящихся к объекту диссертационных исследований. Так теория планирования и организации бизнес-процессов в экономике включает в себя задачу составления оптимального расписания выполнения» определённого задания группой исполнителей, которая, при определённых допущениях может быть спроецирована на задачи; решаемые в. диссертации ([110]). Также существует ряд промышленных, и экономических отраслей, где получение оптимального расписания выполнения какой-либо задачи может существенно влиять на итоговые показатели (например, [115], [112], [81] и др.). Использование полученных в диссертационном исследовании результатов и методов планирования может позволить рассмотреть встречающиеся задачи на качественно ином уровне и обеспечить показатели, достичь которых имеющимися на сегодняшний день методами невозможно.

176

1. I. Bird, L. Robertson, J. Shiers, "Deploying the LHC computing grid the LCG service challenges" // International Symposium on Mass Storage Systems and Technology, pp. 160165, 2005 IEEE International Symposium on Mass Storage Systems and Technology, 2005

2. Оф. сайт проекта DrugDiscovery@Home http://boinc.drugdiscoveryathome.com/

3. Топорков В.В. Модели распределённых вычислений. М.: ФИЗМАТЛИТ, 2004. 320с.

4. Ben-Ari, М. Principles of Concurrent and Distributed Programming (2nd ed.) Addison-Wesley. ISBN 978-0-321-31283-9.

5. Hansen P.B. Model programs for computational science: a programming methodology for multicomputers // Concurrency: Practice and Experience. 1993/ - V. 5. - P. 407-423

6. Andrews, Gregory R. (2000), Foundations of Multithreaded, Parallel, and Distributed Programming, Addison-Wesley, ISBN 0-201-35752-6

7. Yeng-Ting Lee; Kuan-Ta Chen, "Is Server Consolidation Beneficial to MMORPG? A Case Study of World of Warcraft," // Cloud Computing (CLOUD), 2010 IEEE 3rd International Conference on , vol., no., pp.435-442, 5-10 July 2010

8. K. S. Narendra, S. Mukhopadhyay Intelligent Control Using Neural Networks // Neuro-Control Systems: Theory and Applications. A Selected Reprinted Volume., Eds. M. M. Gupta and D. H. Rao. IEEE Press, 1994

9. Hatcher, P.; Reno, M; Antoniu, G.; Bouge, L.\ "Cluster computing with Java," // Computing in Science & Engineering , vol.7, no.2, pp. 34- 39, March-April 2005 doi: 10.1109/MCSE.2005.28

10. Korpela, E.; Werthimer, D.; Anderson, D., Cobb, J.; Leboisky, M; , "SETI@home-massively distributed computing for SETI," // Computing in Science & Engineering , vol.3, no. 1, pp.78-83, Jan/Feb 2001

11. Оф. сайт проекта PrimeGrid http://www.primegrid.com/

12. Оф. сайт проекта ABC@Home http://www.abcathome.com/

13. Stainforth, D.; Kettleborough, J.; Allen, M.; Collins, M.; Heaps, A.; Murphy, J.; , "Distributed computing for public-interest climate modeling research" // Computing in Science & Engineering , vol.4, no.3, pp.82-89, May/Jun 2002

14. Оф. сайт проекта MindModeling@Home http://www.mindmodeling.org

15. Оф. сайт проекта Chess960@Home http://www.chess960athome.org/

16. Оф. Сайт сообщества World Community Grid http://www.worldcommunitygrid.org/

17. Bird, /.; Jones, В.; Kee, K.F.; "The Organization and Management of Grid Infrastructures," // Computer, vol.42, no.l, pp.36-46, Jan. 2009

18. Kurdi, H.; Li, M.; Al-Raweshidy, H; , "A Classification of Emerging and Traditional Grid Systems," // Distributed Systems Online, IEEE , vol.9, no.3, pp.1, March 2008

19. Nash, H.; Blair, D.; Grefenstette, J.; "Comparing algorithms for large-scale sequence analysis," // Bioinformatics and Bioengineering Conference, 2001. Proceedings of the IEEE 2nd International Symposium on , vol., no., pp.89-96, 4-6 Nov 2001

20. Xhafa, Fatos; Abraham, Ajith (Eds.) Metaheuristics for Scheduling in Distributed Computing Environments // Studies in Computational Intelligence, V 146, Springer-Verlag Berlin Heidelberg, 2008

21. Brian J.S. Chee, Curtis Franklin Jr., "Cloud Computing: Technologies and Strategies of the Ubiquitous Data Center" // CRC Press, 2010, ISBN: 1439806128, 288 p.

22. Sciaba, A. et al. gLite 3.1 user guide // CERN 2009 CERN-LCG-GDEIS-722398

23. Kretsis, A.; Kokkinos, P.; Varvarigos, E.; "Developing Scheduling Policies in gLite Middleware," // Cluster Computing and the Grid, 2009. CCGRID '09. 9th IEEE/ACM International Symposium on , vol., no., pp.20-27, 18-21 May 2009

24. Frey J., Foster I., Livny M. et al. Condor-G: a Computation Management Agent for Multi-institutional Grids // Proc. of the 10th International Symposium on High-Performance Distributed Computing. New York: IEEE Press, 2001. - P. 55-66.

25. Gropp W., Lask E. Beowulf Cluster Computing with Linux, 2nd Edition // The MIT Press 2003, 660p 978-0-262-69292-2

26. Silva V. Grid Computing For Developers // Charles River Media, 2006 576p.

27. Romberg, M. \ "The UNICORE architecture: seamless access to distributed resources // High Performance Distributed Computing, 1999. Proceedings. The Eighth International Symposium on , vol., no., pp.287-293, 1999

28. Berman F. et al. Adaptive Computing on the Grid Using AppLeS // IEEE Transactions on parallel and distributed systems, vol. 14, no. 4, April 2003

29. Коффмап Э.Г. Теория расписаний и вычислительные машины М.:Наука, 1984 -334с

30. Taillard, Е. (January 1993). "Benchmarks for basic scheduling problems" // European Journal of Operational Research 64 (2): 278-285. doi: 10.1016/0377-2217(93)90182-M.

31. Muller-Merbach H. Ein Verfahren zur Planung des optimalen Betriebsmetteleinsatzes bei der Terminierung von Grossprojekten II Zeitschrift fuer Wirtschaftliche Fertigung. 1967 N62 83-88

32. Lawler E.L., Wood D.E. Branch and bound methods: a survey II Operations Research. 1966. N14(4). 699-719

33. Wieczorek, M„ Prodan, R., Fahringer, T.\ Scheduling of Scientific Workflows in the ASKALON Grid Enviornment. ACM SIGMOD Record 34(3), 56-62 (2005)

34. Berman, F., et al.: New Grid Scheduling and Rescheduling Methods in the GrADS Project. International Journal of Parallel Programming (IJPP) 33(2-3), 209-229 (2005)

35. Blythe, J., et al.: Task Scheduling Strategies for Workflow-based Applications in Grids. In: IEEE International Symposium on Cluster Computing and the Grid (CCGrid 2005) (2005)

36. Topcuoglu, H., Hariri, S., Wn, M.Y.: Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing // IEEE Transactions on Parallel and Distributed Systems 13(3), 260-274 (2002)

37. Blaha, P., et al. : WIEN2k: An Augmented Plane Waveplus Local Orbitals Program for Calculating Crystal Properties. Institute of Physical and Theoretical Chemistry, Vienna University of Technology (2001)

38. Оф. сайт продукта MOAB cluster suitehttp://www.clusterresources.com/products/moab-cluster-suite/workload-manager.php

39. Шаповалов T.C., Пересветов B.B. Генетический алгоритм составления расписаний для распределенных гетерогенных вычислительных систем // Вычислительные методы и программирование. М.: МГУ, 2009. Том 10, №1.

40. Yu, J., Buyya, R.\ Scheduling Scientific Workflow Applications with Deadline and Budget Constraints using Genetic Algorithms //Scient. Programming 14(3-4), 217—230 (2006)

41. Топорков B.B. Поведенческий синтез систем. -М.: Издательство МЭИ. — 2001. 192с

42. Thain D„ Tannenbaum Т., and Livny М. Distributed Computing in Practice: the Condor Experience // Concurrency and'Computation: Practice and Experience. 2004. - Vol. 17. -No. 2-4. - P. 323-356.

43. Аветисян A.K, Гайсарян C.C., Гришин Д.А. и др. Эвристики распределения задач для брокера ресурсов Grid // Труды Института системного программирования РАН. 2004. Т. 5. С. 41-62.

44. Berman F. High-performance Schedulers II In: I. Foster and С. Kesselman (eds.), The Grid: Blueprint for a New Computing Infrastructure. San Francisco: Morgan Kaufmann,1999. P. 279-309.

45. Yang Y., Raadt K:, and Casanova H. Multiround Algorithms for Scheduling Divisible Loads // IEEE Transactions on Parallel and Distributed Systems. 2005. - Vol. 16. - No. 8. -P. 1092-1102.

46. Beiriger J., Johnson W., Bivens H. et al. Constructing the ASCI Grid // Proc. of the 9th IEEE Symposium on High Performance Distributed Computing. New York: IEEE Press,2000.-P. 193-200.

47. Abramson D., Giddy J., and Kotler L. High Performance Parametric Modeling with Nimrod/G: Killer Application for the Global Grid? // Proc. of the International Parallel and Distributed Processing Symposium. New York: IEEE Press, 2000. - P. 520-528.

48. Воеводин Вл.В. Решение больших задач в распределенных вычислительных средах // Автоматика и телемеханика. 2007. - № 5. - С. 32-45.

49. Zhang Y, Franke Н., Morreira J.E. et al. An Integrated Approach to Parallel Scheduling Using Gang-Scheduling, Backfilling, and Migration // IEEE Trans, on Parallel and Distributed Systems. 2003. 14 (3). P. 236-247.

50. Ioarmidou M.A., Karatza H.D. Multi-site scheduling with multiple job reservations and forecasting methods // In: Guo, M. et al. (eds): ISPA 2006. Lecture Notes in Computer Science, Vol. 4330. Springer-Verlag Berlin Heidelberg. 2006. P. 894-903.

51. Ranganathan к1 and Foster I. Decoupling Computation and Data Scheduling in Distributed Data-intensive Applications // Proc. of the 11th IEEE International Symposium on High Performance Distributed Computing, New York: IEEE Press, 2002. P. 376-381.

52. M. Tang, B.S. Lee, X. Tang, et al.: The Impact of Data Replication on Job Scheduling Performance in the Data Grid, Future Generation Computing Systems, 2006, Vol. 22, No. 3. P. 254-268.

53. N.N. Dang, S.B. Lim, and C.K. Yeo: Combination of Replication and Scheduling in Data Grids, Int. J. of Computer Science and Network Security, 2007, Vol. 7, No. 3. P. 304 308.

54. William H.B. et al. Optor Sim A Grid Simulator for Studying Dynamic Data Replication Strategies // Int. J. on HPC Appl., 2003, Vol. 17, No. 4. P. 403-416.

55. Foster I., Kesselman C., and Tuecke S. The Anatomy of the Grid: Enabling Scalable Virtual Organizations // Int. J. of High Performance Computing Applications. 2001. - Vol. 15.-No. 3,-P. 200-222.

56. Garg S.K., Buyya R., Siegel H. J. Scheduling Parallel Applications on Utility Grids: Time and Cost Trade-off Management // Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009), Wellington, New Zealand. 2009. P. 151-159.

57. Degabriele J.P., Рут D. Economic Aspects of a Utility Computing Service, Trusted Systems Laboratory HP Laboratories Bristol HPL-2007-101 // Technical Report, July 3, 2007.-P. 1-23.

58. Ailamaki A., Dash D., Kantere V. Economic Aspects of Cloud Computing // Flash Informatique, Special HPC, 27 October 2009. P. 45-47.

59. Bredin J., Kotz D., Rus D. Economic Markets as a Means of Open Mobile-Agent Systems // Proceedings of the Workshop "Mobile Agents in the Context of Competition and Cooperation (MAC3)". 1999. P. 43-49.

60. Buyya R., Abramson D., Giddy J. et al. Economic Models for Resource Management and Scheduling in Grid Computing // J. of Concurrency and Computation: Practice and Experience. 2002. - Vol. 14. - No. 5. - P. 1507-1542.

61. Ernemann C., Hamscher V., Yahyapour R. Economic scheduling in Grid computing // Proc. of the 8th Int. JSSPP Workshop. LNCS. Vol. 2537. 2002. P. 129-152.

62. Коваленко B.H., Коваленко Е.И., Корягин Д.А. и др. Управление параллельными заданиями в гриде с неотчуждаемыми ресурсами. Препринт № 63. М.: ИПМ им. М.В. Келдыша РАН, 2007. - 28 с.

63. Киселев А., Корнеев В., Семенов Д., Сахаров И. Управление метакомпьютерными системами // Открытые системы. 2005. - №2. - С. 11-16.

64. Отчёт о проведении патентных исследований по 1 этапу Государственного контракта № 16,740,11,0038 от 01 сентября 2010 г. Под рук. В.В. Топоркова

65. Toporkov V. Multicriteria Scheduling Strategies in Scalable Computing Systems // Proc. of the 9th International Conference on Parallel Computing Technologies, LNCS. Vol. 4671. - Heidelberg: Springer, 2007. - P. 313-317.

66. Toporkov V.V., Tselishchev A. Safety Strategies of Scheduling and Resource Co-allocation in Distributed Computing // Proc. of the 3rd International Conference on Dependability of Computer Systems. Los Alamitos: IEEE CS Press, 2008. - P. 152-159.

67. Научно-технический отчёт о выполнении 1 этапа Государственного контракта № 16.740.11.0038 от 01 сентября 2010г. под рук. В.В. Топоркова

68. Toporkov V.V. Job and Application-Level Scheduling in Distributed Computing // Ubiquitous Computing and Communication (UbiCC) Journal. Special Issue on ICIT 2009 Conference Applied Computing. 2009. Vol. 4. No. 3. P. 559 - 570.

69. Kharitonov V. У. A Consistency Model for Distributed Virtual Reality Systems // Proc. of the 4th International Conference on Dependability of Computer Systems. Los Alamitos: IEEE CS Press, 2009. P. 271-278.

70. А.Б. Барский Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990. - 256с.

71. Мнхалевич B.C., КуксаА.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. — М.:Наука, 1983. — 208с

72. Топорков В.В. Конспект лекций по курсу «Модели и методы анализа проектных решений» 2006

73. Lestor R. Ford jr., D. R. Fulkerson: Flows in Networks, Princeton Univ. Press, 1962.

74. Jin Y. Yen. "An algorithm for Finding Shortest Routes from all Source Nodes to a Given Destination in General Network", Quart. Appl. Math., 27, 1970, 526-530.

75. Оф. сайт платформы Java http://java.oracle.com

76. Оф. сайт проекта Mono http://www.mono-project.com

77. Bilo, К; Flammini, M; Moscardelli, L.\ , "Pareto approximations for the bicriteria scheduling problem," // Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International, vol., no., pp. 83, 26-30 April 2004

78. Оф. сайт корпорации Intel: описание процессора Intel® Core™2 Duo E6850 http://ark.mtel.com/Product.aspx?id=30785

79. Hay D.C. Requirement Analysis: From business views to architecture // Pearson Education, Inc., Prentice Hall, New Jersey, 2003

80. Anderson D.P. and Fedak G. The Computational and Storage Potential of Volunteer Computing // Proc. of the IEEE/ACM International Symposium on Cluster Computing and Grid, New York: IEEE Press, 2006. P. 73-80.

81. Fischer K., Midler J.P., Pischel M, Schier D. A Model For Cooperative Transportation Scheduling // Proceedings of the First International Conference on Multiagent Systems, AAAI, 1995.

82. Fruchterman, Т. M. J. and Reingold, E. M. (1991), Graph drawing by force-directed placement. Software: Practice and Experience, 21:1129-1164. doi: 10.1002/spe.4380211102

83. Karatza, H.D.\ , "A simulation-based performance analysis of gang scheduling in a distributed system," Simulation Symposium, 1999. Proceedings. 32nd Annual , vol., no., pp.26-33,1999

84. Арютов Б.Л., Важенин A.H., Пасин A.B. «Методы повышения эффективности механизированных производственных процессов по условиям их функционирования в растениеводстве: Учебное пособие» Издательство "Академия Естествознания", 2010

85. А.В. Бобченков «Разработка модели и методов управления ресурсами в виртуальных организациях распределенных вычислительных сред», Дис. канд. технических наук, Москва 2011, -156с.

86. Toporkov V.V., Tselishchev A. Safety Scheduling Strategies in Distributed Computing // Int. J. Critical Computer-Based Systems, Vol. 1, No. 1/2/3, 2010. P. 41-58.

87. Топорков В.В., Целищев А.С. Метод критических работ как перспектива эффективной организации распределённых вычислений // Информационные технологии, 2011, №6, с. 13-17

88. Tselishchev A., Toporkov V.V. Compound job scheduling and job-flows management in distributed computing // Proc. of the 54 Int. Colloquium, Ilmenau, Germany, 2009. P. 21 —26.

89. Целищев А. С. Цифровые сертификаты как средство аутентификации в Грид-компьютинге // Труды XVI международной научно-технической конференции "Информационные средства и технологии". В 3 томах. Т. 1. М.: Издательский дом МЭИ, 2008. - 237 с.

90. Tselishchev A. CERN Certification Authority: Evolution Труды XIV международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика», изд. МЭИ, 2008

91. Листинг A.l: Интервалы распределения работ из примера подраздела 3.2.2.1. Critical job 3

92. Scaling interval: 99 time units.1. Critical job tasks: p9p6 distributed

93. Only one task is not distributed, no tree to build. Critical job 4

94. Scaling interval: 103 time units.

95. Critical job tasks: p9 distributed P7p5 distributed

96. Only one task is not distributed, no tree to build. Critical job 5

97. Scaling interval: 99 time units.1. Critical job tasks: P4p7- distributed

98. Only one task is not distributed, no tree to build. Critical job 6

99. Scaling interval: 99 time units.1. Critical job tasks: Pip7 distributed

100. Only one task is not distributed, no tree to build. Critical job 7

101. Scaling interval: 5 time units.

102. Critical job tasks: p7 distributed p8 - distributed

103. Only one transfer in job, no tree to build. Critical job 8

104. Scaling interval: 108 time units.

105. Critical job tasks: p7 distributed plO

106. Only one task is not distributed, no tree to build.1. Critical job 9

107. Scaling interval: 197 time units.1. Critical job tasks: p2p8 distributed

108. Only one task is not distributed, no tree to build. Critical job 10

109. Scaling interval: 103 time units.

110. Critical job tasks: pi distributed p5 - distributed

111. Only one transfer in job, no tree to build. Critical job 11

112. Scaling interval: 103 time units.

113. Critical job tasks: pi distributed p8 - distributed

114. Only one transfer in job, no tree to build. Critical job 12

115. Scaling interval: 300 time units.1. Critical job tasks: p3

116. Only isolated task in job, no tree to build.