автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Разработка и исследование средств отказоустойчивости распределённых вычислительных систем

На правах рукописи

0046

7583

Поляков Артём Юрьевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ СРЕДСТВ ОТКАЗОУСТОЙЧИВОСТИ РАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность 05.13.15 - Вычислительные машины, комплексы и компьютерные сети

Автореферат диссертации на соискание ученой степени кандидата технических наук

1 С ДЕК ?о:э

Новосибирск - 2010

004617583

Работа выполнена на Кафедре вычислительных систем Государственного образовательного учреждения высшего профессионального образования "Сибирский государственный университет телекоммуникаций и информатики" Федерального агентства связи Министерства связи и массовых коммуникаций РФ.

Научный руководитель - доктор технических наук профессор

Член-корреспондент РАН Заслуженный деятель науки РФ Хорошевский Виктор Гаврилович

Официальные оппоненты: доктор технических наук профессор

лауреат государственной премии СССР Рычков Александр Дмитриевич

доктор технических наук Шндловскпн Станислав Викторович

Ведущая организация - Научно-исследовательский институт многопроцессорных вычислительных систем им. А. В. Каляева Южного федерального университета

Защита состоится "23" декабря 2010 г. в 14 час. 00 мин. на заседании Диссертационного совета Д 219.005.02 при ГОУ ВПО "СибГУТИ", по адресу: 630102, г. Новосибирск, ул. Кирова, д. 86, ком. 625.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО "СибГУТИ".

Автореферат разослан "•£2." 2010 г.

Ученый секретарь

Диссертационного совета Д 219.005.02

кандидат технических наук ¡л/!/^——^

доцент " и. И. Резван

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Научно-технический прогресс неразрывно связан с решением вычислительных задач, сложность которых постоянно возрастает. Это определяет потребность в средствах высокопроизводительной обработки информации. Одним из инструментов решения сложных задач являются распределённые вычислительные системы (ВС), характеризующиеся массовым параллелизмом. Они формируются из унифицированных элементов (модулей), которые функционально и конструктивно закончены и имеют средства сопряжения друг с другом. В качестве базовых модулей ВС служат элементарная машина (ЭМ), оснащённая устройством управления, арифметико-логическим устройством (АЛУ), памятью и локальным коммутатором (JIK), и узел ввода-вывода (УВВ), обеспечивающий доступ к данным. Конструктивно одна или несколько ЭМ размещаются на вычислительном узле (ВУ). Современные ВС являются распределёнными и болыпемасштабными, количество ЭМ в них варьируется от десятков до сотен тысяч, а число УВВ от нескольких десятков до сотен. Например, система IBM Roadrunner состоит из 122 400 ЭМ и 2 16 УВВ, а система Cray ХТ5 Jaguar -из 224 162 ЭМ и 256 УВВ.

Согласно статистическим данным среднее время (АГ1) безотказной работы вычислительных узлов распределённых ВС лежит в промежутке 104- 106 ч. (к - интенсивность потока отказов для одного ВУ). Но даже при использовании таких высоконадёжных компонентов в большемасштабных ВС время между частичными отказами в среднем составляет несколько дней. Это ставит под вопрос осуществимость решения трудоёмких задач, представленных параллельными программами с количеством ветвей, сопоставимым с числом элементарных машин в ВС.

Существует множество задач, решение которых даже на современных ВС занимает от нескольких дней до недель. И количество таких задач постоянно растёт. В связи с вышесказанным актуальной является проблема организации отказоустойчивого функционирования большемасштабных ВС.

Исследования в области распределённых вычислительных систем ведутся с 1960-х годов. Проблемам их создания и эксплуатации посвящен ряд фундаментальных работ. Разработаны основы теории функционирования ВС, синтеза оптимальных (макро)структур, теории надёжности и живучести ВС. Созданы инструментальные средства программного обеспечения, изучен широкий круг задач, которые могут эффективно решаться на распределённых ВС. Построены отечественные распределенные ВС с программируемой структурой: "Минск-222", МИНИМАКС, СУММА, МИКРОС, МВС и т. д.

Фундаментальный вклад в теорию и практику вычислительных систем, компьютерных сетей и параллельных вычислительных технологий внесли выдающиеся советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Глушков, В.Ф. Евдокимов,

Э.В. Евреинов, A.B. Забродин, В.П. Иванников, М.Б. Игнатьев, A.B. Каляев, И.А. Каляев, J1.H. Королев, В.Г. Лазарев, С.А. Лебедев, В.К. Левин, Г.И. Марчук, В.А. Мельников, Ю.И. Митропольский, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, A.A. Самарский, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, H.H. Яненко, а также зарубежные учёные: K.M. Chandy, G. Coopennan, S. Cray, J. Dongarra, M. Flynn, I. Foster, A. Gara, L. Lamport, M. Livny, J.S. Plank и другие.

' В диссертации предложены средства организации отказоустойчивого функционирования распределённых ВС. На основе полученных результатов разработаны программные компоненты операционной системы (ОС), позволяющие формировать отказоустойчивые каналы передачи данных, средства создания контрольных точек (KT) восстановления для параллельных и последовательных программ, а также инструментарий оптимизации распределённых KT по объёму и времени сохранения.

Цель работы и задачи исследования. Целью диссертационной работы является разработка и исследование алгоритмических, программных и аппаратурных средств организации отказоустойчивого функционирования распределённых ВС в мультипрограммных режимах.

В соответствии с целью определены нижеследующие задачи:

1. Анализ архитектурных особенностей современных ВС и подходов к обеспечению их отказоустойчивого функционирования.

2. Организация отказоустойчивых гетерогенных каналов связи между территориально удалёнными компонентами пространственно-распределённых ВС.

3. Создание алгоритмов возобновления параллельных и последовательных программ из распределённых контрольных точек.

4. Разработка алгоритмов оптимизации распределённых KT по объёму и времени создания с использованием технологии дельта-сжатия. Суть технологии заключается в сохранении только тех фрагментов состояния программы, которые были модифицированы относительно набора предыдущих KT.

5. Реализация алгоритмов формирования отказоустойчивых гетерогенных каналов передачи данных в виде программного модуля ОС GNU/Linux.

6. Интеграция предложенных алгоритмов возобновления параллельных программ в существующие средства формирования распределённых KT.

7. Создание системного программного инструментария, позволяющего выполнять сжатие KT и формирование результирующих KT в соответствии с техническими ограничениями (на объём используемой памяти); его интеграция с существующими средствами создания KT (ССКТ).

Методы исследования. Для достижения поставленной цели и решения сформулированных в диссертационной работе задач использовались методы теории функционирования распределённых вычислительных систем, теории графов, теории алгоритмов, теории множеств, математический аппарат исследования

операций и теории информации. Экспериментальные исследования осуществлялись с помощью моделирования на пространственно-распределённой мультикла-стерной вычислительной системе.

Научная новизна работы. В диссертации разработаны и исследованы средства организации эффективного отказоустойчивого функционирования распределённых вычислительных систем:

]. Предложена математическая модель отказоустойчивого гетерогенного канала передачи данных, учитывающая пропускные способности составляющих его разнородных каналов связи.

2. Построена математическая модель ВС с отказоустойчивым выполнением параллельных программ. Модель предусматривает: I) сохранение промежуточных состояний программ в контрольных точках, позволяющих возобновить программу в случае отказа; 2) сжатие КТ в процессе их создания.

3. Разработан алгоритм распределения информационных блоков по разнородным каналам передачи данных, обеспечивающий их равномерную загрузку. Уровень инверсий, образующийся в выходном потоке гетерогенного канала, не требует повторной пересылки блоков.

4. Создан алгоритм, позволивший корректно и полностью восстанавливать идентификационную информацию процессов ОС при возобновлении программ из распределённых КТ. Достоинством алгоритма является то, что он использует стандартный интерфейс ОС, следовательно, он может применяться в любых РОБК-совместимых средствах создания контрольных точек.

5. Предложен параллельный алгоритм дельта-сжатия контрольных точек восстановления параллельных программ, разработанных с использованием стандарта ОрепМР.

6. Разработан адаптивный подход, осуществляющий (суб)оптимальный выбор КТ, относительно которой будет выполняться дельта-сжатие. Целями являются: 1) минимизация объёма сжатой КТ; 2) уменьшение количество сжатых КТ, необходимых для формирования результирующей КТ.

7. Создан алгоритм пакетного сжатия, совмещающий универсальное и дельта-сжатие, который обеспечивает (суб)оптимальное время формирования результирующей КТ.

8. Предложен параллельный алгоритм формирования результирующей КТ из набора дельта-сжатых, который выполняет поиск наиболее позднего целостного состояния параллельной программы.

Практическая ценность работы. Разработанные в диссертации модели и алгоритмы в сочетании с существующими средствами обеспечивают отказоустойчивость распределённых вычислительных систем.

Предложенный алгоритм распределения информационных блоков по разнородным каналам связи гарантирует отказоустойчивое соединение узлов ВС и обеспечивает приближение пропускной способности гетерогенного канала к её предельному значению.

Алгоритм восстановления идентификационной информации процессов обеспечивает эквивалентность возобновлённой и исходной программ. Это позволяет сохранять связи между компонентами параллельной программы. Корректность и полнота восстановления идентификационной информации являются важными характеристиками средств создания контрольных точек.

Предложенные алгоритмы дельта-сжатия контрольных точек существенно снижают нагрузку на подсистему ввода-вывода за счёт её распределения между УВВ и ВУ при создании КТ для параллельных программ, характеризующихся частичной модификацией памяти в процессе работы. Разработаны алгоритмы, обеспечивающие (суб)оптимальное время восстановления результирующей КТ из набора сжатых КТ.

Реализация и внедрение результатов работы. Основные результаты диссертационной работы внедрены. Они, в частности, составляют основу программного инструментария поддержки отказоустойчивости пространственно-распределённой мультикластерной вычислительной системы Центра параллельных вычислительных технологий ГОУ ВПО "Сибирский государственный университет телекоммуникаций и информатики" (ЦПВТ ГОУ ВПО "СибГУТИ") и Лаборатории вычислительных систем Института физики полупроводников им. А. В. Ржанова СО РАН (ИФП СО РАН). Вычислительная система активно используется в учебном процессе ГОУ ВПО "СибГУТИ".

