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

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

Емельянов Дмитрий Михайлович

(&<___

МОДЕЛЬ И МЕТОДЫ ВЫБОРА НЕОТЧУЖДАЕМЫХ

РЕСУРСОВ ДЛЯ ПЛАНИРОВАНИЯ ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ

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

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

3 О МАЙ 2013

Москва-2013

005060270

Работа выполнена в Федеральном государственном бюджетном

образовательном учреждении высшего профессионального образования

«Национальный исследовательский университет «МЭИ» (ФГБОУ ВПО «НИУ МЭИ») на кафедре Вычислительной техники.

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

Топорков Виктор Васильевич

Официальные оппоненты: Дзегеленок Игорь Игоревич, доктор технических

наук, профессор, ФГБОУ ВПО «НИУ МЭИ», профессор кафедры Вычислительных машин, систем и сетей

Костенко Валерий Алексеевич кандидат технических наук, старший научный сотрудник, Лаборатория Вычислительных Комплексов факультета ВМК МГУ имени М.В. Ломоносова, ведущий научный сотрудник

Ведущая организация: Объединенный институт ядерных исследований

(ОИЯИ) (г. Дубна)

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

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

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

Автореферат разослан «26 » мал_2013 г.

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

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

Чернов С.А.

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

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

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

Среди различных подходов к планированию в РВС можно выявить следующие тенденции. Одна из них основывается на использовании доступных ресурсов и планировании вычислений на уровне приложений (проекты X-Com, AppLeS, APST, Legion, DRM, Condor-G, Nimrod/G и другие). Другая тенденция связана с образованием виртуальных организаций (ВО) пользователей и предполагает планирование на уровне потоков заданий (комплексы GrAS, GrADS, GARA, Ursala, Silver). В рамках первого из направлений системы планирования и управления ресурсами являются хорошо масштабируемыми и адаптируемыми к особенностям пользовательских приложений. Однако использование независимыми пользователями различных критериев для оптимизации планов выполнения своих заданий (в условиях возможной конкуренции с другими заданиями) может ухудшать такие интегральные характеристики РВС, как время выполнения пакета заданий и уровень загрузки ресурсов. Образование ВО естественным образом ограничивает масштабируемость систем управления заданиями. Однако наличие определенных правил предоставления и потребления ресурсов, основанных, в частности, на экономических моделях, позволяет повысить эффективность планирования и разделения ресурсов на уровне потоков заданий, контроль над которыми осуществляют различного рода метапланировщики, менеджеры, грид-диспетчеры и т.п. Как правило, в основе планирования лежит циклическая иерархическая схема.

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

Таким образом, актуальной является проблема разработки модели и методов управления выполнением независимых заданий в рамках ВО на основе

экономических принципов.

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

Объектом исследования является управление выполнением потоков заданий на неотчуждаемых ресурсах РВС.

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

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

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

1) анализ и исследование циклической схемы управления потоками заданий и ресурсами виртуальной организации РВС с неотчуждаемыми ресурсами, основанной на иерархической модели диспетчеризации;

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

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

4) разработка имитационной модели выбора ресурсов в пределах виртуальной организации;

5) экспериментальное исследование модели и алгоритмов предоставления и потребления неотчуждаемых ресурсов ВО.

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

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

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

2) предложена общая схема коаллокации ресурсов для параллельного задания согласно ресурсному запросу и заданному пользователем критерию эффективности;

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

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

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

использования ресурсов с учетом интересов пользователей, администраторов ВО и собственников ресурсов.

Положения, выносимые на защиту:

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

2) метод планирования потоков заданий с разбиением на подпакеты на основе циклической модели управления заданиями;

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

4) эвристический алгоритм минимизации времени старта и завершения заданий на рассматриваемом интервале планирования;

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

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

Реализация результатов. Работа выполнялась в рамках проектов Совета по грантам Президента Российской Федерации для поддержки ведущих научных школ (шифры НШ-7239.2010.9, НШ-316.2012.9); РФФИ (проекты 09-01-00095, 12-0700042); Минобрнауки России, ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы (государственные контракты № 16.740.11.0038,16.740.11.0516).

Материалы исследования внедрены в учебный процесс подготовки специалистов с высшим образованием по направлению «Информатика и вычислительная техника» специальности 230104.65 «Системы автоматизированного проектирования» по дисциплине «Технология проектирования информационных систем», специальности 230102 «Автоматизированные системы обработки информации и управления» по дисциплине «Информационные технологии» в МИЭМ НИУ ВШЭ, а также были использованы при подготовке курса «Вычислительные системы» кафедры ВТ НИУ «МЭИ».

Апробация работы и публикации. Основные положения и научные результаты докладывались и обсуждались на международных научных конференциях Parallel Computing Technologies РаСТ-2009, 31 августа-4 сентября 2009 г., г. Новосибирск; «Научный сервис в сети Интернет: экзафлопсное будущее», 19-24 сентября 2011 г., г. Новороссийск; «Научный сервис в сети Интернет: поиск новых решений», 17-22 сентября 2012 г., г. Новороссийск; ACS/IEEE International Conference on Computer Systems and Applications, Тунис, Хаммамет; International Conference on Computational Science ICCS 2011, Сингапур, 1-3 июня 2011 г.; ICCS 2012, Омаха, США, 2-6 июня 2012 г.; 7-й международной конференции Dependability and Complex Systems DepCoS-RELCOMEX, Брунов - Вроцлав, Польша, 24-30 июня 2012; «Распределенные вычисления и грид-технологии в науке и образовании», г. Дубна, 16-21 июля 2012г.

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

