Введение к работе
Актуальность работы. Возрастающая потребность в решении сложных задач науки, техники привела к созданию распределённых вычислительных систем (ВС). В общем случае распределённая ВС - это композиция множества элементарных машин (ЭМ) и сети межмашинных связей. Элементарная машина - это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до ЭВМ или специализированного ускорителя. Все основные ресурсы распределённых ВС (как аппаратурные, так и программные) являются логически и технически рассредоточенными. Количество ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч (например, в системе Fujitsu К Computer количество вычислительных ядер равно 705 024).
Исследования в области распределённых вычислительных систем ведутся с середины XX столетия. С тех пор в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную реализацию на распределённых ВС. Построены отечественные вычислительные системы с программируемой структурой: «Минск-222», СУММА, МИНИМАКС, МИК-РОС, МВС, СКИФ и др.
Фундаментальный вклад в теорию и практику вычислительных систем и
параллельных вычислительных технологий внесли советские и российские
учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васи
льев, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, А.В. Забродин,
В.П. Иванников, М.Б. Игнатьев, А.В. Каляев, И.А. Каляев, Л.Н. Королев,
С.А. Лебедев, В.К. Левин, Г.И. Марчук, Ю.И. Митропольский,
Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов,
А.А. Самарский, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров,
В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко, а также зарубежные учёные: S. Cray, М. Flynn, I. Foster, D. Hillis, С. Kesselman, DL. Slotnick, A. Tanenbaum, D. Feitelson и другие. При решении проблем оптимизации функционирования распределённых ВС большую роль сыграли фундаментальные работы в области дискретной математики и исследовании операций советских и российских учёных: В.Л. Вереснева, Э.Х. Гимади,
В.Т. Дементьева, Ю.И. Журавлева, К.В. Рудакова и зарубежных -R. Bellmann, D. Johnson, М. Koffman, Н. Tana и других.
Эффективность использования ресурсов распределённых ВС во многом зависит от того, как организован процесс решения на них задач пользователей. В общем случае задачи представляются параллельными программами и описываются рядом параметров, в числе которых: количество ветвей (ранг необходимой подсистемы), время решения и т.п. В зависимости от характера поступления задач и их параметров принято выделять следующие режимы функционирования ВС: решение сложной задачи, обработка набора задач и обслуживание потока задач. Первый режим является монопрограммным, для решения задачи используются все ресурсы ВС (все ЭМ). Два последних режима функционирования распределённых ВС относятся к мультипрограммным, при этом множество задач одновременно решается на системе, и её ресурсы разделяются между ними.
В режиме обработки набора задач требуется сформировать расписание их решения. Для каждой задачи необходимо определить подсистему ЭМ и момент запуска на выполнение ветвей соответствующей параллельной программы. Этот режим хорошо изучен для задач, параметры которых (ранг и время решения) заданы скалярными величинами, такие алгоритмы внедрены в системы пакетной обработки заданий (TORQUE, SLURM, Altair PBS Pro и
ДР)-
Анализ пользовательских задач показывают, что более 80 % из них обладают свойством масштабируемости. Такие задачи допускают решение на подсистемах с различным количеством ЭМ и называются масштабируемыми или "пластичными" (moldable). Актуальной является задача разработки алгоритмических и программных средств организации мультипрограммного функционирования распределённых ВС в режиме обработки наборов масштабируемых задач.
В диссертации предложены алгоритмы и программные средства оптимизации функционирования распределённых ВС при решении масштабируемых задач с учётом штрафов за задержку их решения и заданных пользователями приоритетов выбора значений параметров задач (их рангов).
Цель работы и задачи исследования. Целью диссертационной работы является разработка и исследование алгоритмов и программных средств организации функционирования распределённых ВС в режиме обработки наборов масштабируемых задач.
В соответствии с целью определены нижеследующие задачи исследования.
Анализ современных подходов к организации функционирования распределённых ВС в мультипрограммных режимах.
Разработка алгоритмов формирования расписаний решения масшта-
бируемых задач набора на распределённых ВС.
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-07-00109, грантами Президента РФ по поддержке ведущих научных школ №НШ-2121.2008.9, НШ-5176.2010.9, грантом мэрии г. Новосибирска молодым учёным № 10-11 (2011), а так же грантами ФГОБУ ВПО "СибГУТИ" (2009,2010,2011).
Внедрение результатов диссертационного исследования подтверждается соответствующими актами.
Достоверность полученных результатов подтверждается проведёнными экспериментами и моделированием, согласованностью с данными имеющимися в отечественной и зарубежной литературе и экспертизами работы, прошедшими при получении грантов.
Апробация работы. Основные результаты работы докладывались и обсуждались на Международных, Всероссийских и региональных научных конференциях, в том числе:
Международной научно-технической конференции "Многопроцессорные вычислительные и управляющие системы" (с. Дивноморское Гелен-джикского района, 2009);
Международной научно-технической конференции "Суперкомпьютерные технологии: разработка, программирование, применение" (с. Дивноморское Геленджикского района, 2010);
Международной научно-технической конференции "Студент и научно-технический прогресс" (г. Новосибирск, 2009, 2010, 2011);
Международной научной молодёжной школе "Высокопроизводительные вычислительные системы" (с. Дивноморское Геленджикского района, 2010);
Российской конференции с международным участием "Новые информационные технологии в исследовании сложных структур" (г. Томск, 2008, 2010);
Научной школе-практикуме для молодых учёных и специалистов "Технологии высокопроизводительных вычислений и компьютерного моделирования" (г. Санкт-Петербург, 2009);
Российской научно-технической конференции "Информатика и проблемы телекоммуникаций" (г. Новосибирск, 2008, 2009, 2010, 2011);
Российской конференции с участием иностранных учёных "Распределённые информационные и вычислительные ресурсы" (г. Новосибирск, 2010);
Всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям (г. Красноярск, 2010);
Пятой сибирской конференции по параллельным и высокопроизводительным вычислениям (г. Томск, 2009).
Публикации. По теме диссертации опубликовано 19 работ, из которых 3 - в изданиях из списка ВАК. Результаты исследований отражены в отчётах по грантам и НИР.
Основные положения диссертации, выносимые на защиту.
Семейство полиномиальных алгоритмов многокритериальной оптимизации мультипрограммного функционирования распределённых вычислительных систем в режиме обработки наборов масштабируемых задач.
Программные пакет формирования и анализа расписаний решения масштабируемых задач на распределённых ВС (пакет MOJOS), предусматривающий средства визуализации расписаний и интерфейс с системами пакетной обработки заданий.
Структура и объём диссертации. Диссертационная работа состоит из введения, трёх глав, заключения и списка литературных источников, изложенных на 97 страницах, а также приложений на 25 страницах.