Диссертационные исследования выполнялись по программе ведущей научной школы (НШ-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 статьи в рецензируемых журналах. Результаты исследований отражены в отчётах по грантам и НИР.

Основные положения диссертации, выносимые на защиту.

1. Математическая модель отказоустойчивого гетерогенного канала передачи данных и эвристический алгоритм распределения информационных блоков, учитывающие разнородность используемых каналов связи.

2. Математическая модель распределённой ВС с отказоустойчивым выполнением параллельных программ, предусматривающая наличие служебной информации процессов ОС и сжатие контрольных точек восстановления.

3. Алгоритм восстановления идентификационной информации процессов параллельной программы, который использует только стандартный интерфейс при взаимодействии с ОС.

4. Алгоритмы определения и сохранения модифицированных фрагментов контрольных точек восстановления (алгоритмы дельта-сжатия).

5. Программный инструментарий дельта-сжатия, реализующий предложенные алгоритмы.

6. Средства отказоустойчивого функционирования пространственно-распределённых мультикластерных ВС.

Структура и объём диссертации. Диссертационная работа состоит из введения, трех глав, заключения, списка используемых литературных источников и приложений. Общий объем работы - 173 страницы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении определены цели и задачи диссертационного исследования, обоснована его актуальность. Сформулированы основные положения, выносимые на защиту.

В первой главе вводится понятие распределенной вычислительной системы, описываются её архитектурные свойства и характеристики. Рассматриваются особенности вычислительных систем с программируемой структурой, кластерных, мультикластерных и GRID-систем.

Распределённые ВС - это вычислительные средства с MIMD архитектурой, которые представляют собой композицию элементарных машин и узлов ввода-вывода. Они являются основным инструментом решения трудоёмких задач.

В силу большемасштабности распределённых ВС особая роль отводится средствам обеспечения их надёжности и живучести. В самом деле, отказы ВУ, принимающих участие в решении трудоёмких задач, приводят к потере промежуточных результатов вычислений и необходимости перезапуска всей параллельной программы, что снижает технико-экономическую эффективность ВС и ставит под вопрос осуществимость решения некоторых трудоёмких задач.

Важным свойством ВС, в отличие от ЭВМ, является возможность частичного отказа, который нарушает нормальную работу лишь некоторого числа её компонентов. Основой методик обеспечения отказоустойчивости распределённых ВС является введение избыточности: аппаратурной или (и) программной. Аппаратурная избыточность позволяет повысить отказоустойчивость за счёт одновременного использования нескольких компонентов для реализации одного и того же процесса (например, технологии RAID, Channel Bonding). Программная избыточность позволяет организовать отказоустойчивое выполнение параллельных программ. Наиболее распространёнными примерами данного подхода являются программы, обладающие свойством адаптируемости или возобиовляемости. Свойство адаптируемости определяет способность программы подстраиваться под число исправных ЭМ. Свойство возобиовляемости предполагает возможность сохранять промежуточное состояние параллельной программы, которое в дальнейшем может быть использовано для её перезапуска (возобновления). В диссертационной работе рассмотрены подходы, основанные как на аппаратурной, так и на программной избыточности.

Во второй главе предложены: 1) математическая модель отказоустойчивого гетерогенного канала передачи данных и алгоритм распределения информационных блоков по разнородным каналам связи; 2) математическая модель ВС с отка-

зоустойчивым выполнением параллельных программ, компоненты алгоритмов возобновления параллельных программ из КТ, а также подходы к оптимизации времени создания и объема распределённых КТ.

Модель отказоустойчивого гетерогенного канала передачи данных. При объединении пространственно удаленных компонентов ВС часто возможно одновременное использование нескольких разнородных телекоммуникационных каналов (радиоканал, выделенная линия, оптоволоконный кабель и т. д.) как единого логического канала связи.

Рассмотрим модель гетерогенного канала передачи данных. Пусть имеется множество С={1,2,..., Щ каналов связи (рис.1), для каждого канала /еС определена его пропускная способность ¿>/. На вход гетерогенного канала подается набор информационных блоков й={\, 2,...,К}, для каждого блока кеО определен его размер -л>.

Рис. 1. Схема гетерогенного канала передачи данных

Алгоритм распределения блоков определяет сюръективное отображение /: О —* С, которое каждому информационному блоку ставит в соответствие один из исправных физических каналов. Алгоритм объединения осуществляет слияние информационных блоков в порядке их поступления; /2) ..., 4- из каналов С.

Для оценки эффективности гетерогенного канала передачи данных используются следующие показатели: совокупная пропускная способность и среднее число инверсий в выходном потоке. В качестве оценки сверху для пропускной способности гетерогенного канала берется суммарная пропускная способность составляющих его физических каналов. При передаче информационных блоков по гетерогенному каналу возможно появление инверсий (нарушения порядка следования блоков) в выходном потоке. Обработка инверсий создает накладные расходы, которые могут в значительной мере повлиять на другие показатели производительности. Для оценки данной характеристики рассматривается усреднённое число I инверсий в выходном потоке, приходящееся на один информационный блок:

[о, /,</,,/<./,

где К- количество передаваемых информационных блоков.

Для гетерогенных каналов актуальной является задача минимизации числа инверсий в выходном потоке.

Алгоритм распределения информационных блоков. Для решения описанной выше задачи автором предложен [1,2,16] эвристический алгоритм RateBalance распределения информационных блоков. Для каждого канала /еС вводится параметр t„ хранящий значение времени окончания передачи данных, находящихся в очереди отправки канала. Далее определяется время доставки информационного блока размером s по каналу i в момент времени t' с учётом текущей загрузки: <p(s, i, t0 = S(t\ t,) + .<//;„ где

В алгоритме RateBalance номер канала для информационного блока размером s выбирается по формуле arg min <p(s,j,t'), далее происходит корректировка

соответствующего параметра!, по формуле t¡ = с)(/', (,) + ¡/Ь,.

Вычислительная сложность RateBalance при обработке одного информационного блока линейна — О(Л'). Моделирование предложенного алгоритма показало, что по сравнению с существующими аналогами он позволяет обеспечить пропорциональную загрузку разнородных каналов связи и приблизить совокупную пропускную способность к её верхней оценке.

Модель ВС с отказоустойчивым выполнением параллельных программ. Рассмотрим распределённую ВС, состоящую из множества ЭМ С={1,2, которые распределены по М вычислительным узлам £={1,2, ..., М]. Пусть также дан вектор а = (аь а2,..., где а,еЕ содержит номер ВУ, на котором расположена ЭМ с номером /.

Параллельная программа Р представляет собой совокупность процессов Р=( 1,2, ..., и'), при этом элементы {1,2, ...,и} реализуют ветви параллельного алгоритма, а {п + 1, п + 2,..., п'} составляют набор служебных процессов. Для выполнения Р, реализующей параллельный алгоритм из п ветвей, выделяется подсистема из л ЭМ. Каждой ветви из Р взаимно однозначно ставится в соответствие одна ЭМ из выделенной подсистемы, служебные процессы отображаются на множество вычислительных узлов. Таким образом, существует отображение всех процессов Р на множество Е: р = (рь р2,..., р„')> Р¡е£, где Р, определяет номер ВУ, на котором выполняется процесс /'.

Пусть в рассматриваемой ВС реализовано отказоустойчивое выполнение параллельных программ. Тогда в процессе работы Р происходит периодическое создание контрольных точек (КТ) восстановления, в которых сохраняется её промежуточное состояние. Обозначим через К, распределённую КТ, которая была создана в некоторый момент времени I и состоит из набора локальных КТ, однозначно соответствующих процессам из Р: К1 = (КЛ,Ка,..-,Кш). Каждая КТ К,, может быть представлена в виде пары <Ьи, £>„>, где Ь„ - локальный компонент, включающий регионы памяти, идентификационную информацию процесса в ОС,

информацию о потоках и открытых файлах и т.д.; D0 = <6'„ , '/'„> - распределённый компонент, где G,,- фрагмент графа информационных связей (например, набор рёбер, инцидентных /'), Т„ - содержимое транзитных сообщений, передававшихся через С,, в момент t создания КТ К,.

Пусть в момент времени V выполняется возобновление программы Р -{1, 2, ..., п'} из КТ К' = Кi на исправной подсистеме ВУ, определяемой вектором [У. Состояние Р'в момент времени /'должно быть эквивалентно состоянию Р в момент времени (, а именно: 1) любые процессы i, i е Р, выполнявшиеся на одном ВУ (р, = Р, ), восстанавливаются также на одном ВУ ([!', - ft','); 2) содержимое памяти соответствующих процессов идентично; 3) идентификационная информация на вычислительных узлах эквивалентна; 4) состояние внешних связей процессов (сокетов, файлов и т. и.) идентично.

Идентификационная информация процессов ОС. В рамках ОС с каждым процессом ассоциирован набор идентификаторов - <d,p,s,g,f>, где: d - идентификатор процесса, уникальный в рамках ВУ; р - уникальный идентификатор процесса-родителя; s - уникальный идентификатор сеанса, к которому принадлежит процесс; g— идентификатор группы;/- номер группы первого плана в рамках сеанса s. Описанная информация сохраняется в локальных компонентах КТ.

Отношение родитель-потомок определяет древовидную организацию процессов в ОС, при этом корнем является процесс с именем init и d = 1. Процессы могут объединяться в группы и сеансы, в рамках которых доступны определённые виды межпроцессных взаимодействий. Членство в группе первого плана даёт возможность осуществлять чтение с терминального устройства, ассоциированного с сеансом процесса.

Обеспечение эквивалентности идентификационной информации процессов параллельной программы. Пусть выполняется первое условие эквивалентности состояний программ. Номера процессов программы Р, выполнявшихся на ВУ j, определим через П(/) = {/1 р, =у,/е/>). Тогда процессы Р'„ /еП будут выполняться на узле j' (У /e ll /j", =j ). Под эквивалентностью идентификационной информации будем понимать изоморфность иерархической организации процессов на узлах j и j (У/, i'c IT d, - p,> => d', =//,■), а также выполнение V i, i'e П условий сохранения:

1) принадлежности к одному сеансу (5, ¿у => s', - У,');

2) лидерства в сеансе ( dj=Sj => d', = s',);

3) принадлежности к одной группе (g, = g,> => g', = g'r);

4) лидерства в группе ( d, =--- g, => d', = g', );

5) принадлежности к группе первого плана (f, =f2 => f, - f2).

На данный момент известны решения указанной задачи только с использованием прямого доступа к внутренним структурам ядра ОС,

В диссертационной работе предложен [5, 8, 10, И] алгоритм User Space Credential Restore (USCR), использующий для взаимодействия с ОС только интер-

фейс системных вызовов. Это позволяет применять его в средствах создания КТ, не имеющих прямого доступа к ядру ОС.

Задача оптимизации объёма КТ. Рассмотрим набор КТ (Кц,К2,,...,К„), соответствующих состоянию г'-го процесса в моменты времени 1,2,...,/. Введём функцию которая определяет размер объекта X в байтах. Пусть также определена функция сжатия КТ, созданной в момент времени относительно ряда предыдущих: к(Ки, К2„..., А'(,ч)„ которая формирует сжатую КТ Ъп\ ЗС/.,;) < Б(К,.,). При этом существует обратная функция к"1 такая, что к ~\Ки, 72„..., Для оптимизации объёма дискового пространства,

используемого для хранения распределённых КТ, и снижения накладных расходов, создаваемых - при формировании КТ, необходимо минимизировать объём сжатой КТ.

Наиболее распространёнными вариантами сжатия КТ являются: 1) универсальные алгоритмы сжатия, для которых = к(Г,.,); 2) сжатие с помощью дельт (дельта-сжатие), которое предусматривает формирование ¡инкрементных = к(7(('.1)>„ Г,.,)) или дифференциальных = к('1\„ /',•,)) контрольных точек (при одинаковой функции к).

В диссертационной работе рассмотрены алгоритмы дельта-сжатия, использующие хеш-функции с низкой вероятностью коллизии для создания "отпечатков" фрагментов КТ, которые в дальнейшем применяются для обнаружения изменённых фрагментов.

Возможны три основных типа изменений одного массива данных относительно другого: модификация, вставка и удаление фрагментов. Алгоритмы дельта-сжатия могут быть классифицированы по видам изменений, которые они способны обнаруживать.

Достаточно распространёнными являются алгоритмы дельта-сжатия, способные обнаруживать только модификации фрагментов. Существуют также подходы, рассчитанные на все указанные виды изменений. Например, алгоритмы, использующие принцип скользящего окна (А. Тпс^е11, 1999).

В диссертационной работе показано, что алгоритмы, основанные на принципе скользящего окна, имеют квадратичную вычислительную сложность относительно объёма обрабатываемых данных. Это делает их неэффективными для сжатия КТ. С другой стороны, для большинства параллельных программ не свойственно интенсивное использование динамической памяти, поэтому можно считать, что операции вставки и удаления фрагментов достаточно редки. В диссертационной работе предложен параллельный алгоритм Р-РНавЬ, позволяющий обнаруживать модифицированные фрагменты КТ.

1. Разработанный алгоритм Р-РНазЬ [4, 9, 12] основан на методике крупноблочного распараллеливания. Он позволяет задействовать все доступные ядра узлов ВС для сжатия КТ параллельных программ, созданных с использованием стандарта ОрепМР. Моделирование алгоритма Р-РНахЬ показало, что он имеет масштабируемость, близкую к линейной.

2. На основе алгоритма Р-Г'НаяЬ предложен адаптивный подход [13 -15], совмещающий преимущества дифференциального и инкрементного дельта-сжатия. Основным видом КТ являются дифференциальные КТ. Пусть производится создание КТ К„ в момент времени / для процесса /е текущая базовая КТ - В соответствии с алгоритмом Р-РНазЬ определяется количество модификаций относительно базовой К Г - '¿\ - лг(7',„ Г,,) и относительно предыдущей КТ 72 = к(Т(,Л)1, Т,^. Если ($('/]) - З^)) / ^Г,,) > В, где В - параметр алгоритма, определяющий некоторое граничное значение, то принимается. решение о сохранении инкрементной КТ, которая становится базовой (/' = /) для последующих КТ. Моделирование предложенного подхода показало, что он позволяет существенно снизить объём и время создания КТ. На рис. 2 показаны объёмы несжатых и дельта-сжатых КТ, полученных для прикладной программы моделирования газодинамических процессов в подушке безопасности автомобиля (Ай1^).

■У.Гб

Рис. 2. Объём 5 КТ, созданных для программы АЫ^; п - номер КТ -- размер несжатой КТ; -- размер дельта-сжатой КТ

3. Предложена модификация Р-РНазИ [13, 15], совмещающая стандартные алгоритмы сжатия и дельта-сжатие. Для ускорения процесса формирования результирующей КТ используется частичное сжатие, которое предусматривает группировку изменённых блоков в пакеты, каждый из которых сжимается независимо от других. Моделирование показало, что данный подход позволяет примерно в два раза снизить накладные расходы при формировании КТ.

4. Предложен параллельный алгоритм формирования результирующей распределённой КТ в условиях возможного нарушения целостности сжатых КТ [15]. Данный алгоритм способен корректно обрабатывать ситуации, когда некоторые блоки одной или нескольких КТ были повреждены, и формировать максимально позднее целостное состояние из набора исправных блоков. В результате работы алгоритма результирующие локальные КТ ветвей параллельной программы располагаются в оперативной памяти вычислительных узлов и готовы к передаче ССКТ.

В третьей главе описана архитектура пространственно-распределённой мультикластерной вычислительной системы ЦПВТ ГОУ ВПО "СибГУТИ" и Лаборатории ВС ИФГТ СО РАН (рис. 3) и средства обеспечения отказоустойчивости ВС.

Рис. 3. Конфигурация пространственно-распределенной мультикластерной ВС

Система объединяет 9 пространственно-распределённых кластерных ВС. Кластеры А - G расположены в ЦПВТ ГОУ ВПО "СибГУТИ", а кластеры H, 1 - в Лаборатории ВС ИФП СО РАН. Каждый из кластеров А -1 может рассматриваться как отдельная ВС, так и как компонент мультикластерной ВС. Системы А, В, С и H являются кластерами рабочих станций и персональных компьютеров. В состав кластера D (Хеоп16) входит 4 вычислительных узла, построенных на двухъядерных процессорах Intel Xeon 5150 (Woodcrest). Кластер Е (Хеоп32) состоит из четырёх вычислительных узлов, оснащённых двумя четырёхядерными процессорами Intel Quad Xeon Е5345. Кластер F (Хеоп80) укомплектован 10 вычислительными узлами, на каждом из которых расположено два четырёхядерных процессора Intel Quad Xeon Е5420. Кластер G (Unicluster) укомплектован четырьмя вычислительными узлами, оснащёнными двумя четырёхядерными процессорами Intel Xeon Е5410. Кластер I (OpteronlO) состоит из 6 двухпроцессорных узлов, каждый из которых представляет собой систему NUMA на базе процессоров AMD Opteron 248.

Коммуникационные среды вычислительных кластеров построены на базе технологий Gigabit и Fast Ethernet, а для их объединения используется сеть Internet (технология VPN). Связь осуществляется через выделенные серверы сегментов ЦПВТ ГОУ ВПО "СибГУТИ" и Лаборатории ВС ИФП СО РАН. В целом система включает более 250 процессорных ядер и имеет пиковую производитель-

ность несколько TeraFLOPS. Мультикластерная ВС допускает масштабирование путём организации взаимодействия с множеством других систем.

Для организации отказоустойчивых каналов передачи данных выполнена реализация предложенного алгоритма RateBalance в виде дополнительного режима драйвера объединения каналов Linux Channel Bonding. Произведено его внедрение в состав программного обеспечения мультикластерной ВС и в оборудование отечественного производителя телекоммуникационных устройств Sigrand (http://www.sigrand.ru).

Для организации отказоустойчивого выполнения параллельных программ на мультикластерной ВС установлен свободно распространяемый пакет [6,7] DMTCP (http://dmtcp.sourceforge.net/), представляющий собой универсальную систему создания KT. В указанном пакете реализован предложенный алгоритм восстановления идентификационной информации процессов параллельных программ, он входит в базовый состав DMTCP, начиная с версии 1.1.9.

Создан программный инструментарий Hash Based Incremental Checkpointing Tool (HBICT, http://sourceforge.net/projects/hbict/), реализующий предложенные алгоритмы дельта-сжатия. Выполнена интеграция HBICT и пакета DMTCP. Созданные средства внедрены в мультикластерную ВС, проведено их моделирование.

В заключении сформулированы основные результаты, полученные в диссертационной работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Разработаны и исследованы алгоритмические, программные и аппаратурные средства организации отказоустойчивого функционирования распределённых вычислительных систем.

1. Предложен подход к распределению информационных блоков по разнородным каналам передачи данных, выполняющий балансировку нагрузки пропорционально их пропускным способностям.

1.1. Построена математическая модель отказоустойчивого гетерогенного канала передачи данных, формируемого из разнородных каналов связи.

1.2. Разработан алгоритм RateBalance распределения информационных блоков по разнородным каналам связи. Алгоритм (в отличие от существующих аналогов) обеспечивает фиксированный уровень инверсий (нарушений порядка следования информационных блоков) в выходном потоке гетерогенного канала передачи данных, при котором не происходит переполнения окон приёма протоколов вышележащих уровней (например, TCP).

1.3. Осуществлено моделирование алгоритма RateBalance и показано, что он не чувствителен к различиям в пропускных способностях объединяемых каналов связи и обеспечивает стабильное приближение совокупной пропускной способности гетерогенного канала к её предельному значению.

15

1.4. Выполнено внедрение алгоритма RateBalance в программное обеспечение пространственно-распределённой мультикластерной ВС и телекоммуникационной платформы Sigrand SG-17R отечественного производителя ООО "Сигранд".

2. Разработаны модели и алгоритмы организации отказоустойчивого выполнения параллельных программ на распределённых вычислительных системах.

2.1. Предложена модель ВС с отказоустойчивым выполнением параллельных программ, предусматривающая наличие служебной информации операционной системы и сжатие контрольных точек восстановления.

2.2. Создан алгоритм восстановления идентификационной информации процессов параллельной программы, который использует интерфейс системных вызовов операционной системы, что позволяет применять его для восстановления данного компонента состояния в любых средствах создания контрольных точек.

2.3. Произведено моделирование разработанного алгоритма, установлено, что он обеспечивает полное и корректное восстановление идентификационной информации при возобновлении группы процессов из контрольной точки.

2.4. Выполнена реализация вышеуказанного алгоритма в свободно распространяемом пакете DMTCP создания контрольных точек.

3. Разработаны алгоритмы дельта-сжатия для оптимизации контрольных точек восстановления программ по объёму и времени создания.

3.1. Создан параллельный алгоритм дельта-сжатия P-FHash, который характеризуется линейным ускорением и предназначен для параллельных программ, использующих стандарт ОрепМР.

3.2. Предложен адаптивный подход, сочетающий преимущества инкремент-ных и дифференциальных контрольных точек. Его использование позволяет снизить зависимость сжатых контрольных точек от предыдущих, что делает возможным сокращение объёмов хранимых данных (например, за счёт удаления устаревших точек - garbage collection). С другой стороны, подход обеспечивает низкие объёмы передаваемых данных, характерные для инкрементных контрольных точек.

3.3. Разработан алгоритм пакетного сжатия, позволивший совмещать эффективность различных видов сжатия. Модифицированные блоки, обнаруженные алгоритмами дельта-сжатия, группируются в пакеты, которые дополнительно сжимаются универсальными алгоритмами независимо друг от друга. Моделирование показало, что такой вариант сжатия ускоряет процесс создания результирующей контрольной точки приблизительно в два раза.

3.4. Создан параллельный алгоритм формирования результирующей контрольной точки по набору сжатых КТ, выполняющий поиск наиболее позднего целостного состояния программы.

4. Конфигурация пространственно-распределённой мультикластерной системы расширена средствами отказоустойчивости, которые обеспечивают: Сформирование отказоустойчивых гетерогенных каналов связи;

2) восстановление параллельных программ из контрольных точек; 3) оптимизацию контрольных точек по времени создания и объёму.

Основные результаты диссертации опубликованы в работах [1-23].

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Поляков, АЛО. Адаптивный подход к распределению информационных блоков по каналам передачи данных / А.Ю. Поляков // Электросвязь. - 2009.- №6,- С. 32-35.-ISSN 0013-5771.

2. Хорошевский, В.Г. Архитектура и программное обеспечение пространственно-распределённых вычислительных систем / В.Г. Хорошевский, М.Г. Курносов, С.Н. Мамойленко, А. Ю. Поляков // Вестник СибГУТИ. - Новосибирск: СибГУТИ, 2010. -№2.-С. 112-122.

3. Поляков, А.Ю. Оптимизация времени создания и объёма контрольных точек восстановления параллельных программ / А.Ю. Поляков, A.A. Данекина // Вестник СибГУТИ. - Новосибирск: СибГУТИ, 2010. -Кг 2,- С. 87-100.

4. Поляков, А.Ю. О восстановлении программ из контрольной точки / А.Ю. Поляков // Всстник ЮУрГУ. Серия "Математическое моделирование и программирование". - 2010. - № 35(211), № 6. - С. 91-103.

5. Cooperman, G. DMTCP and Condor: a New Checkpointing Mechanism [Electronic resource] / G. Cooperman, K. Arya, P. Keller, A.Y. Polyakov // Condor Week 2010. -University of Wisconsin, 2010. - Режим доступа: http://www.cs.vvisc.edu/ condor/CondorWeek2010/condor-presentations/cooperman-dmtcp.pdf.

6. Visan, A.M. Temporal Debugging using URDB [Electronic resource] / Ana Maria Visan, Artem Polyakov, Praveen S. Solanki, Kapil Arya, Tyler Denniston, Gene Cooperman // Technical Report.- Режим доступа: http://arxiv.org/abs/0910.5046vl.

7. Поляков, А.Ю. Организация объединенного канала передачи данных / А.Ю. Поляков // Инфосфера. - Новосибирск, 2009. - № 43. - С. 44-47.

8. Поляков, А.Ю. Об алгоритме восстановления структуры процессов из контрольной точки / А.Ю. Поляков // Материалы Международной научно-технической конференции "Многопроцессорные вычислительные и управляющие системы (МВУС-2009)". -Таганрог: ТТИ ЮФУ, 2009. - Т. 2. - С. 71-73. - ÍSBN 978-5-8327-0341-1.

9. Поляков, А.Ю. Параллельный алгоритм формирования инкрементных контрольных точек / А.Ю. Поляков // Материалы Международной научно-технической конференции "Суперкомпьютерные технологии: разработка, программирование, применение (СКТ 2010)". - Таганрог: ТТИ ЮФУ, 2010. - Т. 1. - С. 290 - 294. - ISBN 978-5-8327-0383-1.

10. Поляков, А.Ю. О восстановлении программ из контрольной точки / А.Ю. Поляков // Параллельные вычислительные технологии (ПаВТ'2010): Труды международной научной конференции (Уфа, 29 марта - 2 апреля 2010 г.) [Электронный ресурс].- Челябинск: Издательский центр ЮУрГУ, 2010.- С. 299-310. ISBN 978-5-696-03987-9. URL: http://omega.sp.susu.ac.ru/books/confcrence/PaVT2010/ full/155.pdf

11. Поляков, А.Ю. Об обеспечении отказоустойчивого решения параллельных задач // Материалы XLVII Международной научной студенческой конференции "Студент и научно-технический прогресс". - Новосибирск: НГУ, 2009. - с. 211.

12. Данекина, A.A. О подходах к созданию инкрементных контрольных точек восстановления / A.A. Данекина, А.Ю. Поляков // Материалы XLVII Международной научной

студенческой конференции "Студент и научно-технический прогресс". - Новосибирск: НГУ, 2010. - с. 296.

13. Поляков, А.Ю. О подходах к оптимизации времени создания и объёма контрольных точек восстановления / АЛО. Поляков, A.A. Данекина // Тезисы докладов Восьмой Российской конференции с международным участием "Новые информационные технологий в исследовании сложных структур (ICAM 2010)".- Томск: HTJI, 2010. - с. 23.-ISBN 9785-89503-440-8.

14. Молдованова, О.В. Исследование современных средств создания контрольных точек восстановления параллельных программ / О.В. Молдованова, А.Ю. Поляков // Тезисы докладов Восьмой Российской конференции с международным участием "Новые информационные технологии в исследовании сложных структур (ICAM 2010)". -Томск: НТЛ, 2010. - с. 22. - ISBN 978-5-89503-440-8.

15. Данекина, A.A. Применение методов хеширования к задаче формирования ин-крементных контрольных точек / A.A. Данекина, А.Ю. Поляков // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций". -2010.-Т. 1. — с. 155.

16. Поляков, А.Ю. Организация объединенного канала передачи данных / А.Ю. Поляков // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций". - 2009. - Т. 1. — С. 131 - 132.

17. Поляков, А.Ю. Эвристические алгоритмы организации функционирования распределенной вычислительной системы с учетом экономических факторов / А.Ю. Поляков // Материалы 11 Международной научной студенческой конференции "Научный потенциал студенчества - будущему России". - Ставрополь: СевКавГТУ, 2008.-Т. 3. - с. 180.

18. Поляков, А.Ю. Об алгоритмах организации функционирования вычислительных систем при обслуживании набора задач с учетом экономических факторов ' А.Ю. Поляков // Материалы XLV Международной Научной Студенческой Конференции "Студент и научно-технический прогресс". - Новосибирск: НГУ, 2007. - С. 45 - 46.

19. Поляков, А.Ю. Организация функционирования вычислительных систем при обслуживании наборов задач с учетом штрафа за задержку решения / А.Ю. Поляков // Российская научно-техническая конференция "Информатика и проблемы телекоммуникаций". - Новосибирск: СибГУТИ, 2007. - С. 276 - 277.

20. Мамойленко, С.Н. Применение генетических алгоритмов для распределения наборов задач по машинам вычислительной системы / С.Н. Мамойленко, H.A. Медведева, А.Ю. Поляков // Материалы Международной научно-технической конференции "Многопроцессорные вычислительные и управляющие системы". - Таганрог: ТТИ ЮФУ, 2007. -Т. 2.-С. 70-75.

21. Поляков, А.Ю. Учет экономических факторов в задаче распределения ресурсов вычислительной системы / А.Ю. Поляков // Материалы XLV1 Международной Научной Студенческой Конференции. - Новосибирск: НГУ, 2008. С. 78 - 79.

22. Мамойленко, С.Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С.Н. Мамойленко, H.A. Медведева, А.Ю. Поляков, A.B. Ефимов // Тезисы докладов Седьмой Российской конференции с международным участием "Новые информационные технологии в исследовании сложных структур (ICAM-2008)". -Томск: НТЛ, 2008.-с. 71.

23. Мамойленко, С.Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычисли-

тельной системы / С.Н. Мамойленко, H.A. Медведева, А.Ю. Поляков, A.B. Ефимов // Российская научно-техническая конференция "Информатика и проблемы телекоммуникаций". - Новосибирск: СнбГУТИ, 2008. - С. 144 - 145.

Поляков Артём Юрьевич

Разработка и исследование средств отказоустойчивости распределенных вычислительных систем

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать "19" ноября 2010 г.

Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд. л. 1,6, заказ № 69, тираж 130 экз., ГОУ ВПО "СибГУТИ". 630102, г. Новосибирск, ул. Кирова, д. 86.

СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. КОНЦЕПТУАЛЬНЫЕ ОСНОВЫ ПОСТРОЕНИЯ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

1.1. Модель вычислительной системы.

1.1.1. Модель коллектива вычислителей.

1.1.2. Топология вычислительных систем.

1.1.3. Алгоритм работы коллектива вычислителей.

1.1.4. Модель вычислительной системы.

1.1.5. Классификация архитектур ВС.

1.1.6. Принципы технической реализации вычислительных систем.

1.1.7. Архитектурные свойства ВС.

1.2. Параллельные алгоритмы.

1.2.1. Понятие параллельного алгоритма.

1.2.2. Принцип крупноблочного распараллеливания.

1.2.3. Понятие о сложных задачах.

1.3. Проблема живучести распределенных вычислительных систем.

1.3.1. Отказы в современных распределенных ВС.

1.3.2. Организация отказоустойчивых каналов передачи данных.

1.3.3. Возобновляемые программы.

1.3.4. Оптимизация контрольных точек восстановления программ.

1.4. Выводы.

ГЛАВА 2. АЛГОРИТМЫ-ОБЕСПЕЧЕНИЯ ОТКАЗОУСТОЙЧИВОГО ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

2.1. Отказоустойчивые гетерогенные каналы передачи данных.

2.1.1. Показатели производительности каналов связи.

2.1.2. Модель гетерогенного канала передачи данных.

2.1.3. Алгоритмы восстановления порядка следования информационных блоков.

2.1.4. Анализ алгоритмов распределения информационных блоков по каналам связи.

2.1.5. Адаптивный алгоритм RateBalance распределения информационных блоков по каналам передачи данных.

2.2. Алгоритмы возобновления программ из контрольных точек восстановления.

2.2.1. Модель вычислительной системы с отказоустойчивым выполнением параллельных программ.

2.2.2. Идентификационная информация.

2.2.3. Основные этапы возобновления параллельных программ.

2.2.4. Задача восстановления идентификационной информации программ.

2.2.5. Алгоритм USCR восстановления идентификационной информации программ.

2.2.6. Вложение алгоритма USCR в существующие синхронизационные схемы.

2.3. Оптимизация контрольных точек восстановления параллельных программ.

2.3.1. Страничный подход к дельта-сжатию КТ.

2.3.2. Подходы к дельта-сжатию КТ, основанные на хешировании.

2.3.3. Особенности дельта-сжатия КТ.

2.3.4. Параллельный алгоритм P-FHash дельта-сжатия КТ.

2.3.5. Адаптивный подход к дельта-сжатию КТ.

2.3.6. Алгоритм РаСотр пакетного сжатия КТ.

2.3.7. Алгоритм формирования результирующей КТ.

2.3.8. Параллельный алгоритм формирования результирующей КТ

2.4. Выводы.

ГЛАВА 3. ПРОСТРАНСТВЕННО-РАСПРЕДЕЛЕННАЯ МУЛЬТИКЛАСТЕРНАЯ ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА.

3.1. Архитектура пространственно-распределенной мультикластерной вычислительной системы.

3.2. Программное обеспечение мультикластерной ВС.

3.2.1. Стандартные компоненты.

3.2.2. Средства организации отказоустойчивых гетерогенных каналов передачи данных.

3.2.3. Средства создания распределенных контрольных точек.

3.2.4. Средства оптимизации объема распределенных КТ.

3.3. Моделирование алгоритма 11а1еВа1апсе.

3.3.1. Оценка количества инверсий в выходном потоке.

3.3.2. Оценка производительности отказоустойчивых гетерогенных каналов передачи данных.

3.4. Моделирование алгоритма ШСИ.

3.4.1. Набор тестовых программ.

3.4.2. Набор прикладных программ.

3.5. Моделирование алгоритмов оптимизации КТ.

3.5.1. Оценка вычислительной сложности алгоритмов дельта-сжатия КТ.

3.5.2. Исследование эффективности алгоритмов дельта-сжатия для параллельных программ.

3.5.3. Моделирование алгоритма Р-РНаБЬ.

3.5.4. Моделирование адаптивного подхода к дельта-сжатию КТ.

3.5.5. Моделирование параллельного алгоритма формирования результирующей КТ.

3.6. Выводы.

Актуальность работы. Научно-технический прогресс неразрывно связан с решением вычислительных задач, сложность которых постоянно возрастает. Это определяет потребность в средствах высокопроизводительной обработки информации. Одним из инструментов решения сложных задач являются распределённые вычислительные системы (ВС), характеризующиеся массовым параллелизмом. Они формируются из унифицированных элементов (модулей), которые функционально и конструктивно закончены и имеют средства сопряжения друг с другом. В качестве базовых модулей ВС служат элементарная машина (ЭМ), оснащённая устройством управления, арифметико-логическим устройством (АЛУ), памятью и локальным коммутатором (ЛК), и узел ввода-вывода (УВВ), обеспечивающий доступ к данным. Конструктивно одна или несколько ЭМ размещаются на вычислительном узле (ВУ). Современные ВС являются распределёнными и болыиемасштабными, количество ЭМ в них варьируется от десятков до сотен тысяч, а число УВВ от нескольких десятков до сотен. Например, система IBM Roadrunner состоит из 122 400 ЭМ и 216 УВВ, а система Cray ХТ5 Jaguar - из 224 162 ЭМ и 256 УВВ.

Согласно статистическим данным среднее время (АГ1) безотказной работы вычислительных узлов распределённых ВС лежит в промежутке 104- 106 ч. (к - интенсивность потока отказов для одного ВУ). Но даже при использовании таких высоконадёжных компонентов в большемасштабных ВС время между частичными отказами в среднем составляет несколько дней. Это ставит под вопрос осуществимость решения трудоёмких задач, представленных параллельными программами с количеством ветвей, сопоставимым с числом элементарных машин в ВС.

Существует множество задач, решение которых даже на современных ВС занимает от нескольких дней до недель. И количество таких задач постоянно растёт. В связи с вышесказанным актуальной является проблема организации отказоустойчивого функционирования большемасштабных ВС. 7

Исследования в области распределённых вычислительных систем ведутся с 1960-х годов. Проблемам их создания и эксплуатации посвящен ряд фундаментальных работ. Разработаны основы теории функционирования ВС, синтеза оптимальных (макро)структур, теории надёжности и живучести ВС. Созданы инструментальные средства программного обеспечения; изучен широкий круг задач, которые могут эффективно решаться на распределённых ВС. Построены отечественные распределенные ВС с программируемой структурой: "Минск-222", МИНИМАКС, СУММА, МИКРОС, МВС и т. д.

Фундаментальный вклад в теорию и практику вычислительных систем, компьютерных сетей и параллельных вычислительных технологий внесли выдающиеся советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, A.B. Забродин, В.П. Иванников, М.Б. Игнатьев, A.B. Каляев, И.А. Каляев, JT.H. Королев, В.Г. Лазарев, С.А. Лебедев, В.К. Левин, Г.И. Марчук, В.А. Мельников, Ю.И. Митропольский, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, A.A. Самарский, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, H.H. Яненко, а также зарубежные учёные: K.M. Chandy, G. Cooperman, S. Cray, J. Dongarra, M. Flynn, I. Foster, A. Gara, L. Lamport, M. Livny, J.S. Plank и другие.

В диссертации предложены средства организации отказоустойчивого функционирования распределённых ВС. На 'основе полученных результатов разработаны программные компоненты операционной системы (ОС), позволяющие формировать отказоустойчивые каналы передачи данных, средства создания контрольных точек (KT) восстановления для параллельных и последовательных программ, а также инструментарий оптимизации распределённых KT по объёму и времени сохранения.

Цель работы и задачи исследования. Целью диссертационной работы является разработка и исследование алгоритмических, программных и аппаратурных средств организации, отказоустойчивого функционирования распределённых ВС в мультипрограммных режимах.

В соответствии с целью определены нижеследующие задачи:

Анализ архитектурных особенностей современных ВС и подходов к обеспечению их отказоустойчивого функционирования.

2. Организация отказоустойчивых гетерогенных каналов связи между территориально удалёнными компонентами пространственно-распределённых ВС.

3. Создание алгоритмов возобновления параллельных и последовательных программ из распределённых контрольных точек.

4. Разработка алгоритмов оптимизации распределённых КТ по объёму и времени создания с использованием технологии дельта-сжатия. Суть технологии заключается в сохранении только тех фрагментов состояния программы, которые были модифицированы относительно набора предыдущих КТ.

5. Реализация алгоритмов формирования отказоустойчивых гетерогенных каналов передачи данных в виде программного модуля ОС GNU/Linux.

6. Внедрение предложенных алгоритмов возобновления параллельных программ в существующие средства формирования распределённых КТ.

7. Создание системного программного инструментария, позволяющего выполнять сжатие КТ и формирование результирующих КТ в соответствии с техническими ограничениями (на объём используемой памяти); его интеграция с существующими средствами создания КТ (ССКТ).

Методы исследования. Для достижения поставленной цели и решения сформулированных в диссертационной работе задач использовались методы теории функционирования распределённых вычислительных систем, теории графов, теории алгоритмов, теории множеств, математический аппарат исследования операций и теории информации. Экспериментальные исследования осуществлялись с помощью моделирования на пространственнораспределённой мультикластерной вычислительной системе.

Научная новизна работы. В диссертации разработаны и исследованы средства организации эффективного отказоустойчивого функционирования распределённых вычислительных систем:

1. Предложена математическая модель отказоустойчивого гетерогенного канала передачи данных, учитывающая пропускные способности составляющих его разнородных каналов связи.

2. Построена математическая модель ВС с отказоустойчивым выполнением параллельных программ. Модель предусматривает: 1) сохранение промежуточных состояний программ в контрольных точках, позволяющих возобновить программу в случае отказа; 2) сжатие КТ в процессе их создания.

3. Разработан алгоритм распределения информационных блоков по разнородным каналам передачи данных, обеспечивающий их равномерную загрузку. Уровень инверсий, образующихся в выходном потоке гетерогенного канала, не требует повторной пересылки блоков.

4. Создан алгоритм, позволивший корректно и полностью восстанавливай, идентификационную информацию процессов ОС при возобновлении программ из распределённых КТ. Достоинством алгоритма является то, что он использует стандартный интерфейс ОС, следовательно, он может применяться в любых Р081Х-совместимых средствах создания контрольных точек.

5. Предложен параллельный алгоритм дельта-сжатия контрольных точек восстановления параллельных программ, разработанных с использованием стандарта ОрепМР.

6. Разработан адаптивный подход, осуществляющий (суб)оптимальный выбор КТ, относительно которой будет выполняться дельта-сжатие. Целями являются: 1) минимизация объёма сжатой КТ; 2) уменьшение количество сжатых КТ, необходимых для формирования результирующей КТ.

