автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Планирование выполнения заданий в распределенных вычислительных системах с применением генетических алгоритмов

На правах рукописи

4841431

Шаповалов Тарас Сергеевич

ПЛАНИРОВАНИЕ ВЫПОЛНЕНИЯ ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С ПРИМЕНЕНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Иркутск — 2011

1 4 (,;др 2011

4841431

Работа выполнена в Учреждении Российской академии наук Вычислительном центре Дальневосточного отделения РАН (ВЦ ДВО РАН).

Научный руководитель:

член-корреспондент РАН, профессор

Смагин Сергей Иванович

Официальные оппоненты: доктор технических наук, профессор

Массель Людмила Васильевна

доктор физико-математических наук, профессор

Нурминский Евгений Алексеевич

Ведущая организация:

Новосибирский государственный университет

Защита состоится 31 марта 2011 г. в 13 ч. 00 мин. на заседании Диссертационного совета Д 003.021.01 в Учреждении Российской академии наук Институте динамики систем и теории управления Сибирского отделения РАН (ИДСТУ СО РАН) по адресу: 664033, Иркутск, ул. Лермонтова, 134. *

С диссертацией можно ознакомиться в библиотеке ИДСТУ СО РАН.

Автореферат разослан 28 февраля 2011 г.

Ученый секретарь диссертационного совета

д.ф.-м.н. А.А. Щеглова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В различных сферах человеческой деятельности можно встретить множество ресурсоемких задач, требующих интенсивных вычислений. Для их решения широко применяются распределенные вычислительные системы (РВС). Примерами РВС могут служить системы, построенные по технологии Grid; Clouds Computing; системы, использующие вычислительное время простаивающих рабочих станций. С 2000 года в мире введен в эксплуатацию ряд. крупных Grid: EGEE, NorduGrid, Open Science Grid, TeraGrid и др. Проводятся исследования по распределению вычислительной работы между простаивающими рабочими станциями с использованием сети Интернет: проекты FolderêHome, GIMPS, MilkyWayÊHome и др.

Основное назначение РВС — решение ресурсоемких вычислительных задач, для которых производительности имеющихся в распоряжении ЭВМ не достаточно. В результате распределения вычислительной работы между процессорами может уменьшаться время расчета и увеличиваться точность решения. Эффективность эксплуатации РВС как среды с коллективной формой обслуживания пользователей зависит в первую очередь от алгоритма распределения ресурсов между запускаемым прикладным программным обеспечением, т.е. от алгоритма составления расписания выполнения заданий. Существенный вклад в развитие таких алгоритмов для РВС и кластерных систем внесли Топорков В.В., Коваленко В.Н., Семяч-кин Д.А., Токарев А.Н., Foster I.T., Kesselman С. и др.

В диссертационной работе исследуется применение генетических алгоритмов (ГА) к решению задачи составления расписаний выполнения заданий в РВС. Идеи ГА, интенсивно разрабатывающиеся в последние десятилетия, успешно применяются при решение различных задач оптимизации. Данный класс алгоритмов исследуется с 70-х годов XX века как в России, так и за рубежом под руководством следующих исследователей: Курейчик В.М., Скобцов Ю.А., Иванов Д.Е., Емельянов В.В., Holland J.H., Jong A.D., Goldberg D.E. и др.

Алгоритмы данного типа, будучи по природе своей стохастическими, могут находить приближенные решения NP-полных задач составления расписаний за полиномиальное время. Данное свойство становится особо важным при построении расписания для РВС с большим числом процессоров и заданий. Для ускорения нахождения субоптимального решения ГА может быть распараллелен естественным образом и скомбинирован с другими алгоритмами.

К настоящему времени нетривиальная проблема использования ГА для составления расписаний выполнения заданий в РВС изучена не достаточно. Наиболее часто для решения данной задачи находят применение алгоритм FCFS, семейство списочных алгоритмов и алгоритм обратного заполнения (Backfill), которые при определенных условиях могут уступать в эффективности составленных расписаний генетическому алгоритму. Таким

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

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

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

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

Методы исследования. В процессе исследования использовались теория расписаний и методы эволюционного поиска. При решении поставленных задач применялись также методы системного и прикладного программирования; методы объектно-ориентированного программирования; технология построения вычислительных кластеров и Grid.

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

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

Исследования по теме диссертации проводились в рамках проектов по программам ДВО РАН: "Численное моделирование физических полей в сложных средах" (№ гос. регистрации 0120.0 603766) с 2006 по 2008 гг.; "Распределенные генетические алгоритмы решения обратных задач электромагнитного зондирования"; "Распределенные информационные вычислительные системы для комплексных научных исследований" (№ гос. регистрации 0120.0 603769) с 2006 по 2008 гг.; "Организация работы вычислительного кластера в режиме удаленного доступа" и 'Тазвитие системного программного обеспечения вычислительного кластера", а также в рамках федеральной целевой программы "Научные и научно-педагогические кад-

ры инновационной России" (проект № 02.740.11.0626) и грантов ДВО РАН № 09-1-П1-01 и № 10-Ш-В-01И-009.

Соответствие диссертации паспорту научной специальности. В соответствии с паспортом специальности 05.13.11 в диссертации были разработаны алгоритмы для организации глобально распределенной обработки данных в РВС и проведено их исследование (п. 9 области исследований).

Апробация работы. Результаты работы докладывались и обсуждались на Всероссийской научной конференции "Научный сервис в сети интернет: многоядерный компьютерный мир. 15 лет РФФИ" (Новороссийск, 24 сентября - 29 сентября 2007 г.), Межрегиональной научно-практической конференции "Информационные и коммуникационные технологии в образовании и научной деятельности" (Хабаровск, 21 мая -23 мая 2008 г.), Международной научной конференции "Распределенные вычисления и Grid-технологии в науке и образовании" (Дубна, 30 июня -

4 июля 2008 г.), Региональной научной конференции "XXXIII Дальневосточная математическая школа-семинар имени академика Е.В. Болотова" (Владивосток, 29 августа - 4 сентября 2008 г.), Международной научной конференции "Параллельные вычислительные технологии" (Санкт-Петербург, 28 января - 1 февраля 2008 г.), Региональной научной конференции "XXXIV Дальневосточная математическая школа-семинар имепи академика Е.В. Золотова" (Хабаровск, 25 июня - 30 июня 2009 г.), Межрегиональной научно-практической конференции "Информационные и коммуникационные технологии в образовании и научной деятельности" (Хабаровск, 21 сентября - 23 сентября 2009 г.), XI Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Иркутск, 15 марта - 21 марта 2010 г.), Международной научно-практической конференции "Суперкомпьютеры: вычислительные и информационные системы" (Хабаровск, 30 июня - 2 июля 2010 г.), Региональной научной конференции "XXXV Дальневосточная математическая школа-семинар имени академика Е.В. Золотова" (Владивосток, 31 августа -

5 сентября 2010 г.), Международной научной конференции "First Russia and Pacific Conference on Computer Technology and Applications" (Владивосток,

6 сентября - 9 сентября 2010 г.), а также неоднократно на семинарах Вычислительного центра ДВО РАН.

Публикации и личный вклад. По материалам диссертации опубликовано 19 печатных работ, в том числе две статьи [1, 2] в журналах, рекомендованных ВАК РФ.

Автором сформулированы задачи составления расписаний и непрерывного планирования выполнения заданий в РВС, разработаны и реализованы алгоритмы планирования выполнения параллельных и непараллельных заданий в РВС, разработаны генетические операторы, учитывающие ограничения, налагаемые на расписания выполнения заданий в РВС. Из совместных работ с Пересветовым В.В., Сапроновым А.Ю., Смаги-ным С.И., Тарасовым А.Г. и Щербой С.И. на защиту выносятся только

результаты, полученные автором лично.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы из 170 наименований, глоссария и приложений. Общий объем диссертации составляет 146 страниц, из которых 126 страниц основного текста, включающего 36 рисунков и две таблицы. Результаты главы 1 опубликованы в работах [1, 7, 11, 15]. Результаты главы 2 опубликованы в [1, 2, 5, 14, 15, 18]. Результаты главы 3 опубликованы в [4, 6, 8-10, 12, 13, 16, 17, 19].

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

Разделим отрезок времени Т, в течение которого поступают задания пользователей, п& + 1 последовательных отрезков (периодов) планирования: Т — итд. гДе Я ~ порядковый номер периода планирования, д = 0,1,..., <5- В каждый из периодов Тч накапливается некоторое количество заданий. Каждое задание включает в себя запрос на выполнение одного или нескольких процессов.

Пусть ид = {щд : г — 1,2,..., Л/,} — множество процессов, принадлежащих заданиям, планируемым в период Тя, где Ич — число процессов, принадлежащих всем заданиям, планируемым в период Г,,.

Пусть Ф = {фт : т 6 М} — неизменяемое в течение всего отрезка времени Т множество всех виртуальных узлов в РВС, где М — множество номеров всех виртуальных узлов в РВС. Под вычислительным узлом (ВУ) понимается один вычислительный элемент (процессор или одно вычислительное ядро процессора), рассматриваемый в связке с соответствующими ему ресурсами. Тогда расписание выполнения процессов щч е ид, планируемых в период Тд в РВС, определяется как множество отрезков времени {слотов) вгтд, зарезервированных для выполнения этих процессов на ВУ

