Содержание к диссертации
СПИСОК СОКРАЩЕНИЙ 5
ВВЕДЕНИЕ 6
ГЛАВА 1. ОСОБЕННОСТИ ОРГАНИЗАЦИИ БОЛЫПЕМАСШТАБНЫХ
РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И СЕТЕЙ .... 15
1.1. Модель коллектива вычислителей. Понятие
«вычислительная система» 15
1.2. Классификация ВС. Распределенные ВС.
Компьютерные сети и кластерные ВС. Grid-
системы 17
Цели создания распределенных ВС и Grid-систем 20
Структурная организация распределенных ВС и Grid-систем 22
Структура элементарных машин 22
Структура телекоммуникационной системы ... 23
1.5. Архитектура и функциональная организация
распределённых ВС и Grid-систем 28
Структура программного обеспечения 28
Основные режимы функционирования 36
1.6. Живучесть распределённых ВС и Grid-систем .... 4 0
1.7. Обзор существующих систем управления
распределенными ВС и Grid-системами 4 3
1.8. Выводы 44
ГЛАВА 2. СРЕДСТВА ОРГАНИЗАЦИИ ФУНКЦИОНИРОВАНИЯ
РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И СЕТЕЙ
(GRID-СИСТЕМ) 45
2.1. Обзор существующих подходов к организации
функционирования распределенных ВС и Grid-
систем 4 5
2.2. Понятия «вычислительный центр», «очередь
задач» и «диспетчер ОС» 48
2.4. Определение рангов для формирования пакетов
задач 50
Выбор ранга задач для формирования пакетов при условии выделения всех доступных ЭМ системы для решения задач 55
Выбор ранга задач для формирования пакетов при условии выделения части доступных ЭМ системы для решения задач 56
2.5. Формирование пакетов задач и определение
времени их решения на ВС 61
Определение последовательности опроса ЭМ для выравнивания загрузки системы 68
Решение теоретико-игровых проблем 72
Основные определения теории игр 72
Решение конечных антагонистических игр ... 73
Решение бесконечных антагонистических
игр 94
2.7.4. Решение игровых ситуаций с «природой» .... 96
2.8. Выводы 98
ГЛАВА 3. ПРОСТРАНСТВЕННО РАСПРЕДЕЛЕННАЯ КЛАСТЕРНАЯ
ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА (GRID-СИСТЕМА) 99
Классификация кластерных ВС 100
Пространственно распределённая кластерная ВС
(Grid-система) 101
Архитектура пространственно распределённой кластерной ВС (Grid-системы) 101
Оценка производительности кластерной ВС . 104
3.3. Моделирование решения поставленных задач
управления распределёнными ВС на кластерной
системе 107
3.4. Разработка диспетчера распределенной очереди
задач в кластерных ВС 111
3.5. Выводы 112
ЗАКЛЮЧЕНИЕ 122
ЛИТЕРАТУРА 123
ПРИЛОЖЕНИЕ. ИСХОДНЫЕ ТЕКСТЫ ПРОГРАММ 141
П.1. Программа, реализующая параллельный алгоритм
метода Брауна-Робинсон 141
П. 2. Программа, реализующая параллельный алгоритм
симплекс-метода 14 4
П.З. Программа распределённого диспетчера очереди
задач 151
СПИСОК СОКРАЩЕНИЙ
ВС - вычислительная система.
ВЦ - вычислительный центр.
ИФП СО РАН - Институт физики полупроводников Сибирского отделения Российской академии наук.
ОС - операционная система.
ПК - персональный компьютер.
ПО - программное обеспечение.
СибГУТИ - Сибирский Государственный университет телекоммуникаций и информатики.
СО АН СССР - Сибирское отделение Академии наук Союза Советских Социалистических Республик.
СС - система связей (телекоммуникационная сеть).
СУ - системное устройство.
ЭВМ - электронно-вычислительная машина.
ЭМ - элементарная машина.
Введение к работе
Актуальность работы. Потребность в высокопроизводительных средствах обработки информации привела к созданию параллельных вычислительных систем (ВС) с массовым параллелизмом[10,29,30,124] . В общем случае, ВС суть композиция элементарных машин (ЭМ), соединённых телекоммуникационной сетью. Построение таких систем основывается на принципах: параллельности выполнения операций, программируемости структуры и конструктивной однородности. Одним из типов архитектур вычислительных систем являются распределённые ВС. Все основные ресурсы таких систем (не только арифметико-логические устройства, но память и средства управления) являются логически и технически распределёнными. Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до 10б и более (например, в МВС-1000М это число равно 7 68, а в создаваемой системе IBM Blue Gene - 1 000 000). Для решения задач могут использоваться как все ЭМ (вся система целиком), так и часть из них. В последнем случае возможно одновременное решение нескольких задач, путём организации параллельного мультипрограммного режима. Опыт применения распределённых ВС показал [см., например, 37,38,44-57], что, чаще всего, для решения задач не требуются ресурсы всей системы. Поэтому проблема создания децентрализованных средств организации функционирования распределенных ВС в мультипрограммных режимах на сегодняшний день является актуальной.
Одновременно с развитием суперкомпьютеров, доступ к которым имели только большие научные организации или промышленные компании, велись разработки ЭВМ общего
пользования [29] . Переход на применение интегральных схем, упрощение архитектуры и удешевление технологии производства электронных компонентов, способствовали появлению и широкому распространению недорогих персональных компьютеров (ПК). Развитие телекоммуникационных технологий (разработка высокоскоростных и доступных широкому кругу пользователей средств связи) дало толчок к созданию компьютерных сетей. Программным образом компьютерные сети могут быть настроены на решение параллельных вычислительных задач. Такие программно настроенные сети стали называть кластерными системами (англ. cluster - группа) [29]. По сути, они являются распределёнными ВС с массовым параллелизмом. Производительность кластерных ВС сравнима с производительностью суперкомпьютеров, а стоимость значительно ниже.
Идея объединения различных пространственно распределённых вычислительных ресурсов, начиная от простых ПК и заканчивая суперкомпьютерами, с использованием стандартных телекоммуникационных средств (сетей, протоколов и т.п.) получила название Grid-технологии [15].
Разработки распределенных вычислительных систем ведутся с середины XX столетия. С тех пор, в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам организации высокопроизводительных вычислительных средств: проведены исследования по построению оптимальных (макро)структур ВС, проработаны многие аспекты разработки программного обеспечения, исследован широкий круг задач, допускающий эффективную реализацию на распределённых ВС. Построены отечественные системы из мини- и микроЭВМ: СУММА, МИНИМАКС,
МИКРОС, семейство систем МВС: МВС-100, МВС-1000, МВС-1000М и т.д.
Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем, компьютерных сетей и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П. Балашов [1,2], В.Б. Бетелин [8], B.C. Бурцев [10,119], В.В. Васильев [12], В.М. Вишневский [13,31], В.В. Воеводин [15], В.М. Глушков [17,106], В.В. Губарев [19], В.Ф. Евдокимов [26], Э.В. Евреинов [27-30], А.В. Забродин [94,160], В.П. Иванников [34], М.Б. Игнатьев [35], А.В. Каляев [37], М.А. Карцев [39], Л.Н. Королев [57], Н.А. Кузнецов [61], В.Г. Лазарев [62,105], С.А. Лебедев [64], В.К. Левин [65,160], Г.И. Марчук [76], Ю.И. Митропольский [43], В.К. Попков [100,101], Д.А. Поспелов [102], И.В. Прангишвили [103,104], Д.В. Пузанков [2,14,80,81], Г.Е. Пухов [105], Г.Г. Рябов [111], А.А. Самарский[152], В.Б. Смолов[116], А.Н. Томилин[128] , A.M. Федотов[129], Я.А. Хетагуров[132] , В.Г. Хорошевский [135-145,157], Б.Н. Четверушкин [148], Ю.И. Шокин [149], Н.Н. Яненко [153] и другие.
Огромные возможности ВС могут быть использованы и раскрыты только при применении эффективных методов и средств организации процессов решения задач [3,4,19,66] и особенно параллельного мультипрограммирования [138]. Под эффективностью методов понимается здесь не только то, что методы способны получить решение за конечное число шагов и с необходимой точностью, но и то, что
реализация этих методов на вычислительных системах позволяет найти решение за необходимо короткое время.
В вычислительных системах, функционирующих в режиме решения потока задач [30,136], характеристики и время поступления этих задач описываются случайными величинами. Поэтому при управлении ВС, затраты на поиск точных экстремумов целевых функций велики. Исследование и разработка методов и алгоритмов решения целевой функции, позволяющих получить хотя бы приближённый результат, являются актуальными.
Распределённые ВС и особенно Grid-системы формируются из не абсолютно надёжных компонентов, т.е. в системе в случайные моменты времени и по разным причинам могут происходить отказы ресурсов. Разработка отказоустойчивых (живучих) средств управления такими системами необходима.
Учитывая все сказанное выше, рассматриваемый в данной работе подход к организации функционирования распределённых вычислительных систем и сетей в мультипрограммных режимах (с использованием континуального подхода [23, 136] и методов теории игр [б, 7, 22, 24, 60, 93, 95, 110, 121, 147, 154,158]) видится перспективным.
Цели работы: разработка и исследование методов, алгоритмов и программных средств организации стохастически оптимального функционирования распределённых ВС и Grid-систем, создание пространственно распределённой кластерной Grid-системы для моделирования параллельных вычислительных технологий. Поставленные цели достигаются путем решения следующих проблем:
развития методов и программных средств формирования оптимальных пакетов задач для не абсолютно надежных распределённых ВС и Grid-систем;
разработки децентрализованных алгоритмов оптимальной загрузки каждой элементарной машины и, тем самым, минимизации времени простоя ресурсов ВС;
определения оптимальных стратегий функционирования распределённых ВС и Grid-систем при обслуживании интенсивных потоков параллельных задач;
создания распределённой в пространстве кластерной вычислительной системы (Grid-системы).
Методы исследования. В области организации функционирования распределённых ВС исследования проводились с использованием методов теории вычислительных систем, теории игр, математического программирования. Экспериментальные исследования осуществлялись путем параллельного моделирования методов решения поставленных проблем, с использованием созданной кластерной Grid-системы.
Научная новизна. В диссертации разработаны и исследованы средства организации функционирования большемас-штабных распределённых ВС и Grid-систем:
предложены математическая модель и децентрализованный алгоритм формирования пакетов задач для не абсолютно надежных распределённых ВС и Grid-систем;
разработаны математическая модель и алгоритм выбора последовательности опроса ЭМ с целью выравнивания загрузки вычислительной системы;
определены оптимальные стратегии функционирования ВС при обслуживании интенсивных потоков параллельных задач.
Практические результаты работы состоят в том, что:
создана и введена в эксплуатацию распределённая в пространстве кластерная Grid-система;
разработан программный комплекс для управления очередью задач в распределённых ВС и Grid-системах;
реализован пакет параллельных программ для оптимизации функционирования большемасштабных распределённых ВС и Grid-систем.
Апробация работы. Основные результаты работы докладывались на Международных, Всероссийских и Региональных научных конференциях, в том числе:
Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (2001, 2002, 2003 гг., г. Новосибирск);
Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (2003 г., г. Геленджик);
Международной научно-технической конференции "Информационные системы и технологии" (2003 г., г. Новосибирск);
Первой Всероссийской научной конференции «Методы и средства обработки информации» (2003 г., Москва) ;
Региональной научной конференции студентов, аспирантов и молодых ученых «Наука. Техника. Инновации» (2002, 2003 гг., г. Новосибирск);
школе-семинаре «Распределённые кластерные вычисления» (2001 г., г. Красноярск).
Реализация результатов работы. Результаты диссертационной работы нашли применение в работах по созданию и развитию распределённой кластерной вычислительной системы Центра параллельных вычислительных технологий Сиб-ГУТИ. Работа поддержана грантами Российского фонда фундаментальных исследований (РФФИ) № 02-07-09380, 02-07-06099, 03-07-06008, 00-01-00126, 02-07-09379. Основные положения диссертационной работы использовались автором при разработке и чтении учебных курсов на Кафедре вычислительных систем СибГУТИ по дисциплинам «Операционные системы», «Распределённые операционные системы» и «Организация ЭВМ и систем».
Практическое использование результатов диссертационных исследований подтверждается соответствующими актами о внедрении.
Основные положения, выносимые на защиту:
стохастическая модель и распределённый алгоритм формирования пакетов задач;
математическая модель и децентрализованный алгоритм поиска оптимальной последовательности опроса ЭМ для выравнивания загрузки распределённых ВС и Grid-систем;
программные средства организации функционирования распределённой очереди задач в кластерных ВС.
Публикации. По теме диссертации опубликовано 14 работ .
Содержание работы.
В первой главе описывается архитектурная и программная организация современных распределённых ВС, кластеров и Grid-систем, определены основные режимы их функционирования.
Во второй главе описана модель функционирования распределённых ВС, сформулированы задачи организации оптимального использования вычислительных ресурсов:
выбор оптимального ранга пакетов задач для решения на не абсолютно надежной ВС;
формирование пакетов задач. Предлагаемая модель позволяет упростить процедуру формирования пакетов, что дает возможность её использования для динамического управления системой;
организации опроса ЭМ в целях выравнивания загрузки системы.
Рассмотрены методы их решения и предложены параллельные версии этих методов.
В третьей главе описана архитектура и программное обеспечение созданной распределённой в пространстве кластерной вычислительной Grid-системы. Эта система эксплуатируется Центром параллельных вычислительных технологий Сибирского государственного университета те-
лекоммуникации и информатики совместно с Институтом физики полупроводников СО РАН.
В заключении приведены основные результаты диссертационной работы.
В приложении представлены исходные тексты разработанных библиотек программ.
