Введение к работе
Актуальность работы. Распределённые вычислительные системы (ВС) являются современным инструментарием обработки информации (список ТорбОО (Ноябрь, 2011) суперкомпьютеров мира). В Российской Федерации технологии и программное обеспечение распределённых и высокопроизводительных ВС относят к критически важным (указ Президента Российской Федерации от 7 июля 2011 г. № 899).
Исследования в области распределённых ВС ведутся с середины XX столетия. С тех пор в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную реализацию на распределённых ВС. Построены отечественные вычислительные системы с программируемой структурой: «Минск 222», СУММА, МИНИМАКС, МИКРОС, МВС, СКИФ и др.
Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли советские, российские и зарубежные учёные, среди которых: Е. П. Балашов, В. Б. Бетелин,
B. С. Бурцев, В. В. Васильев, В. М. Глушков, В. Ф. Евдокимов, Э. В. Евреинов,
А. В. Забродин, В. П. Иванников, М. Б. Игнатьев, А. В. Каляев, И. А. Каляев,
Л. Н. Королёв, С. А. Лебедев, А. О. Лацис, В. К. Левин, И. И. Левин,
Г. И. Марчук, Ю.И. Митропольский, Д. А. Поспелов, И. В. Прангишвили,
Д. В. Пузанков, Г. Е. Пухов, Г. Г. Рябов, А. А. Самарский, В. Б. Смолов,
А. Н. Томилин, Я. А. Хетагуров, В. Г. Хорошевский, Б. И. Четверушкин,
Ю. И. Шокин, И. Н. Яненко, S. Cray, М. Flynn, D. Feitelson, I. Foster, D. Hillis,
C. Kesselman, DL. Slotnick, A. Tanenbaum и другие.
В общем случае распределённая ВС — это композиция множества элементарных машин (ЭМ) и сети межмашинных связей. Элементарная машина— это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах — от процессорного ядра до ЭВМ или специализированного ускорителя. Все основные ресурсы распределённых ВС (как аппаратурные, так и программные) являются логически и технически рассредоточенными. Количество ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч. Например, в системе Fujitsu К Computer количество вычислительных ядер равно 705 024. Современные распределённые ВС являются мулътархитек-турными, масштабируемыми и болъшемасштабными средствами обработки информации, что определяет сложность организации их функционирования.
Задачи, решаемые на распределённых ВС, представляются параллельными программами и описываются рядом параметров, в числе которых: коли-
чество требуемых ЭМ, время решения, штраф за задержку решения и т.п. В зависимости от характера поступления задач и их параметров принято выделять следующие режимы функционирования ВС: решение сложной задачи, обработка набора задач и обслуживание потока задач. Первый режим является монопрограммным, для решения задачи используются все ресурсы распределённой ВС (все ЭМ). Два последних режима функционирования распределённых ВС относятся к мультизадачным, при этом ресурсы системы разделяются между несколькими одновременно решаемыми задачами. Огромные возможности распределённых ВС по решению различных задач могут быть использованы и раскрыты только при применении эффективных методов и средств параллельного мультипрограммирования.
На практике широко используется и хорошо изучен режим обработки наборов задач, параметры которых заданы скалярными величинами. Повысить эффективность функционирования распределённых ВС возможно, если, в частности, задачи допускают решение на подсистемах с различным количеством ЭМ. Такие задачи называются масштабируемыми или «пластичными» (moldable). Исследования пользовательских запросов показывают, что свойством масштабируемости обладают более 80% задач. Также важно разрабатывать децентрализованные методы и алгоритмы управления ресурсами распределённых ВС при обслуживании потоков задач.
Проблема организации эффективного функционирования распределённых ВС трудноразрешима. Поэтому разработка приближённых методов и эвристических алгоритмов организации функционирования распределённых ВС в мультизадачных режимах актуальна.
Цель работы — организация эффективного функционирования распределённых ВС в мультизадачных режимах и создание инструментария параллельного мультипрограммирования распределённых ВС.
Для достижения поставленных целей необходимо решение следующих задач исследования:
анализ и обобщение современного состояния и тенденций развития подходов к организации функционирования распределённых ВС в мультизадачных режимах;
создание методов, алгоритмов и программных средств организации функционирования распределённых ВС в режимах обработки наборов и обслуживании потоков задач;
развитие пространственно-распределённой мультикластерной вычислительной системы и формирование инструментария параллельного мультипрограммирования.
Методы исследования. В области организации функционирования распределённых ВС исследования проводились с использованием методов тео-
рий вычислительных систем, теории игр, математического программирования, исследования операций, теории вероятностей и эволюционных методов оптимизации. Экспериментальные исследования осуществлялись путём моделирования на пространственно-распределённой мультикластерной ВС. Научная новизна работы определяется следующим:
разработано семейство (последовательных и параллельных) алгоритмов организации функционирования распределённых ВС в режиме обработки наборов масштабируемых задач, учитывающих штраф за задержку решения и приоритеты выбора значений параметров задач;
созданы средства оптимизации функционирования распределённых ВС в режиме обработки потоков задач. Определены смешанные стратегии функционирования диспетчеров и планировщиков распределённой ВС;
определены смешанные стратегии функционирования распределённой ВС при обслуживании интенсивных потоков задач на неабсолютно надёжных ресурсах.
Практическая ценность работы состоит в том, что созданные алгоритмы и программные средства входят в состав инструментария параллельного мультипрограммирования распределённых ВС. Разработана система MOJOS (англ. MOldable JObs Scheduling), предназначенная для моделирования, отладки и анализа алгоритмов организации функционирования распределённых ВС. Программные средства внедрены в действующую пространственно-распределённую мультикластерную ВС Центра параллельных вычислительных технологий (ЦПВТ) ФГОБУ ВПО "СибГУТИ" и Лаборатории вычислительных систем Федерального государственного бюджетного учреждения науки Института физики полупроводников им. А. В. Ржанова Сибирского отделения Российской академии наук (ИФП СО РАН).
Реализация и внедрение результатов работы. Основные результаты исследований нашли применение в работах по созданию и развитию пространственно-распределённой мультикластерной ВС ЦПВТ ФГОБУ ВПО "СибГУТИ" и Лаборатории ВС ИФП СО РАН. Диссертационные исследования выполнялись в рамках федеральных целевых программ «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы» (ГК №02.514.11.0002 «Разработка программных технологий для развития российского сегмента Грид, систем параллельного программирования, систем компьютерной графики») и «Научные и научно-педагогические кадры инновационной России» (ГК №02.740.11.0006 «Проведение исследований в области распределённых вычислительных систем и развитие научно-учебного центра параллельных вычислительных технологий ФГОБУ ВПО "СибГУТИ"»). Работа поддержана грантами Российского фонда фундаментальных исследований (№ 00-01-
00126, 02-07-06099, 02-07-09380, 03-07-06008, 08-07-00022, 09-07-00095, 11-07-00109), грантами Президента РФ по поддержке молодых российских учёных и ведущих научных школ (МШІ-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 гг., г. Новосибирск);
Международной научно-технической конференции «Информационные системы и технологии» (2003 г., г. Новосибирск);
Первой Всероссийской научной конференции «Методы и средства обработки информации» (2003 г., г. Москва);
Региональной научной конференции студентов, аспирантов и молодых учёных «Наука. Техника. Инновации» (2002, 2003 гг., г. Новосибирск);
Школе-семинаре «Распределённые кластерные вычисления» (2001 г., г. Красноярск).
Научно-техническом семинаре ФГОБУ ВПО "СибГУТИ" (ежегодно);
Публикации. По теме диссертации опубликовано 63 работы, в том числе 9 — в изданиях из перечня ВАК.
Основные положения диссертации, выносимые на защиту.
Разработано семейство (последовательных и параллельных) алгоритмов организации функционирования распределённых ВС в режиме обработки наборов масштабируемых задач, учитывающих штраф за задержку решения и приоритеты выбора значений параметров задач.
Созданы средства оптимизации функционирования распределённых ВС в режиме обработки потоков задач. Определены смешанные стратегии функционирования диспетчеров и планировщиков распределённой ВС.
Сформирован инструментарий параллельного мультипрограммирования пространственно-распределённой мультикластерной ВС. В состав инструментария включён пакет моделирования и анализа алгоритмов организации функционирования распределённых ВС. С использованием этого пакета проведено моделирование предложенных в работе алгоритмов.
Структура и объём диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка литературы, включающего 350 наименований, и приложения. Текст содержит 18 рисунков.