Фт € Ф:

= {в.т? = ге1д, те Мч} , (1)

где 1Ч — множество номеров процессов, которые будут выполняться в РВС

согласно расписанию а Мч — множество номеров ВУ, па которых данные процессы будут запущены.

Обозначим через г?тч величину, характеризующую ресурс с номером е, которую пользователь заказывает для выполнения процесса щч на некотором ВУ фт. Например, величина г°т?, относящаяся к оперативной памяти, обозначает требуемый на ВУ фт объем данной памяти, а величина, относящаяся к программному обеспечению, отражает наличие (г*тд = 1) или отсутствие (г®т? = 0) данного программного обеспечения на ВУ фт.

Величину, характеризующую ресурс с номером е, который доступен ВУ фт е Ф в момент времени £ е 7\ обозначим через Тогда ре-

сурсы, доступные для ВУ фт в этот момент времени, характеризуются множеством : е = 1,2,..., Л'г}, где е — номер ресурса, Лгг — число

различных видов ресурсов в РВС.

Расписание заданий для РВС является допустимым, если выполняются условия достаточности имеющихся ресурсов для их выполнения:

е Угб/9, Уш 6 Мя, е = 1,2,...,ЛГг. (2)

Под непротиворечивостью расписания 5, понимается выполнение следующих условий.

1. Каждому процессу из множества IIч, который может быть запущен в РВС, должен быть сопоставлен один слот в расписании 5д. Пусть Щ — число слотов в расписании соответствующих планируемым в период Тя процессам, Л^ — число процессов всех заданий, планируемых в период Тд, которые могут выполняться в РВС. Тогда должно быть справедливо равенство N¡¡ =

2. Никакие два слота з,т? 6 5г и £ (г ф _;') не должны быть сопоставлены одному ВУ одновременно: |~) = 0, где | ■ | — длина соответствующего отрезка времени.

Для составления расписания параллельных заданий также необходимо брать в расчет еще два условия непротиворечивости. Для описания данных условий дополнительно введем разбиение множества Ф всех ВУ в РВС на непересекающиеся подмножества Фд = {фт : т £ Мд} — группы ВУ:

лг„

ф = уфг, Ф,р)Фр = 0, д,р = 1,2,..., дфр, (3)

где Ид — количество групп ВУ в РВС, Мд — множество номеров ВУ, принадлежащих группе Ф9.

Пусть ип -- {щд : г £ /и} — множество процессов, принадлежащих р-му заданию, поступившему в период Т„ где 1М — множество номеров

процессов этого задания. При этом

р,

(J U„ = U4, i/,?f)i/M = 0, Z,p=l,2,...,P„ (4)

р=1

где Рд — количество заданий, поступивших в период планирования Тч.

Тогда дополнительные условия непротиворечивости раписания Sq выполнения процессов, принадлежащих параллельным заданиям следующие.

3. Все процессы параллельного задания должны быть спланированы на выполнение в пределах одной группы ВУ. Пусть Мд — множество ВУ д-й группы, тогда в расписании Sq для каждого слота Simg, сопоставленного с i-м процессом из множества должно выполняться условие тп 6 Мд.

4. Все процессы параллельного задания должны иметь одинаковый момент времени запуска и завершения. Для всех i,j € Npq в расписании Sq должно выполняться равенство simq = Sjkq, т,к € Mq. Слотам Simq и Sjkq соответствуют процессы одного параллельного задания.

В большинстве случаев для одного множества процессов Uq можно составить множество расписаний Sq = {SQ? : а € A!q}, где A!q — множество номеров всех возможных расписаний для процессов из множества Uq.

В процессе планирования для номера периода планирования q ф О расписания Saq £ Sq должны удовлетворять условию сопряжения. Пусть длина Taijq отрезка времени ожидания всех ВУ в РВС между завершением слотов расписания и началом слотов расписания Saq задается следующим образом:

VmeM,

где tmaq — момент времени начала выполнения первого слота в расписании Saq на ВУ фт, a im/3(?-i) — момент времени завершения выполнения последнего слота в расписании S/?(g-i) на ВУ фт; а Е A'q, /3 € Тогда расписание S* 6 Saq будет удовлетворять условию сопряжения с расписанием Sp(q-. 1), если

Tpq = rmnTa0q. (5)

а£А'я

Пусть Sq С Sq — подмножество расписаний, удовлетворяющих условию сопряжения. Введем для расписаний Saq € Sq целевую функцию / : Sq —» R+, где Д+ — множество действительных положительных чисел. Оптимальным будем считать расписание S* G Sq, удовлетворяющее условию

/(SJ) = min/(5a,).

В связи с тем, что задача составления расписания в общем случае является МР-полной, на практике приходится ограничиваться поиском субоптимального решения.

Задача планирования состоит в нахождении для каждого периода планирования Тч субоптималыюго расписания вида (1) выполнения процессов щ 6 ич. При этом должно удовлетворять условиям ресурсных ограничений (2), условию сопряжения (5), а также условиям непротиворечивости 1-2 (для непараллельных заданий) или 1-4 (для параллельных заданий).

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

где Ма — множество номеров ВУ, которым сопоставлены слоты из расписания Sq, Ima — множество номеров слотов, сопоставленных с ВУ фт\ G — число всех виртуальных узлов в РВС; ¡simil| — длина слота slma 6 £а; Кта — вес процесса tij при запуске его на ВУ фт. Вес Ajma процесса щ на ВУ фт необходим для учета его приоритета: А¡ma = (Pia)dima, где р,а — приоритет процесса u,-, d,rm, — порядковый номер следования слота stma на ВУ фт согласно расписанию 5а.

___Нет

Выбор лучшего расписания Sq га найденных

Да

Рис. 1: Схема планирования заданий в распределенной вычислительной системе

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

Вторая глава посвящена алгоритмам составления расписаний в распределенных вычислительных системах с применением генетических алгоритмов. Описываются принципы применения генетических алгоритмов для составления расписаний. Указываюся основные проблемы, возникающие при использовании ГА в решении данной задачи. После этого детально излагаются разработанные автором генетические алгоритмы составления допустимых непротиворечивых субоптимальных расписаний выполнения параллельных и непараллельных заданий в РВС; описываются разработанные генетические операторы, механизм учета ресурсных ограничений, налагаемых на расписания, а также механизм учета в генетических операторах зависимостей между заданиями.

Рис. 2: Схема разработанных генетических алгоритмов составления расписаний выполнения заданий для РВС

На рис. 2 представлена объединенная схема разработанных генетических алгоритмов составления расписаний выполнения как непараллельных, так и параллельных заданий. Пунктиром обозначен оператор уплот-

нения, используемый только в случае с параллельными заданиями.

Каждое расписание Sa в ГА должно быть закодировано в форме хромосомы Х„ € X, где X — множество хромосом одной популяции. Автор предлагает выносить номера ВУ за пределы области кодирования слотов в отдельный вектор Х'а ("заголовок" хромосомы). Каждый элемент данного вектора сеть число Nma слотов на ВУ фт. Тогда сами слоты будут описываться кортежами < г, |s¡ma| > и храниться во второй части хромосомы — в векторе X" ("тело" хромосомы). Таким образом, Х'а = {iV„la}, X'á = {< г, |smlo| >}, а вся хромосома Ха =< Х'а, X'¿ >.

Автором разработан механизм учета зависимостей между заданиями. Если г-е задание зависит от j-ro, то должно выполняться условие

