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

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

005012281

Ефимов Александр Владимирович

ОРГАНИЗАЦИЯ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЕНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В РЕЖИМЕ ОБРАБОТКИ НАБОРОВ МАСШТАБИРУЕМЫХ ЗАДАЧ

Специальность 05.13.15 - Вычислительные машины, комплексы и компьютерные сети

1 2 идр 2012

Автореферат диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 2012

005012281

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

Научный руководитель - доктор технических наук профессор

член-корреспондент РАН заслуженный деятель науки РФ Хорошевский Виктор Гаврилович

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

старший научный сотрудник

заведующий лабораторией ИВМиМГ СО РАН

Хайретдинов Марат Саматович

кандидат технических наук генеральный директор ОАО "Ринет" Майданов Юрий Сергеевич

Ведущая организация - Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Национальный исследовательский Томский политехнический университет

Защита состоится "22" марта 2012 г. В "15" часов на заседании Диссертационного совета Д219.005.02 при ФГОБУ ВПО "Сибирский государственный университет телекоммуникаций и информатики", по адресу: 630102, г. Новосибирск, ул. Кирова, д. 86, ком. 625.

С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО "СибГУТИ".

Автореферат разослан "_"_2012 г.

Учёный секретарь

диссертационного совета Д219.005.02 кандидат технических наук доцент

И. И. Резван

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

Актуальность работы. Возрастающая потребность в решении сложных задач науки, техники привела к созданию распределённых вычислительных систем (ВС). В общем случае распределённая ВС - это композиция множества элементарных машин (ЭМ) и сети межмашинных связей. Элементарная машина - это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до ЭВМ или специализированного ускорителя. Все основные ресурсы распределённых ВС (как аппаратурные, так и программные) являются логически и технически рассредоточенными. Количество ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч (например, в системе Fujitsu К Computer количество вычислительных ядер равно 705 024).

Исследования в области распределённых вычислительных систем ведутся с середины XX столетия. С тех пор в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвящённых проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную реализацию на распределённых ВС. Построены отечественные вычислительные системы с программируемой структурой: «Минск-222», СУММА, МИНИМАКС, МИК-

РОС, МВС, СКИФ и др.

Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Глушков, В.Ф.Евдокимов, Э.В. Евреинов, А.В.Забродин, ВП Иванников, М.Б.Игнатьев, А.В.Каляев, И.А. Каляев, Л.Н.Королев, С.А. Лебедев, В.К.Левин, Г.И.Марчук, Ю.И. Митропольский, ДА Поспелов, И.В. Прангишвшш, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, A.A. Самарский, В.Б. Смолов, А.Н.Томилин, Я.А. Хетагуров, В Г Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, H.H. Яненко, а также зарубежные учёные: S.Cray, M.Flynn, I.Foster, D.HÜlis, C.Kesselman, DL. Slotnick, A. Tanenbaum, D. Feitelson и другие. При решении проблем оптимизации функционирования распределённых ВС большую роль сыграли фундаментальные работы в области дискретной математики и исследовании операций советских и российских учёных: В.Л. Береснева, Э.Х. Гимади,

В.Т. Дементьева, Ю.И. Журавлева, К.В. Рудакова и зарубежных -R. Bellmann, D. Johnson, М. Koffman, Н. Taha и других.

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

В режиме обработки набора задач требуется сформировать расписание их решения. Для каждой задачи необходимо определить подсистему ЭМ и момент запуска на выполнение ветвей соответствующей параллельной программы. Этот режим хорошо изучен для задач, параметры которых (ранг и время решения) заданы скалярными величинами, такие алгоритмы внедрены в системы пакетной обработки заданий (TORQUE, SLURM, Altair PBS Pro и

др.).

Анализ пользовательских задач показывают, что более 80 % из них обладают свойством масштабируемости. Такие задачи допускают решение на подсистемах с различным количеством ЭМ и называются масштабируемыми или "пластичными" (moldable). Актуальной является задача разработки алгоритмических и программных средств организации мультипрограммного функционирования распределённых ВС в режиме обработки наборов масштабируемых задач.

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

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

В соответствии с целью определены нижеследующие задачи исследования.

1. Анализ современных подходов к организации функционирования распределённых ВС в мультипрограммных режимах.

2. Разработка алгоритмов формирования расписаний решения масшта-

бируемых задач набора на распределённых ВС.

3. Создание программных средств моделирования алгоритмов формирования расписаний решения пользовательских задач на распределённых ВС.

Методы исследования. Для решения поставленных задач использовались методы теории вычислительных систем, математического программирования, исследования операций и эволюционные методы оптимизации. Экспериментальные исследования осуществлялись путём моделирования на пространственно-распределённой мультикластерной ВС.

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

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

Созданный программный пакет MOJOS - MOldable JObs Scheduling предназначен для моделирования, отладки и анализа алгоритмов формирования расписаний решения масштабируемых задач на распределённых ВС.

Программные средства внедрены в действующую пространственно-распределённую мультикластерную вычислительную систему Центра параллельных вычислительных технологий (ЦПВТ) ФГОБУ ВПО "СибГУТИ" и Лаборатории вычислительных систем Федерального государственного бюджетного учреждения науки Института физики полупроводников им. А.В. Ржанова Сибирского отделения РАН (ИФП СО РАН).

Реализация и внедрение результатов работы. Основные результаты диссертации нашли применение в работах по созданию и развитию пространственно-распределённой мультикластерной вычислительной системы ЦПВТ ФГОБУ ВПО "СибГУТИ" и Лаборатории ВС ИФП СО РАН.

