Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Ефимов Александр Владимирович
ОРГАНИЗАЦИЯ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЕНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В РЕЖИМЕ ОБРАБОТКИ НАБОРОВ МАСШТАБИРУЕМЫХ ЗАДАЧ
Специальность 05.13.15 - Вычислительные машины, комплексы и компьютерные сети
Автореферат диссертации на соискание ученой степени кандидата технических наук
Новосибирск - 2012
Работа выполнена на Кафедре вычислительных систем федерального государственного образовательного бюджетного учреждения высшего профессионального образования УСибирский государственный университет телекоммуникаций и информатикиФ Федерального агентства связи.
Научный руководитель - доктор технических наук профессор член-корреспондент РАН заслуженный деятель науки РФ Хорошевский Виктор Гаврилович
Официальные оппоненты: доктор технических наук старший научный сотрудник заведующий лабораторией ИВМиМГ СО РАН Хайретдинов Марат Саматович кандидат технических наук генеральный директор ОАО УРинетФ Майданов Юрий Сергеевич Ведущая организация - Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования УНациональный исследовательский Томский политехнический университетФ
Защита состоится У22Ф марта 2012 г. В У15Ф часов на заседании Диссертационного совета Д219.005.02 при ФГОБУ ВПО УСибирский государственный университет телекоммуникаций и информатикиФ, по адресу:
630102, г. Новосибирск, ул. Кирова, д. 86, ком. 625.
С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО УСибГУТИФ.
Автореферат разослан У____Ф __________________ 2012 г.
Учёный секретарь диссертационного совета Д219.005.кандидат технических наук доцент И. И. Резван
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Возрастающая потребность в решении сложных задач науки, техники привела к созданию распределённых вычислительных систем (ВС). В общем случае распределённая ВС - это композиция множества элементарных машин (ЭМ) и сети межмашинных связей. Элементарная машина - это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до ЭВМ или специализированного ускорителя. Все основные ресурсы распределённых ВС (как аппаратурные, так и программные) являются логически и технически рассредоточенными. Количество ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч (например, в системе Fujitsu K Computer количество вычислительных ядер равно 705 024).
Исследования в области распределённых вычислительных систем ведутся с середины XX столетия. С тех пор в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвящённых проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную реализацию на распределённых ВС. Построены отечественные вычислительные системы с программируемой структурой: Минск-222, СУММА, МИНИМАКС, МИКРОС, МВС, СКИФ и др.
Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, В.С. Бурцев, В.В. Васильев, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, А.В. Забродин, В.П. Иванников, М.Б. Игнатьев, А.В. Каляев, И.А. Каляев, Л.Н. Королев, С.А. Лебедев, В.К. Левин, Г.И. Марчук, Ю.И. Митропольский, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, А.А. Самарский, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко, а также зарубежные учёные: S. Cray, M. Flynn, I. Foster, D. Hillis, C. Kesselman, DL. Slotnick, A. Tanenbaum, D. Feitelson и другие. При решении проблем оптимизации функционирования распределённых ВС большую роль сыграли фундаментальные работы в области дискретной математики и исследовании операций советских и российских учёных: В.Л. Береснева, Э.Х. Гимади, В.Т. Дементьева, Ю.И. Журавлева, К.В. Рудакова и зарубежных - R. Bellmann, D. Johnson, M. Koffman, H. 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);
Ц Российской конференции с участием иностранных учёных УРаспределённые информационные и вычислительные ресурсыФ (г. Новосибирcк, 2010);
Ц Всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям (г. Красноярск, 2010);
Ц Пятой сибирской конференции по параллельным и высокопроизводительным вычислениям (г. Томск, 2009).
Публикации. По теме диссертации опубликовано 19 работ, из которых 3 - в изданиях из списка ВАК. Результаты исследований отражены в отчётах по грантам и НИР.
Основные положения диссертации, выносимые на защиту.
1. Семейство полиномиальных алгоритмов многокритериальной оптимизации мультипрограммного функционирования распределённых вычислительных систем в режиме обработки наборов масштабируемых задач.
2. Программные пакет формирования и анализа расписаний решения масштабируемых задач на распределённых ВС (пакет MOJOS), предусматривающий средства визуализации расписаний и интерфейс с системами пакетной обработки заданий.
Структура и объём диссертации. Диссертационная работа состоит из введения, трёх глав, заключения и списка литературных источников, изложенных на 97 страницах, а также приложений на 25 страницах.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении определены цели и задачи диссертационного исследования и обоснована его актуальность. Сформулированы основные положения, выносимые на защиту.
В первой главе определяются объект и предмет исследования. Объектом являются распределённые вычислительные системы, а предметом - алгоритмы организации их функционирования. Рассматриваются особенности вычислительных систем с программируемой структурой, кластерных, мультикластерных и GRID систем. Описываются основные режимы функционирования ВС, а так же иерархия средств управления распределёнными ВС.
Вводится понятие масштабируемой задачи, а также анализируются современные подходы и средства планирования решения таких задач на распределённых ВС.
Во второй главе сформулированы постановки решаемых в данной работе задач и предложены алгоритмы их решения.
Общая формулировка поставленной задачи следующая. Имеются распределённая ВС, состоящая из N элементарных машин, и набор I из L масштабируемых задач. Каждая задача i {1, 2,..., L} описывается вектором паi раметров pi = ( pi, pi2,..., piq ) и величиной штрафа за задержку её решения ci в единицу времени,.
ci > Каждый k-ый элемент вектора параметров pik = (rik,tik, wik ) означает, что для решения i-той задачи требуется выделить подсистему из rik элементарных машин на время tik, wik - приоритет данного размера подсистемы (определяемый пользователем). Показатель УудовлетворённостиФ пользователя выбором для решения i-ой задачи k-ой конфигурации, выражается как wik max wiz, z=1,qi где k {1, 2,..., qi}, 0 < rik N, tik > 0, wik > 0.
Считается, что в наборе присутствуют задачи с различным количеством параметров ( qi ). Допускается существование в векторе pi нескольких элементов с одинаковым приоритетом. Каждой ветви параллельной программы выделяется не более одной ЭМ. Любые две ЭМ могут взаимодействовать через сеть связи. Зависимости между величинами rik, tik, wik, ci отсутствуют.
Необходимо для каждой задачи i определить время si начала её решения, выбрать ki - номер элемента вектора pi и выделить множество номеров ЭМ Ji подсистемы необходимого размера. В результате должен быть сформирован вектор S = (k1, s1, J1),(k2, s2, J2),...,(kL, sL, JL), называемый расписанием решения задач на ВС.
Показателями эффективности расписаний являются время T(S) завершения решения последней задачи; суммарный штраф F(S) за задержку решения задач.
L T (S) = max{si + tiki }, F(S) = sic.
i i=1,L i=Кроме этого, качество сформированного расписания оценивается степенью загрузки ресурсов ВС при решении задач.
Требуется найти расписание S* решения задач на вычислительной системе такое, чтобы суммарное время T(S*) решения задач и штраф F(S*) за задержку их решения были минимальными;
minT(S), (1) S min F(S), (2) S при ограничениях:
riki N,t 0, (3) i(t) i i ki {1,..., qi}, 0 < rik N, tik > 0, si 0, ci > 0, где - область допустимых расписаний S, (t) = {i {1,2,..., L}| si t si + tiki } - множество задач, решаемых в момент времени t. Ограничение (3) гарантирует, что в каждый момент времени суммарный ранг задач не превосходит количества элементарных машин ВС.
Задача (1) - (3) относится к многокритериальной оптимизации. Для решения задачи (1) - (3) использовать метод приоритетов, задавая функции (1) приоритет выше, чем функции (2), и метод ортогональной упаковки прямоугольных объектов в контейнеры. При этом задача набора кодируется прямоугольником с шириной, равной rik и высотой tik. Повороты и пересечения прямоугольников не допускаются. Известно, что эта задача является NPсложной, поэтому актуальным является разработка алгоритмов её приближенного решения. В связи с этим предложенные в работе алгоритмы осуществляют поиск не минимальных, а субминимальных показателей целевых функций. Оптимальность алгоритмов ALG_2-4 оценивалась отклонением от нижней границы времени решения задач набора, рассчитываемой по формуL i i ле: Tmin = min (tik rik ).
ki =1,qi N i=Таким образом, решение задачи (1) - (3) разбивается на два этапа. На первом этапе задачи набора группируются в подмножества таким образом, чтобы выполнялись ограничения (3) и достигался субминимум функции (1) (алгоритмы ALG_2-4). Подмножества задач будем называть укрупнёнными задачами. Рассмотрены два варианта учёта показателя УудовлетворённостиФ пользователей. В первом случае (алгоритмы ALG_2-3), вводится дополнительное ограничение:
L i wik L-1 e, (4) max wik i=k =1,qi где - минимально допустимая средняя УудовлетворённостьФ пользоватеe лей. Алгоритм ALG_1 позволяет выбрать параметры для масштабируемых задач так, чтобы выполнялось условие (4). Во втором случае показатель УудовлетворённостиФ пользователей вводится дополнительным параметром оптимизации в целевую функцию (1) (алгоритм ALG_4). На втором этапе определяется последовательность решения укрупнённых задач (пакетов), позволяющая получить минимум функции (2) (алгоритм ALG_5), при этом состав укрупнённых задач не изменяется. Алгоритм ALG_6 позволяет из полученных в результате выполнения алгоритмов ALG_1-5 укрупнённых задач, сформировать итоговое расписание.
Эвристический алгоритм псевдослучайного выбора конфигураций вычислительных ресурсов ALG_1. Целью алгоритма является формирование базовых расписаний для алгоритмов ALG_2-3. Определим условия необходимости применения данного алгоритма. Представим набор задач I в следующем 0 2 виде: I I1 I, где I - подмножество задач набора с одним элементом вектора pi ; I1 - подмножество задач набора, у которых все элементы вектора pi имеют одинаковый приоритет; I - остальные задачи набора;
I0 I1 I = 0. На выполнение ограничения (4) влияет лишь выбор одной из конфигураций ресурсов для задач из подмножества I.
min min wik eL - I 0 - Ik 0 iI Утверждение 1. Если I + I1 eL или , то max max wik I k iI ограничение (4) выполняется при любом выборе параметров (конфигураций ресурсов) для задач подмножества I. Доказательство приведено в диссертации.
Если условия утверждения 1 не выполняются, то предлагается применять следующий алгоритм. Считаем, что для каждой задачи набора уже был выбран номер параметра одной из возможных конфигураций ресурсов, ki таким образом, что они либо совместно удовлетворяют ограничению (4), либо обладают наивысшим приоритетом.
Шаг 1. Для задач подмножества I значения выбираются произвольki но.
Шаг 2. Вычисляются значения средней УудовлетворённостиФ пользователей при решении задач набора согласно текущему выбору их параметров.
Шаг 3. Произвольно выбирается задача из подмножества I и новое значение для неё.
ki Шаг 4. Если изменение приоритета значений параметров задачи не приводит к нарушению условия (4), то фиксируется и осуществляется переход ki к шагу 2; в противном случае значение для выбранной задачи фиксируетki ся.
Шаг 5. Процедура продолжается до тех пор, пока не будет перебраны все задачи подмножества I.
Стохастический алгоритм ALG_2. Алгоритм являются итерационным.
На каждой итерации случайным образом выбираются значения, ki i {1, 2,..., L} так, чтобы удовлетворять ограничению (4), и формируются укрупнённые задачи алгоритмом BFDH (Best-Fit Decreasing Height). Итерации повторяются до тех пор, пока на заданном количестве итераций не будет найдено разбиение задач набора с меньшим значением функции (1). Предложены две модификации алгоритма. В первом случае значения изменяются ki относительно базового разбиения набора задач. Во втором случае значения ki изменяются относительно текущего лучшего разбиения набора задач.
Эволюционный метод оптимизации предусматривает последовательность жизненных циклов популяции. Каждый цикл состоит из следующих операций: выбора пар особей, их размножения, мутации и селекции наиболее приспособленных особей (формирования новой популяции). Процесс повторяется до тех пор, пока на протяжении заданного количества популяций не будет появляться особь c лучшим значением функции приспособленности. Итоговое разбиение задач набора формируется из особи, имеющей наилучшее значение функции приспособленности. Родительские пары выбираются псевдослучайным образом. Для формирования потомков были предложены операторы кроссинговера и мутации. В новую популяцию попадают особи с наивысшим значением функции приспособленности (не более заданного размера популяции).
Для применения генетических алгоритмов для решения задачи (1), (3), необходимо:
- закодировать (представить) решение задачи формирования расписаний;
- определить функцию приспособленности (оптимизации);
- определить способ формирования базовой популяции;
- определить оператор скрещивания (кроссинговера);
- определить оператор мутации;
- определить способ выбора родительских пар и условия формирования новой популяции.
Генетический алгоритм минимизации времени решения задач набора ALG_3. В терминах генетических алгоритмов будем считать, что:
- ген - это задача с определённым номером параметров ;
ki - особь - это совокупность генов для всех задач набора, удовлетворяющая ограничениям (3) - (4);
- популяция - это множество особей;
- функция приспособленности - это значение функции (1).
Базовая популяция формируется с применением алгоритма псевдослучайного выбора конфигураций вычислительных ресурсов ALG_1.
Ниже представлен разработанный алгоритм кроссинговера (количество точек задаются одним из входных параметров алгоритма).
Шаг 1. Для каждой точки кроссинговера случайным образом выбирается позиция между генами особи.
Шаг 2. Гены особи последовательно просматриваются слева направо. Достигая некоторой позиции (точки кроссинговера), родители начинают обмениваться друг с другом генами. Обмены продолжаются, пока не будет достигнута следующая точка кроссинговера. Таким образом, точки кроссинговера означают либо начало, либо окончание обмена генами между родителями.
Мутация - псевдослучайное изменение номера параметров задач для ki псевдослучайного количества генов у особи.
Генетический алгоритм многокритериальной оптимизации (ALG_4). Для обеспечения максимальной УудовлетворённостиФ пользователей расширим задачу (1), (3) дополнительным условием:
L i wik max M (S), M (S) =, (5) S max wik i=k =1,qi и определим функцию оптимизации:
maxQ(S),Q(S) = M (S) / Mmax + Tmin / T(S), (6) S L i i Tmin = min (tik rik ), ki 1,qi N i=где M (S) - сумма УудовлетворённостейФ пользователей; Mmax - максиTmin мальная суммарная УудовлетворённостьФ пользователей; - нижняя оценка времени решения задач набора; , - коэффициенты, определяющие значимость (вес) параметра. Для решения задачи (5) - (6), (3), был разработан генетический алгоритм, в терминах которого будем считать, что:
- ген - это укрупнённая задача (пакет), состоящая из задач, для которых выбрана одна из возможных конфигураций ресурсов;
- особь - это совокупность генов, удовлетворяющая ограничениям (3);
- популяция - это множество особей;
- функция приспособленности - это значение функции (6).
Базовая популяция формируется с применением алгоритма BFDH, при этом номера параметров задач выбираются псевдослучайным образом.
ki В основу алгоритма кроссинговера положен метод перетасовки генов, реализованный следующим образом:
Шаг 1. Гены родительских особей помещаются в общий контейнер и сортируются по критерию УраскрояФ (RmTm)-1 riki tiki, где - ранг Rm i(m) укрупнённой задачи, а - время её решения; - множество задач m Tm (m) входящих в укрупнённую задачу.
m Шаг 2. Если в контейнере имеются одинаковые гены (с полностью одинаковыми задачами), то из двух генов удаляется тот, которому соответствует меньшее значение УраскрояФ.
Шаг 3. Полученная последовательность генов просматривается до тех пор, пока не встретится ген, в котором присутствует хотя бы одна задача, входящая в ранее просмотренные гены. Если такой ген не найден (т.е. просмотрен весь контейнер), то алгоритм завершается.
Шаг 4. Оставшиеся гены контейнера расформировываются. Из получившихся задач удаляются повторяющиеся или присутствующие в не расформированных генах.
Шаг 5. Из оставшихся задач по алгоритму BFDH создаются новые гены и помещаются обратно в контейнер.
Мутация с заданной вероятностью (задаётся параметром алгоритма) выполняется над одной или двумя родительскими особями. Оператор мутации псевдослучайным образом изменяет параметры задач, либо выбирает, для заданной доли задач особи, значения параметров, имеющие максимальный приоритет.
Параллельный генетический алгоритм (P_ALG). Известно что, генетические алгоритмы хорошо приспособлены к распределённым вычислениям. Параллельная версия предложенного генетического алгоритма основана на декомпозиции и распределении исходного набора задач по нескольким вычислителям, на которых выполняется последовательный генетический алгоритм. В данном случае под особью будем понимать совокупность генов, сформированных из полученных вычислителем задач.
Таким образом, каждый вычислитель формирует часть общего расписания.
После окончания эволюции (количества жизненных циклов популяций без улучшения потомством значений функции приспособленности), наиболее приспособленные особи из каждой популяции объединяются в одну. На её основе будет формироваться итоговое расписание.
Алгоритм формирования последовательности решения укрупнённых задач с целью минимизации штрафа за задержку их решения (ALG_5).
На втором этапе определяется последовательность решения укрупнённых задач (пакетов), позволяющая получить минимум функции (2). Состав укрупнённых задач не изменяется.
Пусть S2 = (m1,..., ml,..., mM ) - некоторая последовательность решения пакетов, где ml - номер пакета, который будет решаться в l-ю очередь.
Штраф за решение задач при выбранной последовательности решения пакетов определяется как M l- F (S2 ) = Cml Tmr, l=2 r=где Cml = cim - штраф за задержку решения задач, входящих в m-й пакет.
i * Требуется найти такую последовательность S2, чтобы достичь минимума функции (2).
Доказано, что для последовательности укрупнённых задач справедливо:
Утверждение 2. Для того, чтобы последовательность решения пакетов задач обеспечивала минимум функции (2), необходимо и достаточно, чтобы выполнялись неравенства Tm1 Tm2 Tml TmM ... ... .
Cm1 Cm2 Cml CmM Доказательство приведено в диссертации.
Формирование итогового расписания. Алгоритм работы планировщика (ALG_6). Итоговое расписание S* = (k1, s1, J1),...,(kL, sL, JL ) формируется * * исходя из S1 и S2 следующим образом. Для ki используются значения из * S1. Время начала решения si определяется временем начала решения укрупнённой задачи s*, в которую она была помещена. Время s* r r определяется найденной последовательностью решения укрупнённых задач:
r-* s* = Tml, s1 = 0. Ветви параллельных программ последовательно r l=назначаются на ЭМ распределённой ВС.
Моделирование. Моделирование и численные эксперименты осуществлялись с использованием ресурсов пространственно-распределённой мультикластерной вычислительной системы Центра параллельных вычислительных технология ФГОБУ ВПО ФСибГУТИФ. Предложенные алгоритмы реализованы с использованием языка программирования C++. Компиляция программ осуществлялась GNU\GCC с указанием максимально возможной степени оптимизации (Ц03). Наборы задач генерировались для систем с количеством ЭМ от 21 до 220. Рассматривались наборы с количеством задач 10, 100, 1000 и 10000. Приоритеты значениям параметров задач задавались путём их простой нумерации.
Процедура моделирования алгоритмов состояла из двух этапов: анализ влияния параметров алгоритмов на качество получаемого решения и сравнение алгоритмов между собой. На рис. 1. приведена диаграмма многокритериальной оптимизации, на которой приведены результаты моделирования и сравнения трёх решений задачи (5) - (6), (3), полученных разными способами. Решение № 1 соответствует лучшей особи из базовой популяции генетического алгоритма ALG_4. Решение № 2 получено непосредственно алгоритмом ALG_4. Решение № 3 полученно параллельным генетическим алгоритмом. Из диаграммы можно сделать вывод, что время выполнения алгоритмов, затраченное на поиск субоптимального решения, компенсируется уменьшением суммарного времени решения всех задач набора. Отклонение от нижней границы времени решения задач в среднем составило 15 %. Рост коэффициента ускорения параллельного генетического алгоритма получился близким к линейному.
Время формирования расписания по алгоритму, сек*10-№ 4,№ № 0,1,5,5,8,M(S), *1T(S), сек*1Рис. 1. Пример результатов моделирования:
N = 100; P = 0,9; L = 1000; = 32; STEPSALG_4 = 5; е = 0,5; v = 4;
1 - Rand + BFDH; 2 - ALG_4; 3 - P_ALG - размер популяции; v - количество ветвей P_ALG;
= = 1 - весовые коэффициенты функции Q(S).
В третьей главе описана архитектура пространственно-распределённой мультикластерной ВС Центра параллельных вычислительных технологий ФГОБУ ВПО УСибГУТИФ и Лаборатории ВС ИФП СО РАН (рис. 1). Актуальная информация о конфигурации системы представлена на сайте ЦПВТ ФГОБУ ВПО УСибГУТИФ (
Основное назначение пространственно-распределённой мультикластерной ВС - исследование архитектуры распределённых ВС, отработка инструментария параллельного мультипрограммирования, моделирование сложных физико-технических процессов и природных явлений, а так же подготовка специалистов и научно-педагогических кадров высокой квалификации в области распределённых вычислительных технологий.
В состав программного обеспечения мультикластерной ВС включён разработанный программный пакет MOJOS, предназначенный для моделирования и отладки алгоритмов формирования расписаний решения масштабируемых задач на распределённых ВС. Пакет разработан на языке ANSI C для операционной системы GNU/Linux. В состав пакета входят нижеследующие компоненты.
Рис. 1. Конфигурация пространственно-распределённой мультикластерной вычислительной системы (февраль 2012 года) 1. Подсистема генерирования задач. Задачи генерируются на основе известных статистик поступления задач в распределённые ВС или с использованием моделей потоков задач. Масштабирование задач производится с использованием модели Downey. Приоритеты запросов задаются псевдослучайно с равномерным распределением.
2. Модуль формирования расписаний решения масштабируемых задач. В пакете реализованы алгоритмы формирования расписаний решения задач, основанные на методах упаковки прямоугольных объектов в контейнеры и полубесконечную полосу, а так же алгоритмы, предложенные в главе 2.
3. Средства анализа эффективности сформированных расписаний решения задач.
В пакете MOJOS предусмотрены средства графического представления сформированных расписаний решения задач с помощью пакета gnuplot.
В заключении сформулированы основные результаты, полученные в диссертационной работе.
В приложениях приведены сводные данные о предложенных алгоритмах и описание структурной организации сегментов мультикластернной ВС.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ Предложен подход к организации функционирования распределённых ВС в мультипрограммном режиме обработки наборов масштабируемых задач.
1. Разработано семейство полиномиальных алгоритмов многокритериальной оптимизации мультипрограммного функционирования распределённых ВС в режиме обработки наборов масштабируемых задач. Алгоритмы основаны на стохастических, эвристических и эволюционных методах оптимизации и позволяют учитывать пользовательские приоритеты на размеры подсистем ЭМ для каждой масштабируемой задачи. Отклонение от нижней границы времени решения задач в среднем составило 15 - 20 %.
2. Построен эвристический алгоритм формирования последовательности решения укрупнённых задач на распределённых ВС, который обеспечивает субминимум суммарного штрафа за задержку решения задач набора (алгоритм ALG_5).
3. Предложен алгоритм работы планировщика распределённых ВС (алгоритм ALG_6), который осуществляет формирование расписания обработки наборов масштабируемых задач из последовательностей укрупнённых задач, полученных в результате совместного использования алгоритмов ALG_2-5.
4. Разработан программный пакет MOJOS для моделирования и анализа алгоритмов формирования расписаний решения масштабируемых задач на распределённых ВС, который, в частности, предусматривает интерфейс с современными системами пакетной обработки заданий. Показано что, время выполнения алгоритмов, затраченное на поиск субоптимального расписания, компенсируется уменьшением суммарного времени решения всех задач набора.
5. При непосредственном участии диссертанта создана пространственнораспределённая мультикластерная ВС, которая, помимо стандартных средств параллельного мультипрограммирования, оснащена разработанным инструментарием формирования расписаний, позволяющим решать масштабируемые задачи на ресурсах системы.
Основные результаты диссертации опубликованы в работах [1Ц19].
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Хорошеский, В.Г., Масштабируемый инструментарий параллельного мультипрограммирования пространственно-распределенных вычислительных систем [Текст] / В.Г. Хорошевский, М.Г. Курносов, С.Н. Мамойленко, К.В. Павский, А.В. Ефимов, А.А. Пазников, Е.Н. Перышкова // Вестник СибГУТИ. - Новосибирск: Изд-во СибГУТИ, 2011. - № 11. - С. 3-18. - ISSN 1998-6920.
2. Ефимов, А.В. Организация функционирования распределенных вычислительных систем при обработке наборов масштабируемых задач [Текст] / А.В. Ефимов, С.Н. Мамойленко, Е.Н. Перышкова // Вестник ТГУ: Управление, вычислительная техника и информатика, - Томск: Изд-во НТЛ, 2011. - № 2(15). - С. 51-60. - ISSN 1998-8605.
3. Мамойленко, С.Н. Алгоритмы планирования решения масштабируемых задач на распределённых вычислительных системах [Текст] / С.Н. Мамойленко, А.В. Ефимов // Вестник СибГУТИ. - Новосибирск: Изд-во СибГУТИ, 2010. - № 2. - С. 66 - 78. - ISSN 1998-6920.
4. Ефимов, А.В. Генетический алгоритм организации мультипрограммного функционирования распределенных вычислительных систем [Текст] / Ефимов А.В. // Пятая сибирская конференция по параллельным и высокопроизводительным вычислениям: материалы конференции. - Томск: Изд-во ТГУ, 2010, 01 - 03 декабря 2009 года. - С. 136 - 139. - ISBN 978-5-7511-1942-3.
5. Хорошевский, В.Г. Планирование выполнения параллельных программ с нефиксированными параметрами на распределенных вычислительных системах [Текст] / В.Г. Хорошевский, С.Н. Мамойленко, А.В. Ефимов // Высокопроизводительные вычислительные системы (ВПВС-2010): материалы седьмой международной научной молодежной школы. - Таганрог: Изд-во ТТИ ЮФУ, 2010, 27 сентября - 02 октября 2010. - С. 95 - 100. - ISBN 978-5-8327-0382-4.
6. Хорошевский, В.Г. Планирование выполнения параллельных программ с нефиксированными параметрами на распределенных вычислительных системах [Текст] / В.Г. Хорошевский, С.Н. Мамойленко, А.В. Ефимов // Суперкомпьютерные технологии: разработка, программирование, применение: материалы международной научнотехнической конференции. - Таганрог: Изд-во ТТИ ЮФУ, 2010, 27 сентября - 02 октября 2010. - Т.2. - С. 97 - 101. - ISBN 978-5-8327-0383-1.
7. Ефимов, А.В. Формирование расписаний выполнения параллельных адаптирующихся программ на распределенных вычислительных системах [Текст] / А. В. Ефимов // Информационные технологии: материалы XLVIII международной научно-технической конференции Студент и научно-технический прогресс. - Новосибирск: Изд-во НГУ, 2010, 10 - 14 апреля 2010 года. - С. 297.
8. Максимова, Е.Н. Параллельный генетический алгоритм формирования расписания решения параллельных адаптирующихся задач на распределенных вычислительных системах [Текст] / Е.Н. Максимова, С.Н. Мамойленко, А.В. Ефимов // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО СибГУТИ, 2010, 27 - 28 апреля 2010 года. - Т. 1. - С. 163.
9. Мамойленко, С.Н. Организация мультипрограммного режима обработки набора параллельных адаптирующихся программ на распределенных вычислительных системах [Текст] / С.Н. Мамойленко, А.В. Ефимов // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО СибГУТИ, 2010, 27 - 28 апреля 2010 года. - Т. 1. - С. 166.
10. Максимова, Е.Н. Эволюционный подход к формированию расписаний выполнения адаптирующихся программ на распределенной вычислительной системе [Текст] / Е.Н. Максимова, А.В. Ефимов, С.Н. Мамойленко // Новые информационные технологии в исследовании сложных структур: тезисы докладов Восьмой Российской конференции с международным участием. - Томск: Изд-во: НТЛ, 2010, 05 - 08 октября 2010 года. - С. 17. - ISBN 978-5-89503-440-8.
11. Максимова, Е.Н. Параллельный генетический алгоритм формирования расписаний решения масштабируемых задач на распределенных вычислительных системах [Текст] / Е.Н. Максимова, А.В. Ефимов, С.Н. Мамойленко // XI Всеросийская конференция молодых ученых по математическому моделированию и информационным технологиям: программа и тезисы докладов. - Новосибирск: Изд-во ИВТ СО РАН, 2010, Красноярск, 26 - 27 октября 2010 года. - С. 32.
12. Ефимов, А.В. Моделирование алгоритмов формирования расписаний решения масштабируемых задач на распределённых вычислительных системах [Текст] / А.В. Ефимов, С. Н. Мамойленко, Е.Н. Максимова // XIII Российская конференция с участием иностранных ученых Распределенные информационные и вычислительные ресурсы (DICR-2010): программа и тезисы докладов. - Новосибирск, 2010, 30 ноября - 03 декабря 2010 г. - С. 24.
13. Ефимов, А.В. Анализ эффективности планировщика MAUI на распределенных вычислительных системах / А.В. Ефимов // Материалы Российской научнотехнической конференции Информатика и проблемы телекоммуникаций. - Новосибирск: Изд-во СибГУТИ, 2009. - С. 122 - 123.
14. Ефимов, А.В. Генетический алгоритм распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / А.В.
Ефимов // Материалы XLVII международной научно-технической конференции Студент и научно-технический прогресс. - Новосибирск: Изд-во НГУ, 2009. - С. 206.
15. Ефимов, А.В. Генетический алгоритм распределения параллельных задач с нефиксированными параметрами по машинам распределенной вычислительной системы [Электронный ресурс] / А.В. Ефимов, С.Н. Мамойленко // II сессия научной школы-практикума молодых ученых и специалистов Технологии высокопроизводительных вычислений и компьютерного моделирования. 2009. - Режим доступа:
( 16. Мамойленко, С.Н. Формирование расписания выполнения набора параллельных адаптирующихся задач на распределенных вычислительных системах / С.Н. Мамойленко, А.В. Ефимов // Материалы международной научно-технической конференции Многопроцессорные вычислительные и управляющие системы (МВУС - 2009).Ц Таганрог: Изд-во ТИИ ЮФУ, 2009. Т. 1.Ц С. 200 - 202.
17. Мамойленко, С.Н. Генетический алгоритм распределения параллельных задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С.Н. Мамойленко, А.В. Ефимов // Программа и тезисы докладов Пятая сибирская конференция по параллельным и высокопроизводительным вычислениям. - Томск: Изд-во ТГУ, 2009. - C. 69 - 71.
18. Мамойленко, С.Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / C.Н. Мамойленко, Н.А. Медведева, А. Ю. Поляков, А. В. Ефимов // Материалы Российской научно-технической конференции Информатика и проблемы телекоммуникаций. - Новосибирск: Изд-во СибГУТИ, 2008. Т. 1. - C. 144 - 145 С.
19. Мамойленко, С.Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / C.Н. Мамойленко, Н.А. Медведева, А. Ю. Поляков, А.В. Ефимов // Тезисы докладов Седьмой Российской конференции с международным участием Новые информационные технологии в исследовании сложных структур. - Томск:
НТЛ, 2008. - C. 70.
Ефимов Александр Владимирович Организация функционирования распределенных вычислительных систем в режиме обработки наборов масштабируемых задач Автореферат диссертации на соискание ученой степени кандидата технических наук Подписано в печать У16Ф февраля 2012 г.
Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд. л.1,6, заказ № 12, тираж 150 экз., ФГОБУ ВПО УСибГУТИФ.
630102, г. Новосибирск, ул. Кирова, д. 86.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям