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

• Автор: Емельянов, Дмитрий Михайлович
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 173 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 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.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. Взаимодействие доменов внутри системы NWIRE Задания от пользователей могут поступать на вход любого из локальных метаменеджеров и, кроме ресурсного запроса, содержат критериальные функции
вида start) (оптимизация по приведенному критерию позволяет минимизировать время старта задания). Ресурсный запрос представляет собой набор требований к ресурсам, которые необходимо выделить для выполнения пользовательского задания вместе с оценкой суммарного времени выполнения задания. В случае преждевременного освобождения ресурсов, они могут быть использованы для выполнения заданий, поступивших в систему позднее.
Метаменеджер генерирует варианты выполнения задания на базе ресурсов собственного домена, а также посылает данные задания связанным метаменеджерам. Связанные метаменеджеры также генерируют альтернативы (предложения) выполнения и передают их для анализа первому метаменеджеру.