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

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

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

Среди различных подходов к планированию в РВС можно выявить следующие тенденции. Одна из них основывается на использовании доступных ресурсов и планировании вычислений на уровне приложений (проекты 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−95, 12−700 042) — Минобрнауки России, ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009;2013 годы (государственные контракты №№ 16.740.11.0038, 16.740.11.0516).

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

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