tima > (jma + ¡Sjmal, СДб (¿та 11 tjma — МОМеНТЫ ВрСМСПИ запуска COOT-

ветствующих заданий, | s]ma | — длительность выполнения процесса j-ro задания на ВУ фт € Ф, т е Ма, Ма — множество номеров ВУ, которым соответствуют слоты в расписании, кодируемом хромосомой Ха, i,j е /а, 1а — множество номеров слотов в хромосоме Ха. Для учета зависимостей между заданиями при мутации необходимо соблюдать коридор допустимых значений для отрезка времени выполнения процессов г-го задания в расписании, кодируемом хромосомой Ха: [tj¡¡£,

Важной задачей при применении ГА к составлению расписания для РВС является разработка механизма учета ресурсных ограничений. Под ресурсными ограничениями понимаются правила, определяющие возможность процесса выполняться на данйом ВУ. Автором предлагается использовать дополнительную структуру данных (маску ресурсов), представляющую собой булев вектор Bla = {6¡ma}. В результате создания маски ресурсов элементы 6¡ma € B¡a устанавливают возможность запуска процесса «i 6 (7, которому соответствует слот s¿ma, на ВУ фт е Ф. Маска ресурсов генерируется для каждого задания перед началом новой итерации ГА и не меняется на всем протяжении этой итерации.

Алгоритм создания хромосомы Ха начальной популяции при поиске расписания непараллельных заданий совпадает с алгоритмом FCFS с одним отличием: при выборе очередного ВУ необходимо использовать маску ресурсов. Для иоиска расписания параллельных заданий в начальную популяцию включаются расписания, составленные модифицированным автором алгоритмом обратного заполнения (Backfill).

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

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

Точки разрыва

Первая родительская хромосома

х> \з k k

I SéJ S7J

KU ^11.3 « о

S 1 « s-

Вторая родительская хромосома Рис. 3: Схема скрещивания двух хромосом

масштабируются в соответствии с формулой

i^irnoj ~ |^гЛа| j lim

где Kh и кт — коэффициенты производительности процессоров, которые соответствуют ВУ фь и фт. Такой вариант вычисления длины слота имеет смысл, если все процессоры в Grid принадлежат одному семейству (например, все — Xeon серий 5ххх). В противном случае более точные значения длин слотов можно получить заранее, производя запуск прикладного программного обеспечения при согласованных в пределах Grid "стандартных" параметрах на тех сайтах, где оно установлено, вычисляя коэффициенты ускорения для алгоритма заранее.

Для составления расписания параллельных заданий в операторе мутации для обмена выбираются не отдельные слоты, а множества слотов двух заданий. В случае, когда новое расположение слота занято другим слотом и время начала выполнения процессов, соответствующих данным слотам, совпадает, происходит смещение расписания, как показано на рис. 4. Здесь t' — время начала слота S2iQ на ВУ ф^

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

Проведены численные эксперименты с целью настройки основных параметров: вероятности применения оператора мутации рт, вероятности применения оператора скрещивания рс, размера популяции Z и процента элитных хромосом Е. Установлено, что при составлении расписания непараллельных заданий ГА достигал максимального ускорения при следую-

Рис. 4: Схема сдвига части расписания до (а) и после (б) перемещения слота оператором мутации

щих параметрах: рт га 0.032%, рс га 30%, Е га 10%, Z га 40 - 60, а в случае с параллельными заданиями рт га 0.065%, рс га 30%, Е га 10%, Z га 20 - 30.

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

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

Система планирования имеет клиент-серверную архитектуру. Grid-инструментарий Globus Toolkit предоставляет программный интерфейс к своим компонентам, что позволило интегрировать разработанную систему планирования в инфраструктуру Grid. На рис. 5 показана схема взаимодействия системы планирования с Grid-службами в процессе поиска и выполнения расписаний.

Проведены испытания системы планирования на кластерах Вычислительного центра ДВО РАН, которые показали, что использование генетического алгоритма составления расписания вместо алгоритма обратного заполнения целесообразно при числе процессов в расписании больше 128. Также эксперименты показали, что для РВС, состоящей из вычислительных кластеров ВЦ ДВО РАН, ГА имеет полиномиальную сложность от размерности задачи составления расписания D первой степени. Здесь

Geneur

Модуль ]

ц1

расилсаяйя j ; II Пул

; 1 заданий

Г* А.

; Слой ^взаимодействия-; с Grid •;

i Globus Toolkit:

• t .

Менеджер

запуска Задания

заданий

. . ■■ ;; /

Менеджер Файлы

доставки

файлов Фэйлм

X

GridFTP

1

vC^I—);

Менеджер ресурсов

Г/^gram)

Рис. 5: Схема взаимодействия разработанной системы планирования и Grid через промежуточный программный слой

В = И/С, где N — число вычислительных процессов всех заданий в расписании, а С — число доступных для планирования ВУ.

Рис. б: Время Тр решения задачи составления расписания в зависимости от размерности X) для генетического алгоритма составления расписания непараллельных задапий

Сплошной линией на рис. 6 обозначена зависимость времени решения Тр от размерности О задачи составления расписания непараллельных заданий, а пунктирной — аппроксимирующая линейная функция Тр = 180/) — 130, по которой видно, что сложность алгоритма является линейной функцией от размерности задачи — 0{Б). Аналогичная зависимость показана для генетического алгоритма составления расписания параллельных заданий на рис. 7.

На рис. 8 представлена зависимость коэффициента ускорения кр от

550 -450 -и 350 -

2 4 б 8 10 12 14 Д

Рис. 7: Время Тр решения задачи составления расписания в зависимости от размерности И для генетического алгоритма составления расписания параллельных заданий

Р

Рис. 8: Коэффициент ускорения кр решения задачи в зависимости от числа Р параллельных подпопулхциВ

числа Р параллельных подполуляций в случае с непараллельными (А1) и параллельными (А2) заданиями. Коэффициент ускорения в данном случае вычисляется по формуле кр — Т\/Тр, где Т\ — время непараллельного поиска расписания, а Тр — время поиска для Р вычислительных модулей в системе. Число 1т поколений изоляции — это число поколений ГА, проходящее до обмена найденными решениями между подпопуляциями.

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

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

Приложения включают основные понятия теории генетических алгоритмов, примеры конфигурационных файлов разработанной системы планирования, а также описание программного обеспечения, используемого на ресурсах Вычислительного центра ДВО РАН.

200 180 160 ü 140 ^ 120 100 80 60

25 50 75 100 125 150 175 200 225 250 275 300 L

Рис. 9: Время Tp решения задачи составления расписания в зависимости от числа поколений изоляции /т

РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

1. Разработаны генетические алгоритмы для составления расписаний выполнения непараллельных и параллельных заданий в распределенной вычислительной системе. Алгоритмы позволяют сохранять непротиворечивость расписаний и учитывать одиночные зависимости между заданиями.

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Смагип С.И., Шаповалов Т.С. Генетический алгоритм составления расписания выполнения параллельных заданий в распределенной вычислительной системе // Выч. технологии. — 2010. — Т. 15, № 5. — С. 41-59.

2. Шаповалов Т.С. Генетический алгоритм составления расписания запуска параллельных заданий в Grid // Информатика и системы управления. - 2010. - Т. 4, № 26. - С. 115-126.

3. Шаповалов Т.С., Пересветов В.В. Генетический алгоритм составления расписаний для распределенных гетерогенных вычислительных

систем // Выч. методы и программирование. — 2009. — Т. 10, № 1. — С. 159-167.

4. Пересветов В.В., Сапронов А.Ю., Тарасов А.Г., Шаповалов Т.С. Удаленный доступ к вычислительному кластеру ВЦ ДВО РАН // Выч. технологии. — 2006. — Т. 11, спец. вып. — С. 45-51.

5. Shapovalov T.S., Tarasov A.G. Genetic Algorithm Based Parallel Jobs Scheduling // Proc. of First Russia and Pacific Conf. on Computer Technology and Applications (Vladivostok, from 6th to 9th of September, 2010). - Vladivostok: IACP FEB RAS, 2010. - P. 211-216.

6. Шаповалов Т.С. Эффективность системы планирования, основанной на генетическом алгоритме, для распределенных гетерогенных вычислительных систем // Материалы Межрегион, науч.-нракт. конф. "Информационные и коммуникационные технологии в образовании и научной деятельности" (Хабаровск, 21-23 сентября 2009 г.). — Хабаровск: ТОГУ, 2009. - С. 352-358.

7. Шаповалов. Т.С. О диспетчеризации заданий в распределенных вычислительных средах // Материалы Межрегион, конф. "Информационные и коммуникационные технологии в образовании и научной деятельности" (Хабаровск, 21-23 мая 2008 г.). — Хабаровск: ТОГУ, 2008. - С. 356-362.

8. Шаповалов Т.С. Об интеграции диспетчера заданий в Grid-инструментарий Globus Toolkit. // Материалы XXXV Дальневосточной мат. школы-ссминара им. акад. Б.В. Золотова (Владивосток, 31 августа - 5 сентября 2010 г.). — Владивосток: ИАПУ ДВО РАН, 2010. - С. 904-907.

9. Тарасов А.Г., Шаповалов Т.С., Мальковский С.И. Интеграция вычислительных ресурсов ТОГУ и ВЦ ДВО РАН с применением Grid-технологий // Материалы Междунар. науч.-нракт. конф. "Суперкомпьютеры: вычислительные и информационные технологии" (Хабаровск, 30 июня - 2 июля 2010 г.). - Хабаровск: ТОГУ, 2010. - С. 133138.

10. Шаповалов Т.С. Система планирования выполнения заданий в Grid, основанная на составлении расписаний генетическим алгоритмом // Материалы Междунар. науч.-нракт. конф. "Суперкомпьютеры: вычислительные и информационные технологии" (Хабаровск, 30 июня -2 июля 2010 г.). - Хабаровск: ТОГУ, 2010. - С. 151-153.

11. Шаповалов Т.С., Сапронов A.IO. О методах планирования заданий в Grid // Тр. Третьей междунар. конф. "Распределенные вычисления и Grid-технологии в науке и образовании" (Дубна, 30 июня - 4 июля 2008 г.). - Дубна: ОИЯИ, 2008. - С. 307-309.

12. Шаповалов Т.С., Пересветов В.В., Сапронов А.Ю., Смагин С.И., Тарасов А.Г. Web и Grid технологии обеспечения доступа к ресурсам вычислительного кластера ВЦ ДВО РАН // Материалы Межрегион.

конф. "Информационные и коммуникационные технологии в образовании и научной деятельности" (Хабаровск, 21-23 мая 2008 г.). — Хабаровск: ТОГУ, 2008. - С. 69-76.

13. Шаповалов Т.С. Проект метапланировщика в Grid для Globus Toolkit на базе генетических алгоритмов // Материалы Всерос. конф. "Современные информационные технологии для научных исследований" (Магадан, 20-24 апреля 2008 г.). - Магадан: СВНЦ ДВО РАН, 2008. - С. 86-87.

