Модель и методы выбора неотчуждаемых ресурсов для планирования заданий в распределенных вычислительных средах тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Емельянов, Дмитрий Михайлович

• Емельянов, Дмитрий Михайлович
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Емельянов, Дмитрий Михайлович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

1.1 Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1.4 Выводы

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

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

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

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

4.2.4 Выводы

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

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

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

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

4.3.4 Выводы

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

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

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

4.4.3 Выводы

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

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

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

4.5.3 Выводы

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

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

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

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

4.6.4 Выводы

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

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

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

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

введение

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

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

Среди различных подходов к планированию в РВС можно выявить следующие тенденции. Одна из них основывается на использовании доступных ресурсов и планировании вычислений на уровне приложений (проекты 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 «Автоматизированные системы обработки информации и управления» по дисциплине «Информационные технологии» в МИЭМ НИУ ВШЭ, а также были использованы при подготовке курса «Вычислительные системы» кафедры ВТ НИУ МЭИ.

Апробация работы и публикации. Основные положения и научные результаты докладывались и обсуждались на международных научных конференциях Parallel Computing Technologies РаСТ-2009, 31 августа-4 сентября 2009 г., г. Новосибирск; «Научный сервис в сети Интернет: экзафлопсное будущее», 19-24 сентября 2011 г., г. Новороссийск; «Научный сервис в сети Интернет: поиск новых решений», 17-22 сентября 2012 г., г. Новороссийск; ACS/ШЕЕ 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г.

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

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

Заключение диссертации по теме «Вычислительные машины и системы», Емельянов, Дмитрий Михайлович

4.6.4 Выводы

Результаты экспериментов, представленные в таблицах 4.13-4.15 и на диаграммах 4.14-4.15, демонстрируют преимущество предлагаемых оптимизационных методов Mliii, ЦСП и МПБ перед бэкфиллингом по рассматриваемому целевому критерию минимизации используемого процессорного времени. При этом преимущество увеличивается при понижении уровня загрузки вычислительной среды. Минимальное значение целевого критерия при каждом рассматриваемом уровне загрузки среды обеспечивает МПП.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Емельянов, Дмитрий Михайлович, 2013 год

литература

1.1. Foster and С. Kesselman (editors); The Grid: Blueprint for a Future Computing Infrastructure, Morgan Kaufmann Publishers, USA, 1999.

2. I. Foster and A. Iamnitchi; On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing // Proc. of 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03), Berkeley, CA, USA, February 2003.

3. I. Foster, C. Kesselman and S. Tuecke; The Anatomy of the Grid: Enabling Scalable Virtual Organizations // International J. Supercomputer Applications, 15(3), pp. 200-220, 2001.

4. Deniz Cokuslu, Abdelkader Hameurlain, Kayhan Erciyes; Grid Resource Discovery Based on Centralized and Hierarchical Architectures // International Journal for Infonomics (IJI), Vol. 3, Issue 1, March 2010.

5. E. Imamagic, B. Radic, D. Dobrenic; CRO-GRID Grid Monitoring Architecture // Proceedings of 27th International Conference Information Technology Interfaces, pp. 65 - 72, June 20-23, 2005.

6. M. Baker, R. Buyya and D. Laforenza; Grids and Grid Technologies for Wide-area Distributed Computing // J. of Software-Practice & Experience, Vol. 32, No.15, pp. 1437-1466, December 2002.

7. Топорков B.B. Опорные планы согласованного выделения ресурсов при организации распределенных вычислений на масштабируемых системах // Программирование. - 2008. - № 5. - С. 50-64.

8. Toporkov V., Tselishchev A., Yemelyanov Р., Bobchenkov; A. Composite Scheduling Strategies in Distributed Computing with Non-dedicated Resources // Procedia Computer Science. Vol. 9, pp. 176-185, Elsevier, 2012.

9. David Jackson, Quinn Snell, Mark Clement; Core Algorithms of Maui Scheduler // Proceedings JSSPP '01 Revised Papers from the 7th International Workshop on Job Scheduling Strategies for Parallel Processing, Springer-Verlag London, UK, 2001

10.Y. Zhu; A Survey on Grid Scheduling Systems // Department of Computer Science, Hong Kong University of science and Technology, 2003.

11. J. Schopf; Ten Actions When Super Scheduling // document of Scheduling Working Group, Global Grid Forum, http://www.ggf.0rg/d0cuments/GFD.4.pdf, July 2001.

12. F. Berman, R. Wolski, H. Casanova, W. Cirne, H. Dail, M. Faerman, S. Figueira, J. Hayes, G. Obertelli, J. Schopf, G. Shao, S. Smallen, N. Spring, A. Su and D. Zagorodnov; Adaptive Computing on the Grid Using AppLeS // IEEE Trans, on

Parallel and Distributed Systems (TPDS), Vol.14, No.4, pp.369-382, 2003.

13. V. Hamscher, U. Schwiegelshohn, A. Streit, R. Yahyapour; Evaluation of Job-Scheduling Strategies for Grid Computing // Proc. of GRID 2000, First IEEE/ACM International Workshop, pp. 191-202, Bangalore, India, December, 2000.

13. G. Mateescu; Quality of Service on the Grid via Metascheduling with Resource Co-Scheduling and Co-Reservation // International Journal of High Performance Computing Applications, Vol. 17, No. 3, pp.209-218, 2003.

15. http://www.globus.org/

16. A. A. Khokhar, V. K. Prasanna, M. E. Shaaban, and C. L. Wang; Heterogeneous Computing: Challenges and Opportunities // IEEE Computer, Vol. 26, No. 6, pp. 18-27, June 1993.

17. H. J. Siegel, H. G. Dietz, and J. K. Antonio; Software Support for Heterogeneous Computing // ACM Computing Surveys, Vol.28, No.l, pp. 237 - 239, March 1996.

18. Krzysztof Kurowski, Ariel Oleksiak, Jarek Nabrzyski, Agnieszka Kwiecien, Marcin Wojtkiewicz, Maciej Dyczkowski, Francesc Guim, Julita Corbalan, Jesus Labarta; Multi-criteria Grid Resource Management using Performance Prediction Techniques // Integrated Research in GRID Computing, pp. 215-225, 2007.

19. F. Berman, High-Performance Schedulers, chapter in The Grid: Blueprint for a Future Computing Infrastructure, Morgan Kaufmann Publishers, 1998.

20. http://www.openpbs.org/

21. http://www.cs.wisc.edu/condor/

22. F.D. Sacerdoti, M.J. Katz, M.L Massie and D.E. Culler; Wide area cluster monitoring with Ganglia // Proc. of IEEE International Conference on Cluster Computing, pp.289 - 298, Hong Kong, December 2003.

23. Geoffrey Fox, Sang Lim, Shrideep Pallickara, Marlon Pierce; Message-based cellular peer-to-peer grids: foundations for secure federation and autonomic services // Future Generation Computer Systems - Special issue: P2P computing and interaction with grids. Vol. 21 Issue 3, pp. 401-415, 1 March 2005.

24. Коваленко В. H., Орлов А. В. Управление заданиями в распределенной среде и протокол резервирования ресурсов // Препринт.- М.: ИПМ им. М. В. Келдыша РАН.-2002,- 23 с.

25. Коваленко В. Н., Коваленко Е. И., Корягин Д. А., Любимский Э. 3., Хухлаев Е. В. Управление заданиями в распределенной вычислительной среде // Открытые системы.-2001,-№5-6.-С. 22-28

26. Коваленко В. Н., Семячкин Д. А, Использование алгоритма Backfill в грид // Тр. международной конф. «Распределенные вычисления и Грид-технологии в науке и образовании» (Дубна, 29 июня - 2 июля 2004 г.) - Дубна: ОИЯИ, 2004.- С. 139-144.

27. F. Berman and R. Wolski; The AppLeS Project: A Status Report // Proceedings of the 8th NEC Research Symposium, Berlin, Germany, May 1997.

28. Jang-uk In, Paul Avery, Richard Cavanaugh, Sanjay Ranka; Policy Based Scheduling for Simple Quality of Service in Grid Computing // 18th International Parallel and Distributed Processing Symposium, 26-30 April, 2004.

29. Nabrzyski, Jarek; Schopf, Jennifer M.; Weglarz, Jan (Eds.); Grid Resource Management. State of the Art and Future Trends // Springer, 575 p., 2003. ISBN 978-1-4020-7575-9.

30. R. Buyya, J. Giddy, and D. Abramson; An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications // Proc. of the 2nd International Workshop on Active Middleware Services (AMS 2000), pp. 221-230, Pittsburgh, USA, August, 2000.

31. R. Buyya and D. Abramson and J. Giddy and H. Stockinger; Economic Models for Resource Management and Scheduling in Grid Computing // J. of Concurrency and Computation: Practice and Experience, Vol. 14, Issue. 13-15, pp. 1507-1542,

Wiley Press, December, 2002.

32. C. Ernemann, V. Hamscher and R. Yahyapour; Economic Scheduling in Grid Computing // Proc. of 8th Workshop on Job Scheduling Strategies for Parallel

Processing, in conjunction with HPDC/GGF 5, Edinburgh, Scotland, UK, pp.128-152, July, 2002.

33. D. Wright; Cheap Cycles from the Desktop to the Dedicated Cluster: Combining Opportunistic and Dedicated Scheduling with Condor // Proc. of Conference on Linux Clusters: the HPC Revolution, Champaign Urbana, IL USA, June, 2001.

34. R. Buyya, D. Abramson, and J. Giddy; An economy driven resource management architecture for global computational power Grids // Proc. of 7th International Conf. Parallel and Distributed Processing Techniques and Applications, Las Vegas, June 26-29, 2000.

35. Y. Zhu, L. Xiao, L. M. Ni and Z. Xu; Incentive-based P2P Scheduling in Grid Computing // Proc. of the 3rd International Conference on Grid and Cooperative Computing (GCC2004), Wuhan, China, October, 2004.

36. R. Buyya, D. Abramson, and S. Venugopal; The Grid Economy // Proc. of the IEEE, 93(3), pp. 698-714, 2005.

37. R. Buyya, D. Abramson, and J. Giddy; A Case for Economy Grid Architecture for Service-Oriented Grid Computing // Proceedings of the International Parallel and Distributed Processing Symposium: 10th IEEE International Heterogeneous Computing Workshop (HCW 2001), April 23, 2001, San Francisco, California, USA, IEEE CS Press, USA, 2001.

38. L. Young, S. McGough, S. Newhouse, and J. Darlington; Scheduling Architecture and Algorithms within the ICENI Grid Middleware // Proc. of UK e-Science All HandsMeeting, pp. 5-12, Nottingham, UK, September, 2003.

39. Abramson, D., Buyya, R. & Giddy J.; A computational economy for grid computing and its implementation in the Nimrod-G resource broker // Future generation Computer Systems, 18(8), pp.1061- 1074, October, 2002.

40. S. J. Chapin, D. Katramatos, J. Karpovich and Andrew S. Grimshaw // The Legion Resource Management System // Proc. of the 5th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP '99), in conjunction with the International Parallel and Distributed Processing Symposium (IPDPS '99), Lecture Notes in Computer Science, Vol. 1659, pp. 162-178, San Juan, Puerto Rico, April, 1999.

41. J.P. Jones and B. Nitzberg; Scheduling for Parallel Supercomputing: A Historical Perspective of Achievable Utilization // Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 1-16, Springer-Verlag, 1999.

42. D. Lifka; The ANL/IBM SP Scheduling System // Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 295-303, Springer-Verlag, 1995.

43. Ahuva Mu'allem, Dror Feitelson; Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling // Parallel and Distributed Systems, Vol.12, Issue 6, pp. 529-543, June, 2001.

44. P. Domingues, P. Marques, and L. Silva; DGSchedSim: A trace-driven simulator to evaluate scheduling algorithms for desktop grid environments // Proceedings of the 14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, pp. 83-90, 2006.

45. Toporkov V. Application-level and job-flow scheduling: an approach for achieving quality of service in distributed computing // Proceedings of the 10th international conference on parallel computing technologies, Springer, Heidelberg, LNCS, vol. 5698, 2009.

46. Kurowski K., Nabrzyski J., Oleksiak A. et al. Multicriteria Aspects of Grid Resource Management // In: J. Nabrzyski, J.M. Schopf, and J. Weglarz (eds.), Grid resource management. State of the art and future trends. - Boston: Kluwer Academic Publishers, 2003.

47. Коваленко B.H., Коваленко E. И., Корягин Д. А, Любимский Э. 3., Хухлаев Е. В., Шорин О.Н. Планирование ресурсов в GRID на основе локальных расписаний // ИПМ им. М.В. Келдыша РАН, Москва.

48. http://www.adaptivecomputing.com/support/documentation/

49. Toporkov V, Toporkova A, Bobchenkov A, Yemelyanov D. Resource selection algorithms for economic scheduling in distributed systems // Procedia Computer Science, Elsevier. Vol.4, pp. 2267-2276. 2011.

50. Toporkov V, Yemelyanov D, Toporkova A, Bobchenkov A. Resource co-allocation algorithms for job batch scheduling in dependable distributed computing // Dependable Computer Systems. Springer-Verlag, AICS. Vol. 97. pp. 243-256. Berlin, Heidelberg, 2011.

51. V. Toporkov, A. Tselishchev, D. Yemelyanov, A. Bobchenkov; Composite Scheduling Strategies in Distributed Computing with Non-dedicated Resources // Procedia Computer Science. Elsevier. Vol. 9, pp. 176-185, 2012.

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

53. 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. pp. 143154 (монография на англ. яз.).

54. Таха Х.А. Введение в исследование операций. 7-е издание.: Пер. с англ. — Москва: Издательский дом "Вильяме", 2005. — 912 с.

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

56. A. Roy and V. Sander; Advance Reservation API // Technical Report GFD-E.5, Global Grid Forum (GGF), 2002.

57. Zikos, S., Karatza, H.D. Resource allocation strategies in a 2-level hierarchical grid system // Proceedings of the 41 st Annual Simulation Symposium (ANSS), April 13-16,2008. IEEE Computer Society Press, SCS, pp. 157-164.

58. Claris Castillo, George N. Rouskas, Khaled Harfoush; Resource Co-Allocation for Large-Scale Distributed Environments // Proceedings of HPDC '09 Proceedings of the 18th ACM international symposium on High performance distributed computing, pp. 131-140. ACM New York, NY, USA 2009.

59. Atsuko Takefusa, Hidemoto Nakada, Tomohiro Kudoh, Yoshio Tanaka; An advance reservation-based co-allocation algorithm for distributed computers and network bandwidth on QoS-guaranteed grids // Proceedings of JSSPP'10 Proceedings of the 15th international

conference on Job scheduling strategies for parallel processing, Springer-Verlag Berlin, pp. 1634. Heidelberg, 2010.

60. Toporkov V., Yemelyanov P., Toporkova A., Bobchenkov A. Resource Co-allocation Algorithms for Job Batch Scheduling in Pependable Pistributed Computing // Pependable Computer Systems. Springer-Verlag Berlin Heidelberg. AICS. Vol. 97. pp. 243-256. 2011.

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

62. Farag Azzedin, Muthucumaru Maheswaran, Neil Arnason; A Synchronous Co-Allocation Mechanism for Grid Computing Systems // Cluster Computing, Vol. 7, pp. 39^9, Kluwer Academic Publishers. 2004.

63. Топорков B.B., Целищев А.С. Метод критических работ как перспектива эффективной организации распределенных вычислений // Информационные технологии.-

2011,- №6. -С. 13-17.

64. P. Pinda; Online prediction of the running time of tasks // Proc. 10th IEEE Symp. on High Performance Pistributed Computing, 2001

65. V. Taylor, X. Wu, J. Geisler, X. Li, z. Lan, M. Hereld, I. Judson, and R. Stevens; Prophesy: Automating the modeling process // Proc. Of the Third International Workshop on Active Middleware Services, 2001.

66. Wolski, R, Plank, J.S., Brevik, J. and Bryan; T. Analyzing market-based resource allocation strategies for the computational Grid // International Journal of High Performance Computing Applications, 15(3), pp. 258-281. 2001.

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

2012. С. 495-499.

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

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

70.Rajkumar Buyya, Manzur Murshed; GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing // The Journal of Concurrency and Computation: Practice and Experience (CCPE), Vol. 14, Issue 13-15, Wiley Press, Nov.-Dec., 2002.

71. W.Bell, D. Cameron, L.Capozza; Simulation of Dynamic Grid Replication Strategies in OptorSim Proceeding GRID // '02 Proceedings of the Third International Workshop on Grid Computing, pp. 46-57, Springer-Verlag London, UK, 2002.

72.Toporkov V., Toporkova A., Bobchenkov A., Yemelyanov D. Resource Selection Algorithms for Economic Scheduling in Distributed Systems // International Conference on Computational Science, ICCS 2011, June 1-3, Singapore, Procedía Computer Science. Elsevier. Vol. 4. pp. 2267-2276. 2011.

73. Титов P.H. Разработка системы электронного документооборота для автоматизации управления научно-техническими проектами (на примере европейской организации ядерных исследований): автореф. канд. техн. наук: 05.13.01: МИФИ, 2011.

74. Бобченков А.В. Разработка модели и методов управления ресурсами в виртуальных организациях распределенных вычислительных сред: дис. канд. техн. наук: 05.13.15: НИУ МЭИ, 2011, — 151 с.

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

76. K. Masahiro, N. Katsuhiro, T. Tetsuji; Hypergeometric solution of a stochastic model for traffic flow // Transactions of the Japan Society for Industrial and Applied Mathematics, Vol.16 (3), pp.211-220. 2011.

1ек|ор НИУ «МЭИ» по учебной работе

пР°Ф- Степанова Т.А.

«/V» 2013 г.

«Утверждаю»

АКТ

об использовании результатов кандидатской диссертационной работы аспиранта кафедры Вычислительной техники Московского энергетического института (Национального исследовательского университета) Емельянова Дмитрия Михайловича «МОДЕЛЬ И МЕТОДЫ ВЫБОРА НЕОТЧУЖДАЕМЫХ РЕСУРСОВ ДЛЯ ПЛАНИРОВАНИЯ ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ

СРЕДАХ»

Мы, нижеподписавшиеся представители кафедры Вычислительной техиики к.т.н.. доцент Андреева И.Н., к.т.н , доцент Пирогова М.А., составили настоящий акг о том, что аспирантом кафедры ВТ НИУ «МЭИ» Емельяновым ДМ. были проведены исследования подходов к выбору и разделению ресурсов в распределенных вычислительных средах. Разработанные алгоритмы выбора альтернатив выпотнения и методы планирования являются развитием циклической схемы планирования потоков заданий и обеспечивают «справедливое» разделение ресурсов на основе экономических принципов Для этого был проведен анализ циклической схемы планирования, а также существующих алгоритмов коаллокации ресурсов, выявлены их особенности и ограничения. Предложенная в работе модель циклического планирования и справедливого разделения ресурсов предоставляет всем участникам виртуальной организации (администраторам, пользователям, владельцам вычислительных узлов) возможность влиять на качество выполнения заданий и использования узлов согласно преследуемым интересам. С помощью разработанного программного обеспечения, реализующего предложенные методы и алгоритмы, было проведено имитационное моделирование. В результате проведенных экспериментов показана возможность обеспечения справедливого разделения ресурсов при планировании потока заданий от пользователей, а также совпадение теоретических положений с практикой. Кроме того, показана возможность и целесообразность объединения циклической схемы планирования с традиционным алгоритмом бэкфиллинг. Одновременное наличие описанных свойств и особенностей выгодно отличает предложенную модель от использующихся на сегодняшний день аналогов.

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

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

зам. зав. каф. ВТ по учебной работе, к.т.

зам. зав. каф. ВТ, к.т.н.

/Пирогова М А./

/Андреева И.Н./

Заместит

УТВЕРЖДАЮ

ебной работе , д.т.н., проф. . Тумковский

АКТ

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

университет «МЭИ» Емельянова Дмитрия Михайловича

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

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

Настоящий акт подтверждает, что результаты диссертационной рабо!ы Емельянова Д.М. внедрены в учебный процесс МИЭМ НИУ ВШЭ.

Аспирантом кафедры ВТ НИУ «МЭИ» Емельяновым Д.М. были проведены исследования методов выбора неотчуждаемых ресурсов для планирования потоков заданий в виртуальных организациях распределенных вычислительных сред. Проведён анализ циклической схемы планирования, а также использующихся в современных грид-системах алгоритмов поиска и коаллокации ресурсов. В результате проведённых исследований разработана модель планирования и «справедливого» разделения ресурсов, на основе экономических принципов учитывающая интересы пользователей, администраторов виртуальной организации и владельцев ресурсов.

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

т

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

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

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

Декан Факультета информационных технологий и вычислительной техники

д.т.н., проф._-- —Е.Д. Пожидаев

Зам. Зав. кафедрой Информационных технологий и автоматизированных систем г>, / }

д.т.н., проф._//х^-/ A.M. Кожевников

г