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

• Автор: Целищев, Алексей Сергеевич
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 238 с. : ил.

ОГЛАВЛЕНИЕ
Введение

Глава 1. Парадигмы и алгоритмы планирования распределенных вычислений

1.1. Параллельные и распределенные вычисления. Гридсистемы

1.2. Планирование вычислений в Гридсистемах.

1.2.1. Базовые определения.

1.2.2. Виды Гридпланировщиков.

1.3. Классификация методов планирования и организации вычислений в Грид

1.3.1. планирование

1.3.2. i планирование

1.3.3. Метод критических работ.

1.4. Парадигмы распределенных вычислений.
1.5. Выводы
Глава 2. Иерархическая модель планирования.
2.1. Метапланировщик генератор стратегий распределенных вычислений
2.1.1. Компоненты иерархической модели планирования
2.1.2. Постановка задачи иерархического планирования.
2.2. Модифицированный метод критических работ
2.2.1. Постановка и компоненты задачи составления расписаний.
2.2.2. Масштабируемая модель планирования
2.2.3. Адаптация метода критических работ к работе с экземплярами ресурсов
2.2.4. Метод критических работ в среде с неотчуждаемыми ресурсами
2.2.5. Разрешение коллизий параллельных процессов
2.3. Вспомогательные алгоритмы и эвристики.
2.3.1. Генерация ациклических графов.
2.3.2. Поиск и ранжирование критических работ графа
2.3.3. Динамический поиск вариантов распределения
2.3.4. Эвристический алгоритм разрешения коллизий
2.3.5. Механизм обратной связи модифицированного метода критических работ
2.4. Выводы
Глава 3. Имитационная модель планирования на уровне приложений.
3.1. Функционал и структура имитационной модели
3.2 Результаты работы имитационной модели.
3.2.1. Поиск и ранжирование критических работ.
3.2.2. Масштабирование.
3.2.3. Составление расписания и разрешение коллизий
3.2.5. Масштабирование по стоимости
3.2.6. Производительность модели.
3.3. Выводы
Глава 4. Статистические исследования модифицированного метода критических работ .
4.1. Статистические эксперименты.
4.1.1. Статистика исходов модифицированного метода критических работ
4.1.2. Статистика коллизий.
4.1.3. Эксперименты с величиной интервала масштабирования
4.1.4. Эксперименты с уровнем наличия ресурсов.
4.3. Результаты экспериментов и оценка эффективности модифицированного метода критических работ.
4.4. Выводы
Заключение.
Список использованных источников


Кроме BOINC заметными проектами являются Distributed. Parabon Computation []. Логичным требованием к подобному ППО является требование кроссплатформенности, и большинство из современных middleware ему в той или иной степени отвечают. Важнейшим для Грид-системы является выбор способа организации проведения распределенных вычислений, а также алгоритмы планирования, определяющие последовательность, стратегию и другие составляющие процесса вычислений. В следующих разделах они будут рассмотрены подробнее. Планирование вычислений в Грид-снстемах. Базовые определения. Решаемые в Грид-системах задачи относятся к таким, которые допускают декомпозицию и параллельное выполнение некоторых своих сегментов. Во избежание путаницы определим для Грид-системы такие понятия как подзадача, задание, поток заданий и задача. Подзадача (операция, англ. Иными словами — это атомарная единица работы в рассматриваемой системе. Подзадача является составной частью задания. Задание (англ. Подзадачи задания решаются с помощью одного или нескольких вычислительных узлов, которые могут обмениваться результатами друг с другом. Важным условием отличия задания от подзадачи является тот факт, что между подзадачами могут иметься информационные связи или зависимости по данным, а для выполнения всего задания необходимо выполнение всех составляющих его подзадач. В том случае, если задание не является последовательностью подзадач- (задание-очередь), будем называть его сложноструктурированным. Задания подаются в систему участниками вычислений целиком и следуют принятым спецификациям, например, некоторому формату, с помощью которого оформляется структура задания и различные его характеристики. Поток заданий - это набор заданий, поступающих в Грид-систему с течением времени. В общем случае поток считается бесконечным, а прекращается в том случае, когда система выводится из эксплуатации. Задача-это глобальная проблема, решаемая в процессе вычислений, проводящихся в Грид-системе. Общепринятым видом представления описанных понятий являются графы. Не вдаваясь на данном этапе в подробности и характеристики подзадач и заданий, определим соответствие всех их элементов и элементов графов. Потоком заданий является линейно упорядоченное множество графов й из п элементов, заданием является граф Ок={РьЕк),к=1п, где Рк — множество вершин, соответствующих подзадачам к-го задания, а Ек - множество рёбер, определяющих информационные зависимости (отношение предшествования) Л:-го задания. Под информационной зависимостью между подзадачами р, и р, понимается тот факт, что выполнение подзадачи р7 может начаться только после получения результатов выполнения подзадачи р, из-за зависимости по данным. Такие зависимости можно отобразить, если рассматривать ориентированные информационные графы. Таким образом, дуга между р, и Pj будет свидетельствовать о наличии информационной связи между подзадачами. Информационные графы являются бесконтурными, ибо наличие замкнутого пути повлечёт невозможность выполнения задания. Пример задания, представленного таким информационным графом, представлен на рис. Рис. Цифры на дугах соответствуют условному времени обмена информацией между узлами, на которых выполняются подзадачи. Для того чтобы эффективно выполнить задание необходимо оптимально распределить подзадачи между вычислительными узлами с точки зрения выбранного критерия. Данный процесс называется планированием вычислений, а критериями оптимальности планирования могут быть время или некие экономические параметры. Частью задачи планирования является задача составления расписания, общая постановка которой состоит в том, чтобы с помощью некоторого множества вычислительных узлов и вспомогательных ресурсов выполнить некую фиксированную систему операций (в данном случае задание или в большем масштабе — поток заданий). Цель - для определенных свойств операций, особенностей архитектуры и топологии, выраженных через доступные ресурсы и наложенные на них ограничения, построить оптимальное расписание при заданной мере эффективности (подробнее см.