7. Создан алгоритм пакетного сжатия, совмещающий универсальное и дельта-сжатие, который обеспечивает (суб)оптимальное время формирования

10 результирующей КТ.

8. Предложен параллельный алгоритм формирования результирующей КТ из набора дельта-сжатых, который выполняет поиск наиболее позднего целостного состояния параллельной программы.

Практическая ценность работы. Разработанные в диссертации модели и алгоритмы в сочетании с существующими средствами обеспечивают отказоустойчивость распределённых вычислительных систем.

Предложенный алгоритм распределения информационных блоков по разнородным каналам связи гарантирует отказоустойчивое соединение узлов ВС и обеспечивает приближение пропускной способности гетерогенного канала к её предельному значению.

Алгоритм восстановления идентификационной информации процессов обеспечивает эквивалентность возобновлённой и исходной программ. Это позволяет сохранять связи между компонентами параллельной программы. Корректность и полнота восстановления идентификационной информации являются важными характеристиками средств создания контрольных точек.

Предложенные алгоритмы дельта-сжатия контрольных точек существенно снижают нагрузку на подсистему ввода-вывода за счёт её распределения между УВВ и ВУ при создании КТ для параллельных программ, характеризующихся частичной модификацией памяти в процессе работы. Разработаны алгоритмы, обеспечивающие (суб)оптимальное время восстановления результирующей КТ из набора сжатых КТ.

Реализация и внедрение результатов работы. Основные результаты диссертационной работы внедрены. Они, в частности, составляют основу программного инструментария поддержки отказоустойчивости пространственно-распределённой мультикластерной вычислительной системы Центра параллельных вычислительных технологий ГОУ ВПО "Сибирский государственный университет телекоммуникаций и информатики" (ЦПВТ ГОУ ВПО "СибГУТИ") и Лаборатории вычислительных систем Института физики

11 полупроводников им. А. В. Ржанова СО РАН (ИФП СО РАН). Вычислительная система активно используется в учебном процессе ГОУ ВПО "СибГУТИ".

Диссертационные исследования выполнялись по программе ведущей научной школы (НШ-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 статьи в рецензируемых журналах. Результаты исследований отражены в отчётах по грантам и НИР.

Основные положения диссертации, выносимые на защиту.

1. Математическая модель отказоустойчивого гетерогенного канала передачи данных и эвристический алгоритм распределения информационных блоков, учитывающие разнородность используемых каналов связи.

2. Математическая модель распределённой ВС с отказоустойчивым выполнением параллельных программ, предусматривающая наличие служебной

13 информации процессов ОС и сжатие контрольных точек восстановления.

3. Алгоритм восстановления идентификационной информации процессов параллельной программы, который использует только стандартный интерфейс при взаимодействии с ОС.

4. Алгоритмы определения и сохранения модифицированных фрагментов контрольных точек восстановления (алгоритмы дельта-сжатия).

5. Программный инструментарий дельта-сжатия, реализующий предложенные алгоритмы.

6. Средства отказоустойчивого функционирования пространственно-распределённых мультикластерных ВС.

Структура и объём диссертации. Диссертационная работа состоит из введения, трех глав, заключения, списка используемых литературных источников и приложений. Общий объем работы — 173 страницы.

Основные результаты диссертации опубликованы в работах [8, 9, 24,30-43,70,151].

ЗАКЛЮЧЕНИЕ

Разработаны и исследованы алгоритмические, программные и аппаратурные средства организации отказоустойчивого функционирования распределённых вычислительных систем.

1. Предложен подход к распределению информационных блоков по разнородным каналам передачи данных, выполняющий балансировку нагрузки пропорционально их пропускным способностям.

1.1. Построена математическая модель отказоустойчивого гетерогенного канала передачи данных, формируемого из разнородных каналов связи.

1.2. Разработан алгоритм RateBalance распределения информационных блоков по разнородным каналам связи. Алгоритм (в отличие от существующих аналогов) обеспечивает фиксированный уровень инверсий (нарушений порядка следования информационных блоков) в выходном потоке гетерогенного канала передачи данных, при котором не происходит переполнения окон приёма протоколов вышележащих уровней (например, TCP).

1.3. Осуществлено моделирование алгоритма RateBalance и показано, что он не чувствителен к различиям в пропускных способностях объединяемых каналов связи и обеспечивает стабильное приближение совокупной пропускной способности гетерогенного канала к её предельному значению.

1.4. Выполнено внедрение алгоритма RateBalance в программное обеспечение пространственно-распределённой мультикластерной ВС и телекоммуникационной платформы Sigrand SG-17R отечественного производителя ООО "Сигранд".

2. Разработаны модели и алгоритмы организации отказоустойчивого выполнения параллельных программ на распределённых вычислительных системах.

2.1. Предложена модель ВС с отказоустойчивым выполнением параллельных программ, предусматривающая наличие служебной информации операционной системы и сжатие контрольных точек восстановления.

148

2.2. Создан алгоритм USCR восстановления идентификационной информации процессов параллельной программы, который использует интерфейс системных вызовов операционной системы, что позволяет применять его для восстановления данного компонента состояния в любых средствах создания контрольных точек.

2.3. Произведено моделирование алгоритма USCR, установлено, что он обеспечивает полное и корректное восстановление идентификационной информации при возобновлении группы процессов из контрольной точки.

2.4. Выполнена реализация вышеуказанного алгоритма в свободно распространяемом пакете DMTCP создания контрольных точек.

3. Разработаны алгоритмы дельта-сжатия для оптимизации контрольных точек восстановления программ по объёму и времени создания.

3.1. Создан параллельный алгоритм дельта-сжатия P-FHash, который характеризуется линейным ускорением и предназначен для параллельных программ, использующих стандарт ОрепМР.

3.2. Предложен адаптивный подход, сочетающий преимущества инкрементных и дифференциальных контрольных точек. Его использование позволяет снизить зависимость сжатых контрольных точек от предыдущих, что делает возможным сокращение объёмов хранимых данных (например, за счёт удаления устаревших точек - garbage collection). С другой стороны, подход обеспечивает низкие объёмы передаваемых данных, характерные для инкрементных контрольных точек.

3.3. Разработан алгоритм РаСотр пакетного сжатия, позволивший совмещать эффективность различных видов сжатия. Модифицированные блоки, обнаруженные алгоритмами дельта-сжатия, группируются в пакеты, которые дополнительно сжимаются универсальными алгоритмами независимо друг от друга. Моделирование показало, что такой вариант сжатия ускоряет процесс создания результирующей контрольной точки приблизительно в два раза.

3.4. Создан параллельный алгоритм формирования результирующей контрольной точки по набору сжатых КТ, выполняющий поиск наиболее позднего целостного состояния программы.

4. Конфигурация пространственно-распределённой мультикластерной системы расширена средствами отказоустойчивости, которые обеспечивают:

1) формирование отказоустойчивых гетерогенных каналов связи;

