close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
ФИО соискателя: Мамойленко Сергей Николаевич Шифр научной специальности: 05.13.15 - вычислительные машины, комплексы и компьютерные сети Шифр диссертационного совета: Д 219.005.02 Название организации: Сибирский государственный университет телекомму
На правах рукописи
Мамойленко Сергей Николаевич
ОРГАНИЗАЦИЯ ФУНКЦИОНИРОВАНИЯ
РАСПРЕДЕЛ?ННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
В МУЛЬТИЗАДАЧНЫХ РЕЖИМАХ
Специальность 05.13.15 Вычислительные машины,
комплексы и компьютерные сети
Автореферат
диссертации на соискание учјной степени
доктора технических наук
Новосибирск 2012
Работа выполнена в Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования ѕСибирский
государственный университет телекоммуникаций и информатикиї Федерального агентства связи.
Научный консультант:
доктор технических наук профессор
член-корреспондент РАН
заслуженный деятель науки РФ
Хорошевский Виктор Гаврилович
Официальные оппоненты:
доктор физико-математических наук профессор
академик РАН
Шокин Юрий Иванович
директор
Института вычислительных технологий СО РАН
доктор технических наук профессор
Глинский Борис Михайлович
заведующий лабораторией ѕСибирский
суперкомпьютерный центрї
Института вычислительной математики и
математической геофизики СО РАН
доктор технических наук профессор
Цапко Геннадий Павлович
заведующий Кафедрой автоматики
и компьютерных систем
Национального исследовательского
Томского политехнического университета
Ведущая организация:
Научно-исследовательский институт
многопроцессорных вычислительных
систем имени академика А.В. Каляева
Федерального государственного автономного
образовательного учреждения высшего
профессионального образования
Южный федеральный университет
Защита состоится ѕ 29 ї мая 2012 г. в
1500
часов на заседании диссертаци-
онного совета Д 219.005.02 при ФГОБУ ВПО ѕСибирский государственный
университет телекоммуникаций и информатикиї по адресу: 630102, г. Новосибирск, ул. Кирова, д. 86, ауд. 625.
С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО ѕСибГУТИї.
Автореферат разослан ѕ__ї________ 2012 г.
Учјный секретарь
диссертационного совета Д 219.005.02
кандидат технических наук, доцент
И. И. Резван
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Распределјнные вычислительные системы (ВС)
являются современным инструментарием обработки информации (список
Top500 (Ноябрь, 2011) суперкомпьютеров мира). В Российской Федерации
технологии и программное обеспечение распределјнных и высокопроизводительных ВС относят к критически важным (указ Президента Российской
Федерации от 7 июля 2011 г. ? 899).
Исследования в области распределјнных ВС ведутся с середины XX столетия. С тех пор в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвящјнных проблемам организации высокопроизводительных
вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг
задач, допускающих эффективную реализацию на распределјнных ВС. Построены отечественные вычислительные системы с программируемой структурой: ѕМинск 222ї, СУММА, МИНИМАКС, МИКРОС, МВС, СКИФ и др.
Фундаментальный вклад в теорию и практику вычислительных систем и
параллельных вычислительных технологий внесли советские, российские и
зарубежные
учјные,
среди
которых:
Е. П.
Балашов,
В. Б.
Бетелин,
В. С. Бурцев, В. В. Васильев, В. М. Глушков, В. Ф. Евдокимов, Э. В. Евреинов,
А. В. Забродин, В. П. Иванников, М. Б. Игнатьев, А. В. Каляев, И. А. Каляев,
Л. Н.
Королјв,
С. А.
Лебедев,
А. О.
Лацис,
В. К.
Левин,
И. И.
Левин,
Г. И. Марчук, Ю. И. Митропольский, Д. А. Поспелов, И. В. Прангишвили,
Д. В. Пузанков, Г. Е. Пухов, Г. Г. Рябов, А. А. Самарский, В. Б. Смолов,
А. Н. Томилин, Я. А. Хетагуров, В. Г. Хорошевский, Б. Н. Четверушкин,
Ю. И. Шокин, Н. Н. Яненко, S. Cray, M. Flynn, D. Feitelson, I. Foster, D. Hillis,
C. Kesselman, DL. Slotnick, A. Tanenbaum и другие.
В общем случае распределјнная ВС это композиция множества элементарных
машин
(ЭМ)
и
сети
межмашинных
связей.
Элементарная
машина это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах от процессорного ядра до ЭВМ или специализированного ускорителя. Все основные
ресурсы распределјнных ВС (как аппаратурные, так и программные) являются логически и технически рассредоточенными. Количество ЭМ в распределјнных ВС допускает варьирование от нескольких единиц до сотен тысяч.
Например, в системе Fujitsu K Computer количество вычислительных ядер
Современные распределјнные ВС являются мультархитектурными, масштабируемыми и большемасштабными средствами обработки информации, что определяет сложность организации их функционирования
равно 705 024.
.
Задачи, решаемые на распределјнных ВС, представляются параллельны-
ми программами и описываются рядом параметров, в числе которых: коли-
3
чество требуемых ЭМ, время решения, штраф за задержку решения и т.п.
В зависимости от характера поступления задач и их параметров принято
выделять следующие режимы функционирования ВС: решение сложной задачи, обработка набора задач и обслуживание потока задач. Первый режим
является монопрограммным, для решения задачи используются все ресурсы распределјнной ВС (все ЭМ). Два последних режима функционирования
распределјнных ВС относятся к мультизадачным, при этом ресурсы системы разделяются между несколькими одновременно решаемыми задачами.
Огромные возможности распределјнных ВС по решению различных задач
могут быть использованы и раскрыты только при применении эффективных методов и средств параллельного мультипрограммирования
.
На практике широко используется и хорошо изучен режим обработки на-
боров задач, параметры которых заданы скалярными величинами. Повысить
эффективность функционирования распределјнных ВС возможно, если, в
частности, задачи допускают решение на подсистемах с различным количеством ЭМ. Такие задачи называются масштабируемыми или ѕпластичнымиї
(moldable). Исследования пользовательских запросов показывают, что свойством масштабируемости обладают более 80% задач. Также важно разрабатывать децентрализованные методы и алгоритмы управления ресурсами
распределјнных ВС при обслуживании потоков задач.
Проблема организации эффективного функционирования распределјнных
ВС трудноразрешима
. Поэтому разработка приближјнных методов и эври-
стических алгоритмов организации функционирования распределјнных ВС
в мультизадачных режимах актуальна.
Цель работы
организация эффективного функционирования распре-
делјнных ВС в мультизадачных режимах и создание инструментария параллельного мультипрограммирования распределјнных ВС.
Для достижения поставленных целей необходимо решение следующих
за-
дач исследования:
•
анализ и обобщение современного состояния и тенденций развития подходов к организации функционирования распределјнных ВС в мультизадачных режимах;
•
создание методов, алгоритмов и программных средств организации
функционирования распределјнных ВС в режимах обработки наборов
и обслуживании потоков задач;
•
развитие пространственно-распределјнной мультикластерной вычислительной системы и формирование инструментария параллельного мультипрограммирования.
Методы исследования. В области организации функционирования распределјнных ВС исследования проводились с использованием методов тео-
4
рии вычислительных систем, теории игр, математического программирования, исследования операций, теории вероятностей и эволюционных методов
оптимизации. Экспериментальные исследования осуществлялись путјм моделирования на пространственно-распределјнной мультикластерной ВС.
Научная новизна работы
•
определяется следующим:
разработано семейство (последовательных и параллельных) алгоритмов организации функционирования распределјнных ВС в режиме обработки наборов масштабируемых задач, учитывающих штраф за задержку решения и приоритеты выбора значений параметров задач;
•
созданы средства оптимизации функционирования распределјнных ВС
в режиме обработки потоков задач. Определены смешанные стратегии
функционирования диспетчеров и планировщиков распределјнной ВС;
•
определены смешанные стратегии функционирования распределјнной
ВС при обслуживании интенсивных потоков задач на неабсолютно надјжных ресурсах.
Практическая ценность работы
состоит в том, что созданные ал-
горитмы и программные средства входят в состав инструментария параллельного мультипрограммирования распределјнных ВС. Разработана система MOJOS (англ. MOldable JObs Scheduling), предназначенная для моделирования, отладки и анализа алгоритмов организации функционирования
распределјнных ВС. Программные средства внедрены в действующую пространственно-распределјнную мультикластерную ВС Центра параллельных
вычислительных технологий (ЦПВТ) ФГОБУ ВПО СибГУТИ и Лаборатории вычислительных систем Федерального государственного бюджетного
учреждения науки Института физики полупроводников им. А. В. Ржанова
Сибирского отделения Российской академии наук (ИФП СО РАН).
Реализация и внедрение результатов работы. Основные результаты
исследований нашли применение в работах по созданию и развитию пространственно-распределјнной мультикластерной ВС ЦПВТ ФГОБУ ВПО
СибГУТИ и Лаборатории ВС ИФП СО РАН. Диссертационные исследования выполнялись в рамках федеральных целевых программ ѕИсследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годыї (ГК ?02.514.11.0002
ѕРазработка программных технологий для развития российского сегмента
Грид, систем параллельного программирования, систем компьютерной графикиї) и ѕНаучные и научно-педагогические кадры инновационной Россииї
(ГК ?02.740.11.0006 ѕПроведение исследований в области распределјнных
вычислительных систем и развитие научно-учебного центра параллельных
вычислительных технологий ФГОБУ ВПО СибГУТИї). Работа поддержана грантами Российского фонда фундаментальных исследований (? 00-01-
5
00126, 02-07-06099, 02-07-09380, 03-07-06008, 08-07-00022, 09-07-00095, 11-0700109), грантами Президента РФ по поддержке молодых российских учјных и ведущих научных школ (?НШ-2121.2008.9, НШ-5176.2010.9, НШ2175.2012.9, МК-2317.2012.9), а так же грантами ФГОБУ ВПО СибГУТИ
(2008-2011 гг.). Результаты работы внедрены в учебный процесс Сибирского
государственного университета телекоммуникаций и информатики. Практическое использование результатов диссертационных исследований подтверждается соответствующими актами о внедрении.
Достоверность
подтверждается проведјнными экспериментами и моде-
лированием, согласованностью с данными, имеющимися в отечественной и
зарубежной литературе и экспертизами работы, прошедшими при получении
грантов.
Апробация работы.
Основные результаты работы докладывались на
Международных, Всероссийских и Региональных научных конференциях, в
том числе:
•
Международной научно-технической конференции ѕИнтеллектуальные
и многопроцессорные системыї (2003 г., г. Геленджик);
•
Международной научно-технической конференции ѕМногопроцессорные вычислительные и управляющие системыї (2009 г., с. Дивноморское Геленджикского района);
•
Международной научно-технической конференции ѕСуперкомпьютерные технологии: разработка, программирование, применениеї (2010 г.,
с. Дивноморское Геленджикского района);
•
Международной научно-технической конференции ѕСтудент и научнотехнический прогрессї (2009-2011 гг., г. Новосибирск);
•
Международной научной молодјжной школе ѕВысокопроизводительные вычислительные системыї (2010 г., с. Дивноморское Геленджикского района);
•
Российской конференции с международным участием ѕНовые информационные
технологии
в
исследовании
сложных
структурї
(2008,
2010 гг., г. Томск);
•
Научной школе-практикуме для молодых учјных и специалистов ѕТехнологии высокопроизводительных вычислений и компьютерного моделированияї (2009 г., г. Санкт-Петербург);
•
Международной научно-технической конференции ѕИнформатика и проблемы телекоммуникацийї (2001-2011 гг., г. Новосибирск);
6
•
Международной научно-технической конференции ѕИнформационные
системы и технологииї (2003 г., г. Новосибирск);
•
Первой Всероссийской научной конференции ѕМетоды и средства обработки информацииї (2003 г., г. Москва);
•
Региональной научной конференции студентов, аспирантов и молодых
учјных ѕНаука. Техника. Инновацииї (2002, 2003 гг., г. Новосибирск);
•
Школе-семинаре ѕРаспределјнные кластерные вычисленияї (2001 г., г.
Красноярск).
•
Научно-техническом семинаре ФГОБУ ВПО СибГУТИ (ежегодно);
Публикации. По теме диссертации опубликовано 63 работы, в том числе
9 в изданиях из перечня ВАК.
Основные положения диссертации, выносимые на защиту.
1. Разработано семейство (последовательных и параллельных) алгоритмов организации функционирования распределјнных ВС в режиме обработки наборов масштабируемых задач, учитывающих штраф за задержку решения и приоритеты выбора значений параметров задач.
2. Созданы средства оптимизации функционирования распределјнных ВС
в режиме обработки потоков задач. Определены смешанные стратегии
функционирования диспетчеров и планировщиков распределјнной ВС.
3. Сформирован инструментарий параллельного мультипрограммирования пространственно-распределјнной мультикластерной ВС. В состав
инструментария включјн пакет моделирования и анализа алгоритмов
организации функционирования распределјнных ВС. С использованием этого пакета проведено моделирование предложенных в работе алгоритмов.
Структура и объјм диссертации.
Диссертация состоит из введения,
четырјх глав, заключения, списка литературы, включающего 350 наименований, и приложения. Текст содержит 18 рисунков.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во
введении
раскрыта актуальность темы диссертации, сформулиро-
ваны цели исследований и основные задачи, которые необходимо решить
для их достижения, определена практическая ценность и кратко излагаются
структура и основные результаты работы, а также представлены положения,
выносимые на защиту.
7
В
первой главе
описываются объект и предмет исследований, вводятся
основные понятия, используемые в тексте диссертации (задача, параметры
задачи, и т.д.), приведено описание режимов функционирования распределјнных ВС. Представлен анализ известных методов организации функционирования распределјнных ВС в мультизадачных режимах, рассмотрены
наиболее распространјнные средства их поддержки.
Объектом исследований
дований
являются распределјнные ВС.
Предмет иссле-
организация функционирования распределјнных ВС в мультиза-
дачных режимах функционирования.
Подготовив программу(ы) и необходимые для неј данные пользователь
описывает, каким образом эта программа должна быть выполнена на распределјнной ВС, т.е. формирует для распределјнной ВС
задачу
. Описание
задачи включает в себя значения ряда параметров, например: количество
требуемых ЭМ (ранг задачи), максимальное время выполнения программы,
ограничения, накладываемые на выделяемые ЭМ (например, наличие графического сопроцессора). Для описания задач чаще всего используются специализированные языки, например JSDL (англ. Job Submission Description
Language). Также могут задаваться дополнительные характеристики задач,
в том числе штраф за задержку решения задач, очередь, в которую помещается задача и т.п.
В зависимости от способа задания значений параметров задачи принято разделять на: ѕфиксированныеї (англ. rigid), ѕмасштабируемыеї (англ.
moldable) и ѕадаптирующиесяї (англ. evolving и malleable).
задачи
Фиксированные
требуют для выполнения программ чјтко заданное количество ЭМ
на определјнное время. Для таких задач значения соответствующих параметров задаются скалярными величинами.
щиеся
Масштабируемые адаптируюи
задачи допускают выполнение программ на подсистемах с различным
количеством ЭМ и временем выполнения. Параметры таких задач задаются
диапазоном или вектором значений. При этом, для масштабируемых задач
размер подсистемы ЭМ для выполнения программ выбирается один раз перед началом их решения и не меняется. Адаптирующиеся задачи допускают
изменение количества ЭМ в процессе их решения. Исследования пользовательских запросов показывают, что свойством масштабируемости обладают
более 80% задач.
Решение задач на распределјнных ВС осуществляется в режиме пакетной обработки. В таком режиме пользователь формирует задачу, после чего
передајт еј в систему управления ресурсами распределјнной ВС. Порядок
обслуживания задач и их запуск на решение определяются режимом функционирования распределјнной ВС и алгоритмами диспетчеризации и планирования.
Математические методы, алгоритмы и программы, организующие работу
ВС в мультизадачных режимах, составляют
8
инструментарий параллельного
мультипрограммирования
. Этот инструментарий должен быть практически
эффективным. Он не должен приводить к временным затратам ВС, существенно уменьшающим долю системного времени, приходящуюся на реализацию пользовательских программ. Эффективность инструментария должна
оцениваться такими же количественными характеристиками, как и параллельные алгоритмы: показателями сложности, коэффициентами ускорения
и накладных расходов.
На практике широко используется и хорошо изучен режим обработки
наборов фиксированных задач. Наибольшее распространение получили системы TORQUE, Altair PBS Pro, Oracle Grid Engine, IBM LoadLeveler. Для
планирования решения задач наборов чаще всего используются алгоритмы:
FCFS (англ. First-Come-First-Served), SJF (англ. Shortest-Job-First), LJF (англ. Longest-Job-First), а так же технологии Backlling и
Gang Scheduling, поз-
воляющие увеличить эффективность решения задач с небольшим временем
решения. Существуют алгоритмы, учитывающие несколько критериев при
планировании решения задач (например ранг задач и время решения). Системы пакетной обработки, используемые на практике, допускают наличие
в очередях масштабируемых задач и позволяют пользователям указывать
значения ранга в виде множества или диапазона. Планировщики обычно используют свойство масштабируемости, выбирая первое подходящее значение
ранга и не учитывая время решения. Известны алгоритмы выбора значений
параметров задач путјм их ранжирования, исходя из прогнозируемой загрузки ВС или предполагаемого характера поступления задач.
Во
второй главе
рассматривается режим обработки наборов масштаби-
руемых задач. Предложен подход к организации функционирования распределјнных ВС при решении масштабируемых задач с учјтом пользовательских приоритетов выбора значений параметров задач и штрафа за задержку
решения задач. Описаны разработанные алгоритмы формирования расписаний решения масштабируемых задач на распределјнных ВС.
Постановка задачи.
Имеется распределјнная ВС, состоящая из
ментарных машин. На вход системы поступил набор
I = {Ii }
N
эле-
независимых
i = 1, L, где L количество задач в наборе. Каждая задача Ii = ?pi , ci ?
pi = (p1i , p2i , . . . , pqi i ) и величиной штрафа
ci за задержку еј решения в единицу времени, qi количество элементов в
k
k k
k
векторе pi , qi ? 1, ci > 0. Элемент вектора параметров pi = (ri , ti , wi ) ознаk
чает, что с приоритетом wi для решения i-той задачи требуется выделить
k
k
k
k
k
подсистему из ri ЭМ на время ti , 0 < ri ? N , ti > 0, wi > 0, k = 1, qi .
Считается, что в наборе присутствуют задачи с различным qi количеством параметров. Допускается существование в векторе pi нескольких элезадач,
описывается вектором параметров
ментов с одинаковым приоритетом. Каждой ветви параллельной программы
должно быть выделено не более одной ЭМ; одна ЭМ не может быть назначена для выполнения более, чем одной ветви параллельной программы. Любые
9
две ЭМ могут взаимодействовать через сеть связи. Зависимости между веk k
k
личинами ri , ti , wi , ci отсутствуют.
для каждой задачи Ii определить время si начала еј решения,
Требуется
выбрать
ki
номер элемента вектора
pi
и выделить множество ЭМ
Ji
(под-
систему ЭМ необходимого размера). В результате должен быть сформирован
вектор
S = ?(k1 , s1 , J1 ), (k2 , s2 , J2 ), . . . , (kL , sL , JL )?, называемый расписани-
ем решения задач набора
на распределјнной ВС. Расписание должно
быть сформировано так, чтобы значение некоторого критерия (или нескольких критериев) было наилучшим. О критериях, используемых в данной диссертации, будет сказано ниже.
Выбор значений
ki ? {1, . . . , qi }
определяет ѕудовлетворјнностьї пользо-
вателей сформированным расписанием решения задач набора
W (S) = L?1
L
?
wiki
.
max wik
i=1 k=1,q
i
В работе предложена следующая
ния масштабируемых задач
схема формирования расписаний реше-
(рисунок 1). В основу этой схемы положена
идея формирования расписаний решения фиксированных задач с использованием ѕукрупнјнныхї задач, предложенная в середине XX века в работах
Д. А. Поспелова и В. Г. Хорошевского, и в дальнейшем получившая широкое
распространение.
Рисунок 1 Процедура формирования расписаний решения
масштабируемых задач
Формирование расписаний решения задач набора предложено осуществлять в три этапа. На первом этапе формируются ѕукрупнјнныеї задачи подмножества задач набора, одновременно запускаемые на решение на распределјнной ВС и разделяющие еј ресурсы. Ранг ѕукрупнјннойї задачи не
превышает количество ЭМ в распределјнной ВС, а время еј решения определяется максимальным временем решения входящих в неј задач набора.
На втором этапе определяется последовательность запуска ѕукрупнјнныхї
задач на решение. На третьем этапе, исходя из сформированных ѕукрупнјнныхї задач и последовательности их запуска на решение, строится итоговое
расписание решения задач набора.
10
Этап 1. Формирование укрупнјнных задач
.
Постановка задачи
первого этапа имеет следующий вид. Решением за-
S1 = (K, M, ?), где K = ?k1 , k2 , . . . , kL ? вектор выбранных для задач значений ki , M = |?| количество формируемых ѕукрупнјнныхї задач, ? = {?m } множество ѕукрупнјнныхї задач, ?m = {Ii ? I},
i ? {1, 2, . . . , L}. Время решения ѕукрупнјнныхї задач определяется как
дачи будет тройка
T (S1 ) =
M
?
m=1
Требуется
определить решение
S1?
max tki i .
Ii ??m
такое, чтобы:
T (S1? ) = min T (S1 ),
S1 ??1
при ограничениях:
?
riki ? N,
m = 1, M ,
(1)
(2)
Ii ??m
M
?
|?m | = L,
m=1
где
?1
M
?
?m = ?.
(3)
m=1
область допустимых решений
S1 .
Ограничение (2) определяет, что
суммарный ранг задач, входящих в каждую ѕукрупнјннуюї задачу, не превосходит количество ЭМ распределјнной ВС. Ограничение (3) гарантирует,
что все задачи набора распределены по ѕукрупнјннымї задачам, и каждая
из задач набора находится только в одной ѕукрупнјннойї задаче и пустых
ѕукрупнјнныхї задач не сформировано.
В работе предложено два способа учјта ѕудовлетворјнностиї пользователей при формировании ѕукрупнјнныхї задач.
Способ 1. Задано ограничение на значение средней ѕудовлетворјнностиї
пользователей
.
В систему ограничений вводится дополнительное условие, определяющее
минимальную допустимую среднюю ѕудовлетворјнностьї пользователей
W (S1 ) ? e.
e
(4)
Для формирования ѕукрупнјнныхї задач с учјтом ограничения (4) предложены следующие алгоритмы.
ki
)
Эвристический алгоритм 1 (однократный случайный выбор значений
. Алгоритм заключается в случайном выборе для всех задач набора зна-
чений
ki
так, чтобы удовлетворялось ограничение (4), и использовании из-
вестных алгоритмов формирования ѕукрупнјнныхї задач для наборов фиксированных задач.
11
Представим набор задач
I
в следующем виде:
I0
?
множество задач набора с одним элементом вектора
?
I 1 I 2 , где I 0 подpi ; I 1 подмножество
задач набора, у которых все элементы вектора pi имеют одинаковый прио? 1? 2
2
0
ритет; I остальные задачи набора; I
I
I = ?. Очевидно, что на
выполнение ограничения (4) влияет лишь выбор ki для задач подмножеI 2 . В работе определено условие возможности случайного выбора для
ства
задач значений
ki .
min min wik
|
Если |I 0| + |I 1| ? eL или max max w > AL?|I|I |?|I
, то
|
ограничение (4) выполняется при любом выборе параметров (конфигураций
ресурсов) для задач набора.
Ii ?I 2
Утверждение 1.
Ii ?I 2
k
k
k
i
0
1
2
В случае, когда утверждение 1 не выполняется, предлагается применять
следующий алгоритм выбора значений
Шаг 0
ние
ki
ki .
. Считаем, что для каждой задачи набора уже было выбрано значе-
таким образом, что удовлетворялось ограничение (4). Например, для
каждой задачи может быть выбран параметр с наивысшим приоритетом.
1
. Для задач подмножества I значения ki выбираются произвольно.
Шаг 1
Шаг 2
Шаг 3
ki
Шаг 4
. Вычисляется значение средней ѕудовлетворјнностиї пользовате-
лей при решении задач набора согласно текущему выбору их параметров.
2
. Произвольно выбирается задача из подмножества I и новое значение
для неј.
. Если изменение
ki
не приводит к нарушению условия (4), то
ki
фиксируется и осуществляется переход к шагу 2; в противном случае значение
ki
не изменяется.
Шаг 5
I2
Стохастический алгоритм 2 (многократный случайный выбор значений
множества ki)
. Процедура продолжается до тех пор, пока не будут перебраны все
задачи подмножества
.
. Алгоритм 2 является обобщением алгоритма 1. Суть алго-
ритма заключается в итерационном выполнении алгоритма 1 до тех пор,
пока не будет найден выбор значений
ki ,
который позволяет получить раз-
биение задач набора на ѕукрупнјнныеї задачи, имеющее лучшее значение
целевой функции (1). Предложены две модификации алгоритма. В первом
случае перед выполнением алгоритма 1 значения
ki
для задач набора вы-
бираются так, чтобы параметры имели наивысший приоритет и наименьшее
запрашиваемое время решения задачи. Во втором случае для алгоритма 1
значениями
ki
являются текущие ѕлучшиеї значения, найденные на преды-
дущих итерациях.
Эволюционный алгоритм
3 (поиск решения генетическим алгоритмом).
Эволюционные методы оптимизации предусматривают последовательность
жизненных циклов популяции. Каждый цикл состоит из: выбора пар особей, их размножения, мутации и селекции наиболее приспособленных особей
12
(формирования новой популяции). Процесс повторяется до тех пор, пока на
протяжении заданного количества популяций не будут появляться особи c
лучшими значениями функции приспособленности.
В терминах генетических алгоритмов в работе предложено следующее
кодирование решения задачи (1)-(4):
-
ген
особь
это задача с выбранным значением
ki ;
это совокупность генов. При этом, у каждого гена значение
выбрано так, чтобы удовлетворялось ограничение (4);
-
популяция
функция приспособленности
это множество особей;
это значение функции (1), получаемое
после разбиения задач набора с выбранными значениями
ki
на ѕукруп-
нјнныеї задачи.
Начальная популяция формируется с помощью алгоритма 1 (однократного случайного выбора значений
ki ). Родительские пары выбираются случай-
ным образом. Предложен следующий многоточечный оператор кроссинговера (количество точек задајтся одним из входных параметров оператора).
Шаг 1
Шаг 2
. Для каждой точки кроссинговера случайным образом выбирается
позиция между генами особи.
. Гены особи последовательно просматриваются слева направо. До-
стигая точки кроссинговера, родители начинают обмениваться друг с другом
генами. Обмены продолжаются, пока не будет достигнута следующая точка
кроссинговера.
Оператор
мутации
случайным образом изменяет значения
ki
для неко-
торого (случайного) количества генов у особи.
В новую популяцию попадают особи с наилучшим значением функции
приспособленности. Размер популяции (количество особей) в процессе эволюции не меняется.
Итоговое решение формируется из особи, имеющей наилучшее значение
функции приспособленности.
Случай 2. Средняя ѕудовлетворјнностьї пользователей является целевой функцией
.
Функция
W (S1 )
средней ѕудовлетворјнностиї пользователей рассматри-
вается как вторая целевая функция для задачи (1)-(4):
W (S1? ) = max W (S1 )
S1 ??1
(5)
Задача (1)(4),(5) относится к многокритериальной оптимизации. Для еј
решения предложено использовать метод весовых коэффициентов, формируя из двух целевых функций (1) и (5) одну следующим образом:
Q(S1 ) = ?W (S1 )/Wmax + ?Tmin /T (S1 ),
13
(6)
где
Wmax
Tmin =
бора;
максимальная суммарная ѕудовлетворјнностьї пользователей;
L
{
}
?
min rik · tki нижняя оценка времени решения задач наN ?1
i=1 k?1,qi
?, ?
весовые коэффициенты (значения определяются методом экс-
пертных оценок или экспериментальным путјм).
?
Требуется найти S1 такое, чтобы
Q(S1? ) = max Q(S1 ),
S1 ??1
(7)
при ограничениях (2)-(3).
Эволюционный алгоритм
4 (поиск решения многокритериальной задачи
генетическим алгоритмом). В терминах генетических алгоритмов решение
задачи кодируется следующим образом:
-
ген
ѕукрупнјннаяї задача, состоящая из задач, для каждой из ко-
торых выбрано значение
-
ki ;
особь
функция приспособленности
множество ѕукрупнјнныхї задач;
это значение функции (6).
Начальная популяция формируется с применением случайного выбора
ki
значений
и формирования ѕукрупнјнныхї задач алгоритмом Best-Fit-
Decreasing-Height (BFDH).
На основе известного метода перетасовки генов предложен следующий
оператор кроссинговера:
Шаг 1
. Гены родительских особей помещаются в общий контейнер и сор-
тируются
?1
(Rm Tm )
по
критерию
ѕзагрузки
вычислительных
ресурсовї
? { ki ki }
ri ti , где Rm ранг ѕукрупнјннойї задачи m, а Tm i??m
время еј решения.
Шаг 2
. Если в контейнере имеются гены, содержащие одинаковые задачи,
но с разными значениями
ki ,
то из двух генов удаляется тот, которому соот-
ветствует меньшее значение критерия ѕзагрузки вычислительных ресурсовї.
Шаг 3
. Полученная последовательность генов просматривается до тех
пор, пока не встретится ген, в котором присутствует хотя бы одна задача,
входящая в ранее просмотренные гены. Если такой ген не найден (т.е. просмотрен весь контейнер), то алгоритм завершается.
Шаг 4
. Оставшиеся гены контейнера расформировываются. Из получив-
шихся задач удаляются повторяющиеся или присутствующие в нерасформированных генах.
Шаг 5
. Из оставшихся задач по алгоритму BFDH создаются новые гены
и помещаются обратно в контейнер.
14
Оператор
мутации
с заданной вероятностью выполняется над одной или
двумя родительскими особями, случайным образом изменяя у задач значения
ki .
Параллельный эволюционный алгоритм
5 (поиск решения многокрите-
риальной задачи параллельным генетическим алгоритмом). Известно, что
генетические алгоритмы хорошо приспособлены к распределјнным вычислениям. Суть предложенного параллельного алгоритма в декомпозиции и
распределении исходного набора задач по нескольким вычислителям, на которых выполняется алгоритм 4. Таким образом, каждый вычислитель формирует часть общего расписания. Окончательное решение формируется из
наиболее приспособленных особей каждой популяции.
Проведено
моделирование
предложенных
алгоритмов
формирования
ѕукрупнјнныхї задач. Предложенные алгоритмы реализованы с использованием языка программирования C++. Компиляция программ осуществлялась GNU\GCC с указанием максимально возможной степени оптимизации.
1
20
Наборы задач генерировались для систем с количеством ЭМ от 2 до 2 . Рассматривались наборы с количеством задач 10, 100, 1000 и 10000. Приоритеты
значениям параметров задач задавались путјм их простой нумерации. Моделирование показало, что алгоритмы эффективны, они обеспечивают субминимум времени решения задач набора, который отличается от нижней грани
в среднем на 15 20% (рисунок 2).
Рисунок 2 Влияние параметров алгоритмов 2 (а и б) и 3 (в и г)
на качество их работы.
(L
= 10000, e = 0.50 (a и в), e = 0.95 (б и г) )
15
Этап 2. Определение последовательности запуска ѕукрупнјнныхї задач
на решение
.
На втором этапе определяется последовательность решения ѕукрупнјнныхї задач, позволяющая получить минимум штрафа за задержку решения
задач набора. Состав ѕукрупнјнныхї задач не меняется.
Постановка задачи второго этапа следующая. Пусть задана некоторая
S2 = (m1 , . . . , ml , . . . , mM ) решения ѕукрупнјнныхї заml номер ѕукрупнјннойї задачи, которая будет решаться в l-ю
очередь, l = {1, . . . , M }. Штраф F (S2 ) за решение задач при выбранной попоследовательность
дач, где
следовательности решения пакетов определяется как
F (S2 ) =
где
Cml =
пакет,
T mr
?
Ii ??ml
M ?
l?1
?
{Cml Tmr },
(8)
l=2 r=1
ci
штраф за задержку решения задач, входящих в
время решения
mr -ой
ml -й
ѕукрупнјннойї задачи.
S2? , чтобы достичь минимума
Требуется найти такую последовательность
функции (8).
Утверждение 2. Для того чтобы последовательность решения ѕукрупнјнныхї задач обеспечивала минимум функции (8), необходимо и достаточно, чтобы выполнялись неравенства:
Tm1
Tm2
Tml
TmM
.
?
? ··· ?
? ··· ?
Cm1
Cm2
Cml
CmM
(9)
Последовательность может быть найдена любым известным методом сортировки.
Этап 3. Формирование итогового расписания решения задач
.
?
Итоговое расписание S = ?(k1 , s1 , J1 ), . . . , (kL , sL , JL )?, формируется исS1? и S2? , следующим образом.
?
1. Для ki используются значения из S1 .
ходя из
2. Время начала решения задачи si определяется временем начала реs?l , в которую она была помещена. Время s?l
определяется найденной последовательностью решения ѕукрупнјнныхї заl?1
?
?
?
дач: s1 = 0, sl =
Tmr .
r=1
3. Ветви параллельных программ последовательно назначаются на ЭМ
шения ѕукрупнјннойї задачи
распределјнной ВС.
В
третьей главе
описана организация функционирования распределјн-
ных ВС в режиме обслуживания потоков задач, сформулированы задачи организации оптимального использования вычислительных ресурсов, рассмотрены методы их решения и предложены параллельные версии этих методов.
16
функционирования распределјнных ВС в режиме обслуживания потоков задач
В работе предложена схема организации
(рисунок 3).
Рисунок 3 Схема функционирования распределјнной ВС в режиме
обслуживания потоков задач
В систему поступает несколько независимых потоков задач. Каждая за-
?ti , ri ?, где ti максимальное время решения i-ой
ri еј ранг. Время поступления и параметры каждой задачи слу-
дача описывается парой
задачи, а
чайные величины. Считается, что интенсивности потоков настолько высоки,
что в очередях присутствуют задачи всех рангов (на практике это условие
легко удовлетворить, если задачи обладают свойством масштабируемости).
При этом, интенсивности потоков задач различны.
В системе функционирует группа
диспетчеров
элементов распределјн-
ной операционной системы, каждый из которых обслуживает один поток задач. Каждый диспетчер из задач потока формирует ѕукрупнјнныеї задачи с
заданными характеристиками. Сформированные ѕукрупнјнныеї задачи помещаются в
очередь ѕукрупнјнныхї задач
. Множество локальных очередей
диспетчеров формирует распределјнную очередь ѕукрупнјнныхї задач.
В режиме обслуживания потоков задач ресурсы распределјнной ВС случайным образом разделяются на подсистемы ЭМ, каждая из которых управляется отдельным
планировщиком
(также элементом распределјнной опера-
ционной системы). Планировщики ВС выбирают из распределјнной очереди
ѕукрупнјнныеї задачи и организовывают их решение. Если очередь ѕукрупнјнныхї задач оказывается пустой, то ресурсы распределјнный ВС простаивают.
В диссертации с использованием методов теории игр разработаны алгоритмы поиска стратегий случайного выбора: 1) ранга ѕукрупнјнныхї задач;
2) времени решения ѕукрупнјнныхї задач и 3) последовательности опроса
распределјнной очереди ѕукрупнјнныхї задач.
17
Выбор рангов ѕукрупнјнныхї задач
.
r, а для еј реi ЭМ, то издержки диспетчера могут
Если диспетчер сформировал ѕукрупнјннуюї задачу ранга
шения планировщиком будет выделено
быть оценены как:
cir
c1
где
{
rc1 + (i ? r)c2
=
ic2 + (r ? i)c3
при
при
i ? r,
i < r,
цена эксплуатации одной ЭМ в единицу времени;
(10)
c2
величина
штрафа, выплачиваемого диспетчером в единицу времени за одну простаивающую ЭМ;
c3
величина штрафа, налагаемого на диспетчера в единицу
времени, если он сформировал ѕукрупнјннуюї задачу с рангом, большим на
единицу числа выделенных ЭМ, т. е.
r = i + 1, i, r = 0, N ; N
число ЭМ в
вычислительной подсистеме.
Рассматриваемая математическая модель относится к классу многоходовых антагонистических игр с нулевой суммой. Издержки диспетчера при
формировании ѕукрупнјнныхї задач различных рангов и выделении подсистем для их решения составляют матрицу платежей:
C = ?cir ?.
На практике часто встречается ситуация, при которой в потоке имеются
задачи различных рангов. Поэтому алгоритм функционирования диспетчера, состоящий в формировании ѕукрупнјнныхї задач только одного ранга,
представляется неэффективным. Следовательно, рассматриваемая модель
не должна иметь решения в чистых стратегиях, т. е. матрица
C = ?cir ?
не
должна иметь седловых точек. В работе доказано следующее утверждение.
Утверждение 3. Матрица C = ?cir ? не имеет седловых точек тогда и
только тогда, когда:
c1 < c2 ,
c3 > N c1 ? (N ? 1)c2 .
(11)
Несмотря на высокую надјжность современной элементной базы, на которой строятся распределјнные ВС, в них могут происходить отказы ресурсов.
Под
отказом
понимается невозможность одной или нескольких ЭМ выпол-
нять свои функции. Причины и формы отказов (отказ каналов, полный и
частичный отказы и т.п.), в данном случае, значения не имеют. Поэтому выделение требуемой подсистемы ЭМ может оказаться невозможным или будет
выделено больше ЭМ для организации отказоустойчивого режима функционирования.
В работе предложен
алгоритм
, позволяющий формировать ѕукрупнјн-
ныеї задачи так, чтобы, учитывая возможные отказы, сократить простой
вычислительных ресурсов.
В этом случае алгоритм функционирования диспетчера может быть представлен в виде топологического дерева (рисунок 4). Нулевой ход осуществляется случайным механизмом и определяет текущее состояние системы (наличия
k
исправных ЭМ,
0 ? k ? N ).
Вероятность
18
pk
того, что в стационарном
режиме работы в системе имеется
k
исправных ЭМ может быть найдена
известными методами теории вычислительных систем.
Рисунок 4 Топологическое дерево алгоритма формирования
ѕукрупнјнныхї задач
Первый ход осуществляется планировщиком. Он выделяет подсистему из
i
ЭМ,
0 ? i ? k.
Второй ход делает диспетчер. Независимо от состояния си-
стемы и хода, который сделал планировщик, он выбирает для формирования
ѕукрупнјннойї задачи ранг
r, 0 ? r ? N .
Для ѕсокрытияї информации о состоянии системы в работе предложено
изменить коэффициенты платјжной матрицы следующим образом:
c?ir = cir p?i ,
(12)
N
?
pk . Очевидно, что p?i ? p?j , при i < j , i, j ? {0, 1, . . . , n}. Таk=i
кое изменение коэффициентов справедливо потому, что планировщик может
где
p?i =
выделить
i
ЭМ только в случаях, когда
k?i
. Достоверность такого изме-
нения может быть установлена при рассмотрении исходной матрицы платежей, в которой строки строго доминируют в соотношении вероятностей
состояния ВС.
Как и в случае абсолютно надјжных распределјнных ВС, функционирование диспетчера, при котором он формирует ѕукрупнјнныеї задачи только одного ранга, является неэффективным. В работе доказано следующее
утверждение.
Матрица C ? = ?c?ir ? не имеет седловых точек тогда и
только тогда, когда:
Утверждение 4.
c2 > c1 ,
где a =
i=j+1
N p?n
p?N ?1 c1
.
,
c3 ? [a, b] ? [c2 , ?),
? (N ? 1)c2 b = c2 min {
j=0,N
19
ip?i ?jp?j
(N ?j)p?j ?(N ?1)p?i
(13)
,
} p?j ? p?i ?
j ?
i pj
,
В качестве инструментов для решения поставленных задач в работе рассмотрены метод Брауна-Робинсон и симплекс-метод. Применение последнего возможно из-за сводимости антагонистических игр к задачам линейного
программирования.
Разработаны последовательные и параллельные программы, реализующие предложенные алгоритмы. Моделирование показало (рисунок (5)), что
представленные методы позволяют найти решение, т. е. сходятся. Результаты методов отличаются друг от друга не более чем на 10 процентов. По числу шагов эффективным оказался симплекс-метод с матрицей, приведјнной
относительно минимизирующего игрока. Однако по времени решения наилучшие результаты показал метод Брауна-Робинсон с векторной системой
второго типа (последовательное нахождение максимального и минимального
платежей). Поэтому можно с уверенностью сказать, что для поиска стратегии функционирования ВС целесообразным является использование метода
Брауна-Робинсон.
Рисунок 5 Некоторые результаты моделирования алгоритмов выбора
рангов ѕукрупнјнныхї задач
Определение времени решения ѕукрупнјнныхї задач
.
При освобождении вычислительных ресурсов планировщик выбирает следующую ѕукрупнјннуюї задачу из очереди, выделяет ей необходимые ресурсы и назначает фактическое время для еј решения. В случае, когда будет
выделен квант времени меньше, чем требуемое время решения ѕукрупнјн-
20
нойї задачи, то еј решение считается невозможным. В противном случае
будет простой выделенных ресурсов. В работе предложена следующая математическая модель и разработаны алгоритмы для определения числа задач
в ѕукрупнјнныхї задачах и назначаемых им квантов времени для решения.
Выбрав ранг ѕукрупнјннойї задачи, диспетчер формирует еј из
m задач
и выставляет в очередь. По мере освобождения ресурсов готовые ѕукрупнјнныеї задачи выбираются из очереди, им выделяется подсистема ЭМ и
+
+
назначается квант времени решения ?, ? ? [0, ? ], где ?
максимально
допустимое время решения ѕукрупнјннойї задачи. Если назначенное время
равно
0,
это значит, что ѕукрупнјннаяї задача просто удаляется из очереди
без решения еј на ВС. Она расформировывается, и исходные задачи помещаются обратно во входную очередь.
Если диспетчер каждый раз создајт ѕукрупнјнныеї задачи из
потока, а планировщик назначает им время решения, равное
?,
m
задач
то средние
издержки на решение одной ѕукрупнјннойї задачи оцениваются как:
{
cm? =
c4
где
mT c1 + (? ? mT )c2
?c2 + (mT ? ?)c4 ,
если
если
? ? mT ;
mT < ?,
(14)
штраф за превышение времени решения ѕукрупнјннойї задачи на
единицу времени,
T
математическое ожидание величины
ti .
Предложенная математическая модель относится к классу непрерывных
(бесконечных) игр. Издержки при формировании ѕукрупнјнныхї задач из
разного количества задач и назначении им разного времени решения составляют матрицу платежей
C = ?cm? ?.
Очевидно, что алгоритмы работы диспетчера и планировщика по постоянному выбору одного и того же количества задач и выделению одного и
того же кванта времени представляются неэффективными. В работе доказано следующее утверждение.
Матрица C = ?cm?? не имеет решения в чистых стратегиях, если выполняются следующие условия:
Утверждение 5.
m? T c1 + (?+ ? m? T ? ?? )c2
,
m? T ? ??
?
??+
{[ + ]
}
m? = min ?T , m+ ?? = arg max C(m+ , ?),
?
+
c2 > c1 ,
c4 >
(15)
если m+T > ?+,
,
если m+T ? ?+,
??[0,? )
m+ максимально допустимое число задач в пакете. Запись [x] означает
целую часть от x.
где
В качестве инструментария решения поставленной задачи предлагается
использовать метод
?-разбиения,
который заключается в приведении непре[0, ?+ ] на отрезки дли-
рывной игры к конечной путјм разбиения интервала
ной
?.
В работе экспериментально показано, что уже при величине
21
?,
равной
0,01, возможно получить решение задачи. С уменьшением
?
увеличивается
размер получаемой матрицы платежей, а результаты решения отличаются
меньше чем на 10%.
Определение последовательности опроса распределјнной очереди ѕукрупнјнныхї задач
.
Так как ѕукрупнјнныеї задачи формируются диспетчерами независимо,
интенсивности потоков поступления задач в локальные очереди и время поступления задач случайные величины, то может возникнуть ситуация,
когда количество генерируемых ѕукрупнјнныхї задач диспетчерами различное. Построена математическая модель и разработан алгоритм функционирования планировщиков распределјнной ВС, позволяющие сократить накладные расходы на поиск задач в распределјнной очереди ѕукрупнјнныхї
задач.
Как только планировщику распределјнной ВС выделена подсистема для
решения задач, он формирует запросы на приобретение ѕукрупнјнныхї задач из распределјнной очереди. Время, которое он затратит на поиск ѕукрупнјнныхї задач, зависит от:
•
порядка опроса диспетчеров ВС
•
ѕсостоянияї распределјнной очереди ѕукрупнјнныхї задач (в очере? ? ?
дях каких диспетчеров есть ѕукрупнјнныеї задачи) i1 i2 i3 . . .;
•
структуры связей между планировщиками и диспетчерами, т.е. расстояния
•
di
i1 i2 i3 . . .;
до опрашиваемого (i-ого) диспетчера;
объјма передаваемых данных
si
и
fi
от диспетчера с номером
i,
соот-
ветственно в случаях успешного и неуспешного запросов.
Очередь ѕукрупнјнныхї задач рассматривается как незаинтересованная
инстанция, которая не выбирает для себя оптимальных стратегий, а функционирует по своим законам, независящим от поведения планировщиков. Поэтому построенная математическая модель поиска оптимальной последовательности опроса диспетчеров относится к классу игр с ѕприродойї.
Временные издержки, которые несјт планировщик при выборе различных способов опроса диспетчеров и состояния очереди, составляют матрицу
платежей:
C = ?Ci1 i2 i3 ...,i?1 i?2 i?3 ... ?,
(16)
?
Ci1 i2 i3 ...,i?1 i?2 i?3 ... = sij ? dij ? +
j?
?1
fij dij время, затрачиваемое планиj=1
ровщиком на поиск ѕукрупнјнныхї задач при выборе последовательности
?
? ? ?
опроса i1 i2 i3 . . . и нахождения системы в состоянии i1 i2 i3 . . ., j номер в
последовательности опроса диспетчеров такой, что во всех опрошенных до
где
22
этого диспетчеров не оказывается ѕукрупнјнныхї задач в очереди, другими
словами ik ?
/ i?1 i?2 i?3 . . ., ij ? ? i?1 i?2 i?3 . . ., j = 1, 2, . . . , j ? .
Если имеется возможность оценить вероятность нахождения распределјнной очереди ѕукрупнјнныхї задач в каждом из еј состояний (например,
с использованием методов теории массового обслуживания или экспертных
оценок), то решение поставленной задачи сводится к поиску минимума функции:
F (i1 i2 i3 . . .) =
?
P (i?1 i?2 i?3 . . .)Ci1 i2 i3 ...,i?1 i?2 i?3 ... ,
(17)
i?1 i?2 i?3 ...
P (i?1 i?2?
i?3 . . .)
где
вероятность нахождения системы в состоянии
i?1 i?2 i?3 . . .,
запись
означает, что суммирование ведјтся по всем возможным соi?1 i?2 i?3 ...
стояниям очереди.
Если невозможно оценить вероятность нахождения очереди в каждом из
еј состояний, тогда решение задачи может быть найдено по критерию Гурвица: путјм выбора такой последовательности опроса диспетчеров, которая
позволит получить минимум функции:
F (i1 i2 i3 . . .) = ? ?max
Ci1 i2 i3 ...,i?1 i?2 i?3 ... + (1 ? ?) ?min
Ci1 i2 i3 ...,i?1 i?2 i?3 ... ,
? ?
? ?
i1 i2 i3 ...
i1 i2 i3 ...
(18)
? коэффициент, определяющий степень риска менеджера, 0 ? ? ? 1,
? = 0 менеджер максимально рискует при выборе последовательности,
а при ? = 1 рискует наименьшим образом (критерий крайнего пессимизма).
В работе показано, что применение критерия Гурвица при ? = 0 возможно только при условии, что fi < si , а при ? = 1 только для не полносвягде
при
занных систем (т.е. если структура связей отлична от полного графа).
В
четвјртой главе
описана архитектура пространственно-распределјн-
ной мультикластерной ВС Центра параллельных вычислительных технологий ФГОБУ ВПО СибГУТИ и Лаборатории ВС ИФП СО РАН (рисунок 6).
Актуальная информация о конфигурации системы представлена на сайте
ЦПВТ ФГОБУ ВПО СибГУТИ (http://cpct.sibsutis.ru).
Основное назначение пространственно-распределјнной мультикластерной
ВС исследование архитектуры распределјнных ВС, отработка инструментария параллельного мультипрограммирования, моделирование сложных физико-технических процессов и природных явлений, а так же подготовка специалистов и научно-педагогических кадров высокой квалификации в области
распределјнных вычислительных технологий.
В состав программного обеспечения мультикластерной ВС (см. рисунок
7) включјн разработанный программный пакет MOJOS, предназначенный
для моделирования и отладки алгоритмов формирования расписаний решения масштабируемых задач на распределјнных ВС. Пакет разработан на
23
Рисунок 6 Конфигурация пространственно-распределјнной
мультикластерной вычислительной системы (январь 2012 года)
языке ANSI C для операционной системы GNU\Linux. В состав пакета входят нижеследующие компоненты:
1. Подсистема генерирования задач. Задачи генерируются на основе известных статистик поступления задач в распределјнные ВС или с использованием моделей потоков задач. Масштабирование задач производится с использованием модели Downey. Приоритеты запросов задаются псевдослучайно с равномерным распределением.
2. Модуль формирования расписаний решения масштабируемых задач и
поиска смешанных стратегий функционирования диспетчеров и планировщиков распределјнной ВС. В модуле реализованы оригинальные
алгоритмы автора.
3. Средства анализа эффективности сформированных расписаний решения задач. В пакете MOJOS предусмотрены средства графического
представления сформированных расписаний решения задач с помощью
пакета gnuplot.
В
заключении
сформулированы основные результаты, полученные в
диссертационной работе.
В
приложениях
приведены сводные данные о предложенных алгорит-
мах, исходные коды основных модулей разработанной системы MOJOS и
24
Рисунок 7 Программное обеспечение пространственно-распределјнной
мультикластерной вычислительной системы
(жирным шрифтом выделены оригинальные компоненты)
описание структурной организации сегментов пространственно-распределјнной мультикластерной вычислительной системы.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
1. Разработаны алгоритмы организации функционирования распределјнных вычислительных систем в режиме обработки наборов масштабируемых задач.
1.1. Предложен метод организации функционирования распределјнных ВС в режиме обработки наборов масштабируемых задач, учитывающий
пользовательские
приоритеты
выбора
параметров
и штраф за задержку решения задач.
1.2. Построено семейство полиномиальных (последовательных и параллельных) алгоритмов формирования расписаний решения масштабируемых задач наборов на распределјнных ВС. Алгоритмы
25
основаны на стохастических, эвристических и эволюционных методах оптимизации и позволяют учитывать пользовательские приоритеты на размеры подсистем ВС для каждой масштабируемой
задачи. Моделирование показало, что алгоритмы эффективны, они
обеспечивают субминимум времени решения задач набора, который отличается от нижней грани на 15 20%.
1.3. Разработан эвристический алгоритм определения последовательности решения ѕукрупнјнныхї задач на распределјнных ВС, обеспечивающий (суб)минимум суммарного штрафа за задержку решения задач набора.
2. Созданы средства оптимизации функционирования распределјнных вычислительных систем в режиме обслуживания потоков задач.
2.1. Предложен подход к организации функционирования распределјнных ВС в режиме обслуживания стохастических потоков задач, учитывающий интенсивности поступления задач по разным
каналам в распределјнную ВС и отказы вычислительные ресурсов.
2.2. Построены теоретико-игровые модели и алгоритмы для децентрализованных диспетчеров очередей задач и планировщиков ресурсов
распределјнных
ВС.
Алгоритмы
позволяют
формировать
ѕукрупнјнныеї задачи из задач потока и сокращают простои ресурсов распределјнных ВС. Они учитывают топологию логических связей между планировщиками и диспетчерами, стохастическую природу потоков задач и отказы ресурсов распределјнных
вычислительные систем.
2.3. Выведены необходимые условия существования оптимальных смешанных стратегий формирования ѕукрупнјнныхї задач и организации их поиска в распределјнной очереди.
2.4. Получены смешанные стратегии функционирования распределјнных ВС в режиме обслуживания потоков задач.
3. При непосредственном участии диссертанта создана пространственнораспределјнная мультикластерная ВС.
3.1. Разработан инструментарий параллельного мультипрограммирования распределјнных ВС, включающий программные компоненты, базирующиеся на оригинальных алгоритмах автора.
3.2. Создан программный пакет MOJOS для моделирования и анализа
алгоритмов организации функционирования распределјнных ВС,
26
имеющий интерфейс с современными системами пакетной обработки заданий. Показано, что время выполнения алгоритмов, затраченное на поиск субоптимального расписания, компенсируется
уменьшением суммарного времени решения всех задач набора.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
а) Публикации в рецензируемых журналах из списка ВАК:
1. Хорошевский В. Г., Курносов М. Г.,
Мамойленко С. Н., Павский К. В.,
Ефимов А. В., Пазников А. А., Перышкова Е. Н. Масштабируемый инструментарий параллельного мультипрограммирования пространственно-распределјнных вычислительных систем // Вестник СибГУТИ. - Новосибирск:
Изд-во ФГОБУ ВПО ѕСибГУТИї, 2011. ? 4. С. 3 18. ISSN 19986920.
2.
Мамойленко С. Н.,
Ефимов А. В., Перышкова Е. Н.. Организация
функционирования распределјнных вычислительных систем при обработке
масштабируемых задач // Вестник Томского государственного университета. Серия ѕУправление, вычислительная техника и информатикаї. Томск:
Изд-во Томского государственного университета, 2011. - ? 2(15). - С. 51 60. ISSN 1998-5605.
3. Хорошевский В. Г., Курносов М. Г.,
Мамойленко С. Н..
Простран-
ственно-распределјнная мультикластерная вычислительная система: Архитектура и программное обеспечение // Вестник Томского государственного университета. Серия ѕУправление, вычислительная техника и информатикаї. Томск: Изд-во Томского государственного университета, 2011. ? 1(14). - С. 79-84. ISSN 1998-5605.
4. Хорошевский В. Г., Курносов М. Г.,
Мамойленко С. Н., Поляков А. Ю.
Архитектура и программное обеспечение пространственно-распределјнных
вычислительных систем // Вестник ГОУ ВПО ѕСибГУТИї. - Новосибирск:
Изд-во ГОУ ВПО СибГУТИ, 2010. ?2. С. 112 122. ISSN 1998-6920.
5.
Мамойленко С. Н.,
Ефимов А. В. Алгоритмы планирования реше-
ния масштабируемых задач на распределјнных вычислительных системах //
Вестник
ГОУ
ВПО
СибГУТИ.
Новосибирск:
Изд-во
ГОУ
ВПО
СибГУТИ, 2010. N 2. С. 66-78. ISSN 1998-6920.
6. Хорошевский В. Г.,
Мамойленко С. Н., Майданов Ю. С., Смирнов С. В.
Об организации функционирования кластерных вычислительных систем //
Автометрия, Новосибирск, 2004, Т.40, N 1, С. 41-50.
7. Хорошевский В. Г.,
Мамойленко С. Н.
Стратегии стохастически оп-
тимального функционирования распределјнных вычислительных систем //
Автометрия. 2003. N 2. С. 81-91.
27
8. Khoroshevsky V. G.,
Mamoilenko S. N.,
Maidanov Yu. S., Smirnov S. V.
On cluster computer functioning // Optoelectronics, Instrumentation and data
processing, Vol. 40, No. 1, 2004, pp. 35-42.
9. Khoroshevsky V. G., Mamoilenko S. N. Stochastically optimal functioning strategies of distributed computing systems // Optoelectronics, Instrumentation and data processing, Vol. 39, No. 2, 2003, pp. 68-76.
б) Публикации в материалах научных мероприятий (международных и российских конференциях):
10.
Мамойленко С. Н.,
Перышкова Е. Н., Ефимов А. В. Две модифика-
ции генетического алгоритма формирования расписаний решения масштабируемых заданий на распределјнных вычислительных системах // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. Новосибирск: Изд-во ГОУ ВПО ѕСибГУТИї, 2011,
21 22 апреля 2011 года. Т. 1. С. 207-208.
11.
Мамойленко С. Н., Перышкова Е. Н., Ефимов А. В. Сравнение мето-
дов кодирования решений генетического алгоритма формирования решений
выполнения масштабируемых программ на распределјнных вычислительных системах // Материалы XLIX международной научной студенческой
конференции Студент и научно-технический прогресс: Информационные
технологии / НГУ. Новосибирск, 2011. С. 229.
12. Ефимов А. В.,
Мамойленко С. Н.,
Максимова Е. Н. Моделирование
алгоритмов формирования расписаний решения масштабируемых задач на
распределјнных вычислительных системах [Электронный ресурс] // Распределенные информационные и вычислительные ресурсы (DICR-2010): доклады XIII Российской конференции с участием иностранных ученых. Электрон. данные. Новосибирск, 2010, 30 ноября - 03 декабря 2010 г. - Режим до-
http://conf.nsc.ru/files/conferences/dicr2010/fulltext/29970
/29971/maksimova-mamoilenko.pdf.
ступа:
13.
Мамойленко С. Н.,
Кожушко Р. И. Формирование расписаний ре-
шения масштабируемых задач на распределјнных вычислительных системах
модифицированными методами 1.5D и 2D упаковки объектов в полосу // Информатика и проблемы телекоммуникаций: материалы Российской научнотехнический конференции. Новосибирск: Изд-во ГОУ ВПО ѕСибГУТИї,
2011, 21 22 апреля 2011 года. Т. 1. С. 205.
14.
Мамойленко С. Н.,
Крамаренко К. Е. Нейросетевой алгоритм со-
ставления расписаний решения задач на распределјнных вычислительных
системах // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. Новосибирск: Изд-во ГОУ ВПО
ѕСибГУТИї, 2011, 21 22 апреля 2011 года. Т. 1. С. 200-201.
28
15.
Мамойленко С. Н.,
Кожушко Р. И. Модифицированные алгоритмы
2D упаковки для формирования расписания выполнения набора адаптирующихся задач на распределјнных вычислительных системах // Информатика
и проблемы телекоммуникаций: материалы Российской научно-технический
конференции. Новосибирск: Изд-во ГОУ ВПО ѕСибГУТИї, 2010, 27 28
апреля 2010 года. Т. 1. С. 156.
16. Крамаренко К. Е.,
Мамойленко С. Н.
Нейросетевой алгоритм фор-
мирования расписания выполнения набора адаптирующихся задач // Информатика и проблемы телекоммуникаций: материалы Российской научнотехнический конференции. - Новосибирск: Изд-во ГОУ ВПО СибГУТИ,
2010, 27 - 28 апреля 2010 года. - Т. 1. - С. 157.
17. Максимова Е. Н.,
Мамойленко С. Н.,
Ефимов А. В. Параллельный
генетический алгоритм формирования расписания решения параллельных
адаптирующихся задач на распределјнных вычислительных системах // Информатика и проблемы телекоммуникаций: материалы Российской научнотехнический конференции. Новосибирск: Изд-во ГОУ ВПО ѕСибГУТИї,
2010, 27 28 апреля 2010 года. Т. 1. С. 163.
18.
Мамойленко С. Н., Великородний И.М. Алгоритм организации функ-
ционирования очередей задач в распределјнных вычислительных системах
// Информатика и проблемы телекоммуникаций: материалы Российской научно-технической конференции. - Новосибирск: Изд-во ГОУ ВПО СибГУТИ,
2010, 27 - 28 апреля 2010 года. - Т. 1. - С. 164.
19.
Мамойленко С. Н.,
Ефимов А.В. Организация мультипрограммно-
го режима обработки набора параллельных адаптирующихся программ на
распределјнных вычислительных системах // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции.
- Новосибирск: Изд-во ГОУ ВПО СибГУТИ, 2010, 27 - 28 апреля 2010 года.
- Т. 1. - С. 166.
20. Максимова Е. Н., Ефимов А. В.,
Мамойленко С. Н.
Параллельный
генетический алгоритм формирования расписания решения параллельных
адаптирующихся задач на распределјнных вычислительных системах // Научная студенческая конференция Лаборатории НГУ-Интел 2010. Новосибирск: НГУ, 2010, 22 мая 2010 года.
21. Хорошевский В. Г., Курносов М. Г.,
Мамойленко С. Н. Научно-учеб-
ный центр параллельных вычислительных технологий ГОУ ВПО СибГУТИ
// Суперкомпьютерные технологии. Разработка, программирование, применение: материалы международной научно-технической конференции. - Таганрог: Изд-во ТТИ ЮФУ, 2010, 27 сентября - 02 октября 2010. - Т.2. - С.
306 - 208.- 1 электрон, опт. диск (CDROM).- ISBN 978-5-8327-0383-1.
22. Хорошевский В. Г., Курносов М. Г.,
ный
центр
параллельных
Мамойленко С. Н. Научно-учеб-
вычислительных
технологий
ГОУ
ВПО
СИБГУТИ // Высокопроизводительные вычислительные системы (ВПВС-
29
2010): материалы седьмой международной научной молодежной школы. Таганрог: Изд-во ТТИ ЮФУ, 2010, 27 сентября - 02 октября 2010. - С. 146 148. - ISBN 978-5-8327-0382-4
23. Хорошевский В. Г.,
Мамойленко С. Н.,
Ефимов А. В. Планирова-
ние выполнения параллельных программ с нефиксированными параметрами
на распределенных вычислительных системах // Высокопроизводительные
вычислительные системы (ВПВС-2010): материалы седьмой международной
научной молодежной школы. - Таганрог: Изд-во ТТИ ЮФУ, 2010, 27 сентября - 02 октября 2010. - С. 95 - 100. - ISBN 978-5-8327-0382-4.
24. Хорошевский В. Г.,
Мамойленко С. Н.,
Ефимов А. В. Планирование
выполнения параллельных программ с нефиксированными параметрами на
распределјнных вычислительных системах // Суперкомпьютерные технологии. Разработка, программирование, применение: материалы международной научно-технической конференции. - Таганрог: Изд-во ТТИ ЮФУ, 2010,
27 сентября - 02 октября 2010. - Т.2. - С. 97 - 101.- 1 электрон, опт. диск
(CDROM).- ISBN 978-5-8327-0383-1.
25. Хорошевский В. Г., Курносов М. Г.,
Мамойленко С. Н.
Простран-
ственно-распределенные мультикластерные вычислительные системы: архитектура и программное обеспечение // Материалы Всероссийской научнотехнической конференции Научное и технические обеспечение исследований и освоения шельфа Северного Ледовитого океана, 2010. С. 5459.
26.
Ситников
С. Г.,
Хорошевский
В. Г.,
Курносов
М. Г.,
Мамойленко С. Н. Архитектура, анализ и организация функционирования
распределенных вычислительных систем // Программа ѕУниверситетский
кластерї: материалы конференции ѕОблачные вычисления: образование, научные исследования, разработкиї. Москва: Hewlett-Packard Development
Company, L.P., 15-16 апреля 2010. С. 51.
27. Хорошевский В. Г., Курносов М. Г.,
Мамойленко С. Н.
Инструмен-
тарий параллельного мультипрограммирования большемасштабных распределјнных гетерогенных вычислительных систем // Материалы конференции
Результаты ориентированных целевых фундаментальных исследований и их
использование в российской промышленности. Таганрог: НИИ МВС ЮФУ,
2010.
28. Ефимов А. В.,
Мамойленко С. Н.,
Максимова Е. Н. Моделирова-
ние алгоритмов формирования расписаний решения масштабируемых задач
на распределјнных вычислительных системах // XIII Российская конференция ѕРаспределенные информационные и вычислительные ресурсыї (DICR2010): программа и тезисы докладов с участием иностранных ученых. Новосибирск, 2010, 30 ноября 03 декабря 2010 г. С. 24.
29. Ефимов А. В.,
Мамойленко С. Н.,
Максимова Е. Н. Моделирова-
ние алгоритмов формирования расписаний решения масштабируемых задач
на распределјнных вычислительных системах // XIII Российская конферен-
30
ция ѕРаспределјнные информационные и вычислительные ресурсыї (DICR2010): программа и тезисы докладов с участием иностранных ученых. Новосибирск, 2010, 30 ноября 03 декабря 2010 г. - С. 24. 1 электрон, опт.
диск (CDROM).
30. Максимова Е. Н., Ефимов А. В.,
Мамойленко С. Н.
Эволюционный
подход к формированию расписаний выполнения адаптирующихся программ
на распределјнной вычислительной системе // Новые информационные технологии в исследовании сложных структур: тезисы докладов Восьмой Российской конференции с международным участием. Томск: Изд-во: НТЛ,
2010, 05 08 октября 2010 года. С. 17. ISBN 978-5-89503-440-8.
31. Максимова Е. Н., Ефимов А. В.,
Мамойленко С. Н.
Параллельный
генетический алгоритм формирования расписаний решения масштабируемых задач на распределенных вычислительных системах // XI Всероссийская конференция молодых ученых по математическому моделированию и
информационным технологиям: программа и тезисы докладов. Новосибирск: Изд-во ИВТ СО РАН, 2010, Красноярск, 26 27 октября 2010 года. С. 32.
32. Хорошевский В. Г., Курносов М. Г.,
Мамойленко С. Н.
Архитек-
тура, анализ и организация функционирования распределенных вычислительных систем // Тезисы докладов Международной конференции Облачные вычисления. Образование. Исследования. Разработки. М.: ИСП РАН,
2010. С. 76.
33. Хорошевский В. Г., Курносов М. Г.,
Мамойленко С. Н.
Простран-
ственно-распределенная мультикластерная вычислительная система: архитектура и программное обеспечение // Новые информационные технологии
в исследовании сложных структур: тезисы докладов Восьмой Российской
конференции с международным участием. Томск: Изд-во: НТЛ, 2010, 05 08 октября 2010 года. - С. 27. ISBN 978-5-89503-440-8.
34. Максимова Е. Н.,
Мамойленко С. Н. Генетический алгоритм распре-
деления наборов параллельных задач с нефиксированными параметрами по
машинам распределенной вычислительной системы // Материалы Российской научно-технической конференции ѕИнформатика и проблемы телекоммуникацийї, Новосибирск: ГОУ ВПО ѕСибГУТИї, 27-28 апреля 2009 года,
С. 127-128.
35.
Мамойленко С. Н.,
Крамаренко К. Е. Применение нейросетевых
алгоритмов для распределения наборов параллельных задач по машинам
распределенной вычислительной системы // Материалы Российской научнотехнической конференции ѕИнформатика и проблемы телекоммуникацийї,
Новосибирск: ГОУ ВПО ѕСибГУТИї, 27-28 апреля 2009 года, С. 128-129
36. Хорошевский В. Г.,
Мамойленко С. Н.,
Курносов М. Г. Архитектур-
ные концепции, анализ и организация функционирования вычислительных
систем с программируемой структурой // Труды Международной научно-
31
технической конференции Информационные технологии и математическое
моделирование систем 2008-2009, Москва, 2009, С. 7479.
37.
Мамойленко С. Н., Ефимов А. В. Формирование расписания выпол-
нения набора параллельных адаптирующихся задач на распределенных вычислительных системах // Материалы Международной научно-технической
конференции Многопроцессорные вычислительные и управляющие системы (МВУС-2009). - Таганрог: ТТИ ЮФУ, 2009. Т. 1. - С. 200 - 2002. ISBN
978-5-8327-0341-1.
38.
Хорошевский
В. Г.,
Мамойленко
С. Н.,
Курносов
М. Г.,
Поляков А. Ю. Параллельные вычислительные технологии в учебном процессе // Сборник тезисов докладов 50-й (L) научно-методической конференции ГОУ ВПО ѕСибГУТИї, Новосибирск: ГОУ ВПО ѕСибГУТИї, 6 февраля
2009 года, С. 63
39.
Мамойленко С. Н.,
Ефимов А. В. Генетический алгоритм распреде-
ления параллельных задач с нефиксированными параметрами по машинам
распределенной вычислительной системы // Сборник тезисов пятой сибирской конференции по параллельным и высокопроизводительным вычислениям, Томск: Изд-во Томского университета, 1-3 декабря 2009, С.69-68
40.
Мамойленко С. Н.,
Медведева Н. А., Поляков А. Ю., Ефимов А. В.
Применение эволюционных алгоритмов для распределения набора задач с
нефиксированными параметрами по машинам распределенной вычислительной системы // Материалы Российской научно-технической конференции
"Информатика и проблемы телекоммуникаций 2008, с. 144-145.
41. Хорошевский В. Г.,
Мамойленко С. Н.,
Курносов М. Г. О центре па-
раллельных вычислительных технологий ГОУ ВПО ѕСибГУТИї // Журнал
ѕИнфосфераї, N 40, 2008, С.43-44.
42.
Мамойленко С. Н.,
Медведева Н. А., Поляков А. Ю., Ефимов А. В.
Применение эволюционных алгоритмов для распределения набора задач с
нефиксированными параметрами по машинам распределенной вычислительной системы. // Тезисы докладов Седьмой Российской конференции с международным участием Новые информационные технологии в исследовании
сложных структур (ICAM-2008). Томск : НТЛ, 2008. с. 71.
43.
Мамойленко С. Н.,
Павский К. В., Курносов М. Г., Посохов А. С.,
Медведева Н. А., Поляков А. Ю. Использование мультикластерной вычислительной системы для подготовки специалистов в области параллельных
вычислительных технологий // Тезисы докладов XLIX научно-методической
конференции Проблемы перехода на многоуровневую систему образования.
Новосибирск: Изд-во СибГУТИ, 2008. С. 38.
44.
Мамойленко С. Н.,
Медведева Н. А., Поляков А. Ю. Применение
генетических алгоритмов для распределения наборов задач по машинам вычислительной системы // Материалы международной научно-технической
32
конференции ѕМногопроцессорные вычислительные и управляющие системыї, пос. Дивноморское, Геленджик, 24 29 сентября, 2007, C. 70-25.
45. Хорошевский В. Г.,
Мамойленко С. Н.,
Медведева Н. А. Примене-
ние генетических алгоритмов для распределения наборов задач по машинам вычислительной системы // Материалы 8-й Международной научнотехнической конференции ѕИскусственный интеллект. Интеллектуальные и
многопроцессорные системы - 2007ї, 2007.
46.
Мамойленко С. Н.,
Медведева Н. А. Современные средства органи-
зации функционирования распределјнных вычислительных систем // Материалы Российской научно-технической конференции Информатика и проблемы телекоммуникаций, Новосибирск, Т1, 2007, с.274-275
47.
Мамойленко C. Н.,
Медведева Н. А. Опыт применения мультикла-
стерной вычислительной системы для преподавания курса ѕРаспределјнные операционные системыї // Сборник тезисов докладов XLVIII Научнометодической конференции, Новосибирск, СибГУТИ, 2007 г., C. 33
48. Хорошевский В. Г.,
Мамойленко С. Н.,
Медведева Н. А. Алгоритмы
распределения набора задач с нефиксированными параметрами по машинам
вычислительной системы // Материалы третьей международной научной
молодежной школы ѕВысокопроизводительные вычислительные системыї,
Таганрог: Изд-во ТРТУ, 2006, с. 33-36.
49.
Мамойленко С. Н.,
Медведева Н. А. Алгоритмы организации функ-
ционирования вычислительных систем при обслуживании задач с нефиксированными параметрами // Материалы Российской научно-технической
конференции Информатика и проблемы телекоммуникаций, Новосибирск,
2006, с. 77-78.
50.
Мамойленко С. Н.
Об организации функционирования вычисли-
тельных систем при обслуживании задач с нефиксированными параметрами
// Материалы Российской научно-технической конференции Информатика
и проблемы телекоммуникаций, Новосибирск, 2006, с. 75-76.
51.
Khoroshevsky
V. G.,
Mamoilenko
S. N.,
Kurnosov
M. G.,
Space-distributed multi-cluster computer system for training in
parallel computational technologies // Proceedings of 7th International Siberian
Workshop and Tutorial EDM’2006, Erlagol, Russia.
Medvedeva N. A.
52.
Мамойленко С. Н.,
Седельников М. С., Медведева Н. А. Опыт ис-
пользования распределјнной мультикластерной вычислительной системы для
подготовки специалистов в области сетевых технологий // Сборник тезисов
докладов XLVII Научно-методической конференции, Новосибирск, СибГУТИ,
2006 г., C. 32
53. Хорошевский В. Г.,Мамойленко
С. Н., Седельников М. С. Распреде-
ленная система управления заданиями для кластерных вычислительных систем // Материалы Международной научно-технической конференции ѕИн-
33
теллектуальные и многопроцессорные системы 2005ї, пос. Дивноморское,
26 сентября 1 октября, 2005 г., том 1, С. 65-69.
54. Хорошевский В. Г., Майданов Ю. С.,
Мамойленко С. Н.,
Седель-
ников М. С. Организация мультипрограммных режимов функционирования
распределенных кластерных вычислительных систем // Труды Второй Всероссийской научно конференции ѕМетоды и средства обработки информации
2005ї, Москва, МГУ, 5-7 октября, 2005 г., стр. 295-301.
55. Khoroshevsky V. G.,
Mamoilenko S. N., Maidanov Y. S., Sedelnikov M. S.
Space-distributed multicluster computer system with multiprogramme regimes
supporting // International science conference ACIT – Software Engineering,
June 20-24, 2005, Novosibirsk, Russia, 136-138 p.p.
56.
Мамойленко С. Н.,
Седельников М. С. Распределенная кластерная
вычислительная система как средство подготовки специалистов в области
параллельных вычислительных процессов // Сборник тезисов докладов XLVI
Научно-методической конференции, Новосибирск, СибГУТИ, 2005 г., C. 45
57. Хорошевский В. Г.,
Мамойленко С. Н.,
Майданов Ю. С. Живучие
кластерные вычислительные системы // Материалы первой Всероссийской
научной конференции ѕМетоды и средства обработки информацииї, Москва,
2003, стр. 148-150.
58.
Мамойленко С. Н. Непрерывная теоретико-игровая модель функци-
онирования распределенных вычислительных систем // Материалы Международной научно-технической конференции ѕИнформатика и проблемы телекоммуникацийї, Новосибирск, 2003, 151-152
59.
Мамойленко С. Н.
Многоходовая теоретико-игровая модель функ-
ционирования распределјнных большемасштабных вычислительных систем
в условиях отказов ресурсов // Материалы Международной научно-технической конференции ѕИнформационные системы и технологииї, Новосибирск,
2003, Т.2. С. 147.
60.
Мамойленко С. Н.
Теоретико-игровая модель функционирования
распределенной очереди задач в кластерных вычислительных системах //
Материалы Всероссийской научной конференции ѕНаука. Технологии. Инновации.ї, Новосибирск, 2003, Ч.2, С. 18-19.
61.
Мамойленко С. Н., Кузнецов Д. В. Применение методов теории непре-
рывных игр в организации функционирования вычислительных систем //
Материалы Международной научно-технической конференции Информатика и проблемы телекоммуникаций, Новосибирск, 2002, С. 131-132
62.
Мамойленко С. Н.
Многоходовая игровая модель функционирова-
ния вычислительных систем // Материалы Международной научно-технической конференции Информатика и проблемы телекоммуникаций, Новосибирск, 2002, С. 132-133.
63.
Мамойленко С. Н.,
Хорошевский В. Г. Параллельные методы ор-
ганизации функционирования распределенных вычислительных систем //
34
Материалы Региональной научной конференции студентов, аспирантов и молодых учебных Наука. Техника. Инновации., Новосибирск, 2002, Ч.2, С.
10-12.
Личный вклад автора в совместные публикации
Результаты диссертационной работы, выносимые на защиту, принадлежат автору, что подтверждено публикациями в научных изданиях. В работах
опубликованных в соавторстве автору принадлежат: способы и алгоритмы
организации функционирования распределјнных ВС в режиме обработки
наборов задач [1-5] и обслуживании потоков задач [6-9]. В работах [10-20, 2831, 34, 35, 37, 39, 40, 42, 44, 45-47, 61] представлены постановки задач исследования, авторские алгоритмы и результаты их моделирования. В работах
[23-25, 36, 48, 49, 50] автором написаны разделы, отражающие результаты по
организации функционирования распределјнных ВС в мультизадачных режимах. В работах [6, 8, 26, 43, 53-57] представлено участие автора в создании
пространственно-распределјнной мультикластерной вычислительных системы. Работы [21, 22, 27, 32, 33, 38, 41, 51, 52, 56] подтверждают внедрение
результатов, полученных автором, в практические разработки и учебный
процесс Центра параллельных вычислительных технологий и Кафедры вычислительных систем ФГОБУ ВПО СибГУТИ. Во всех совместных работах
авторство неделимое.
35
Мамойленко Сергей Николаевич
Организация функционирования
распределјнных вычислительных систем
в мультизадачных режимах
Автореферат
диссертации на соискание учјной степени
доктора технических наук
Подписано в печать ѕ____ї _______ 2012 г.
Формат бумаги 60x84/16, отпечатано на ризографе, шрифт ? 10,
изд. л.___, заказ ? ____, тираж ____ экз., ФГОБУ ВПО СибГУТИ.
630102, г. Новосибирск, ул. Кирова, д. 86.
36
Документ
Категория
Технические науки
Просмотров
94
Размер файла
2 264 Кб
Теги
Докторская
1/--страниц
Пожаловаться на содержимое документа