опубликованы в 28 печатных работах: 27 статьях, включая 3 статьи в изданиях из перечня ВАК, и одну главу в монографии (в соавторстве).

Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения и списка использованной литературы. Текст работы изложен на 170 страницах. Список литературы включает 76 наименований. В работе содержится 33 рисунка и 33 таблицы.

Содержание работы

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

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

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

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

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

Экономические модели планирования эффективны для организации

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

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

Пакет Заданий Пакет Заданий

Рис. 1. Цикличное планирование пакетов заданий в потоке

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

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

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

Можно выделить следующие основные особенности ЦСП.

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

2. Учет приоритетов локальных и глобальных заданий при поиске альтернативных наборов слотов.

3. Составление эффективных или оптимальных планов выполнения пакета заданий в соответствии с политикой, принятой в ВО.

4. Линейная сложность АПС относительно числа доступных слотов в текущем цикле планирования.

Основные ограничения ЦСП состоят в следующем.

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

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

ЦСП имеет ряд преимуществ по сравнению с децентрализованной диспетчеризацией и взята за основу модели планирования потоков заданий и справедливого разделения ресурсов.

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

1. Администраторы ВО должны иметь возможность управлять процессом планирования, задавая политику прохождения потока заданий (или отдельных

пакетов).

2. Пользователи ВО должны иметь возможность влиять на план выполнения собственных заданий путем задания критерия выполнения в ресурсном запросе.

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

4. На каждом цикле планирования система должна позволять задавать соотношение- между оптимизацией выполнения заданий в отдельности и оптимизацией пакета заданий в целом.

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

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

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

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

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

Входные данные алгоритма - список из N слотов, полученный из расписания загрузки узлов на заданном интервале планирования и упорядоченный по неубыванию времени старта. Алгоритм осуществляет последовательный отбор слотов с подходящими параметрами в «окно». Обозначим через т текущее число слотов в списке окна. Тогда алгоритм АПО для одного задания имеет следующий вид.

Шаг 1. Из упорядоченного списка слотов выбирается очередной подходящий слот зу, / = 1.....N. Слот 5/ подходит; если выполняются следующие условия:

a) производительность узла, на котором выделен слот, >р

b) длительность слота не менее требуемой с учетом производительности соответствующего узла /(.$;) > /р(«()ф.

При выполнении ЭТИХ условий СЛОТ Sl добавляется в список слотов формируемого «окна». В случае, если весь список доступных слотов просмотрен, то конец алгоритма.

Шаг 2. Время старта «окна» полагается равным времени старта последнего добавленного слота. Далее происходит проверка всех текущих слотов «окна». Время их завершения должно удовлетворять неравенству: 2еий?(^) > /р^Ур+ЛаМ,

У = 1.....

где Тепс1(з/) - время окончания слота «у, а Т1а$1 — момент старта последнего добавленного слота. Если с учетом времени старта «окна» длительности слота не хватает, чтобы выполнить часть задания, этот слот удаляется из списка слотов «окна».

Шаг 3. Переход к шагу 1, до тех пор, пока т < п.

Если количество слотов в окне т > п, то выбирается «окно» й7, состоящее из п слотов, оптимальное по заданному критерию сг!¥ и удовлетворяющее ресурсному запросу.

Шаг 4. Значения критерия сгIVнайденного «окна» ^сравнивается со значением сг' - текущим лучшим значением целевого критерия для всех найденных ранее «окон». В случае, если сгЖ < сг', «окно» Ж объявляется новым лучшим «окном»-кандидатом, а сгШ становится новым лучшим значением критерия: сг' = сгФ. Переход к шагу 1.

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

Рассмотрим задачу выбора «окна» размером п на списке из т > п слотов (для случая т = п выбор тривиален) с оптимальным значением критерия сг\У и удовлетворяющего ограничению на суммарный бюджет С выполнения задания.

Текущее расширенное «окно» состоит из слотов .....¡т. Стоимость

использования каждого из слотов с учетом их необходимой длительности: с\,с2,...,ст. Предположим, что каждый из слотов имеет характеристику г/, 1 = 1.....п, а сумму значений я необходимо минимизировать в итоговом «окне».

Тогда имеем задачу линейного булева программирования:

а,г, + а2г2 +... + ашгт пип, а,с, + а2с2 +... + атся < С, а1+а2+... + ат=п, аг е {0,1},/" = \,...,т.

Нахождение коэффициентов а1,а1,...,ат, каждый из которых принимает целочисленные значения 0 или 1, а суммарное количество единиц равно и, фактически определит «окно» с оптимальным (минимальным) значением заданного критерия сгЖ.

Алгоритм АПО используется для поиска альтернатив выполнения в рамках метода планирования с разделением на подпакеты МПП, Основное отличие МПП

от исходной ЦСП состоит в принципе формирования системы заданий, а именно в разделении пакета заданий на подпакеты. МПП предполагает выбор комбинации слотов для каждого подпакета в отдельности на заданном интервале планирования (рис. 2). Число подпакетов, на которые «разрезается» пакет заданий, определяет соотношение учета индивидуальных требований пользователей и политики планирования всего пакета заданий, принятой в ВО.

Поиск альтернатив выполнения для подпакетов происходит согласно заданному пользователем критерию в МОС. Чем выше степень отличия найденных альтернатив, тем больше возможностей появляется для оптимизации итогового «окна». Разнородность альтернатив обеспечивается тем, что каждое выполнение АПО осуществляется на модифицированном списке слотов и позволяет формировать «окна» с существенно различными характеристиками (стоимостью, временем выполнения и др.) даже при оптимизации по одному критерию.

Локальное Расписание

Пакет Заданий

Рис. 2. Метод планирования с делением исходного пакета заданий МПП

МПП состоит из следующих этапов.

1. В начале цикла планирования на вход метапланировщика вместе с актуальными локальными расписаниями узлов, поступает пакет пользовательских заданий, который на основе заданного приоритета делится на к подпакетов (шаг 1 на рис. 2).

2. На і-ой итерации, і = 1,подпакет с г'-ым приоритетом поступает на вход МОС (б), который, с учетом всех слотов, доступных после планирования первых /-1 подпакетов, формирует множество альтернатив выполнения для каждого задания с учетом индивидуального критерия поиска, заданного в ресурсном запросе.

3. г'-ый подпакет вместе со списком альтернатив выполнения входящих в него

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

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

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

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

Существующие средства моделирования распределенных сред, такие как GridSim, являются слишком «тяжеловесными», и, кроме того, оперируют укрупненными характеристиками РВС такими, как, пропускная способность сетей, средняя загрузка узлов, типы локальных планировщиков. Они не решают задачу оптимизации планирования на уровнях потоков заданий и отдельных пользовательских приложений. Разработанная система имитационного моделирования зарегистрирована в государственном реестре программ для ЭВМ: свидетельство №2011613238 «Модуль поиска альтернативных наборов слотов «Slot Processor», свидетельство №2013613801 «Модуль поиска оптимальных наборов слотов «SlotProcessorV2», свидетельство №2013613800 «Модуль справедливого разделения неотчуждаемых ресурсов «Batch Slicing»,

свидетельство №2013613799 «Модуль комбинированного планирования потока заданий «Batch Slice Filling».

Ядро системы состоит из 9 компонентов:

• реализация вычислительных процедур и функций распределения случайных величин - параметров РВС;

• генерация ресурсных запросов;

• генерация распределенной вычислительной среды;

• обработка слотов с реализацией АЛО;

• выбор оптимальной комбинации альтернатив (ВКС);

• планирование с разделением на подпакеты (МПП);

• планирование по бэкфиллингу;

• планирование на основе сочетания МПП и бэкфиллига (МПБ).

Основные особенности разработанной имитационной модели состоят в следующем.

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

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

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

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

Для постановки модельных экспериментов обоснованы общие настройки компонентов модели. Типовой размер цикла планирования принят равным 600 единицам времени. Количество узлов в ресурсном домене задается равным 24. Производительность узлов является случайной равномерно распределенной величиной. Этим обеспечивается разнообразие ресурсов при том, что отличие наименее и наиболее производительных экземпляров не превышает одного порядка внутри домена. Удельная стоимость ресурса назначается на этапе ценообразования в зависимости производительности и случайной скидки/наценки, подчиняющейся нормальному распределению. Количество заданий на каждом цикле планирования принимается равным 20. Максимальная стоимость, которую готов заплатить пользователь за выполнения задания, задается таким образом, чтобы «богатейшие» пользователи могу позволить себе использование «дорогих» ресурсов (рыночная стоимость + наценка в 60%), а «беднейшие» пользователи вынуждены рассчитывать на скидки. Эти факторы предотвращают монополизацию наиболее производительных и, соответственно, самых дорогостоящих ресурсов.

В четвертой главе приведены результаты экспериментального исследования модели и методов циклического планирования с разбиением на подпакеты в комбинации с бэкфиллингом (МПП и МПБ).

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

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

минимизации среднего процессорного времени выполнения заданий (Тпроц), Процессорное время альтернативы вычисляется как сумма длительностей слотов, входящих в сформированное окно. На рис. 3 представлено значение Тяроц в зависимости от числа к е {1,2,3,5,6,10,20} подпакетов, на которое делится исходный пакет заданий и уровня загрузки среды.

Уровень загрузки среды определяется средним относительным количеством Y неудач - циклов планирования, в ходе которых не удается найти план выполнения для всех заданий пакета. Эксперименты проводились при высоком (У = 0.3), среднем (7= 0.03) и низком уровнях загрузки (У < 0.0002).

200 -р=-

' ргос

190 -I-г—

Высокий уровень загрузки среды Средний уровень загрузки среды

Низкий уровень загрузки среды

130---

120 -I-1-1-1-1-1-1-1

1 2 з 5 б ю 20 Количество подпакетов

Рис. 3. Среднее значение используемого процессорного времени

В экспериментах по планированию пакета заданий выявлены следующие закономерности.

Увеличение числа формируемых подпакетов обуславливает:

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

• уменьшение суммарной стоимости прохождения пакета заданий;

• увеличение числа неудач.

При увеличении уровня доступных ресурсов:

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

• уменьшается количество неудач;

• уменьшается стоимость прохождения пакета заданий.

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

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

180 170 160 ISO 140

щ 1 вг^^

-ш-В-

*-А-

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

Характеристики выполнения отдельных заданий с учетом пользовательских критериев приведены в таблице 1. На каждом цикле планирования для каждого задания пакета случайным образом, на основе равномерного распределения, устанавливался один из следующих критериев: Тстарт -время старта; Твы„ -время выполнения; Тзав- время завершения; <2 -суммарная стоимость. На этапе поиска альтернативных наборов слотов алгоритм АЛО осуществлял минимизацию выбранных критериев.

Таблица 1 содержит усредненные показатели планирования для 5000 экспериментов.

Таблица 1. Результаты планирования заданий

Оптимизация Количество альтернатив Время старта Время выполнения Время завершения Стоимость выполнения

ш1п Тстарт 12.8 171.7 56.1 227.8 1281.1

тт Твып 10.6 214.5 39.3 253.9 1278.5

тш Тзав 12.2 169.6 45 205.5 1283.2

ппп(} 12.9 262.6 55.5 318 1098.3

АПС 12.1 222 50.3 272.3 1248.4

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

Данные, приведенные в таблице 1, показывают, поиск альтернатив с помощью оптимизационного алгоритма АПО в среднем обеспечивает лучшие значения выбранного критерия, по сравнению с результатами планирования тех же самых заданий, в исходной схеме ЦСП с использованием алгоритма АПС. Преимущество достигает 28% при минимизации времени выполнения, 13% - при минимизации стоимости, более 30% - при минимизации времени старта и завершения. Следует заметить, что использование критерия Тзав обеспечивает лучшие показатели по минимизации времени старта и завершения заданий, а наилучшее время выполнения обеспечивается при выборе критерия Твып.

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

ресурсы распределяются равномерно, вне зависимости от их характеристик.

Для оценки возможности применения разработанных подходов в реальных системах исследовано фактическое время выполнения разработанных алгоритмов в зависимости от характеристик ресурсного домена. Исследование проводилось на платформе с Intel Core ІЗ с 2 ядрами @ 2.93 ГГц и Java 1.6.

Рис. 4. Время реализации алгоритмов в зависимости от числа процессорных

узлов, Ny

Рис. 4 демонстрирует зависимость времени работы АЛО в зависимости от критерия оптимизации и количества узлов (длина интервала планирования составляла 600 единиц). Графики на рис. 4,5, а соответствуют вышерассмотренным критериям. Дополнительно приведены зависимости для следующих случаев: min Тпрец- время работы алгоритма АЛО при минимизации процессорного времени; СПср - среднее время поиска одной альтернативы выполнения с помощью алгоритма АПС в схеме ЦСП.

Для 400 узлов в домене нашлось более 250 альтернатив выполнения задания, а общее время работы алгоритма превышало 3 секунды (на рис. 4 график не показан).

Среднее время работы алгоритмов min Твып, min Тзав, min Тпроч и min Q подтверждает, что данные алгоритмы на практике имеют сложность не выше квадратичной относительно количества узлов РВС.

Рис. 5 показывает зависимость фактического времени реализации алгоритмов АПС и АПО от длительности интервала планирования (количество узлов в домене составляло 100 единиц). Наибольшее время выполнения (2.5 секунды при длительности интервала планирования равной 3600 единиц) дает применение ЦСП (на рис. 5 график не показан). Это объясняется большим количеством формируемых альтернатив (в среднем более 400 альтернатив выполнения на казвдое задание). При этом все алгоритмы обладают линейной сложностью относительно длительности интервала планирования и, соответственно, количества доступных слотов.

Рис. 5. Время реализации алгоритмов в зависимости от длительности интервала

планирования, Г

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

Рис. 6. Средняя прибыль владельца ресурса в зависимости от назначенной удельной стоимости узла

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

Как видно из рис. 6, максимальное значение прибыли 5 достигается при значении удельной стоимости близкой к «среднерыночной» {ссрр «6). При этом повышение или понижение цены ведет к потере прибыли и изменению уровня загрузки (отношению времени использования узла к длительности интервала планирования). Для крайних рассматриваемых значений (2, 10) удельной стоимости узла прибыль падает на 50%. Максимальный уровень загрузки ресурса (44%) достигается при назначении с=2, а минимальный уровень (12%) - при с = 10.

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

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

Проведено сравнительное исследование алгоритмов планирования ЦСП, МПП, МПБ и бэкфиллинга. Наилучшие значения критерия (при минимизации Тпроц) обеспечили ЦСП и МПП, осуществляющие оптимизацию выполнения всего пакета заданий. Их преимущество над бэкфиллингом составляет 15% и 19%, соответственно в условиях высокой загрурки среды, и увеличивается до 40% и 50% - при низком уровне загрузки. Стоит, заметить, что бэкфиллинг предназначен в основном для планирования очереди заданий и осуществляет их компактное расположение в начале интервала планирования. Результаты эксперимента показали, что бэкфиллинг обеспечивает наименьшее время старта заданий по сравнению с ЦСП и МПП, а МПБ обеспечивает «компромиссные» значения рассматриваемых характеристик, обеспечивая меньшее, по сравнению с МПП, время старта при более эффективном, по сравнению с бэкфиллингом, значением целевого критерия.

В заключении представлены основные результаты диссертации.

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

2. Предложен метод планирования пакета заданий с разделением на подпакеты -обобщение циклической схемы планирования.

3. Разработан алгоритм поиска наборов слотов и коаллокации подзаданий АПО, осуществляющий оптимизацию по заданному критерию и являющийся обобщением алгоритма АПС.

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

5. Разработан метод планирования потока заданий на основе сочетания бэкфиллинга и МПП.

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

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

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

1. Топорков В.Б., Топоркова A.C., Бобченкое A.B., Емельянов Д.М. Стратегии организации и поддержки масштабных вычислений в распределенных средах // Открытое образование. 2011 г. № 2 (86). -Т. 2. -С. 15-18.

2. Емельянов Д.М.. Топорков В.В. Экономическая модель справедливого разделения ресурсов в вычислительных средах // Открытое образование. 2012 г. № 4. -С. 63-70.

3. Топорков В.В., Емельянов Д.М. Экономическая модель планирования и справедливого разделения ресурсов в распределенных вычислениях // Открытое образование. 2012 г. № 2 (91). -С. 39-42.

Публикации в других изданиях

4. Топорков В.В., Топоркова A.C., Целищев A.C., Емельянов Д.М. Диспетчеризация потоков заданий и планирование вычислений в распределенных средах // Труды Третьей Всероссийской научной конференции «Методы и средства обработки информации». М.: Изд-во МГУ им. М.В. Ломоносова. 2009 г.-С. 287-298.

5. Toporkov V.V., Toporkova А„ Tselishchev A., Yemelvanov Р. Job and Application-Level Scheduling: an Integrated Approach for Achieving Quality of Service in Distributed Computing // Proc. of the 4th

• International Conference on Dependability of Computer Systems. Los Alamitos, 2009. pp. 202 - 209.

6. Топорков B.B, Топоркова A.C., Целищев A.C., Бобченков A.B., Емельянов Д.М. Масштабируемые модели планирования и управления потоками заданий в распределенных вычислениях II Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции. - М.: Изд-во МГУ. 2009 г. -С. 335 - 339.

7. Топорков В.В, Топоркова A.C., Целишев A.C., Емельянов Д.М. Управление потоками заданий и планирование вычислений в распределенных средах // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09». - М.: Физматлит. 2009 г. -Т. 2. -С. 3-9.

8. Целшцев A.C., Бобченков A.B., Емельянов Д.М. Модифицированный метод критических работ в решении задачи планирования распределенных вычислений // Труды XVII Международной научно-технической конференции «Информационные средства и технологии». 20 - 22 октября 2009 г.; Москва. В 3 томах. -М.: Издательский дом МЭИ. -Т. 1. -С. 84-90.

9. Топорков В.В., Топоркова A.C., Целищев A.C.. Емельянов Д.М. Планирование масштабных вычислений в распределенных средах // Материалы XXXVI международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе» IT+SE'09 (20 - 30 мая 2009 г.): Приложение к журналу «Открытое образование», 2009 г. -С. 37-40.

10. Toporkov V.V., Toporkova А., Tselishchev А., Yemelvanov Р.. Bobchenkov A. Economic Models of Scheduling in Distributed Systems // In: T. Walkowiak, J. Mazurkiewicz, J. Sugier, and W. Zamojski (eds.), Monographs of System Dependability (Vol. 1-3). Dependability of Networks (Vol. 2). 2010. Wroclaw: Oflcyna Wydawnicza Politechnki Wroclawskiej. 210 p.

11. Toporkov V.V., Toporkova A., Tselishchev A., Yemelvanov D. Toporkov V.V., Toporkova A., Tselishchev A., Yemelyanov D. Scalable Co-Scheduling Strategies in Distributed Computing // Proceedings of the 2010 ACS/IEEE International Conference on Computer Systems and Applications, Hammamet, Tunisia, May 16-19th, 2010.2010. pp. 18-25. II IEEE CS Press

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

13. Топорков В.В., Топоркова A.C., Бобченков A.B., Емельянов Д.М.. Целшцев A.C. Экономические модели организации распределенных вычислений // Труды международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе», Май 2010 г., Крым. М.: Открытое образование. 2010 г. -С. 7-10.

14. Топорков В.В., Топоркова A.C., Бобченков A.B., Емельянов Д.М.. Целищев A.C. Планирование вычислений в распределенных средах на основе экономических принципов // Труды Международной суперкомпьютерной конференции "Научный сервис в сети Интернет: суперкомпьютерные центры и задачи", 20-25 сентября 2010 г., Абрау-Дюрсо. М.: Изд-во МГУ им. М.В. Ломоносова. 2010 г. -С. 258-263.

15. Топорков В.В., Топоркова A.C., Бобченков A.B., Емельянов Д.М.. Целищев A.C. Экономические принципы организации распределенных вычислений // Труды международной научно-технической конференции "Суперкомпыотерные технологии: разработка, программирование, применение" СКТ-2010. Таганрог: Изд-во ТТИ ЮФУ. 2010 г. -Т. 2. -С. 92-96.

16. Toporkov V., Toporkova A., Bobchenkov A., Yemelvanov D. Resource Selection Algorithms for Economic Scheduling in Distributed Systems // International Conference on Computational Science, ICCS

2011, June 1-3,2011, Singapore, Procedia Computer Science. Elsevier. 2011. Vol. 4. pp. 2267-2276.

17. Toporkov V., Yemelvanov P.. Toporkova A., Bobchenkov A. Resource Co-allocation Algorithms for Job Batch Scheduling in Dependable Distributed Computing // Dependable Computer Systems. Springer-Veriag Berlin Heidelberg. 2011. AICS. Vol. 97. pp. 243-256.

18. Toporkov V., Bobchenkov A., Toporkova A., Tselishchev A., Yemelvanov D. Slot Selection and Co-allocation for Economic Scheduling in Distributed Computing // PaCT 2011. Springer-Veriag Berlin Heidelberg. 2011, LNCS. Vol. 6873. pp. 368-383.

19. Топорков B.B., Топоркова A.C., Емельянов Д.М.. Бобченков А.В., Целищев А.С. Алгоритмы поиска альтернативных наборов слотов в задаче планирования пакета заданий // Труды Международной суперкомпьютерной конференции "Научный сервис в сети Интернет: экзафлопсное будущее". 19-24 сентября 2011 г. Новороссийск. М.: Изд-во МГУ им. М.В. Ломоносова. 2011 г. -С. 15-22.

20. Топорков В.В., Топоркова А.С., Емельянов Д.М.. Бобченков А.В., Целищев А.С. Алгоритмы отбора слотов в задаче планирования пакета заданий в распределенных средах // Международный конгресс по интеллектуальным системам и информационным технологиям. 2-9 сентября 2011. г. Россия, Краснодарский край, пос. Дивноморское. М.: Физматлит. 2011 г. -Т. 1. -С. 346-352.

21. Топорков В.В., Бобченков А.В., Емельянов Д.М. Алгоритмы планирования выполнения пакета заданий в распределенных вычислительных средах // Труды XIX Международной научно-технической конференции "Информационные средства и технологии", 18-20 октября 2011 г., Москва. М.: Издательский дом МЭИ. 2011 г. -Т. 1. -С. 94-101.

22. Toporkov V.V., Bobchenkov A., Yemelvanov Р.. Toporkova A. Resource co-allocation algorithms in distributed job batch scheduling // In: Ali Al-Dahoud (ed.), Advances in Information Technology from AI to Virtual Reality, 2011. UbiCC. 124 p.

23. Toporkov V., Tselishchev A., Yemelvanov P.. Bobchenkov A. Composite Scheduling Strategies in Distributed Computing with Non-dedicated Resources II Procedia Computer Science. Vol. 9. Elsevier.

2012. pp.176-185.

24. Toporkov V., Tselishchev A., Yemelvanov P.. Bobchenkov A. Dependable strategies for job-flows dispatching and scheduling in virtual organizations of distributed computing environments // Complex Systems and Dependability. Berlin, Heidelberg: Springer-Veriag, AICS. 2012. V. 170. pp. 240-255.

25. Топорков B.B., Бобченков A.B., Емельянов Д.М. Планирование системы независимых заданий в распределенных вычислительных средах с неотчуждаемыми ресурсами // Труды Международной научно-методической конференции «Информатизация инженерного образования» — ИНФОРИНО-2012 (Москва, 10—11 апреля 2012 г.). — М.: Издательский дом МЭИ, 2012 г. -С. 246-249.

26. Топорков В.В., Емельянов Д.М. Справедливое разделение ресурсов в задаче планирования пакета заданий в распределеных средах И Труды Международной суперкомпьютерной конференции «Научный сервис в сети Интернет: поиск новых решений» (Абрау-Дюрсо, 17-22 сентября 2012 г.). М.: Изд-во МГУ им. М.В. Ломоносова. 2012 г. -С. 495-499.

27. Топорков В.В., Бобченков А.В., Емельянов Д.М.. Кореньков В.В., Целищев А.С., Потехин П.А. Стратегии метапланирования на неотчуждаемых ресурсах распределенных вычислительных сред // Труды VI Международной конференции «Параллельные вычисления и задачи управления» (РАСО'2012, Москва, ИПУ РАН, 24-26 октября 2012 г.). - Труды в 3 т. - М.: ИПУ РАН, 2012 г. - Т. 1.-С. 348-363.

28. Toporkov V.V., Tselishchev A.S., Yemelvanov P.M.. Bobchenkov A.V. Dependable job-flow dispatching and scheduling in virtual organizations of distributed computing environments // Distributed Computing and Grid-Technologies in Science and Education: Proceedings of the 5th Intern. Conf. (Dubna, 16-21 July, 2012). -Dubna: JINR, 2012. pp. 234-242.

Подписано в печать OS'^vOiS f\' зак. m Тир. ЮО П.л.

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

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

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

университет «МЭИ»

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

04201357797

Емельянов Дмитрий Михайлович

МОДЕЛЬ И МЕТОДЫ ВЫБОРА НЕОТЧУЖДАЕМЫХ

РЕСУРСОВ ДЛЯ ПЛАНИРОВАНИЯ ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ

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

компьютерные сети

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

Научный руководитель д.т.н., профессор Топорков Виктор Васильевич

Москва-2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ........................................................................................................................................4

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМЫ ПЛАНИРОВАНИЯ ЗАДАНИЙ НА НЕОТЧУЖДАЕМЫХ РЕСУРСАХ В РВС.................................................................................................................................................10

1.1 Введение..........................................................................................................................................10

1.2 Используемые термины и обозначения..........................................................................................11

1.3 Особенности планирования в РВС....................................................................................................12

1.3.1 Разнородность и автономность ресурсов РВС....................................................................................................16

1.3.2 Динамичность ресурсов........................................................................................................................................17

1.3.3 Особенности отбора ресурсов..............................................................................................................................17

1.4 Принципы организации РВС.............................................................................................................18

1.4.1 Виртуальные организации в среде с неотчуждаемыми ресурсами.................................................................18

1.4.2 Диспетчеризация в РВС.........................................................................................................................................20

1.5 Подходы к планированию в РВС......................................................................................................23

1.5.1 Целевые функции, ориентированные на приложения......................................................................................23

1.5.2 Целевые функции, ориентированные на ресурсы.............................................................................................24

1.5.3 Экономические модели планирования...............................................................................................................25

1.5.4 Методы решения задач планирования...............................................................................................................27

1.6 Обзор существующих систем планирования...................................................................................28

1.6.1 Брокер ресурсов 1\Птгос1-С...................................................................................................................................28

1.6.2 РСРБ и алгоритм обратного заполнения..............................................................................................................30

1.6.3 Система М\Л/ШЕ.......................................................................................................................................................34

1.6.4 Циклическая схема планирования потоков заданий.........................................................................................36

1.7 Исследование алгоритмов, лежащих в основе ЦСП.........................................................................41

1.7.1 Модуль обработки слотов....................................................................................................................................41

1.7.2 Алгоритм выбора оптимальной или эффективной комбинации слотов..........................................................43

1.7.3 Особенности циклической схемы планирования потоков заданий................................................................45

1.8 Постановка задачи............................................................................................................................49

1.9 Выводы по главе...............................................................................................................................51

ГЛАВА 2. МОДЕЛЬ СПРАВЕДЛИВОГО РАЗДЕЛЕНИЯ НЕОТЧУЖДАЕМЫХ РЕСУРСОВ В РВС............53

2.1 Концепция модели планирования и справедливого разделения неотчуждаемых ресурсов.........53

2.2 Алгоритм поиска набора слотов, оптимального по заданному критерию.........................................................56

2.2.1 Система заданий и ресурсные запросы...............................................................................................................57

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

2.3.1 Основные положения метода..............................................................................................................................70

2.3.3 Процедура сдвига окон.........................................................................................................................................78

2.4 Комбинированный метод планирования с использованием бэкфиллинга....................................81

2.5 Анализ предложенной модели планирования................................................................................83

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

ГЛАВА 3. РАЗРАБОТКА СИСТЕМЫ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ...................................88

3.1 Вопросы разработки системы имитационного моделирования.....................................................88

3.2. Компоненты системы имитационного моделирования.................................................................90

3.2.1 Функции распределения случайных величин....................................................................................................92

3.2.2 Компонент генерации ресурсных запросов.......................................................................................................94

3.2.3 Компонент генерации вычислительной среды..................................................................................................96

3.2.4 Модуль обработки слотов....................................................................................................................................99

3.2.5 Компонент выбора оптимальной комбинации слотов....................................................................................101

3.2.6 Компонент МПП...................................................................................................................................................103

3.2.7 Компонент планирования очереди заданий на основе бэкфиллинга...........................................................105

3.2.8 Компонент планирования очереди заданий на основе МПБ..........................................................................106

3.2.9 Компонент графического отображения результатов планирования..............................................................107

3.3 Исходные данные для проведения экспериментов......................................................................109

3.3.1 Параметры генерации начального состояния вычислительной среды..........................................................110

3.3.2 Параметры генерации исходного пакета пользовательских заданий............................................................112

3.4 Выводы по главе.............................................................................................................................114

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ СХЕМ И МЕТОДОВ ПЛАНИРОВНИЯ..............115

4.1 Исследование алгоритма поиска наборов слотов оптимальных по заданному критерию...........115

4.1.1 Исследуемые алгоритмы поиска альтернативных наборов слотов................................................................115

4.1.2 Постановка эксперимента..................................................................................................................................116

4.1.3. Результаты эксперимента..................................................................................................................................117

4.1.4 Выводы.................................................................................................................................................................126

4.2 Исследование схемы планирования с разделением на подпакеты МПП......................................127

4.2.1 Исследуемые алгоритмы....................................................................................................................................127

4.2.2 Постановка эксперимента..................................................................................................................................128

4.2.3 Результаты экспериментов.................................................................................................................................130

4.2.4 Выводы.................................................................................................................................................................138

4.3 Исследование схемы планирования пакета заданий ЦСПБ с использованием бэкфиллинга.......139

4.3.1 Исследуемые конфигурации МПБ.....................................................................................................................139

4.3.2 Постановка эксперимента..................................................................................................................................140

4.3.3 Результаты экспериментов.................................................................................................................................141

4.3.4 Выводы.................................................................................................................................................................142

4.4 Исследование алгоритма выбора оптимальных наборов слотов в рамках МПП..........................143

4.4.1 Постановка эксперимента..................................................................................................................................144

4.4.2 Результаты экспериментов.................................................................................................................................145

4.4.3 Выводы.................................................................................................................................................................148

4.5 Исследование влияния назначенной стоимости ресурса на загруженность и спрос.....................148

4.5.1 Постановка эксперимента..................................................................................................................................149

4.5.2 Результаты экспериментов.................................................................................................................................150

4.5.3 Выводы.................................................................................................................................................................153

4.6 Сравнительное исследование алгоритмов планирования.............................................................153

4.6.1 Анализируемые алгоритмы................................................................................................................................154

4.6.2 Постановка эксперимента..................................................................................................................................154

4.6.3 Результаты экспериментов.................................................................................................................................155

4.6.4 Выводы.................................................................................................................................................................159

ЗАКЛЮЧЕНИЕ.......................................................................................................................................160

ЛИТЕРАТУРА................................................................................................................................163

Приложение А: Акт об использовании результатов диссертации в НИУ МЭИ.....................171

Приложение В: Акт об использовании результатов диссертации в МИЭМ НИУ ВШЭ..........172

введение

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

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

Среди различных подходов к планированию в РВС можно выявить следующие тенденции. Одна из них основывается на использовании доступных ресурсов и планировании вычислений на уровне приложений (проекты X-Com, AppLeS, APST, Legion, DRM, Condor-G, Nimrod/G и другие). Другая тенденция связана с образованием виртуальных организаций (ВО) пользователей и предполагает планирование на уровне потоков заданий (комплексы GrAS, GrADS, GARA, Ursala, Silver). В рамках первого из направлений системы планирования и управления ресурсами являются хорошо масштабируемыми и адаптируемыми к особенностям пользовательских приложений. Однако использование независимыми пользователями различных критериев для оптимизации планов выполнения своих заданий (в условиях возможной конкуренции с другими заданиями) может ухудшать такие интегральные характеристики РВС, как время выполнения пакета заданий и загрузка ресурсов. Образование ВО естественным образом ограничивает масштабируемость систем управления заданиями. Однако наличие определенных правил предоставления и потребления ресурсов, основанных, в частности, на экономических моделях, позволяет повысить эффективность планирования и

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

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

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

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

Объектом исследования является управления выполнением потоков заданий на неотчуждаемых ресурсах РВС.

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

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

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

1) анализ и исследование циклической схемы управления потоками заданий и ресурсами виртуальной организации РВС с неотчуждаемыми ресурсами, основанной на иерархической модели диспетчеризации;

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

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