2) восстановление параллельных программ из контрольных точек; 3) оптимизацию контрольных точек по времени создания и объёму.

1. Бабаян, Б. А. Многопроцессорные ЭВМ и методы их проектирования / Б. А. Бабаян, А. В. Бочаров, А. С. Волин. -М. : Высшая школа, 1990. - 143 с.

2. Бовет, Д. Ядро Linux = Understanding the Linux Kernel / Д. Бовет, M. Чезати. БХВ-Петербург, 2007.- с. 1104.- ISBN 0-596-00565-2, 978-5-94157-957-0.

3. Бурцев, B.C. Параллелизм вычислительных процессов и развитие архитектур суперЭВМ. М.: ИВВС РАН, 1997.

4. Васильев, В. В. Многопроцессорные вычислительные структуры для анализа задач на сетях / В. В. Васильев, А. Г. Додонов // Проблемы электроники и вычислительной техники. 1976. - №4. - С. 85 - 97.

5. Водяхо, А. И. Высокопроизводительные системы обработки данных / А. И. Водяхо, H. Н. Горпец, Д. В. Пузанков. М.: Высшая школа, 1997. - 304 с.

6. Воеводин, В. В. Математические модели и методы в параллельных процессах / В. В. Воеводин. М.: Наука, 1986. - 296 с.

7. Воеводин, В. В. Параллельные вычисления / В.В. Воеводин, В л.В. Воеводин. СПб. : БХВ-Петербург, 2002. - 608 с.

8. Данекина, A.A. О подходах к созданию инкрементных контрольных точек восстановления / A.A. Данекина, А.Ю. Поляков // Материалы XLVII Международной научной студенческой конференции "Студент и научно-технический прогресс".-Новосибирск: НГУ, 2010. с. 296.

9. Дикер-Пилдуш, Г. Сети ATM корпорации Cisco = Cisco ATM Solutions. — M.: «Вильяме», 2004. С. 880. - ISBN 1-57870-213-5.

10. Дмитриев, Ю. К. Вычислительные системы из мини-ЭВМ / Ю.К. Дмитриев, В.Г. Хорошевский, Э.В. Евреинов. М.: Радио и связь, 1982. -304 с.

11. Евдокимов, В.Ф. Параллельные вычислительные структуры на основе разрядных методов / В.Ф. Евдокимов, А.И. Стасюк. К.: Наукова думка, 1987. -311 с.

12. Евреинов, Э.В. О возможности построения вычислительных систем в условиях запаздывания сигналов / Э.В. Евреинов // Вычислительные системы. — 1962.-№3.-С. 3-16.

13. Евреинов, Э. В. Однородные вычислительные системы, структуры и среды / Э.В. Евреинов. М.: Радио и связь, 1981. - 208 с.

14. Евреинов, Э.В. Однородные универсальные вычислительные системы высокой производительности / Э.В. Евреинов, Ю.Г. Косарев. Новосибирск: Наука. Сибирское отд-е, 1966. -308 с.

15. Евреинов, Э.В. Однородные вычислительные системы / Э.В. Евреинов, В.Г. Хорошевский. Новосибирск: Наука. Сибирское отд-е, 1978. - 319 с.

16. Каляев, A.B. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений / A.B. Каляев, И.И. Левин. -М.: Янус-К, 2003. -380 с.

17. Каляев, И.А. Реконфигурируемые мультиконвейерные вычислительные структуры / И.А. Каляев, И.И. Левин, Е.А. Семерников, В.И. Шмойлов; под общ. ред. И.А. Каляева. Ростов н/Д: Издательство ЮНЦ РАН, 2008. - 320 с.

18. Кнут, Д. Э. Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. 3-е изд. — M.: «Вильяме», 2006. - С. 720. - ISBN 0-201-89683-4.

19. Корнеев, B.B. Об организации коммуникаций между процессами в вычислительной системе МИКРОС / В.В. Корнеев и др. // Вычислительные системы. 1985. - С. 70-84.

20. Корнеев, B.B. Вычислительные системы / В. В. Корнеев. -М.: Гелиос АРВ, 2004. 512 с.

21. Корнеев, В.В. Архитектура вычислительных систем с программируемой структурой / В.В. Корнеев. Новосибирск: Наука, 1985.

22. Лав, Р. Разработка ядра Linux = Linux Kernel Development / Роберт Лав. Вильяме, 2008. - с. 448. - ISBN 5-8459-1085-4, 0-672-32720-1.

23. Монахов, О.Г. Организация межмашинных взаимодействий в вычислительных системах с программируемой структурой МИКРОС / О.Г. Монахов, Э.А. Монахова // Вычислительные системы. Новосибирск, 1984. - № 105. - С. 85-104.

24. Монахов, О.Г. Параллельные системы с распределенной памятью: управление ресурсами и заданиями / О.Г. Монахов, Э.А. Монахова. Новосибирск: ИВМиМГ PCO РАН, 2000. - 168 с.

25. Монахова, Э.А. Синтез оптимальных диофантовых структур / Э.А. Монахова // Вычислительные системы. Новосибирск, 1979. - Вып. 80. -С.18-35.