14. Шаповалов Т.С. Применение генетических алгоритмов для поиска оптимального расписания заданий в Grid // Тр. Между-нар. конф. "Параллельные вычислительные технологии" (Санкт-Петербург, 28 января - 1 февраля 2008 г.). — Челябинск: ЮУрГУ, 2008. - С. 500-505.

15. Шаповалов Т.С. Параллельный алгоритм планирования заданий для распределенных гетерогенных вычислительных систем. — Хабаровск, 2006. - 31 с. - (Препринт / ВЦ ДВО РАН; № 134).

16. Пересветов В.В., Сапронов А.Ю., Тарасов А.Г., Шаповалов Т.С. Организация работы вычислительного кластера в режиме удаленного доступа. - Хабаровск, 2007. - 34 с. - (Препринт / ВЦ ДВО РАН; № 110).

17. Шаповалов Т.С., Тарасов А.Г., Щерба С.И. Организация Grid-сети ДВО РАН // Всерос. науч. конф. "Научный сервис в сети интернет: многоядерный компьютерный мир. 15 лет РФФИ" (Новороссийск, 2429 сентября 2007 г.). - М.: МГУ, 2007. - С. 94.

18. Шаповалов Т.С. Об учете ограничений на составление расписания заданий в Grid с использованием генетических алгоритмов // Тр. IX Всерос. конф. молодых ученых по мат. моделированию и информ. технологиям (Кемерово, 28-30 октября 2008 г.). — Кемерово: ИВТ СО РАН, 2008. - С. 97-98.

19. Шаповалов Т.С. Параллельный алгоритм планирования заданий для распределенных гетерогенных вычислительных систем. Geneur: Свидетельство об официальной регистрации программы для ЭВМ № 2009612081. - М.: ФГУ ФИПС, 2009.

Редакционно-издательский отдел Учреждения Российской академии наук Института динамики систем и теории управления СО РАН 664033, Иркутск, ул. Лермонтова, д. 134

Подписано к печати 25.02.2011 г. Формат бумаги 60 x 84 1/16, объем 1,2 п.л. Заказ № 2. Тираж 100 экз.

Отпечатано в ИДСТУ СО РАН

Введение

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 Реализации систем планирования запуска заданий в Grid

3.2 Система планирования Geneur.

3.3 Компиляция, установка и настройка Geneur

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

ВЦ ДВО РАН.

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

Примерами РВС могут служить системы, интегрирующие вычислительные ресурсы высокой производительности (построенные по технологии Grid) [29,85,86]; Clouds Computing [65,120]; системы, использующие процессорное время простаивающих рабочих станций [35,101]. С начала 2000 года в мире введены в эксплуатацию ряд крупных Grid: EGEE1, NorduGrid2, Open Science Grid3, TeraGrid4 и другие [28]. Ведутся проекты по распределению вычислительной работы между простаивающими рабочими станциями с использованием сети Интернет: Folder@Home (исследование сворачивания белков); GIMPS (поиск простых чисел Мерсенна); Milky Way@Home (создание трёхмерной динамической модели звёздных потоков в нашей галактике) и другие5.

Основное назначение РВС — решение ресурсоемких вычислительных задач, для которых производительности имеющихся в распоряжении ЭВМ недостаточно. В результате распределения вычислительной работы по узлам может уменьшаться время расчета и увеличиваться точность решения. Эффективность эксплуатации РВС напрямую зависит от методов планирования выполнения заданий, включающих последовательное нахождение http: //www.eu-egee.org

2http://www.nordugrid.org

3http://www.opensciencegrid.org http://www.teragrid.org shttp://distributed.ru связанных расписаний выполнения заданий.

В общем случае, задача составления расписания является ТУР-полной [13, 95]. Ссылки на исследования АГР-полных задач, формулировки которых близки к формулировкам задач составления расписаний, имеются в [107].

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

Метод критического пути — точный метод составления ресурсно-независимых расписаний для заданий с заранее известными длительностями. Он дает кратчайшую длину расписания при условии неограниченности ресурсов. В классическом варианте данный метод далек от практического применения в РВС. Исследования стохастической [128] и динамической [64] модификаций этого метода, содержащих вероятностные предположения о длительности заданий, делают его более практичным.

Множество задач составления расписаний можно сформулировать в терминах линейного или целочисленного программирования, но при условии сильного упрощения постановок задач [131]. Необходимо отметить метод ветвей и границ [116], адаптированный в различных формах для составления расписаний [108,117,123]. Данные методы привязаны к целевой функции и специфике ограничений на расписания. В работе [77] показывается, что большинство ограничений, которые содержатся в реальных задачах составления расписаний, плохо подходят для традиционных методов линейного и целочисленного программирования и могут применяться лишь к ограниченному кругу подобных задач.

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

Эвристические методы также широко используются при решении задач планирования. В этом случае эвристики трактуются как правила планирования. Данный вид эвристик, оперируя множеством заданий, устанавливает порядок их выполнения. Если задание можно сопоставить с различными исполнителями, то эвристика должна их указать. В работе [132] приводится обзор ряда эвристик для задач планирования. В [79] сравниваются восемь эвристик на множестве однотипных задач составления ресурсо-зависимых расписаний. В [80] сравниваются алгоритмы, основанные на эвристиках, с алгоритмами, основанными на методе ограниченного перебора. Результаты сравнения показали, что алгоритмы, основанные на эвристиках, плохо приспособлены для ситуаций, в которых ресурсы сильно ограничены.

Применению эвристических правил в алгоритмах планирования посвящены публикации [66,99,131,139]. Находят применение методы решения задач планирования, использующие экспертные и основанные на знаниях (knowledge-based) системы [89,103,138,142]. Каждый набор экспертных правил детально прорабатывается под ту или иную задачу, поэтому алгоритмы данной группы являются узкоспециализированными. Системы, основанные на знаниях, обычно делят задачу на подзадачи, решением которых занимаются подпрограммы-агенты. Вопросы динамического планирования, когда расписание может быть составлено повторно уже после запуска заданий, рассматриваются в работе [4].

Также ведутся исследования по составлению расписаний в мультипроцессорных вычислительных средах с помощью решения систем булевых уравнений, описывающих ресурсные ограничения [7]. Из преимуществ данного подхода молено отметить то, что он позволяет учитывать различные ограничения, предъявляемые к расписанию, а также использовать существующие эффективные решатели булевых уравнений (SAT-решатели). Однако применение SAT-решателей требует приведения булевых функций общего вида к дизъюнктивной нормальной форме, что, как правило, является трудной задачей в классической постановке [6].

При планировании заданий в РВС в основном используются: алгоритм FCFS, списочный алгоритм и алгоритм обратного заполнения. Алгоритм FCFS (First Come First Serve) — простой и хорошо изученный алгоритм. Задания выстраиваются в список согласно порядку их поступления. Как только необходимое количество вычислительных ресурсов становится доступным заданию, которое находится в начале списка, оно запускается. Данный метод имеет следующие преимущества: нет необходимости в информации о длительности выполнения заданий, алгоритм прост в реализации и не требует больших вычислительных затрат.

В ряде случаев с помощью данного алгоритма можно получать удовлетворительные расписания [140]. Тем не менее FCFS может приводить к появлению большого числа простаивающих процессоров, если в очереди находится множество параллельных заданий с большим числом процессов [159]. Часто на практике FCFS дополняется модификацией алгоритма обратного заполнения.

Списочный алгоритм [94] подразумевает составление списка заданий согласно некоторому множеству эвристик планирования. Затем происходит запуск очередного задания из списка, как только необходимое количество ресурсов становится доступным. В работе [100] приводятся результаты исследований нескольких эвристик планирования. Как и FCFS, списочные алгоритмы не требуют предварительной информации о длительности выполнения заданий.

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

• Позволяет составлять расписания для гетерогенных РВС.

• Избегает зависания низкоприоритетных заданий в очередях, гарантируя их запуск.

• Может составлять достаточно плотные по времени расписания.

• Обладает приемлемыми характеристиками скорости работы. Основные шаги алгоритма обратного заполнения следующие.

1. Выяснение, какие процессоры и на какое время будут свободны.

2. Свободные отрезки времени с одним началом объединяются в окна.

3. Из всех окон выбирается самое широкое.

4. Среди оставшихся заданий выбирается наиболее точно удовлетворяющее данному окну задание и планируется на запуск в начале выбранного окна.

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

Одной из популярных систем планирования для вычислительных кластеров является Maui. В ее состав входит алгоритм обратного заполнения [110]. Этот алгоритм также задействован во многих других планировщиках [124,136,151,169,170]. Подробнее с данным алгоритмом можно ознакомиться в работе [34]. Построение архитектуры систем планирования для Grid, а также детальное сравнение основных алгоритмов планирования обсуждаются в работе [165].

Генетические алгоритмы (ГА). Предпосылкой возникновения ГА стали несколько открытий в биологии. В 1859 году Чарльз Дарвин опубликовал работу "Происхождение видов", где были провозглашены основные принципы эволюционной теории: наследственность (потомки сохраняют свойства родителей), изменчивость (потомки почти всегда не идентичны), естественный отбор (выживают наиболее приспособленные). Тем самым было показано, какие механизмы могут приводить к эволюционному развитию флоры и фауны. Первые публикации, которые впоследствии привели к идее генетических алгоритмов, принадлежат Нильсу Баричел-ли (Nils Barricelli). Его работы [59-61] были направлены, прежде всего, на понимание природного феномена наследственности.

