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

• Автор: Шаповалов, Тарас Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Хабаровск
• Количество страниц: 146 с. : ил.

Оглавление
Введение

1 Планирование выполнения заданий в распределенных вы

числительных системах

1.1 Распределенные вычислительные системы

1.2 Задача планирования выполнения заданий в распределенной вычислительной системе

1.3 Алгоритм планирования выполнения заданий в распределенной вычислительной системе

2 Генетические алгоритмы составления расписаний для распределенных вычислительных систем

2.1 Методы кодирования расписаний в генетических алгоритмах

2.2 Генетические алгоритмы составления расписания для распределенной вычислительной системы

2.2.1 Форма представления расписания

2.2.2 Функция пригодности
2.2.3 Учет зависимостей между заданиями
2.2.4 Учет ресурсных ограничений
2.2.5 Создание начальной популяции
2.2.6 Оператор скрещивания
2.2.7 Оператор мутации
2.2.8 Оператор уплотнения
2.3 Параметры генетических алгоритмов
2.4 Сравнение генетического алгоритма составления расписания параллельных заданий с алгоритмом обратного заполнения
3 Практическая реализация алгоритма планирования
3.1 Реализации систем планирования запуска заданий в i . .
3.2 Система планирования Сепсиг
3.3 Компиляция, установка и настройка вепеиг
3.4 Планирование запуска заданий на вычислительных ресурсах
ВЦ ДВО РАН.
Заключение
Литература


В году Чарльз Дарвин опубликовал работу “Происхождение видов”, где были провозглашены основные принципы эволюционной теории: наследственность (потомки сохраняют свойства родителей), изменчивость (потомки почти всегда не идентичны), естественный отбор (выживают наиболее приспособленные). Первые публикации, которые впоследствии привели к идее генетических алгоритмов, принадлежат Нильсу Баричел-ли (Nils Barricelli). Его работы [-] были направлены, прежде всего, на понимание природного феномена наследственности. Основателем современной теории генетических алгоритмов считается Джон Холланд (John Holland). В его работе года [4] впервые вводится термин “генетический алгоритм” и предлагается схема классического генетического алгоритма (canonical genetic algorithm). Холланд заложил фундамент для дальнейших исследований в данной области и, в частности, для понимания основных законов функционирования эволюционных алгоритмов. Важной вехой в развитии теории ГА стала диссертация Алана Де Йонга (Alan De Jong) []. В ней проведено исследование различных аспектов ГА с помощью компьютерных экспериментов. Набор тестов для проверки эффективности работы генетических алгоритмов, предложенный Де Йонгом, является множеством задач поиска экстремумов функций от простых унимодальных до мультимодальных. Подобные наборы тестов часто применяются для отладки работы алгоритмов. В работе [] Лоренс Девис (Lawrence Davis) впервые предложил использовать ГА для поиска расписаний. В отличие от методов локального поиска [] и метода имитации отжига [,1], основанных на манипуляции одним решением, ГА использует популяцию решений, давая им большую устойчивость к преждевременной сходимости к локальным экстремумам. Для усиления данного свойства используются параллельные варианты генетических алгоритмов с несколькими подпопуляциями. Также находят применение смешанные методы, в которых ГА комбинируется с другими алгоритмами. В работе [1] исследуются сочетания генетического алгоритма с методами, основанными на эвристиках упорядочения. Данный тип эвристик определяет правила формирования списка всех заданий, устанавливающего порядок их выполнения. Использование ГА для усовершенствования эвристик в различных эвристических методах описано в [2]. Исследование алгоритмов планирования для РВС является достаточно молодым направлением. Только к концу -х — началу -х годов XX века сложилось достаточно целостное представление о границах применимости детерминированных методов теории расписаний к планированию параллельных вычислений [. В книге [1] описываются точные ресурсно-зависимые методы решения задач минимизации длины расписания в вычислительных системах. Подробное изложение вопросов составления расписаний параллельных вычислений дается в работе [5]. Там же рассматривается задача составления расписания с прерываниями и приводится описание алгоритмов решения этих задач. В работе [5] предлагается классификация систем планирования заданий в РВС и формулируются требования, предъявляемые к этим системам. Также необходимо отметить исследования в области стратегий планирования в РВС — выбор того или иного алгоритма для планирования в зависимости от наступивших событий. В работе [) предлагается использование семейств стратегий распределения ресурсов, состоящих из опорных планов, и прогнозирования освобождения ресурсов на основе моделирования действий локальных систем планирования. Помихмо минимизации времени выполнения заданий, в работе [] предлагается минимизировать вероятность нарушений в работе сети и функционировании узлов распределенной вычислительной системы. Такой подход, названный дву целевым (Ыо1^ес1пге), описывает два варианта алгоритма, в каждом из которых используются весовые характеристики для поддержания баланса между временем выполнения и вероятностью сбоев. Использование ГЛ для нахождения расписания запуска заданий с учетом задержек на передачу данных между узлами вычислительного кластера обсуждается в [2]. В [] описан ряд испытаний ГЛ и различных детерминированных методов составления расписаний.