Введение к работе
Актуальность работы. Научно-технический прогресс неразрывно связан с решением вычислительных задач, сложность которых постоянно возрастает. Это определяет потребность в средствах высокопроизводительной обработки информации. Одним из инструментов решения сложных задач являются распределённые вычислительные системы (ВС), характеризующиеся массовым параллелизмом. Они формируются из унифицированных элементов (модулей), которые функционально и конструктивно закончены и имеют средства сопряжения друг с другом. В качестве базовых модулей ВС служат элементарная машина (ЭМ), оснащённая устройством управления, арифметико-логическим устройством (АЛУ), памятью и локальным коммутатором (ЛК), и узел ввода-вывода (УВВ), обеспечивающий доступ к данным. Конструктивно одна или несколько ЭМ размещаются на вычислительном узле (ВУ). Современные ВС являются распределёнными и болынемасштабными, количество ЭМ в них варьируется от десятков до сотен тысяч, а число УВВ от нескольких десятков до сотен. Например, система IBM Roadrunner состоит из 122 400 ЭМ и 216 УВВ, а система Cray ХТ5 Jaguar - из 224 162 ЭМ и 256 УВВ.
Согласно статистическим данным среднее время (к~) безотказной работы вычислительных узлов распределённых ВС лежит в промежутке 104 - 106 ч. (X - интенсивность потока отказов для одного ВУ). Но даже при использовании таких высоконадёжных компонентов в болынемасштабных ВС время между частичными отказами в среднем составляет несколько дней. Это ставит под вопрос осуществимость решения трудоёмких задач, представленных параллельными программами с количеством ветвей, сопоставимым с числом элементарных машин в ВС.
Существует множество задач, решение которых даже на современных ВС занимает от нескольких дней до недель. И количество таких задач постоянно растёт. В связи с вышесказанным актуальной является проблема организации отказоустойчивого функционирования болынемасштабных ВС.
Исследования в области распределённых вычислительных систем ведутся с 1960-х годов. Проблемам их создания и эксплуатации посвящен ряд фундаментальных работ. Разработаны основы теории функционирования ВС, синтеза оптимальных (макро)структур, теории надёжности и живучести ВС. Созданы инструментальные средства программного обеспечения, изучен широкий круг задач, которые могут эффективно решаться на распределённых ВС. Построены отечественные распределенные ВС с программируемой структурой: "Минск-222", МИНИМАКС, СУММА, МИКРОС, МВС и т. д.
Фундаментальный вклад в теорию и практику вычислительных систем, компьютерных сетей и параллельных вычислительных технологий внесли выдающиеся советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, А.В. Забродин, В.П. Иванников, М.Б. Игнатьев, А.В. Каляев,
И.А. Каляев, Л.Н. Королев, В.Г. Лазарев, С.А. Лебедев, В.К. Левин,
Г.И. Марчук, В.А. Мельников, Ю.И. Митропольский, Д.А. Поспелов,
И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, А.А. Самарский,
В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров, В.Г. Хорошевский,
Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко, а также зарубежные учёные: К.М. Chandy, G. Cooperman, S. Cray, J. Dongarra, M. Flynn, I. Foster, A. Gara, L. Lamport, M. Livny, J.S. Plank и другие.
В диссертации предложены средства организации отказоустойчивого функционирования распределённых ВС. На основе полученных результатов разработаны программные компоненты операционной системы (ОС), позволяющие формировать отказоустойчивые каналы передачи данных, средства создания контрольных точек (КТ) восстановления для параллельных и последовательных программ, а также инструментарий оптимизации распределённых КТ по объёму и времени сохранения.
Цель работы и задачи исследования. Целью диссертационной работы является разработка и исследование алгоритмических, программных и аппаратурных средств организации отказоустойчивого функционирования распределённых ВС в мультипрограммных режимах.
В соответствии с целью определены нижеследующие задачи:
Анализ архитектурных особенностей современных ВС и подходов к обеспечению их отказоустойчивого функционирования.
Организация отказоустойчивых гетерогенных каналов связи между территориально удалёнными компонентами пространственно-распределённых ВС.
Создание алгоритмов возобновления параллельных и последовательных программ из распределённых контрольных точек.
Разработка алгоритмов оптимизации распределённых КТ по объёму и времени создания с использованием технологии дельта-сжатия. Суть технологии заключается в сохранении только тех фрагментов состояния программы, которые были модифицированы относительно набора предыдущих КТ.
Реализация алгоритмов формирования отказоустойчивых гетерогенных каналов передачи данных в виде программного модуля ОС GNU/Linux.
Интеграция предложенных алгоритмов возобновления параллельных программ в существующие средства формирования распределённых КТ.
Создание системного программного инструментария, позволяющего выполнять сжатие КТ и формирование результирующих КТ в соответствии с техническими ограничениями (на объём используемой памяти); его интеграция с существующими средствами создания КТ (ССКТ).
Методы исследования. Для достижения поставленной цели и решения сформулированных в диссертационной работе задач использовались методы теории функционирования распределённых вычислительных систем, теории графов, теории алгоритмов, теории множеств, математический аппарат исследования операций и теории информации. Экспериментальные исследования
осуществлялись с помощью моделирования на пространственно-распределённой мультикластерной вычислительной системе.
Научная новизна работы. В диссертации разработаны и исследованы средства организации эффективного отказоустойчивого функционирования распределённых вычислительных систем:
Предложена математическая модель отказоустойчивого гетерогенного канала передачи данных, учитывающая пропускные способности составляющих его разнородных каналов связи.
Построена математическая модель ВС с отказоустойчивым выполнением параллельных программ. Модель предусматривает: 1) сохранение промежуточных состояний программ в контрольных точках, позволяющих возобновить программу в случае отказа; 2) сжатие КТ в процессе их создания.
Разработан алгоритм распределения информационных блоков по разнородным каналам передачи данных, обеспечивающий их равномерную загрузку. Уровень инверсий, образующийся в выходном потоке гетерогенного канала, не требует повторной пересылки блоков.
Создан алгоритм, позволивший корректно и полностью восстанавливать идентификационную информацию процессов ОС при возобновлении программ из распределённых КТ. Достоинством алгоритма является то, что он использует стандартный интерфейс ОС, следовательно, он может применяться в любых
POSIX-совместимых средствах создания контрольных точек.
Предложен параллельный алгоритм дельта-сжатия контрольных точек восстановления параллельных программ, разработанных с использованием стандарта ОрепМР.
Разработан адаптивный подход, осуществляющий (суб)оптимальный выбор КТ, относительно которой будет выполняться дельта-сжатие. Целями являются: 1) минимизация объёма сжатой КТ; 2) уменьшение количество сжатых КТ, необходимых для формирования результирующей КТ.
Создан алгоритм пакетного сжатия, совмещающий универсальное и дельта-сжатие, который обеспечивает (суб)оптимальное время формирования результирующей КТ.
Предложен параллельный алгоритм формирования результирующей КТ из набора дельта-сжатых, который выполняет поиск наиболее позднего целостного состояния параллельной программы.
Практическая ценность работы. Разработанные в диссертации модели и алгоритмы в сочетании с существующими средствами обеспечивают отказоустойчивость распределённых вычислительных систем.
Предложенный алгоритм распределения информационных блоков по разнородным каналам связи гарантирует отказоустойчивое соединение узлов ВС и обеспечивает приближение пропускной способности гетерогенного канала к её предельному значению.
Алгоритм восстановления идентификационной информации процессов обеспечивает эквивалентность возобновлённой и исходной программ. Это позволяет сохранять связи между компонентами параллельной программы. Корректность и полнота восстановления идентификационной информации являются важными характеристиками средств создания контрольных точек.
Предложенные алгоритмы дельта-сжатия контрольных точек существенно снижают нагрузку на подсистему ввода-вывода за счёт её распределения между УВВ и ВУ при создании КТ для параллельных программ, характеризующихся частичной модификацией памяти в процессе работы. Разработаны алгоритмы, обеспечивающие (суб)оптимальное время восстановления результирующей КТ из набора сжатых КТ.
Реализация и внедрение результатов работы. Основные результаты диссертационной работы внедрены. Они, в частности, составляют основу программного инструментария поддержки отказоустойчивости пространственно-распределённой мультикластерной вычислительной системы Центра параллельных вьгаислительных технологий ГОУ ВПО "Сибирский государственный университет телекоммуникаций и информатики" (ЦПВТ ГОУ ВПО "СибГУ-ТИ") и Лаборатории вьгаислительных систем Института физики полупроводников им. А. В. Ржанова СО РАН (ИФП СО РАН). Вычислительная система активно используется в учебном процессе ГОУ ВПО "СибГУТИ".
Диссертационные исследования выполнялись по программе ведущей научной школы (НШ-2121.2008.9, НШ-5176.2010.9), проекту 32.1.1 "Архитектура, проблемы функционирования и моделирование болынемасштабных распределённых вьгаислительных систем" Программы IV.32.1 базовых исследований СО РАН и в рамках проектов №07-07-00142, 08-07-00018, 09-07-00095 Российского фонда фундаментальных исследований.
Алгоритм распределения информационных блоков по разнородным каналам связи был реализован в виде режима драйвера объединения каналов ОС GNU/Linux (Linux Channel Bonding). Модифицированный драйвер внедрен в программное обеспечение платформы Sigrand SG-17R отечественного производителя телекоммуникационного оборудования ООО "Сигранд" и применяется на действующих каналах связи в России и странах СНГ.
Алгоритм восстановления идентификационной информации процессов параллельной программы реализован в виде модуля свободно распространяемого пакета создания распределённых контрольных точек DMTCP (Distributed MultiThreaded Checkpointing), начиная с версии 1.1.9.
Предложенные алгоритмы дельта-сжатия КТ легли в основу программного инструментария HBICT (Hash-Based Incremental Checkpointing Tool), который позволяет: 1) производить оценку и выбор наиболее эффективного режима сжатия для конкретных параллельных программ и конфигураций ВС; 2) в сочетании с существующими средствами создания КТ выполнять автоматическое сжатие формируемых КТ (выполнена интеграция HBICT с пакетом DMTCP);
3) обеспечить (суб)оптимальное время формирования результирующей КТ из набора сжатых.
Достоверность полученных результатов подтверждается проведёнными экспериментами и моделированием, согласованностью с данными, имеющимися в отечественной и зарубежной литературе, и экспертизами работы, прошедшими при получении грантов.
Апробация работы. Основные результаты работы докладывались и обсуждались на Международных, Всероссийских и региональных научных конференциях, в том числе:
-Международных научно-технических конференциях "Многопроцессорные вычислительные и управляющие системы" (с. Дивноморское Геленджик-ского района, 2007, 2009 гг.).
Международных научных студенческих конференциях "Студент и научно-технический прогресс" (г. Новосибирск, 2007, 2008, 2009, 2010 гг.).
Всероссийских научно-технических конференциях "Информатика и проблемы телекоммуникаций" (г. Новосибирск, 2007, 2008, 2009, 2010 гг.).
Всероссийских конференциях с международным участием "Новые информационные технологии в исследовании сложных структур" (г. Томск, 2008, 2010 гг.).
Международной научной студенческой конференции "Научный потенциал студенчества - будущему России" (г. Ставрополь, 2008 г.).
Международной научной конференции "Параллельные вычислительные технологии (ПаВТ'2010)" (г. Уфа, 2010 г.).
Международной научно-технической конференции "Суперкомпьютерные технологии" (с. Дивноморское Геленджикского района, 2010 г.).
Публикации. По теме диссертации опубликовано 23 работы, включая 4 статьи в рецензируемых журналах. Результаты исследований отражены в отчётах по грантам и НИР.
Основные положения диссертации, выносимые на защиту.
Математическая модель отказоустойчивого гетерогенного канала передачи данных и эвристический алгоритм распределения информационных блоков, учитывающие разнородность используемых каналов связи.
Математическая модель распределённой ВС с отказоустойчивым выполнением параллельных программ, предусматривающая наличие служебной информации процессов ОС и сжатие контрольных точек восстановления.
Алгоритм восстановления идентификационной информации процессов параллельной программы, который использует только стандартный интерфейс при взаимодействии с ОС.
Алгоритмы определения и сохранения модифицированных фрагментов контрольных точек восстановления (алгоритмы дельта-сжатия).
Программный инструментарий дельта-сжатия, реализующий предложенные алгоритмы.
6. Средства отказоустойчивого функционирования пространственно-распределённых мультикластерных ВС.
Структура и объём диссертации. Диссертационная работа состоит из введения, трех глав, заключения, списка используемых литературных источников и приложений. Общий объем работы - 173 страницы.