Основателем современной теории генетических алгоритмов считается Джон Холланд (John Holland). В его работе 1975 года [104] впервые вводится термин "генетический алгоритм" и предлагается схема классического генетического алгоритма (canonical genetic algorithm). Холланд заложил фундамент для дальнейших исследований в данной области и, в частности, для понимания основных законов функционирования эволюционных алгоритмов.

Важной вехой в развитии теории ГА стала диссертация Алана Де Йонга (Alan De Jong) [81]. В ней проведено исследование различных аспектов ГА с помощью компьютерных экспериментов. Набор тестов для проверки эффективности работы генетических алгоритмов, предложенный Де Йонгом, является множеством задач поиска экстремумов функций от простых унимодальных до мультимодальных. Подобные наборы тестов часто применяются для отладки работы алгоритмов.

В работе [77] Лоренс Девис (Lawrence Davis) впервые предложил использовать ГА для поиска расписаний. В отличие от методов локального поиска [17] и метода имитации отжига [52,111], основанных на манипуляции одним решением, ГА использует популяцию решений, давая им большую устойчивость к преждевременной сходимости к локальным экстремумам. Для усиления данного свойства используются параллельные варианты генетических алгоритмов с несколькими подпопуляциями.

Также находят применение смешанные методы, в которых ГА комбинируется с другими алгоритмами. В работе [141] исследуются сочетания генетического алгоритма с методами, основанными на эвристиках упорядочения. Данный тип эвристик определяет правила формирования списка всех заданий, устанавливающего порядок их выполнения. Использование ГА для усовершенствования эвристик в различных эвристических методах описано в [102]. Ведутся исследования по объединению математического аппарата нечеткой логики с генетическими алгоритмами для планирования выполнения заданий [93], где с помощью нечеткой логики происходит динамическая настройка значений вероятности применения генетических операторов.

Исследование алгоритмов планирования для РВС является достаточно молодым направлением. Только к концу 70-х — началу 80-х годов XX века сложилось достаточно целостное представление о границах применимости детерминированных методов теории расписаний к планированию параллельных вычислений [14,21-23,31,34,70,105,106,161].

В книге [1] описываются точные ресурсно-зависимые методы решения задач минимизации длины расписания в вычислительных системах. Подробное изложение вопросов составления расписаний параллельных вычислений дается в работе [5]. Там же рассматривается задача составления расписания с прерываниями и приводится описание алгоритмов решения этих задач. В работе [135] предлагается классификация систем планирования заданий в РВС и формулируются требования, предъявляемые к этим системам.

Также необходимо отметить исследования в области стратегий планирования в РВС — выбор того или иного алгоритма для планирования в зависимости от наступивших событий. В работе [34] предлагается использование семейств стратегий распределения ресурсов, состоящих из опорных планов, и прогнозирования освобождения ресурсов на основе моделирования действий локальных систем планирования.

Помимо минимизации времени выполнения заданий, в работе [54] предлагается минимизировать вероятность нарушений в работе сети и функционировании узлов распределенной вычислительной системы. Такой подход, названный двуцелевым (biobjective), описывает два варианта алгоритма, в каждом из которых используются весовые характеристики для поддержания баланса между временем выполнения и вероятностью сбоев.

Использование ГА для нахождения расписания запуска заданий с учетом задержек на передачу данных между узлами вычислительного кластера обсуждается в [122]. В [55] описан ряд испытаний ГА и различных детерминированных методов составления расписаний. Они показали, что использование генетических алгоритмов вместо детерминированных способно повысить эффективность эксплуатации вычислительного кластера.

Ведутся исследования по введению принципов экономики при распределении ресурсов в РВС между заданиями [72]. В этом случае определяется стоимость ресурсов и бюджет владельцев заданий. Затем происходит регуляция баланса между стоимостью и предложением. Введение стоимости выполнения задания мотивирует их владельцев "тратить" свой бюджет, подбирая оптимальный для них баланс между временем завершения расчетов и размером бюджета.

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

1. Разработка и исследование генетических алгоритмов для составления расписаний выполнения непараллельных и параллельных заданий в РВС.

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

3. Программная реализация системы планирования выполнения заданий в РВС типа Grid.

Объектом исследования служит теория и практика организации распределенных вычислений.

Предметом исследования являются методы планирования заданий в РВС.

Методы исследования. В процессе исследования использовались теория расписаний и методы эволюционного поиска. При решении поставленных задач применялись также методы системного и прикладного программирования; методы объектно-ориентированного программирования; технология построения вычислительных кластеров и Grid.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы из 170 наименований, глоссария и приложений. Объём работы (за исключением глоссария и приложений) составляет 126 страниц в формате машинописного текста, в том числе 36 рисунков и две таблицы.

Заключение

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

Сформулируем основные результаты диссертации.

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

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

3. Разработана и программно реализована система планирования выполнения заданий в РВС типа Grid, основанная на разработанных автором алгоритмах. Данный программный комплекс спроектирован с учетом возможности составления расписаний одновременно на множестве вычислительных узлов в сети. Эксперименты над данной системой планирования показали, что рост скорости нахождения одного субоптимального расписания не меняется с увеличением числа вычислительных узлов. Испытания для различных конфигураций РВС и числа процессов показали, что при числе процессов больше числа ВУ наблюдается выигрыш от использования ГА по сравнению с алгоритмом обратного заполнения. Проведены испытания данной системы планирования для конфигурации РВС, соответствующей вычислительным ресурсам ВЦ ДВО РАН. Численные эксперименты показали целесообразность ее применения.

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

1. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация / А.Б. Барский. — М.: Радио и связь,1990. 256 с.

2. Бурцев B.C. Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ / B.C. Бурцев. М.: ИВВС РАН, 1997. - 152 с.

3. Воеводин В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. СПб.: БХВ-Петербург, 2002. - 608 с.

4. Гершуни Д.С. Планирование вычислений в системах жесткого реального времени (обзор и перспективы). Выч. техника. Системы управления.1991. В.6 С. 4-51.

5. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов / Б.А. Головкин. — М.: Радио и связь, 1983. 272 с.

6. Журавлев Ю.И. Об экономном умножении булевых уравнений / Ю.И. Журавлев, И.М. Платоненко // ЖВМ и МФ. 1984. - Т.24, № 1. -С. 164-166.

7. Опарин Г. А. Булевы модели синтеза параллельных планов решения вычислительных задач / Г.А. Опарин, А.П. Новопашин // Вестник НГУ. Серия: Информационные технологии. — 2008. — Том 6, Вып. 1. — С. 5359.

8. Калиниченко Д.В. Методы и средства прогнозирования времени выполнения последовательных программ / Д.В. Калиниченко, А.П. Капитонова, Н.В. Ющенко // Методы математического моделирования. ВМиК МГУ. 1997. - №2.

9. Коваленко В. Эволюция и проблемы Grid / В. Коваленко, Д. Корягин // Открытые системы. — 2003. — №1. — С. 23-33.

10. Коваленко В. Комплексное программное обеспечение грида вычислительного типа / В. Коваленко. — М.: ИПМ РАН, 2007. — 39 с.

11. Коваленко В.Н. Использование алгоритма Backfill в грид / В.Н. Коваленко, Д.А. Семячкин // Распределенные вычисления и Грид-технологии в науке и образовании. — Дубна, 2004. — С. 139-144.

12. Коган Б.И. Экспериментальные исследования программ / Б.И. Коган.1. М.: Наука, 1988. — 184 с.

13. Коффман Э.Г. Теория расписаний и вычислительные машины / Э.Г. Коффман. М.: Наука, 1984. - 336 с.

14. Конвей Р.В. Теория расписаний / Р.В. Конвей, B.JI. Максвелл, J1.B. Миллер. — М.: Наука, 1975. — 360 с.

15. Корнеев В.В. Параллельные вычислительные системы / В.В. Корнеев.1. М.: Нолидж, 1999. 320 с.

16. Корнеев В.В. Архитектуры с распределенной разделяемой памятью / В.В. Корнеев // Открытые системы. 2001. - №. - С. 15-23.

17. Кочетов Ю.А. Методы локального поиска для дискретных задач размещения / Ю.А. Кочетов. — Новосибирск: Омега Принт, 2009.

18. Курейчик В.М. Параллельные генетические алгоритмы: обзор и состояние проблемы / В.М. Курейчик, Д.С.Кныш // Известия РАН. Теорияи системы управления. — 2010. — Ш — С. 72-82.

19. Курейчик В.М. Генетические алгоритмы. Монография, ТРТУ, Таганрог, 1998. 242 с.

20. Лацис А. Как построить и использовать суперкомпьютер / А. Лацис.

21. М.: Бестселлер, 2003. 240 с.

22. Липаев В.В. Распределение ресурсов в вычислительных системах / В.В. Липаев. — М.: Статистика, 1979. 248 с.

23. Майника Э. Алгоритмы оптимизации на сетях и графах / Э. Майника. М.: Мир, 1981. - 328 с.