Диссертационные исследования выполнялись в рамках федеральных целевых программ "Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007 - 2013 годы" (ГК №02.514.11.0002 "Разработка программных технологий для развития российского сегмента Грид, систем параллельного программирования, систем компьютерной графики") и "Научные и научно-педагогические кадры инновационной России" (ГК №02.740.11.0006 "Проведение исследований в области распределённых вычислительных систем и развитие научно-учебного центра параллельных вычислительных технологий ФГОБУ ВПО

«СибГУТИ»"). Работа поддержана грантами Российского фонда фундаментальных исследований №09-07-13534, 08-07-00022, 09-07-00095, 11-0700109, грантами Президента РФ по поддержке ведущих научных школ №НШ-2121.2008.9, НШ-5176.2010.9, грантом мэрии г. Новосибирска молодым учёным № 10-11 (2011), а так же грантами ФГОБУ ВПО "СибГУТИ" (2009,2010,2011).

Внедрение результатов диссертационного исследования подтверждается соответствующими актами.

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

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

-Международной научно-технической конференции "Многопроцессорные вычислительные и управляющие системы" (с. Дивноморское Гелен-джикского района, 2009);

- Международной научно-технической конференции "Суперкомпьютерные технологии: разработка, программирование, применение" (с. Дивноморское Геленджикского района, 2010);

- Международной научно-технической конференции "Студент и научно-технический прогресс" (г. Новосибирск, 2009,2010,2011);

- Международной научной молодёжной школе "Высокопроизводительные вычислительные системы" (с. Дивноморское Геленджикского района, 2010);

- Российской конференции с международным участием "Новые информационные технологии в исследовании сложных структур" (г. Томск, 2008,2010);

- Научной школе-практикуме для молодых учёных и специалистов "Технологии высокопроизводительных вычислений и компьютерного моделирования" (г. Санкт-Петербург, 2009);

- Российской научно-технической конференции "Информатика и проблемы телекоммуникаций" (г. Новосибирск, 2008,2009,2010, 2011);

- Российской конференции с участием иностранных учёных "Распределённые информационные и вычислительные ресурсы" (г. Новосибирск, 2010);

- Всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям (г. Красноярск, 2010);

- Пятой сибирской конференции по параллельным и высокопроизводительным вычислениям (г. Томск, 2009).

Публикации. По теме диссертации опубликовано 19 работ, из которых 3 - в изданиях из списка ВАК. Результаты исследований отражены в отчётах

по грантам и НИР.

Основные положения диссертации, выносимые на защиту.

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

2. Программные пакет формирования и анализа расписаний решения масштабируемых задач на распределённых ВС (пакет MOJOS), предусматривающий средства визуализации расписаний и интерфейс с системами пакетной обработки заданий.

Структура и объём диссертации. Диссертационная работа состоит из введения, -трёх глав, заключения и списка литературных источников, изложенных на 97 страницах, а также приложений на 25 страницах.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Общая формулировка поставленной задачи следующая. Имеются распределённая ВС, состоящая из N элементарных машин, и набор I из L масштабируемых задач. Каждая задача i е {1,2,...,!} описывается вектором параметров д =(p],pf,-,p-') и величиной штрафа с(за задержку её решения в единицу времени, с, > 0.

Каждый к-ый элемент вектора параметровр, = (/;*,/,',w') означает, что для решения í'-той задачи требуется выделить подсистему из г,* элементарных машин на время tf, wf - приоритет данного размера подсистемы (определяемый пользователем). Показатель "удовлетворённости" пользователя выбо-

ром для решения /-ой задачи А-ой конфигурации, выражается как wf /шах w~,

/ z-1,?,

гдеАе{1,2,...,^}, О<r*<N, /* >0, ^>0.

Считается, что в наборе присутствуют задачи с различным количеством параметров (qt). Допускается существование в векторе pt нескольких элементов с одинаковым приоритетом. Каждой ветви параллельной программы выделяется не более одной ЭМ. Любые две ЭМ могут взаимодействовать

к к к

через сеть связи. Зависимости между величинами tj , /, , w, , с, отсутствуют.

Необходимо для каждой задачи / определить время s( начала её решения, выбрать kj - номер элемента вектора pt и выделить множество номеров ЭМ Jj подсистемы необходимого размера. В результате должен быть сформиро-'

ван вектор 5 = {(Aj, ij, ^j), (¿2, > )»—»(^Z-»^Z, > ^Z-)) > называемый расписанием решения задач на ВС.

Показателями эффективности расписаний являются время T\S) завершения решения последней задачи; суммарный штраф F(S) за задержку решения задач.

T(S) = max{s, + tf'}, F(S)= .

i=\,L ,=i

Кроме этого, качество сформированного расписания оценивается степенью загрузки ресурсов ВС при решении задач.

Требуется найти расписание S* решения задач на вычислительной системе такое, чтобы суммарное время T(S*) решения задач и штраф F(S*) за задержку их решения были минимальными;

min T(S), - m

Sen Vi

при ограничениях:

min F(S), SeSl

2 r^ <iV,V/>0

(2) (3)

СеЕ(Г)

е {1,...,<7, }, 0 < $ < N, > 0, с, > 0, si > 0 где О - область допустимых расписаний 5,

Н(Г) = {/е {1,2,...,!} | х, </ < } - множество задач, решаемых в момент

времени /. Ограничение (3) гарантирует, что в каждый момент времени суммарный ранг задач не превосходит количества элементарных машин ВС.

Задача (1) - (3) относится к многокритериальной оптимизации. Для решения задачи (1) - (3) использовать метод приоритетов, задавая функции (1) приоритет выше, чем функции (2), и метод ортогональной упаковки прямоугольных объектов в контейнеры. При этом задача набора кодируется прямоугольником с шириной, равной г} и высотой . Повороты и пересечения прямоугольников не допускаются. Известно, что эта задача. является ЫР-сложной, поэтому актуальным является разработка алгоритмов ее приближенного решения. В связи с этим предложенные в работе алгоритмы осуществляют поиск не минимальных, а субминимальных показателей целевых функций. Оптимальность алгоритмов А№_2-4 оценивалась отклонением от нижней границы времени решения задач набора, рассчитываемой по формуле: Т =-Ттт(^

Таким образом, решение задачи (1) - (3) разбивается на два этапа. На первом этапе задачи набора группируются в подмножества таким образом, чтобы выполнялись ограничения (3) и достигался субминимум функции (1) (алгоритмы АЦЗ_>4). Подмножества задач будем называть укрупнёнными задачами Рассмотрены два варианта учёта показателя "удовлетворённости" пользователей. В первом случае (алгоритмы А1Х}_2-3), вводится дополнительное ограничение:

(4)

'П'шахи',

где е - минимально допустимая средняя "удовлетворённость" пользователей Алгоритм АЬС_1 позволяет выбрать параметры для масштабируемых задач так, чтобы выполнялось условие (4). Во втором случае показатель "удовлетворённости" пользователей вводится дополнительным параметром оптимизации в целевую функцию (1) (алгоритм АЬС_4). На втором этапе определяется последовательность решения укрупнённых задач (пакетов), позволяющая получить минимум функции (2) (алгоритм АЬС_5), при этом состав укрупнённых задач не изменяется. Алгоритм АЬвб позволяет из полученных в результате выполнения алгоритмов А1ЛЗ_1-5 укрупнённых задач, сформировать итоговое расписание.

Эвристический алгоритм псевдослучайного выбора конфигураций вычислительных ресурсов АШ_1. Целью алгоритма является формирование базовых расписаний для алгоритмов АЬ0 2-3. Определим условия необходимости применения данного алгоритма. Представим набор задач I в следующем виде: /°и/'и/2, где 1° - подмножество задач набора с одним элементом

вектора р1; Iх - подмножество задач набора, у которых все элементы вектора р1 имеют одинаковый приоритет; I2 - остальные задачи набора; 0 12

I гл1 =0.На выполнение ограничения (4) влияет лишь выбор одной из конфигураций ресурсов для задач из подмножества I2.

к

ШШ ГПШ11';

Утверждение 1. Если ]/°|-|-|/1| ^ или '

k

шах шах w,

eL- 1° -И

I2

то

ie.1 к

ограничение (4) выполняется при любом выборе параметров (конфигураций

ресурсов) для задач подмножества I2. Доказательство приведено в диссертации.

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

таким образом, что они либо совместно удовлетворяют ограничению (4), либо обладают наивысшим приоритетом.

Шаг 1. Для задач подмножества /2 значения к, выбираются произвольно.

Шаг 2. Вычисляются значения средней "удовлетворённости" пользователей при решении задач набора согласно текущему выбору их параметров.

Шаг 3. Произвольно выбирается задача из подмножества /2 и новое значение kj для неё.

Шаг 4. Если изменение приоритета значений параметров задачи не приводит к нарушению условия (4), то фиксируется к, и осуществляется переход к шагу 2; в противном случае значение ^ для выбранной задачи фиксируется.

Шаг 5. Процедура продолжается до тех пор, пока не будет перебраны все задачи подмножества I2.

Стохастический алгоритм ALG 2. Алгоритм являются итерационным. На каждой итерации случайным образом выбираются значения kt, /е{1,2,...,1} так, чтобы удовлетворять ограничению (4), и формируются укрупнённые задачи алгоритмом BFDH (Best-Fit Decreasing Height). Итерации повторяются до тех пор, пока на заданном количестве итераций не будет найдено разбиение задач набора с меньшим значением функции (1). Предложены две модификации алгоритма. В первом случае значения kt изменяются относительно базового разбиения набора задач. Во втором случае значения kj изменяются относительно текущего лучшего разбиения набора задач.

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

Для применения генетических алгоритмов для решения задачи (1), (3), необходимо:

- закодировать (представить) решение задачи формирования расписаний;

- определить функцию приспособленности (оптимизации);

- определить способ формирования базовой популяции;

- определить оператор скрещивания (кроссинговера);

- определить оператор мутации;

- определить способ выбора родительских пар и условия формирования новой популяции.

Генетический алгоритм минимизации времени решения задач набора АЮ_3. В терминах генетических алгоритмов будем считать, что:

- ген - это задача с определённым номером параметров ;

- особь - это совокупность генов для всех задач набора, удовлетворяющая ограничениям (3) - (4);

- популяция - это множество особей;

- функция приспособленности - это значение функции (1).

Базовая популяция формируется с применением алгоритма псевдослучайного выбора конфигураций вычислительных ресурсов АЬО_1.

Ниже представлен разработанный алгоритм кроссинговера (количество точек задаются одним из входных параметров алгоритма).

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

Шаг 2. Гены особи последовательно просматриваются слева направо. Достигая некоторой позиции (точки кроссинговера), родители начинают обмениваться друг с другом генами. Обмены продолжаются, пока не будет достигнута следующая точка кроссинговера. Таким образом, точки кроссинговера означают либо начало, либо окончание обмена генами между родителями.

Мутация - псевдослучайное изменение номера параметров задач к, для

псевдослучайного количества генов у особи.

Генетический алгоритм многокритериальной оптимизации (АШ_4). Для обеспечения максимальной "удовлетворённости" пользователей расширим задачу (1), (3) дополнительным условием:

L W*'

maxM(S), M(S) = V—(5) Sed ttrn axw,

t=i .i,

и определим функцию оптимизации:

шахQ(S),Q(S) = а■ M(S)/М^ T(S), (6)

SeCl

т. =—Yrnin

где M(S) - сумма "удовлетворённостей" пользователей; Мгоах - максимальная суммарная "удовлетворённость" пользователей; Гт-Ш - нижняя оценка времени решения задач набора; а , Р - коэффициенты, определяющие значимость (вес) параметра. Для решения задачи (5) - (6), (3), был разработан генетический алгоритм, в терминах которого будем считать, что:

- ген - это укрупнённая задача (пакет), состоящая из задач, для которых выбрана одна из возможных конфигураций ресурсов;

- особь - это совокупность генов, удовлетворяющая ограничениям (3);

- популяция - это множество особей;

- функция приспособленности - это значение функции (6).

Базовая популяция формируется с применением алгоритма BFDH, при этом номера параметров задач к, выбираются псевдослучайным образом.

В основу алгоритма кроссинговера положен метод перетасовки генов, реализованный следующим образом:

Шаг 1. Гены родительских особей помещаются в общий контейнер и сор-

—1 к■ к-

тируются по критерию "раскроя" (RmTm) 2 r¡ 'U' , где Rm ~ Ранг

í'eO(m)

укрупнённой задачи т, а Тт - время её решения; Ф{т) - множество задач

входящих в укрупнённую задачу т .

Шаг 2. Если в контейнере имеются одинаковые гены (с полностью одинаковыми задачами), то из двух генов удаляется тот, которому соответствует меньшее значение "раскроя".

Шаг 3. Полученная последовательность генов просматривается до тех пор, пока не встретится ген, в котором присутствует хотя бы одна задача,

входящая в ранее просмотренные гены. Если такой ген не найден (т.е. просмотрен весь контейнер), то алгоритм завершается.

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

Шаг 5. Из оставшихся задач по алгоритму ВРЭН создаются новые гены и помещаются обратно в контейнер.

Мутация с заданной вероятностью (задаётся параметром алгоритма) выполняется над одной или двумя родительскими особями. Оператор мутации псевдослучайным образом изменяет параметры задач, либо выбирает, для заданной доли задач особи, значения параметров, имеющие максимальный приоритет.

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

Алгоритм формирования последовательности решения укрупнённых задач с целью минимизации штрафа за задержку их решения (АШ_5).

На втором этапе определяется последовательность решения укрупнённых задач (пакетов), позволяющая получить минимум функции (2). Состав укрупнённых задач не изменяется.

Пусть 52=(т1,...,т1,...,тм) - некоторая последовательность решения пакетов, где /я/ - номер пакета, который будет решаться в 1-ю очередь. Штраф за решение задач при выбранной последовательности решения пакетов определяется как

М 1-1

= 21 Ст1 £ Ттг ' 1=2 г=1

где Ст; = _ штраф за задержку решения задач, входящих в т-й пакет.

1

Требуется найти такую последовательность 52, чтобы достичь минимума функции (2).

Доказано, что для последовательности укрупнённых задач справедливо: Утверждение 2. Для того, чтобы последовательность решения пакетов задач обеспечивала минимум функции (2), необходимо и достаточно, чтобы выполнялись неравенства

Т т Т Т

С«! Ст2 Ст, Стм

Доказательство приведено в диссертации.

Формирование итогового расписания. Алгоритм работы планировщика

(АШ_б). Итоговое расписание 5* = ((Ai.ii,-.(¿¿.¿л,^)) формируется * %

исходя из 51 и следующим образом. Для А, используются значения из

. Время начала решения определяется временем начала решения * *

укрупнённой задачи 5Г, в которую она была помещена. Время

определяется найденной последовательностью решения укрупнённых задач: * Г~1 *

яг = '£1Тт,$1=0. Ветви параллельных программ последовательно

/=1

назначаются на ЭМ распределённой ВС.

Моделирование. Моделирование и численные эксперименты осуществлялись с использованием ресурсов пространственно-распределённой мультикластерной вычислительной системы Центра параллельных вычислительных технология ФГОБУ ВПО "СибГУТИ". Предложенные алгоритмы реализованы с использованием языка программирования С++. Компиляция программ осуществлялась вЫШлСС с указанием максимально возможной степени оптимизации (-03). Наборы задач генерировались для систем с количеством ЭМ от 21 до 220. Рассматривались наборы с количеством задач 10, 100, 1000 и 10000. Приоритеты значениям параметров задач задавались путём их простой нумерации.

Процедура моделирования алгоритмов состояла из двух этапов: анализ влияния параметров алгоритмов на качество получаемого решения и сравнение алгоритмов между собой. На рис. 1. приведена диаграмма многокритериальной оптимизации, на которой приведены результаты моделирования и сравнения трёх решений задачи (5) - (6), (3), полученных разными способами. Решение № 1 соответствует лучшей особи из базовой популяции генетического алгоритма АЬО_4. Решение № 2 получено непосредственно алгоритмом АЬО_4. Решение № 3 полученно параллельным генетическим алгоритмом. Из диаграммы можно сделать вывод, что время выполнения алгоритмов, затраченное на поиск субоптимального решения, компенсируется уменьшением суммарного времени решения всех задач набора. Отклонение

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

Время формирования расписания по алгоритму, сек*10"3

Ы= 100, />= 0,9; L = 1000; S = 32; STEPSALG J = 5; е = fl.5,v = 4;

1 - Rand + BFDH; 2 - ALG_4; 3 - P ALG 6 - размер популяции; v - количество ветвей PALG; а = ß = 1 - весовые коэффициенты функции Q(S).

В третьей главе описана архитектура пространственно-распределённой мультикластерной ВС Центра параллельных вычислительных технологий ФГОБУ ВПО "СибГУТИ" и Лаборатории ВС ИФП СО РАН (рис. 1). Актуальная информация о конфигурации системы представлена на сайте ЦПВТ ФГОБУ ВПО "СибГУТИ" (http : //cpct. sibsutis. ru).

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

В состав программного обеспечения мультикластерной ВС включён разработанный программный пакет MOJOS, предназначенный для моделирования и отладки алгоритмов формирования расписаний решения масштабируемых задач на распределённых ВС. Пакет разработан на языке ANSI С для операционной системы GNU/Linux. В состав пакета входят нижеследующие компоненты.

Рис. 1. Конфигурация пространственно-распределённой мультикластериой вычислительной системы (февраль 2012 года)

1. Подсистема генерирования задач. Задачи генерируются на основе известных статистик поступления задач в распределённые ВС или с использованием моделей потоков задач. Масштабирование задач производится с использованием модели Downey. Приоритеты запросов задаются псевдослучайно с равномерным распределением.

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

3. Средства анализа эффективности сформированных расписаний решения задач.

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

В заключении сформулированы основные результаты, полученные в

диссертационной работе.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

основаны на стохастических, эвристических и эволюционных методах оптимизации и позволяют учитывать пользовательские приоритеты на размеры подсистем ЭМ для каждой масштабируемой задачи. Отклонение от нижней границы времени решения задач в среднем составило 15-20 %.

2. Построен эвристический алгоритм формирования последовательности решения укрупнённых задач на распределённых ВС, который обеспечивает субминимум суммарного штрафа за задержку решения задач набора (алгоритм ALG5).

3. Предложен алгоритм работы планировщика распределённых ВС (алгоритм ALG 6), который осуществляет формирование расписания обработки наборов масщтабируемых задач из последовательностей укрупнённых задач, полученных в результате совместного использования алгоритмов ALG_2-5.

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

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

Основные результаты диссертации опубликованы в работах [1-19].

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

1. Хорошеский, В.Г., Масштабируемый инструментарий параллельного мультипрограммирования пространственно-распределенных вычислительных систем [Текст] / В.Г. Хорошевский, М.Г. Курносое, С.Н. Мамойленко, К.В. Павский, A.B. Ефимов, A.A. Пазников, E.H. Перышкова // Вестник СибГУТИ. - Новосибирск: Изд-во «Сиб-ГУТИ», 2011. - № 11.-С. 3-18.-ISSN 1998-6920.

2. Ефимов, A.B. Организация функционирования распределенных вычислительных систем при обработке наборов масштабируемых задач [Текст] / A.B. Ефимов, С.Н. Мамойленко, E.H. Перышкова // Вестник ТГУ: Управление, вычислительная техника и информатика, - Томск: Изд-во HTJI, 2011. - №2(15). - С. 51-60. -ISSN 1998-8605.

3. Мамойленко, С.Н. Алгоритмы планирования решения масштабируемых задач на распределённых вычислительных системах [Текст] / С.Н. Мамойленко, A.B. Ефимов // Вестник СибГУТИ. - Новосибирск: Изд-во «СибГУТИ», 2010. - № 2. -С. 66 - 78.-ISSN 1998-6920.

4. Ефимов, A.B. Генетический алгоритм организации мультипрограммного функционирования распределенных вычислительных систем [Текст] / Ефимов A.B. // Пятая сибирская конференция по параллельным и высокопроизводительным вычислениям: материалы конференции. - Томск: Изд-во ТГУ, 2010, 01 - 03 декабря 2009 года. -С. 136- 139. - ISBN 978-5-7511-1942-3.

5. Хорошевский, В.Г. Планирование выполнения параллельных программ с нефиксированными параметрами на распределенных вычислительных системах [Текст] / В.Г. Хорошевский, С.Н. Мамойленко, A.B. Ефимов // Высокопроизводительные вычислительные системы (ВПВС-2010): материалы седьмой международной научной молодежной школы. - Таганрог: Изд-во ТТИ ЮФУ, 2010, 27 сентября -02 октября 2010. - С. 95 - 100. - ISBN 978-5-8327-0382-4.

6. Хорошевский, В.Г. Планирование выполнения параллельных программ с нефиксированными параметрами на распределенных вычислительных системах [Текст] / В.Г. Хорошевский, С.Н. Мамойленко, A.B. Ефимов // Суперкомпьютерные технологии: разработка, программирование, применение: материалы международной научно-технической конференции. - Таганрог: Изд-во ТТИ ЮФУ, 2010, 27 сентября - 02 октября 2010.-Т.2.-С. 97 - 101. - ISBN 978-5-8327-0383-1.

7. Ефимов, A.B. Формирование расписаний выполнения параллельных адаптирующихся программ на распределенных вычислительных системах [Текст] / А. В. Ефимов // Информационные технологии: материалы XLVIII международной научно-технической конференции «Студент и научно-технический прогресс». - Новосибирск: Изд-во НГУ, 2010,10 - 14 апреля 2010 года. - С. 297.

8. Максимова, E.H. Параллельный генетический алгоритм формирования расписания решения параллельных адаптирующихся задач на распределенных вычислительных системах [Текст] / E.H. Максимова, С.Н. Мамойленко, A.B. Ефимов // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО «СибГУТИ», 2010, 2728 апреля 2010 года. - Т. 1. - С. 163.

9. Мамойленко, С.Н. Организация мультипрограммного режима обработки набора параллельных адаптирующихся программ на распределенных вычислительных системах [Текст] / С.Н. Мамойленко, A.B. Ефимов II Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО «СибГУТИ», 2010,27 - 28 апреля 2010 года. - Т. 1. - С. 166.

10. Максимова, E.H. Эволюционный подход к формированию расписаний выполнения адаптирующихся программ на распределенной вычислительной системе [Текст] / E.H. Максимова, A.B. Ефимов, С.Н. Мамойленко // Новые информационные технологии в исследовании сложных структур: тезисы докладов Восьмой Российской кон-•ференции с международным участием. - Томск: Изд-во: НТЛ, 2010, 05 - 08 октября 2010 года. - С. 17. - ISBN 978-5-89503-440-8.

11. Максимова, E.H. Параллельный генетический алгоритм формирования расписаний решения масштабируемых задач на распределенных вычислительных системах [Текст] / E.H. Максимова, A.B. Ефимов, С.Н. Мамойленко // XI Всеросийская конференция молодых ученых по математическому моделированию и информационным технологиям: программа и тезисы докладов. - Новосибирск: Изд-во ИВТ СО РАН, 2010, Красноярск, 26 - 27 октября 2010 года. - С. 32.

12. Ефимов, A.B. Моделирование алгоритмов формирования расписаний решения масштабируемых задач на распределённых вычислительных системах [Текст] / A.B. Ефимов, С. Н. Мамойленко, E.H. Максимова // XIII Российская конференция с участием иностранных ученых «Распределенные информационные и вычислительные ресурсы» (DICR-2010): программа и тезисы докладов. - Новосибирск, 2010, 30 ноября - 03 декабря 2010 г. - С. 24.

13. Ефимов, A.B. Анализ эффективности планировщика MAUI на распределенных вычислительных системах / A.B. Ефимов // Материалы Российской научно-технической конференции «Информатика и проблемы телекоммуникаций». - Новосибирск: Изд-во СибГУТИ, 2009. - С. 122 - 123.

14. Ефимов, A.B. Генетический алгоритм распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / A.B. Ефимов // Материалы XLVII международной научно-технической конференции «Студент и научно-технический прогресс». - Новосибирск: Изд-во НГУ, 2009. - С. 206.

15. Ефимов, A.B. Генетический алгоритм распределения параллельных задач с нефиксированными параметрами по машинам распределенной вычислительной системы [Электронный ресурс] / A.B. Ефимов, С.Н. Мамойленко // II сессия научной школы-практикума молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования». 2009. - Режим доступа: (http://escience.ifmo.ru/files/hpc2009/thesises.pdf)

16. Мамойленко, С.Н. Формирование расписания выполнения набора параллельных адаптирующихся задач на распределенных вычислительных системах / С.Н. Мамойленко, A.B. Ефимов // Материалы международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (МВУС - 2009).- Таганрог: Изд-во ТИИ ЮФУ, 2009. Т. 1.- С. 200 - 202.

17. Мамойленко, С.Н. Генетический алгоритм распределения параллельных задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С.Н. Мамойленко, A.B. Ефимов // Программа и тезисы докладов «Пятая сибирская конференция по параллельным и высокопроизводительным вычислениям». -Томск: Изд-во ТГУ, 2009. - С. 69 - 71.

18. Мамойленко, С.Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С.Н. Мамойленко, H.A. Медведева, А. Ю. Поляков, А. В. Ефимов // Материалы Российской научно-технической конференции «Информатика и проблемы телекоммуникаций». - Новосибирск: Изд-во СибГУТИ, 2008. Т. 1. -С. 144 - 145 С.

19. Мамойленко, С.Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С.Н. Мамойленко, H.A. Медведева, А. Ю. Поляков, A.B. Ефимов // Тезисы докладов Седьмой Российской конференции с международным участием «Новые информационные технологии в исследовании сложных структур». - Томск: НТЛ.2008.-С. 70.

Ефимов Александр Владимирович

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать "16" февраля 2012 г.

Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд. л. 1,6, заказ № 12, тираж 150 экз., ФГОБУ ВПО "СибГУТИ". 630102, г. Новосибирск, ул. Кирова, д. 86.

61 12-5/2624

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ

БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ"

ОРГАНИЗАЦИЯ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В РЕЖИМЕ ОБРАБОТКИ НАБОРОВ МАСШТАБИРУЕМЫХ ЗАДАЧ

Специальность:

05.13.15 - Вычислительные машины, комплексы и компьютерные сети

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

Ефимов Александр Владимирович

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель -доктор технических наук профессор

член-корреспондент РАН заслуженный деятель науки РФ В. Г. Хорошевский

Новосибирск - 2012

СОДЕРЖАНИЕ

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ........................................................................4

ВВЕДЕНИЕ...................................................................................................................

ГЛАВА 1 ОСНОВЫ ОРГАНИЗАЦИИ ФУНКЦИОНИРОВАНИЯ

РАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.....................................14

1Л Понятие о распределённых вычислительных системах..............................14

1ЛЛ Модель коллектива вычислителей.........................................................14

1Л.2 Классификация архитектур вычислительных систем..........................16

1Л.З Функциональная организация распределённых ВС.............................20

1.2 Основные режимы функционирования ВС..................................................26

1.2 Л Монопрограммный режим......................................................................26

1.2.2 Мультипрограммный режим...................................................................26

1.3 Классификация задач......................................................................................27

1.4 Формирование расписания обработки наборов масштабируемых задач

на распределённых вычислительных системах.................................................32

1.4.1 Задача формирования расписаний.........................................................32

1.4.2 Обзор методов и алгоритмов формирования расписаний...................34

1.4.3 Методы кодирования расписаний..........................................................38

1.4.4 Обзор средств планирования..................................................................38

1.5 Выводы.............................................................................................................39

ГЛАВА 2 АЛГОРИТМЫ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В РЕЖИМЕ ОБРАБОТКИ НАБОРА МАСШТАБИРУЕМЫХ ЗАДАЧ..............................................................................40

2.1 Методы решения.............................................................................................40

2.2 Выбор параметров масштабируемых задач..................................................42

2.3 Формирование укрупненных задач с целью минимизации времени решения задач набора...........................................................................................44

2.3.1 Стохастический алгоритм.......................................................................46

2.3.2 Генетический алгоритм...........................................................................46

2.4 Многокритериальная оптимизация формирования укрупненных задач . 47

2

2.4.1 Последовательный генетический алгоритм с кроссинговером перетасовки генов.............................................................................................48

2.4.2 Параллельный генетический алгоритм с кроссинговером перетасовки генов.............................................................................................49

2.5 Формирование последовательности решения укрупнённых задач с целью минимизации штрафа за задержку их решения.....................................50

2.6 Формирование итогового расписания решения масштабируемых задач

на распределенных ВС..........................................................................................53

2.7 Моделирование алгоритмов формирования расписаний решения

задач на распределённых вычислительных системах.......................................54

2.8 Выводы.............................................................................................................64

ГЛАВА 3 ПРОСТРАНСТВЕННО РАСПРЕДЕЛЕННАЯ ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ.......66

3.1 Архитектура пространственно-распределенной мультикластерной вычислительной системы.....................................................................................66

3.2 Программное обеспечение пространственно-распределённой мультикластерной вычислительной системы....................................................68

3.2.1 Стандартные компоненты.......................................................................68

3.2.2 Пакет MOJOS поддержки мультипрограммных режимов

обработки наборов масштабируемых задач...................................................69

3.2.2 Интерфейс с системами пакетной обработки заданий.........................71

3.3 Выводы.............................................................................................................76

ЗАКЛЮЧЕНИЕ.........................................................................................................77

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ................................................79

ПРИЛОЖЕНИЯ.........................................................................................................98

Приложение 1 Сводная таблица алгоритмов.....................................................98

Приложение 2 Структурная организация сегментов мультикластерной

вычислительной системы.....................................................................................99

Приложение 3 Исходные тексты программ.....................................................102

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

АЛУ - арифметико-логическое устройство. БИС - большая интегральная схема. ВМ - вычислительный модуль. ВС - вычислительная система.

ИФПСОРАН - Федеральное государственное бюджетное учреждение науки Институт физики полупроводников им. A.B. Ржанова Сибирского отделения Российской академии наук. ЛК - локальный коммутатор. ЛП - локальная память.

МКМД - Множественный поток команд и множественный поток данных. МКОД - Множественный поток команд и одиночный поток данных. НИР - Научно-Исследовательская работа.

ОКМД - Одиночный поток команд и множественный поток данных. ОКОД - Одиночный поток команд и одиночный поток данных. ОС - операционная система. ПК - персональный компьютер. ПО - программное обеспечение.

СО АН СССР - Сибирское отделение Академии наук Союза Советских Социалистических Республик. СУ - системное устройство.

ФГОБУ ВПО "СибГУТИ" - Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования "Сибирский государственный университет телекоммуникаций и информатики". ЦПВТ - Центр параллельных вычислительных технологий. ЭВМ - электронная вычислительная машина. ЭМ - элементарная машина. ЭП - элементарный процессор. API - Application Programming Interface.

BFDH - Best-Fit Decreasing Height. FCFS - First Come First Serve. JSDL - Job Submission Description Language. LJF - Longest-Job-First.

MIMD - Multiple Instruction stream / Multiple Data stream. MISD - Multiple Instruction stream / Single Data stream. MOJOS - Moldable Jobs Scheduling MPI - Message Passing Interface. SAT - SATisfiability.

SIMD - Single Instruction stream / Multiple Data stream. SISD - Single Instruction stream / Single Data stream. SJF - Shortest-Job-First.

ВВЕДЕНИЕ

Актуальность работы. Возрастающая потребность в решении сложных задач науки, техники и экономики привела к созданию распределённых высокопроизводительных вычислительных систем (ВС). В общем случае распределённая ВС - это композиция множества элементарных машин (ЭМ) и сети межмашинных связей. Элементарная машина - это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до ЭВМ или специализированного ускорителя. Все основные ресурсы распределённых ВС (как аппаратурные, так и программные) являются логически и технически рассредоточенными. Количество ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч (например, в системе Fujitsu К Computer [85] количество вычислительных ядер равно 705 024).

Исследования в области распределённых вычислительных систем ведутся с середины XX столетия [23 - 27]. С тех пор в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную реализацию на распределённых ВС [4, 5, 7, 9, 10, 13, 18, 20-22, 99, 133, 134]. Построены отечественные вычислительные системы с программируемой структурой: «Минск-222», СУММА, МИНИМАКС, МИКРОС, МВС, СКИФ и др.

Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В.

Васильев, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, A.B. Забродин,

B.П. Иванников, М.Б. Игнатьев, A.B. Каляев, И.А. Каляев, JI.H. Королев,

C.А. Лебедев, В.К. Левин, Г.И. Марчук, Ю.И. Митропольский, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов,

A.A. Самарский, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров,

B.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, H.H. Яненко, а также зарубежные учёные: S. Cray, М. Flynn, I. Foster, D. Hillis, С. Kesselman, DL. Slotnick, A. Tanenbaum, D. Feitelson и другие. При решении проблем оптимизации функционирования распределённых ВС большую роль сыграли фундаментальные работы в области дискретной математики и исследовании операций советских и российских учёных: В.Л. Береснева, Э.Х. Гимади, В.Т. Дементьева, Ю.И. Журавлева, К.В. Рудакова и зарубежных - R. Bellmann, D. Johnson, М. Koffman, Н. Taha и других.

Эффективность использования ресурсов распределённых ВС во многом зависит от того, как организован процесс решения на них задач пользователей. В общем случае задачи представляются параллельными программами и описываются рядом параметров, в числе которых: количество ветвей (ранг необходимой подсистемы), время решения и т.п. В зависимости от характера поступления задач и их параметров принято выделять следующие режимы функционирования ВС [27]: решение сложной задачи, обработка набора задач и обслуживание потока задач. Первый режим является монопрограммным, для решения задачи используются все ресурсы ВС (все ЭМ). Два последних режима функционирования распределённых ВС относятся к мультипрограммным, при этом множество задач одновременно решается на системе, и её ресурсы разделяются между ними.

В режиме обработки набора задач на распределённой ВС требуется сформировать расписание их решения. Для каждой задачи необходимо определить подсистему ЭМ и момент запуска на выполнение ветвей соот-

ветствующей параллельной программы. Этот режим хорошо изучен для задач, параметры которых (ранг и время решения) заданы скалярными величинами, такие алгоритмы внедрены в системы пакетной обработки заданий (TORQUE, SLURM, Altair PBS Pro и др.).

Анализ пользовательских задач показывает [119], что более 80 % из них обладают свойством масштабируемости. Такие задачи допускают решение на подсистемах с различным количеством ЭМ и называются масштабируемыми или "пластичными" (moldable) [129]. Актуальной является задача разработки алгоритмических и программных средств организации функционирования распределённых ВС в мультипрограммном режиме обработки наборов масштабируемых задач.

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

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

В соответствии с целью определены нижеследующие задачи исследования.

1. Анализ современных подходов к организации функционирования распределённых ВС в мультипрограммных режимах.

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

3. Создание программных средств моделирования алгоритмов формирования расписаний решения пользовательских задач на распределённых ВС.

Методы исследования. Для решения поставленных задач использовались методы теории вычислительных систем, математического программирования, исследования операций и эволюционные методы оптимизации. Экспериментальные исследования осуществлялись путём моделирования на пространственно-распределённой мультикластерной ВС с применением методов системного, прикладного и объектно-ориентированного программирования.

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

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

Созданный программный пакет MOJOS - MOldable JObs Scheduling предназначен для моделирования, отладки и анализа алгоритмов формирования расписаний решения масштабируемых задач на распределённых ВС.

Программные средства внедрены в действующую пространственно-распределённую мультикластерную вычислительную систему Центра параллельных вычислительных технологий (ЦПВТ) ФГОБУ ВПО "СибГУТИ" и Лаборатории вычислительных систем Федерального государственного бюджетного учреждения науки Института физики полупроводников им. А.В. Ржанова Сибирского отделения РАН (ИФП СО РАН).

Реализация и внедрение результатов работы. Основные результаты диссертации нашли применение в работах по созданию и развитию пространственно-распределённой мультикластерной вычислительной системы ЦПВТ ФГОБУ ВПО "СибГУТИ" и Лаборатории ВС ИФП СО РАН.

Диссертационные исследования выполнялись в рамках федеральных целевых программ "Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007 - 2013 годы" (ГК № 02.514.11.0002 "Разработка программных технологий для развития российского сегмента Грид, систем параллельного программирования, систем компьютерной графики") и "Научные и научно-педагогические кадры инновационной России" (ГК № 02.740.11.0006 "Проведение исследований в области распределённых вычислительных систем и развитие научно-учебного центра параллельных вычислительных технологий ФГОБУ ВПО «СибГУТИ»"). Работа поддержана грантами грантами Президента РФ по поддержке молодых российских учены и ведущих научных школ (№ НШ-5176.2010.9, НШ-2175.2012.9, МК-2317.2012.9), Российского фонда фундаментальных исследований №09-07-13534, 08-07-00022, 09-07-00095, 11-07-00109, грантом мэрии г. Новосибирска молодым учёным № 10-11 (2011), а так же грантами ФГОБУ ВПО "СибГУТИ" (2009, 2010, 2011).

Внедрение результатов диссертационного исследования подтверждается соответствующими актами.

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

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

-Международной научно-технической конференции "Многопроцессорные вычислительные и управляющие системы" (с. Дивноморское Гелен-джикского района, 2009);

- Международной научно-технической конференции "Суперкомпьютерные технологии: разработка, программирование, применение" (с. Дивноморское Геленджикского района, 2010);

- Международной научно-технической конференции "Студент и научно-технический прогресс" (г. Новосибирск, 2009, 2010, 2011);

- Международной научной молодёжной школе "Высокопроизводительные вычислительные системы" (с. Дивноморское Геленджикского района, 2010);

-Российской конференции с международным участием "Новые информационные технологии в исследовании сложных структур" (г. Томск, 2008, 2010);

- Научной школе-практикуме для молодых учёных и специалистов "Технологии высокопроизводительных вычислений и компьютерного моделирования" (г. Санкт-Петербург, 2009);

- Российской научно-технической конференции "Информатика и проблемы телекоммуникаций" (г. Новосибирск, 2008, 2009, 2010, 2011);

- Российской конференции с участием иностранных учёных "Распределённые информационные и вычислительные ресурсы" (г. Новосибирск, 2010);

- Всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям (г. Красноярск, 2010);

- Пятой сибирской конференции по параллельным и высокопроизводительным вычислениям (г. Томск, 2009).

Публикации. По теме диссертации опубликовано 19 работ, из которых 3 - в изданиях из списка ВАК. Результаты исследований отражены

в отчётах по грантам и НИР.

Личный вклад. Все основные результаты диссертационной работы получены автором лично.

Основные положения диссертации, выносимые на защиту.

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

2. Программный пакет формирования и анализа расписаний решения масштабируемых задач на распределённых ВС (пакет