26. Немет, Э. Руководство администратора Linux. Установка и настройка = Linux Administration Handbook / Эви Немет, Гарт Снайдер, Трент Хейн. -2-е изд. М.: Вильяме, 2007. - 1072 с. - ISBN 0-13-148004-9.

27. Объединение нескольких пар на базе ATM // Рекомендация МСЭ-Т G.998.1. -2005.

28. Поляков, А.Ю. Адаптивный подход к распределению информационных блоков по каналам передачи данных / А.Ю. Поляков // Электросвязь. 2009. — №6. - С. 32-35. - ISSN 0013-5771.

29. Поляков, А.Ю. Об обеспечении отказоустойчивого решения параллельных задач / А.Ю. Поляков // Материалы XLVII Международной научной студенческой конференции "Студент и научно-технический прогресс". Новосибирск: НГУ, 2009. - с. 211.

30. Поляков, А.Ю. Оптимизация времени создания и объёма контрольных точек восстановления параллельных программ / А.Ю. Поляков, A.A. Данекина // Вестник СибГУТИ. Новосибирск.: СибГУТИ. - 2010. - №2. - С. 87-100.

31. Поляков, А.Ю. Организация объединенного канала передачи данных / А.Ю. Поляков // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций". Новосибирск: СибГУТИ, 2009.-Т. 1.-С. 131-132.

32. Поляков, А.Ю. Организация объединенного канала передачи данных / А.Ю. Поляков // Инфосфера. Новосибирск, 2009. - №43. - С. 44-47.

33. Поляков А.Ю. Организация функционирования вычислительных систем при обслуживании наборов задач с учетом штрафа за задержку решения// i

34. Российская научно-техническая конференция "Информатика и проблемы телекоммуникаций". Новосибирск: СибГУТИ, 2007. - С. 276 - 277.

35. Поляков, А.Ю. О восстановлении программ из контрольной точки / А.Ю. Поляков // Вестник ЮУрГУ. Серия "Математическое моделирование и программирование". 2010. - № 35(211), № 6. - С. 91-103.

36. Поляков А.Ю. Учет экономических факторов в задаче распределения ресурсов вычислительной системы // Материалы XLVI Международной Научной Студенческой Конференции. — Новосибирск: НГУ, 2008. — С. 78 — 79.

37. Роббинс, А. Linux: программирование в примерах. Пер с англ / А. Роб-бинс. М.: КУДИЦ-ОБРАЗ, 2005. - 656 с.

38. Рычков, А.Д. Численное моделирование газодинамических процессов в камере сгорания автомобильного устройства безопасности (airbag) / А.Д. Рычков, Н.Ю. Шокина // Вычислительные технологии. 2002. - т.7, №1. — С. 34-42.

39. Сайт компании ООО "Сигранд" Электронный ресурс. Режим доступа: http://www.sigrand.rn, свободный (дата обращения 14.10.2010).

40. Сайт компании Shareband Электронный ресурс. Режим доступа: http://sharedband.com/, свободный (дата обращения 5.11.2010).

41. Сайт компании Xrio Электронный ресурс. Режим доступа: http://www.xrio.com, свободный (дата обращения 5.11.2010).

42. Сайт проекта GNU/SCREEN Электронный ресурс. -Режим доступа: http://www.gnu.org/software/screen/, свободный (дата обращения 14.10.2010).

43. Сайт проекта GZIP Электронный ресурс.- Режим доступа: http://www.gzip.org/, свободный (дата обращения 14.10.2010).

44. Сайт проекта HBICT Электронный ресурс.— Режим доступа: http://sourceforge.net/projects/hbict/, свободный (дата обращения 14.10.2010).

45. Сайт проекта LAMMPS Электронный ресурс. Режим доступа: http://lammps.sandia.gov/, свободный (дата обращения 14.10.2010).

46. Сайт проекта Linux Channel Электронный ресурс. Режим доступа: http://bonding.sourceforge.net/, свободный (дата обращения 14.10.2010).

47. Сайт проекта MPICH2 Электронный ресурс. Режим доступа: http://www.mcs.anl.gov/research/projects/mpich2/, свободный (дата обращения 14.10.2010).

48. Сайт проекта NETPIPE (Network Protocol Independent Performance Evaluator) Электронный ресурс. Режим доступа: http://www.scl.ameslab.gov/netpipe/, свободный (дата обращения 14.10.2010).

49. Сайт проекта NTOOLS Электронный ресурс.- Режим доступа: http://net-tools.berlios.de/, свободный (дата обращения 14.10.2010).

50. Сайт проекта OpenMPI Электронный ресурс. Режим доступа: http://www.open-mpi.org/, свободный (дата обращения 14.10.2010).

51. Сайт проекта PROCPS Электронный ресурс.- Режим доступа: http://procps.sourceforge.nety, свободный (дата обращения 14.10.2010).

52. Сайт проекта Rsync Электронный ресурс. — Режим доступа: http://rsync.samba.org/, свободный (дата обращения 14.05.2010).

53. Сайт проекта ТОР500 Электронный ресурс.— Режим доступа: www.top500.org/, свободный (дата обращения 14.10.2010).

54. Сайт проекта VMWare Электронный ресурс. -Режим доступа: http://www.vmware.com, свободный (дата обращения 14.10.2010).

55. Сайт проекта Xdelta Электронный ресурс.- Режим доступа: http://xdelta.org/, свободный (дата обращения 14.10.2010).

56. Таненбаум, Э. Распределенные системы. Принципы и парадигмы / Э. Таненбаум. М.: ванн Стеен; СПб.: Питер, 2003. — 877 с: ил. — (Серия «Классика computer science»).

57. Таненбаум, Э. Современные операционные системы = Modern Operating Systems / Э. Таненбаум. СПб.: Питер, 2010.- с. 1120.- (Серия: Классика Computer Science). - ISBN 978-5-49807-306-4, 978-013006633.

58. Хетагуров, Я. А. Основы проектирования управляющих вычислительных систем / Я.А. Хетагуров. М.: Радио и связь, 1991. - 287 с.

59. Хокни, Р. Параллельные ВС. Архитектура, программирование и алгоритмы / Роджер Хокни, Карл Джессоуп; пер. с англ. Д. Н. Абашкина. -М.: Радио и связь, 1986. 392 с.

60. Хокни, Р. Параллельные ЭВМ / Роджер Хокни, Карл Джессоуп; пер. с англ. Д. Н. Абашкина. М. : Радио и связь, 1986. - 390 с.

61. Хорошевский, В.Г. Инженерный анализ функционирования вычислительных машин и систем. М.: Радио и связь, 1987.

62. Хорошевский, В.Г. Архитектура и программное обеспечение пространственно-распределённых вычислительных систем / В.Г. Хорошевский, М.Г. Курносов, С.Н. Мамойленко, А. Ю. Поляков // Вестник СибГУТИ. Новосибирск: СибГУТИ, 2010. - №2. - С. 112-122.

63. Хорошевский, В. Г. Архитектура вычислительных систем / В. Г. Хорошевский. М.: МГТУ им. Н. Э. Баумана, 2008. - 520 с.

64. Andresen, D., Baosong Z. Heterogeneous channel bonding on a Beowulf cluster / D. Andresen, Z. Baosong // Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications. 2000. -P. 2479-2484.

65. Andresen, D. Heterogeneous Channel Bonding Revisited / D. Andresen, S. Hanenkamp // Proceeding of Parallel and Distributed Computing and Systems. — ACTA Press, 2003.-Vol. l.-p.253.

66. An overview of the BlueGene/L supercomputer / Т. B. Team // Proceedings of SC2002: High Performance Networking and Computing. Baltimore, MD, 2002.

67. Ansel, J. DMTCP: Transparent Checkpointing for Cluster Computations and the Desktop / J. Ansel, K. Arya, G. Cooperman // Proc. of IEEE International Parallel and Distributed Processing Symposium (IPDPS'09). -IEEE Press, 2009. P. 1-12.158

68. Beck, M. Compiler-assisted checkpointing / M. Beck, J.S. Plank, G. Kingsley // Technical Report CS-94-269. University of Tennessee at Knoxville, Department of Computer Science, 1994.

69. Chandy, K.M. Distributed Snapshots: . Determining Global States of Distributed Systems / K. Mani Chandy // ACM Transactions on Computer Systems. — 1985.-Vol. 3.-P. 63-75.

70. Dewolfs, D. FT-MPI, Fault-Tolerant Metacomputing and Generic: Name Services: A Case Study / Dewolfs, D., Broeckhove, J., Sunderam, V., Fagg, G. // Lecture Notes in Computer Science. Springer Berlin/Heidelberg, 2006. - Vol. 4192. -P. 133-140, 2006.

71. Dieter, W.R. User-level checkpointing for LinuxThreads programs / W.R. Dieter, J.E. Lumpp // USENIX Annual Technical Conference (FREENIX Track).-2001.-P. 81-92.

72. DLL injection Electronic resource. // Wikipedia. Режим доступа: http://en.wikipedia.org/wil-ci/DLLinjection, свободный (дата обращения 14.10.2010).

73. Dong, X. A Case Study of Incremental and Background Hybrid In-Memory Checkpointing / X. Dong, N. Muralimanohar, N.P. Jouppi, Y. Xie // The Exascale Evaluation and Research Techniques Workshop (EXERT) at ASPLOS 2010. 2010.

74. Elnozahy, N.B. The Performance of Consistent Checkpointing / E.N. Elnozahy, D.B. Johnson, W. Zwaenepoel // Proceedings of the 11th Symposium on Reliable Distributed Systems. 1992. - P. 39-47.

75. Elnozahy, E.N. A survey of rollback-recovery protocols in message-passing systems / E.N. Elnozahy, L. Alvisi, У.М. Wang, D.B. Johnson // ACM Computing Surveys. 2002. -Vol. 34, N. 3. - P. 375^108.

76. FIPS 180-1. Secure Hash Standard. U.S. // Department of Com-merce/N.I.S.T., National Tech-nical Information Service. Springfield, VA, 1995.

77. Flynn, M. Some Computer Organisations and Their Effectiveness // IEEE Trans. Computers. 1972. - Vol. 21, № 9. p. 948 - 960.

78. Flynn, M. Very high-speed computing system / M. Flynn // Proc. of IEEE, 1966.-№54.-P. 1901 -1909.

79. Foster, I. The Anatomy of the Grid: Enabling Scalable Virtual Organizations /1. Foster // Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, 2001. P. 1 - 4.