24. Михалевич B.C. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов /B.C. Михалевич, А.И. Кукса. — М.: Наука, 1983. — 208 с.

25. Панченко Т.В. Генетические алгоритмы / Т.В. Панченко. — Астрахань: Издательский дом «Астраханский университет», 2007. — 87 с.

26. Пересветов В.В., Сапронов А.Ю., Тарасов А.Г. Вычислительный кластер бездисковых рабочих станций. Препринт № 83. / В.В. Пересветов, А.Ю. Сапронов, А.Г. Тарасов. Хабаровск: ВЦ ДВО РАН, 2005. -50 с.

27. Пересветов В.В., Сапронов А.Ю., Тарасов А.Г., Шаповалов Т.С. Организация работы вычислительного кластера в режиме удалённого доступа. Препринт № 110 / В.В. Пересветов, А.Ю. Сапронов, А.Г. Тарасов, Т.С. Шаповалов // Хабаровск: ВЦ ДВО РАН, 2007.

28. Пономаренко B.C., Листровой C.B., Минухин C.B., Знахур C.B. Методы и модели планирования ресурсов в Grid-системах / B.C. Пономаренко, C.B. Листровой, C.B. Минухин, C.B. Знахур. — Харьков: Издательский Дом "ИНЖЭК", 2008. 408 с.

29. Попков Ю.С. Макросистемы и Grid-технологии: моделирование динамических стохастических сетей / Ю.С. Попков // Проблемы управления. 2003. - №8 - С. 10-20.

30. Смагин С.И. Шаповалов Т.С. Генетический алгоритм составления расписания выполнения параллельных заданий в распределенной вычислительной системе // Вычислительные технологии. — 2010. — Т. 15, №5.- С. 41-59.

31. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы / B.C. Танаев, B.C. Гордон, Я.М. Шафранский.- М.: Наука, 1984. — 384 с.

32. Таненбаум Э. Архитектура компьютера / Э. Таненбаум. — СПб.: Питер, 2002. 704 с.

33. Топорков В.В. Модели распределенных вычислений / В.В. Топорков. -М.: ФИЗМАТЛИТ, 2004. 320 с.

34. Филамофитский М.П. Система поддержки метакомпьютерных расчетов Х-Com: архитектура и технология работы / М.П. Филамофитский // Вычислительные методы и программирование. — 2004. — Т.5. — № 2- С. 123-137.

35. Фостер Я., Кессельман К., Тьюке С. Grid-службы для интеграции распределенных систем / Я. Фостер, К. Кессельман, С. Тьюке // Открытые системы. — 2003. №1. — С. 20-26.

36. Шаповалов Т.С. Генетический алгоритм составления расписания запуска параллельных заданий в Grid / Т.С. Шаповалов // Информатика и системы управления. — 2010. — Т.4. №26. — С. 115-126.

37. Шаповалов Т.С. Об интеграции диспетчера заданий в Grid-инструментарий Globus Toolkit. / Т.С. Шаповалов // Материалы XXXV Дальневосточной математической школы-семинара имени академика Е.В. Золотова. — Владивосток: ИАПУ ДВО РАН, 2010. — С. 904-907.

38. Шаповалов Т.С., Пересветов В.В. Генетический алгоритм составления расписаний для распределенных гетерогенных вычислительных систем / Т.С. Шаповалов, В.В. Пересветов // Вычислительные методы и программирование. 2009. - Т. 10, №1. - С. 159-167.

39. Шаповалов Т.С. Параллельный алгоритм планирования заданий для распределенных гетерогенных вычислительных систем. Препринт № 134 / Т.С. Шаповалов. Хабаровск: ВЦ ДВО РАН, 2006.

40. Шаповалов Т.С., Пересветов В.В., Сапронов А.Ю., Смагин С.И., Тарасов А.Г. Web и Grid технологии обеспечения доступа к ресурсам вычислительного кластера ВЦ ДВО РАН / Т.С. Шаповалов, В.В. Пересветов,

41. А.Ю. Сапронов, С.И. Смагин, А.Г. Тарасов // Материалы Межрегиональной конференции «Информационные и коммуникационные технологии в образовании и научной деятельности». — Хабаровск: Изд-во Тихоокеан. гос. ун-та, 2008. — С. 69-76.

42. Шаповалов Т.С. Применение генетических алгоритмов для поиска оптимального расписания заданий в Grid / Т.С. Шаповалов // Труды международной конференции "Параллельные вычислительные технологии". Челябинск: Изд. ЮУрГУ, 2008. - С. 500-505.

43. Шаповалов Т.С., Сапронов А.Ю. О методах планирования заданий в Grid / Т.С. Шаповалов, А.Ю. Сапронов // Труды третьей международной конференции "Распределенные вычисления и Grid-технологии в науке и образовании". Дубна: ОИЯИ, 2008 - С. 307-309.

44. Aarts Е.Н. Job Shop Scheduling by Simulated Annealing / E.H. Aarts, P.J. van Laarhoven, J.K. Lenstra // Operations Research. — 1992. — Vol. 40(1).- P. 113-125.

45. Adams J. The shifting bottleneck procedure for job shop scheduling / J. Adams, E. Balas, D. Zawack // Management Science. — 1988. — Vol. 34(3).- P. 391-401.

46. Atakan D. Biobjective Scheduling Algorithms for Execution Time-Reliability Trade-off in Heterogeneous Computing Systems / D. Atakan, 0. Fusun // The Computer Journal. 2005. - Vol 48(3). -P. 300-314.

47. Atakan D., Fusun O. Genetic Algorithm Based Scheduling of Meta-Tasks with Stochastic Execution Times in Heterogeneous Computing Systems / D. Atakan, 6. Fusun // Cluster Computing. 2004. - Vol. 7. -P. 177-190.qj.«

48. Bailey D. The NAS Parallel Benchmarks. Technical Report № RNR-94-007 / D. Bailey, E. Barszcz, J. Barton, et al. // Washington: 1994.

49. Baluja S. A massively distributed parallel genetic algorithm (mdpGA). Technical report CMU-CS-92-196 / S. Baluja // Pittsburgh: Carnegie Mellon University, 1992.

50. Barricelli A. Symbiogenetic Evolution Processes Realized by Artificial Methods / A. Barricelli // Methodos. 1957. - Vol. 9. - P. 35-36.

51. Barricelli A. Numerical Testing of Evolution Theories: Part I / A. Barricelli // Acta Biotheoretica. Vol. 16. - 1962. — P. 94.

52. Barricelli A. Numerical Testing of Evolution Theories: Part II / A. Barricelli // Acta Biotheoretica. Vol. 16. - 1962. - P. 122.

53. Baker M. Cluster Computing White Paper / M. Baker // UK, Portsmouth: University of Portsmouth, 2000. — 119 p.

54. Berry M., Gordon S. Data Mining Techniques: For Marketing, Sales, and Customer Relationship Management. 2nd edition / M. Berry, S. Gordon.- John Wiley and Sons: 2004. 643 p.

55. Blazewicz J., Lenstra J.K. Scheduling subject to resource constraints: classification and complexity / J. Blazewicz, J.K. Lenstra // Discrete Applied Mathematics. 1983. - Vol. 5. - P. 11-24.

56. Brian H. Cloud computing / H. Brian // Communications of the ACM. — 2008. Vol. 51(7). - P. 9-11.

57. Boctor F.F. Some efficient multi-heuristic procedures for resource-constrained project scheduling / F.F. Boctor // European journal of operational research. 1990. - Vol. 49(1). - P. 3-13.

58. Brune M. Managing clusters of geographically distributed high-performance computers / M. Brune, J. Gehring, A. Keller, A. Reinefeld // Concurrency- Practice and Experience. 1999. - Vol. 11(15). - P. 887-911.

59. Bierwirth C. On permutation representations for scheduling problems / C. Bierwirth, D. Mattfeld, H. Kopfer // In 4th PPSN: 1996. P. 310-318.

60. Bierwirth C. A generalized permutation approach to job shop scheduling with genetic algorithms / C. Bierwirth // OR Spektrum. — 1995. — Vol. 17- P. 87-92.

61. Bruno J. Scheduling independent tasks to reduce mean finishing time / J. Bruno, E. Coffman, R. Sethi // Communications of the ACM. — 1974. — Vol. 17(7) P. 382-387.

62. Buyya E.R. High Performance Cluster Computing: V.l.Architectures and Systems, V.2.Programming and applications / E.R. Buyya. — New Jersey: Prentice Hall PTR, 1999.

63. Buyya E.R. Economic-based Distributed Resource Management and Scheduling for Grid Computing. Doctor of Philosophy thesis / E.R. Buyya. — School of Computer Science and Software Engineering Monash University, Melbourne, Australia: 2002.

64. Buncic P. The AliEn system, status and perspectives / P. Buncic, A.J. Peters, P. Saiz. — Computing in High Energy and Nuclear Physics, La Jolla, California: 2003.

65. Collins R.J. Selection in massively parallel genetic algorithms / R.J. Collins, D.R. Jefferson //In proceedings of the 4th International Conference on Genetic Algorithms and their Applications (ICGA), San Diego CA: 1991. P. 249-256.

66. Cohoon J.P. Genetic Placement / J.P. Cohoon, W.D. Paris // IEEE Trans, on CAD. 1987. - Vol. 6(6). - P. 956-964.