4) разработка имитационной модели выбора ресурсов в пределах виртуальной организации;

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

Методы исследования. Поставленные задачи решались с использованием методов исследования операций и имитационного моделирования. Научная новизна работы состоит в следующем:

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

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

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

• обоснована комбинированная схема планирования на основе сочетания

циклической схемы и алгоритма обратного заполнения (бэкфиллинга),

реализующая преимущества обоих подходов.

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

Положения, выносимые на защиту:

• циклическая модель планирования, поддерживающая распределение ресурсов с учетом интересов всех участников ВО;

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

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

• эвристический алгоритм минимизации времени старта и завершения заданий на рассматриваемом интервале планирования;

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

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

Реализация результатов. Работа выполнялась в рамках проектов Совета по грантам Президента Российской Федерации для поддержки ведущих научных школ (шифры НШ-7239.2010.9, НШ-316.2012.9); РФФИ (проекты 09-01-00095, 12-0700042); Минобрнауки России, ФЦП «Научные и научно-педагогические кадры

инновационной России» на 2009-2013 годы (государственные контракты №№ 16.740.11.0038, 16.740.11.0516).

Материалы исследования внедрены в учебный процесс подготовки специалистов с высшим образованием по направлению «Информатика и вычислительная техника» специальности 230104.65 «Системы автоматизированного проектирования» по дисциплине «Технология проектирования информационных систем», специальности 230102 «Автоматизированные системы обработки информации и управления» по дисциплине «Информац