80. Foster, I. The Grid: Blueprint for a New Computing Infrastructure / I. Foster, C. Kesselman. Morgan-Kaufmann, 1998.

81. Gropp, W. Using MPI-2: Advanced Features of the Message-Passing Interface. MIT Press, 1999.

82. Hargrove, P.H. Berkeley Lab Checkpoint/Restart (BLCR) for Linux Clusters / P.H. Hargrove, J.C. Duell // In Proceedings of SciDAC 2006. -2006.

83. Heo, J. Space-Efficient Page-Level Incremental Checkpointing / Junyoung Heo, Sangho Yi, Yookun Cho, Jiman Hong, Sung Y. Shin // Proceedings of the 2005 ACM symposium on Applied computing. USA, NY, NewYork:ACM, 2005.-P. 1558 - 1562. -ISBN1-58113-964-0.

84. Hockney, R. The communication challenge for MPP: Intel Paragon and Meiko CS-2 / R. Hockney. Parallel Computing. - 1994. - Vol: 20, № 3. -P. 389-398.

85. Hockney, R. Parallel Computers 2: Architecture, Programming and Algorithms / R. Hockney, K. Jesshope. Philadelphia: Hilger, 1988.

86. Hunt, J.J. Delta algorithms: an empirical analysis / J.J.Hunt , K.-P. Vo , W.F. Tichy // ACM Transactions on Software Engineering and Methodology (TOSEM). 1998. - Vol. 7, N. 2. - P. 192 - 214.161

87. Janakiraman, G.J. Application-transparent distributed checkpoint-restart on standard operating systems / G.J. Janakiraman, J.R. Santos, D. Subhraveti, and Y. Turner // Dependable Systems and Networks (DSN-05). 2005. - P. 260 - 269.

88. IEEE Standard for Local and metropolitan area networks Link Aggregation (IEEE 802.1AX) // IEEE Computer Society. - New York, USA, 2008.

89. ITU-T Recommendation G.991.2. Single-pair high-speed digital subscriber line (SHDSL) transceivers. —December, 2003.

90. Karp, R.M. Efficient randomized pattern-matching algorithms / R.M. Karp, M.O. Rabin // IBM Journal of Research and Development. 1987. - Vol. 31, N. 2. -P. 249-260.

91. Kim, B-J. Comparison of the existing checkpoint systems / B.-J. Kim // Technical report. IBM Watson, 2005.

92. Kim, J. Utilizing heterogeneous networks in distributed parallel comput / Kim J., Lilja D.J. // Proceedings of the Sixth IEEE Intnl. Symp. High Performance Distributed Computing HPDC,Portland, 1997.-p. 336.

93. Kiswany, S.A. stdchk: A Checkpoint Storage System for Desktop Grid Computing / S.A. Kiswany, M. Ripeanu, S. S. Vazhkudai, A. Gharaibeh // Proc. of ICDCS 2008.- USA, DC, Washington :IEEE Computer Society, 2008.-P. 613-624. ISSN 978-0-7695-3172-4.

94. Koo R. Rollback-Recovery for Distributed Systems / R. Koo, S. Toueg et al. // IEEE Transactions on Software Engineering. — 1987. — P. 23-31.162

95. Laadan, O. Transparent checkpoint-restart of multiple processes for commodity clusters / O. Laadan, J. Nieh // 2007 USENIX Annual Technical Conference. 2007. - P. 323-336.

96. Laadan, O. Transparent networked checkpoint-restart for commodity clusters / Oren Laadan, Dan Phung, and Jason Nieh // 2005 IEEE International Conference on Cluster Computing. IEEE Press, 2005. - P. 1-13. - ISSN 1552 - 5244.

97. Li, K. Realtime, concurrent checkpoint for parallel programs / K.Li, J.F. Naughton, J.S. Plank // Proc. of Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 1990. - P. 79-88, March 1990.

98. Li, K. Lowlatency, concurrent checkpointing for parallel programs / Kai Li, Jeffrey F. Naughton, and James S. Plank // IEEE Transactions on Parallel and Distributed Systems. 1994. - N. 5. - P. 874-879.

99. Litzkow, M. Supporting checkpointing and process migration outside the UNIX kernel / M. Litzkow, M. Solomon // USENIX Enteenth Symposium on Reliable Distributed systems. 1992. - P. 3 - 9.

100. Litzkow, M. The evolution of Condor checkpointing // Mobility: processes, computers, and agents ACM Press / M. Litzkow, M. Solomon // Addison-Wesley Publishing Co.- USA, NY, New York, 1999,- P. 163-164.-ISBN:0-201-37928-7.

101. MacDonald, J. File system support for delta compression / J. MacDonald // MS Thesis. UC Berkeley, 2000.

102. Muthitacharoen, A. A low-bandwidth network file system / A. Muthitacharoen , B. Chen , D. Mazieres // Proceedings of the eighteenth ACM symposium on Operating systems principles. USA, NY, New York: ACM, 2001. -P. 174-187. - ISBN 1-58113-389-8.

103. Nam H-C. Probabilistic Checkpointing / H. Nam, J. Kim, S. Lee, S. Lee // Proceedings of Intl. Symposium on Fault-Tolerant Computing. 1997. - P. 153-160.

104. Perumal, S. Channel bonding in SHDSL systems I S. Perumal, T. Pearman, S. Huang, S.R. Blackwell // United States Patent 7106760. 2006.163

105. Plank, J. Libckpt: Transparent checkpointing under Unix / J. Plank, M. Beck, G. Kingsley, K. Li // Proceedings of the USEN1X Winter 1995 Technical Conference. 1995. - P. 213-224.

106. Plank, J. S. Compressed differences: An algorithm for fast incremental checkpointing / J.S. Plank, J. Xu, R.H.B. Netzer // Technical Report CS-95-302. -University of Tennessee, 1995.

107. Plank, J.S. Diskless Checkpointing / J.S. Plank, K. Li, M.A. Puening // IEEE Trans. Parallel and Distributed Systems. 1998. -N. 9(10). -P. 972-986.

108. Postel, J. Internet Protocol / J.Postel // Request for Comments 791. September, 1981.

109. Postel, J. Transmission Control Protocol / J. Postel // Request for Comments 793.-September, 1981.

110. Raynal, M. Adaptive checkpointing in message passing distributed systems / M. Raynal // International Journal of Systems Science. 1997. - P. 1145-1161.

111. Recommendation G.703. Physical/Electrical Characteristics of Hierarchical Digital Interfaces. — 1972 last amended in 1991.

112. Rieker, M. Transparent user-level checkpointing for the Native POSIX Thread Library for Linux / M. Rieker, J. Ansel, G. Cooperman // Proc. of Parallel and Distributed Processing Techniques and Applications. 2006. - P. 492-498.

113. Rivest, R., The MD4 message digest algorithm / Ronald Rivest // Proc. of Advances in Ciyptology CRYP-TO'90. - Springer-Verlag, 1991. - P. 303-311.164

114. Rivest, R., The MD5 Message-Digest Algorithm / Ronald Rivest // RFC1321. -1992.

115. Ruscio, J. DejaVu: Transparent user-level checkpointing, migration, and recovery for distributed systems / J. Ruscio, M. Heffner, S. Varadarajan // IEEE International Parallel and Distributed Processing Symposium. 2007. - P. 1-10.

116. Sankaran, S. The LAM/MPI checkpoint/restart framework: System-initiated checkpointing / S. Sankaran, J.M. Squyres, B.Barrett, A. Lumsdaine // International Journal of High Performance Computing Applications. -2005. -N. 19. P. 479-493.

117. Sankaran, S. The LAM/MPI Checkpoint/Restart Framework: System-Initiated Checkpointing / S. Sankaran, J.M. Squyres, B.Barrett, A.Lumsdaine, J. Duell, P.Hargrove, E.Roman // Proceedings of LACSI Symposium. 2003.-P. 479-493.

118. Simpson, W. PPP in HLDC-like Framing,/ W.-Simpson// Request for Comments 1662.-July, 1994.

119. Sklower,K. The PPP Multilink Protocol; (MP) / K. Sklower, B.Lloyd, G. McGregor, D. Carr, T. Coradetti // Request for Comments: 1990. August 1996.

120. Snir, M. MPI—.The Complete Reference / Marc Snir, Steve W. Otto, Steven Huss-Lederman, David W. Walker, and Jack Dongarra // The MPI Core, 2nd edition. MIT Press, Cambridge, MA, 1998. - Vol. 1.

121. Stellner, G Cocheck: Checkpointing and process migration for MPI / Georg Stellner // IPPS '96: Proceedings of the 10th International Parallel Processing Symposium. USA, DC, Washington: IEEE Computer Society, 1996. - P. 526-531.

122. Sunderam, V. S. PVM: A Framework for Parallel Distributed Computing / V.S. Sunderam // Concurrency: Practice and Experience, 2, 4. 1990. — P. 315-339.

123. Sunderam, V. The PVM, Concurrent Computing System: Evolution, Experiences, and Trends / V. Sunderam, J. Dongarra, A. Geist, and R Manchek // Parallel Computing. 1994. - Vol. 20, No. 4. - P. 531-547.

124. Tridgell, A. Efficient algorithms for sorting and synchronization / A. Tridgell //PhD thesis. TheAustrailianNational University, 1999, (rsync).

125. Wang, Y-M. Checkpointing and its applications / Y-M. Wang, Y. Huang, K-P. Vo, P-Y. Chung, and C. Kintala // 25th International Symposium on Fault-Tolerant Computing. CA, Pasadena, 1995. - P. 22-31.

126. Weeratunga, D. The NAS Parallel Benchmarks / Weeratunga, D., Barscz, E., Barton, J. Browning, D. // NAS Technical Report RNR-94-007. NASA Ames Research Center, Moffett Field, CA, 1994.

127. Zandy, V.C. Process hijacking / Victor C. Zandy, Barton P. Miller and Miron Livny // Proc. Of 8th IEEE International Symposium on High Performance Distributed Computing. 1999. - P. 177-184.

128. Zhang, Y. User-level checkpoint and recovery for LAM/MPI / Youhui Zhang, Dongsheng Wong, and Weimin Zheng // ACM SIGOPS Operating Systems Review. 2005. - Vol. 39. - P. 72-81.

129. Zheng, G. FTC-Charm++: An in-memory checkpoint-based fault tolerant runtime for Charm++ and MPI / Gengbin Zheng, Lixia Shi, and L.V. Kale // 2004 IEEE International Conference on Cluster Computing (Fault-Tolerant Session). -2004.-P. 93-103.