67. Darrel W. A Genetic Algorithm Tutorial. Technical Report CS-93-103 / W. Darrel. — Department of Computer Science, Colorado State University, Fort Collins, US: 1993.

68. Davis L. Job shop scheduling with genetic algorithms / L. Davis //In proceedings of an International Conference on Genetic Algorithms and their Applications, Pittsburgh, Lawrence Erlbaum Associates: 1985. — P. 136140.

69. Davis L. Genetic Algorithms and Simulated Annealing / L. Davis. — San Mateo: Morgan Kaufman Publisher, 1987. — 216 p.

70. Devis E.W. A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling / E.W. Devis, J.H. Patterson // Management Science. 1975. - Vol. 21(8). - P. 944-955.

71. Devis E.W. An algorithm for optimal project scheduling under multiple resource constraints / E.W. Devis, G.E. Heidorn // Management Science.- 1971. Vol 17(12). - P. 803-817.

72. De Jong A.K. An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis / A.K. De Jong // University of Michigan: 1975.

73. Dean J. MapReduce: Simplified Data Processing on Large Clusters / J. Dean, S. Ghemawat // Communications of the ACM. — 2008. — Vol. 51(1).- P. 107-113.

74. Dorndorf U., Pesch E. Evolution based learning in a job shop scheduling environment / U. Dorndorf, E. Pesch // Computers Ops Res. — 1995. — Vol. 22. P. 25-40.

75. Ellert M. Advanced Resource Connector middleware for lightweight computational Grids / M. Ellert et al. // Future Generation Computer Systems. 2007. - Vol. 23. - P. 219-240.

76. Foster I. The anatomy of the Grid: enabling scalable virtual organizations / I. Foster, C. Kesselman, S. Tuecke // International Journal of High Performance Computing Applications. 2001. - Vol. 15(3). - P. 200-222.

77. Foster I., Kesselman C. The Grid 2 Blueprint for a New Computing Infrastructure. Second Edition. / I. Foster, C. Kesselman. — Elsevier, 2003.

78. Fox B., McMahon M. Genetic operators for sequencing problems. Foundations of genetic algorithms / B. Fox, M. McMahon. — Morgan Kaufmann, 1991.

79. Fox M.S. ISIS — a Knowledge-based system for factory scheduling /M.S. Fox, S.F. Smith // Expert Systems. 1984. - Vol. 1(1). - P. 25-49.

80. Feitelson D.G. Improved utilization and responsiveness with gang scheduling in Job Scheduling Strategies for Parallel Processing / D.G. Feitelson, M.A. Jette // Lecture Notes in Computer Science. — 1997. — Vol. 1291. P. 238-261.

81. Feitelson D.G. Metrics and benchmarking for parallel job scheduling / D.G. Feitelson, L. Rudolph // Lecture Notes in Computer Science. — 1998. — Vol. 1459 P. 1-24.

82. Gabbert P., et al. A system for learning routes and schedules with genetic algorithms / P. Gabbert, et al. //In Proceedings of the Fourth Intl. Conf. on Genetic Algorithms, ICGA-91, Morgan Kaufmann: 1991. — P. 430-436.

83. Galantucci L. Assembly and Disassembly Planning by using Fuzzy Logic and Genetic Algorithms / L. Galantucci, G. Percoco, R. Spina // International Journal of Advanced Robotic Systems. — 2004. — Vol. 1(2).- P. 67-74.

84. Garey M. Bounds for multiprocessor scheduling with resource constraints / M. Garey, R. Graham // SIAM Journal on Computing. — 1975. — Vol. 4(2).- P. 187-200.

85. Garey M., Johnson D. Computers and intractability: a guide to the theory of NP-Completeness / M. Garey, D. Johnson. — New York: W. H. Freeman and Co., 1990. 338 p.

86. Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning / D. Goldberg. — Massachusetts: Addison-Wesley, 1989. — 372 p.

87. Grefenstette J.J. Parallel adaptive algorithms for function optimization. Technical report no. CS-81-19 / J.J. Grefenstette. — Nashville: Vanderbilt University, 1981.

88. Grimshaw S.A. The Legion vision of a worldwide virtual computer / S.A. Grimshaw, A.W. William // Communications of the ACM. — 1997. — Vol. 40(1). P. 39-45.

89. Harvey W.D., Ginsberg M.L. Limited discrepancy search / W.D. Harvey, M.L.Ginsberg. CIRL, University of Oregon, Eugene, OR, USA: 1995.

90. Havanki W.A. TYeegion Scheduling for Wide Issue Processors / W.A. Havanki, S. Banerjia, T.M. Conte //In proceedings of 4th Intl. Symp. on High Performance Computer Architecture: 1998. — P. 266-276.

91. Heien E.M. Computing Low Latency Batches with Unreliable Workers in Volunteer Computing Environments /E.M. Heien, P.D. Anderson, K. Hagihara // Journal of Grid Computing. 2009. - Vol. 7(4). - P. 501-518.

92. Hilliard M.R., et al. Machine Learning Applications to Job Shop Scheduling / M.R. Hilliard, et al. // In proceedings of the AAAI-SIGMAN Workshop on Production Planning and Scheduling. New York: ACM, 1988. P. 728-737.

93. Hildum D. Flexibility in a knowledge-based system for solving dynamic resource-constrained scheduling problems. Umass CMPSCI Technical Report N.94-77 / D. Hildum. — University of Massachusetts, Amherst: 1994.

94. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence / J.H. Holland. Cambridge, The MIT Press: 1992.

95. Horn W.A. Single-machine job sequencing with treelike precedence ordering and linear delay penalties / W.A. Horn //SI AM Journal on Applied Mathematics. 1972. - Vol. 23(2). - P. 189-202.

96. Horn W.A. Minimizing average flow time with parallel machines / W.A. Horn // Operations Research. 1973. - Vol. 21(3). - P. 846-847.

97. Husbands P. Genetic algorithms for scheduling. Technical Report N.89 / P. Husbands. AISB Quarterly: 1996.

98. Johnson T.J. An algorithm for the resource-constrainted project scheduling problem. Doctoral Thesis / T.J. Johnson. — Massachusetts Institute of Technology, Cambridge: 1967.

99. Junwei C. An agent-based resource management system for grid computing / C. Junwei, D. Spooner, J.D. Turner, S. Jarvis, D.J. Kerbyson, S. Saini, G. Nudd // 2nd IEEE/ACM International Symposium "Cluster Computing and the Grid": 2002. P. 350-350.

100. Jackson D. Core algorithms of the Maui scheduler / D. Jackson, Q. Snell, M. Clement // Lecture Notes in Computer Science. — 2001. — Vol. 2221- P. 87-102.

101. Kirkpatrick S., et al. Optimization by Simulated Annealing / S. Kirkpatrick, et al. // Science. 1983. - Vol. 220 - P. 671-680.

102. Kojima K. Asynchronous parallel distributed genetic algorithm with elite migration / K. Kojima, M. Ishigame, G. Chakraborty, H. Hatsuo // International Journal of Computational Intelligence. — 2007. — Vol. 4(2)- P. 105-111.

103. Krallmann J. On the Design and Evaluation of Job Scheduling Systems / J. Krallmann, U. Schwiegelshohn, R. Yahyapour // Lecture Notes in Computer Science. 1999. - Vol. 1659. - P. 17-42.

104. Kurowski K. User Preference Driven Multiobjective Resource Management in Grid Environments / K. Kurowski, J. Nabrzyski, J. Pulacki // In proceedings of CCGrid: 2001. P. 114.

105. Larry J.E. The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination / Larry J.E. // In proceedings of the First Workshop on Foundations of Genetic Algorithms. Morgan Kaufmann: 1991. P. 265-283.

106. Land A.H. An autmatic method of solving discrete programming problems / A.H. Land, A.G. Doig // Econometrica. 1960. - Vol. 28 - P. 497-520.

107. Lawler E.L. Branch and Bound methods: a survey / Lawler E.L., Wood D.E. // Operations Research. 1966. - Vol. 14(4) - P. 699-719.

108. Lee W. Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach / W. Lee, J.S.

109. Howard, P.R. Vwani, A.M. Anthony // Journal of Parallel And Distributed computing. 1997. - Vol. 47. - P. 8-22.

110. Lifka D.A. The ANL/IBM SP Scheduling System / D.A. Lifka // Lecture Notes in Computer Science. 1995. - Vol. 949. - P. 295-303.

111. Luis V.M. A break in the clouds: towards a cloud definition / R.M. Luis,

112. C. Juan, L. Maik // ACM SIGCOMM Computer Communication Review.- 2008. Vol. 39(1). - P. 50-55.

113. Mansour N. A hybrid genetic algorithm for task allocation in multicomputers / N. Mansour, G. Fox //In proceedings of the Fourth Intl. Conf. on Genetic Algorithms, ICGA-91, Morgan Kaufmann: 1991. — P. 466-473.

114. Moore M. An Accurate and Efficient Parallel Genetic Algorithm to Schedule Tasks on a Cluster / M. Moore // International Parallel and Distributed Processing Symposium (IPDPS'03): 2003. P. 145.

115. Müller-Merbach H. Ein Verfahren zur Planung des optimalen Betriebsmitteleinsatzes bei der Terminierung von Großprojeckten /

116. H. Müller-Merbach // Zeitschrift für wirtschaftliche Fertigung. — 1967. — Vol. 62. P. 83-88.

117. Mualem A.W. Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling / A.W. Mualem,

118. D.G. Feitelson //In proc. 12th Intl. Parallel Processing Symposium: 1998.- P. 542-546.

119. McGregor S. Embracing Plagiarism: Theoretical, Biological and Empirical Justification for Copy Operators in Genetic Optimisation / S. McGregor,

120. Harvey // Genetic Programming and Evolvable Machines. —2005. — Vol. 6(4). P. 407-420.

121. Nakano R. Genetic Algorithms for Job-Shop Scheduling Problems / R. Nakano, T. Yamada //In proceedings of Modern Heuristic for Decision Support, London: 1997. P. 67-81.

122. Nakano R. Conventional genetic algorithms for job-shop problems / R. Nakano, T. Yamada //In proceedings of the Fourth Intl. Conf. on Genetic Algorithms (ICGA-91), Morgan Kaufmann: 1991. — P. 474-479.

123. Neumann K. Stochastic project networks — temporal analysis, scheduling and cost minimization / K. Neumann. — Berlin: Springer-Verlag, 1990.

124. Norbis M.I. A multiobjective, multilevel heuristic for dynamic resource constrained scheduling problems / M.I. Norbis, J.M. Smith // European Journal of Operational Research. — 1988. — Vol. 33(1). — P. 30-41.

125. Patterson J.H. A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem / J.H. Patterson // Management Science. 1984. - Vol. 30(7) - P. 854-867.

126. Panwalker S. A survey of scheduling rules / S. Panwalker, W. Iskander // Operations Research. 1997. - Vol. 25(1). - P. 45-61.

127. Palmer G. An Integrated Approach to Manufacturing Planning / G. Palmer. — Huddersfield: University of Huddersfield, 1994.

128. Pesch E. Learning in Automated manufacturing: a local search approach / E. Pesch. — Heidelberg: Physica-Verlag, 1994.

129. Pugliese F. Modeling and Supporting Grid Scheduling / F. Pugliese, D. Talia, R. Yahyapour // Journal of Grid Computing. 2008. - Vol. 6(2). - P. 195-213.

130. Qingjiang W. De-centralized job scheduling on computational Grids using distributed backfilling / Qingjiang W., Xiaolin G., Shouqi Z., Yang L. // Concurrency and Computation: Practice and Experience. — 2006. — Vol. 18(14). P. 1829-1838.

131. Reeves C.R. Genetic algorithms and neighbourhood search / C.R. Reeves // In Evolutionary Computing. 1994. — Vol. 865. — R 115-130.

132. Sadeh N. Look-Ahead Techniques for Micro-Opportunistic Job Shop Scheduling. PhD thesis / N. Sadeh. — School of Computer Science, Carnegie Mellon University, Pittsburgh: 1991.

133. Sampson S.E. Local search techniques for the generalized resource constrained project scheduling problem / S.E. Sampson, E.N. Weiss // Naval Research Logistics. 1993. — Vol. 40(5). - P. 665.

134. Schwiegelshohn U. Analysis of First-Come-First-Serve Parallel Job Scheduling / U. Schwiegelshohn, R. Yahyapour //In proceedings of the 9th SIAM Symposium on Discrete Algorithms: 1998. — P. 629-638.

135. Syswerda G. The Application of Genetic Algorithms to Resource Scheduling / G. Syswerda //In proceedings from the 4th International Conference on Genetic Algorithms. San Mateo, Morgan Kaufmann: 1990. P. 502-508.

136. Smith S.F. The use of multiple problem decompositions in time constrained planning tasks / S.F. Smith, P. Ow //In proceedings of the ninth international joint conference on artificial intelligence. — 1985. — Vol. 2. P. 1013-1015.

137. Schwiegelshohn U. Preemptive weighted completion time scheduling of parallel jobs / U. Schwiegelshohn //In Proceedings of the 4th Annual European Symposium on Algorithms (ESA96): 1996. — P. 39-51.

138. Schwiegelshohn U. Smart bounds for weighted response time scheduling / U. Schwiegelshohn, W. Ludwig, J.L. Wolf, J.J. Turek, P. Yu // SIAM Journal on Computing. 1999. - Vol. 28(1). - P. 237-253.

139. Shapovalov T.S. Genetic Algorithm Based Parallel Jobs Scheduling / T.S. Shapovalov, A.G. Tarasov //In Proceedings of First Russia and Pacific Conference on Computer Technology and Applications. Vladivostok: IACP FEB RAS, 2010. - P. 211-216.

140. Smith W.E. Various optimizers for single-stage production / W.E. Smith // Naval Research Logistics Quarterly. — 1956. — Vol.3. — R 59-66.

141. Smith W. Scheduling with advanced reservations / W. Smith, I. Foster, V. Yaylor // IPDPS 2000. Proceedings. 14th International: 2000. — P. 127-132.

142. Smith W. Predicting application run times using historical information / W. Smith, I. Foster, V. Taylor // Lecture Notes on Computer Science. — 1998. Vol. 1459. - P. 122-142.

143. Smith W., Wong P. Resource selection using execution and queue wait time predictions. NASA Technical report NAS-02-003 / W. Smith, P. Wong. NASA: 2002.

144. Shubhra S.R. New Operators of Genetic Algorithms for Traveling Salesman Problem / S.R. Shubhra, B. Sanghamitra, K.P. Sankar // 17th International Conference on Pattern Recognition (ICPR'04). — 2004. — Vol. 2 P. 497-500.

145. Simoes A. Enhancing Transposition Performance / A. Simoes, E. Costa // In proceedings of the 1999 Congress on Evolutionary Computation (CEC 99). Washington: 1999. P. 1434-1441.

146. Simoes A. Transposition versus Crossover: An Empirical Study / A. Simoes, E. Costa //In proceedings of the Genetic and Evolutionary Computation Conference. 1999. - Vol. 1. - P. 612-619.

147. Steuer R.E. Multiple Criteria Optimization, Theory, Computation and Application / R.E. Steuer. Krieger Pub Co: 1986. - 546 p.

148. Smarr L. Metacomputing / L. Smarr, C. Catlett // Communications of the ACM. 1992. - Vol. 35(6). - P. 44-52.

149. Syswerda G. Uniform crossover in genetic algorithms / G. Syswerda //In 3rd ICGA, Los Altos: 1989. P. 2-9.

150. Tanese R. Distributed genetic algorithms / R. Tanese //In Proceedings of the 3rd International Conference on Genetic Algorithms and their application (ICGA). San Mateo, CA, Morgan Kaufmann: 1989. — P. 434439.

151. Thain D. Grid Computing: Making The Global Infrastructure a Reality / D. Thain, T. Tannenbaum, M. Livny — John Wiley: 2003. — 1060 p.

152. Turek J.J. Scheduling parallel tasks to minimize average response time / J.J. Turek, U. Schwiegelshohn, J.L. Wolf, P. Yu // In Proceedings of the 5th SIAM Symposium on Discrete Algorithms: 1994. — P. 112-121.

153. Ulder N.L.J. Genetic local search algorithm for the traveling salesman problem / N.L.J. Ulder, E. Pesch, P.J.M. van Laarhoven, J. Bandelt, H. Aarts // In 1st PPSN: 1994. P. 109-116.

154. Ullman J.D. Polynomial complete scheduling problems / J.D. Ullman // Operating Systems Review. 1973. - Vol. 7(4). - P. 96-101.

155. Viet T. A Master-Slave Algorithm for Hybrid MPI-OpenMP Programming on a Cluster of SMPs / T. Viet, T. Yoshinaga, M. Sowa // Joho Shori Gakkai Kenkyu Hokoku. 2002. - Vol. 80. - P. 107-112.

156. Vose M.D. Random heuristic search: Applications to GAs and functions of unitation / M.D. Vose, J.E. Rowe // Computer Methods in Applied Mechanics and Engineering. 2000. - Vol. 186(2). - P. 195-220.

157. Wren A. Genetics, structures and covers — an application to scheduling. Technical Report 90.23 / A. Wren, D. Wren. — School of Computer Science, University of Leeds: 1990.

158. Yahyapour R. Design and Evaluation of Job Scheduling Strategies for Grid Computing / R. Yahyapour // Computer Engineering Institute: 2002.

159. Yamada T. Job-Shop Scheduling by Simulated Annealing Combined with Deterministic Local Search / T. Yamada, R. Nakano // Kluwer academic publishers: 1996 R 237-248.

160. Yamada T. A genetic algorithm with multi-step crossover for job-shop scheduling problems / T. Yamada, R. Nakano //In GALESIA-95: 1995. — P. 146-151.

161. Yoo A.B. An efficient and scalable coscheduling technique for large symmetric multiprocessor clusters / A.B. Yoo, M. Jette // Lecture Notes in Computer Science. 2001. - Vol. 2221 - P. 21-40.

162. Zhang Y., et al. An integrated approach to parallel scheduling using gang-scheduling, backfilling and migration / Y. Zhang, H. Franke, J.E. Moreira, et al. // Lecture Notes in Computer Science. — 2001. — Vol. 2221. — P. 133158.