Содержание к диссертации
Введение
ГЛАВА 1. Организация функционирования живучих распределенных вычислительных систем 13
1.1. Понятие о живучих вычислительных системах 13
1.1.1. Функциональные структуры живучих ВС 19
1.1.2. Средства поддержки живучести ВС 22
1.2. Графовые модели живучих вычислительных систем 24
1.3. Локализация неисправных элементарных машин в вычислительных системах 26
1.4. Средства самодиагностики вычислительных систем 28
1.4.1. Диагностические модели ВС 30
1.5. Методы дешифрации синдрома ВС 33
1.5.1. Табличный метод 35
1.5.2. Аналитический метод 38
1.6. Выводы 39
ГЛАВА 2. Алгоритмы организации мультипрограммного функционирования и поддержки живучести вычислительных систем 41
2.1. Алгоритмы распределения параллельных задач по элементарным машинам вычислительной системы 41
2.2. Алгоритм заполнения свободных временных тактов элементарных машин вычислительной системы фрагментами задач 45
2.2.1. Последовательная версия алгоритма 46
2.2.2. Параллельная версия алгоритма 48
2.3. Алгоритм выбора числа элементарных машин вычислительной системы для решения пакета задач 50
2.2.1. Последовательная версия алгоритма 51
2.2.2. Параллельная версия алгоритма 52
2.4. Алгоритм распределения задач по элементарным машинам вычислительной системы с учетом операций диагностирования 52
2.5. Алгоритм распределения задач по элементарным машинам вычислительной системы при коллективных взаимопроверках элементарных машин 53
2.6. Минимизация времени решения прикладных задач 57
2.6.1. Использование парных диагностических взаимопроверок элементарных машин 58
2.6.2. Использование коллективных диагностических взаимопроверок элементарных машин 62
2.7. Динамическое распределение фрагментов задач по элементарным машинам вычислительной системы 64
2.8. Алгоритм распределения задач по элементарным машинам вычислительной системы при произвольной трудоемкости фрагментов 68
2.8.1 Минимизация времени диагностирования 68
2.8.2 Минимизация времени решения прикладных задач 73
2.9 Выводы 76
ГЛАВА 3. Методы определения технического состояния вычислительных систем 79
3.1. Формирование таблицы неисправностей вычислительной системы при их автоматической реконфигурации 79
3.1.1. Структура универсальной таблицы неисправностей элементарных машин ВС 79
3.1.2. Оценка объема требуемой памяти 83
3.1.2. Сокращение таблицы неисправностей ВС за счет временной избыточности 86
3.1.3. Оценка необходимых вычислительных ресурсов для хранения таблицы неисправностей 91
3.3. Аналитический метод дешифрации синдрома вычислительной системы 94
3.3.1. Дешифрация синдрома ВС в реальном времени 96
3.3.2. Оценка необходимых ресурсов ВС 100
3.4. Алгоритмы ускоренной дешифрации синдрома вычислительной системы 102
3.4.1. Методы для несимметричных диагностических моделей 103
3.4.2. Методы для симметричных диагностических моделей 105
3.5. Определение состояния вычислительной системы при использовании коллективных проверок 109
3.6. Выводы 110
ГЛАВА 4. Живучие кластерные вычислительные системы 112
4.1.. Классификация кластерных вычислительных систем. Принципы построения живучих кластерных вычислительных систем 112
4.2. Архитектура и программное обеспечение пространственно-распределенной мультикластерной вычислительной системы Центра параллельных вычислительных технологий СибТУТИ 113
4.3. Моделирование на кластерной вычислительной системе потоков параллельных задач 118
4.4. Разработка диспетчера вьшислительной системы, учитывающего операции контроля и диагностики 120
4.5. Разработка средств оценки состояния вычислительной системы.. 121
4.6. Организация удаленного доступа к кластерной вьшислительной систему 122
4.7. Моделирование мультипрограммного функционирования распределенных кластерных вычислительных систем 123
4.8. Выводы 132
Заключение 134
Литератутра 136
Приложение. Исходные тексты программ 151
- Локализация неисправных элементарных машин в вычислительных системах
- Алгоритм распределения задач по элементарным машинам вычислительной системы при коллективных взаимопроверках элементарных машин
- Оценка необходимых вычислительных ресурсов для хранения таблицы неисправностей
- Архитектура и программное обеспечение пространственно-распределенной мультикластерной вычислительной системы Центра параллельных вычислительных технологий СибТУТИ
Введение к работе
Актуальность проблемы. Потребность в высокопроизводительных средствах обработки информации привела к созданию распределенных вычислительных систем (ВС). В общем случае, функциональная структура распределенных ВС представляется композицией из элементарных машин (ЭМ) и коммуникационной сети; Все основные ресурсы таких: систем (не только арифметико-логические устройства, но и память, средства управления и коммуникационная сеть) являются логически и технически распределёнными. Число ЭМ уже в современных распределенных ВС допускает варьирование от нескольких единиц до 106 (например, в российской системе MBС-1000М это число равно 768, а в создаваемой системе IBM Blue Gene должно достигнуть 1 000 000). Распространенный режим функционирования распределенных ВС - монопрограммный, в нем все ресурсы используются для решения одной задачи. Распределенные ВС, обладая колоссальными вычислительными ресурсами, должны эффективно работать ив мультипрограммных режимах. В последнем случае ресурсы ВС делятся между несколькими задачами. Существует класс задач, где ВС применяются в качестве средств управления, и их отказ может повлечь за собой серьезные экономические потери, экологические катастрофы и даже человеческие жертвы. Поэтому для решения таких задач необходимо чтобы В С обладали свойством живучести, т.е. способностью продолжать вычисления даже при отказе части ресурсов. Одними из самых важных этапов в организации живучего мультипрограммного функционирования распределенных ВС являются контроль и диагностика, позволяющие своевременно обнаружить наличие отказов и локализовать неисправные ресурсы. Из сказанного следует актуальность проблем по-вышения-эффективности-использования-ресурсовраспределенныхВС за.счет-параллельного мультипрограммирования и создания децентрализованных средств обнаружения отказов и локализации неисправностей.
Исследования в области распределенных вычислительных систем ведутся с 1960-х годов. В нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам разработки высокопроизводительных вычислительных средств: проведены исследования-по организации функционирования и оптимизации (макро)структур ВС, проработаны многие аспекты разработки программного обеспечения, исследован широкий круг задач, допускающий эффективную реализацию на распределённых ВС. В качестве примеров можно привести отечественные системы "Минск-222", СУММА, МИНИМАКС, семейства систем МИКРОС и МВС.
Фундаментальный вклад в теорию и практику вычислительных и теле
коммуникационных систем и параллельных вычислительных технологий вне
сли советские и российские учёные, среди которых: Е.П.Балашов,
В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Вишневский, В.В. Воеводин,
В.М. Глушков, В.Ф.Евдокимов Э.В; Евреинов, А.В; Забродин,
В.П. Иванников, М.Б. Игнатьев, А.В. Каляев, М.А.Карцев, Л.Н.Королев, Н.А.Кузнецов, В.Г.Лазарев, С.А.Лебедев, В.К.Левин, Г.И.Марчук, Ю.И. Митропольский, В.К.Попков, Д.А.Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г.Рябов, А.А. Самарский, В.Б. Смолов, А.Н. Томилин, Я:А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко и другие.
В диссертации разрабатывается подход, позволяющий планировать и организовать совместное выполнение на распределенных ВС параллельных прикладных вычислений и диагностических процедур. На основе данного подхода могут быть созданы распределенные средства организации живучих вычислительных систем, работающих в мультипрограммных режимах.
Цель работы и задачи исследования. Целью диссертационной работы является разработка и анализ моделей, методов, алгоритмов и системных программ, организующих мультипрограммные режимы функционирования
распределенных вычислительных систем и обеспечивающих их контроль и диагностику.
К основным задачам исследований относятся:
анализ методов организации функционирования распределенных живучих ВС;
разработка последовательных и параллельных алгоритмов распределения задач по элементарным машинам ВС, учитывающих операции контроля и диагностики;
построение процедур определения технического состояния ВС на основе результатов взаимотестирования элементарных машин;
создание программных средств, обеспечивающих диспетчеризацию ВС при наличии пакетов задач и учитывающих операции контроля и диагностики;
реализация программных средств оценки технического состояния ВС.
Методы исследований. При решении поставленных задач в диссертации использовались элементы аппаратов теории множеств и теории графов, методы теории расписаний и теории параллельных вычислений, имитационное моделирование, а также технология объектно-ориентированного программирования.
Научная новизна работы. Автором получены следующие научные результаты, которые выносятся на защиту.
Последовательные и параллельные алгоритмы, осуществляющие распределение параллельных задач по элементарным машинам, и операции контроля и диагностики.
Аналитический метод дешифрации синдрома вычислительной системы, ориентированный на работу в режиме реального времени.
Специализированные методы ускоренной дешифрации синдрома вычислительной системы, учитывающие частные свойства диагностических моделей.
Табличный метод дешифрации синдрома вычислительной системы, основанный на универсальной таблице потенциальных синдромов для всех диагностических графов, возможных в процессе реконфигурации ВС. Варианты реализации метода, обеспечивающие сокращение размера таблицы за счет избыточных временных ресурсов или уменьшение времени дешифрации синдрома системы при увеличении объема памяти, необходимого для хранения таблицы.
Функциональная структура пространственно распределенной мультик-ластерной вычислительной системы и программные средства мультипрограммирования и поддержки живучести ВС.
Практическая ценность работы. Созданные диссертантом модели, методы и алгоритмы организации диагностических процессов в композиции с известными средствами планирования параллельных вычислений составляют базу для построения живучих распределенных ВС.
Оригинальные параллельные алгоритмы распределения пакетов задач по элементарным машинам ВС позволяют на этапе планирования вычислений вводить операции контроля и диагностики.
Применение табличного метода дешифрации синдрома ВС обеспечивает сокращение необходимого объема памяти (за счет хранения таблиц потенциальных синдромов в виде одной универсальной таблицы неисправностей для множества диагностических графов, используемых в процессе реконфигурации).
Разработанный пакет параллельных программ организует не только мультипрограммное функционирование распределенных ВС, но и позволяет осуществить их контроль и диагностику.
Путем моделирования на распределенных кластерных ВС установлена эффективность разработанных средств и показано, что они составляют основу при построении живучих ВС.
Мультикластерная ВС и созданное программное обеспечение используются для исследований в области распределенной обработки информации и в учебном процессе СибТУТИ.
Реализация и внедрение. Результаты диссертации применены в распределенной мультикластерной вычислительной системе Центра параллельных вычислительных технологий СибТУТИ (см. рис. 3). Диссертационная работа поддержана грантами Российского фонда фундаментальных исследований (РФФИ) № 02-07-09380, 03-07-06008, 02-03-90379. Основные положения диссертационной работы использовались автором при разработке и чтении учебных курсов на Кафедре вычислительных систем СибТУТИ по дисциплинам «Отказоустойчивые вычислительные системы», «Операционные системы» и «Организация ЭВМ и систем».
Применение научных результатов диссертации подтверждено соответствующими актами.
Апробация работы. Основные результаты диссертационной работы докладывались на Международных, Всероссийских и Региональных научных конференциях, в том числе:
Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (2001, 2002 гг., г. Новосибирск);
Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (2003 г., г. Геленджик);
Международной научно-технической конференции "Информационные системы и технологии" (2003 г., г. Новосибирск);
Первой Всероссийской научной конференции «Методы и средства обработки информации» (2003 г., г. Москва);
Региональной научной-конференции студентов, аспирантов-и молодых ученых «Наука. Техника. Инновации» (2003 г., г. Новосибирск);
Школе-семинаре «Распределённые кластерные вычисления» (2001 г., г. Красноярск).
Публикации. По теме диссертационной работы опубликовано 12 печатных работ, включая 2-статьи в центральных изданиях.
Объем и структура диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, и приложений, изложенных на 154 страницах.
Содержание работы.
В первой главе дан краткий обзор способов организации живучих ВС. Рассмотрены функциональные структуры живучих ВС, средства их самодиагностики, ВС с централизованной и децентрализованной дешифрацией синдромов и др.
Вторая глава посвящена планированию работы живучих вычислительных систем и организации взаимопроверок элементарных машин.
В третьей главе предлагаются методы определения технического состояния вычислительных систем по результатам взаимных тестов элементарных машин.
В четвертой главе описана архитектура и программное обеспечение пространственно-распределённой мультикластерной вычислительной системы, эксплуатируемой Центром параллельных вычислительных технологий Сибирского государственного университета телекоммуникаций и информатики (ЦПВТ СибГУТИ).
В заключении приведены основные результаты диссертационной работы.
В приложении представлены исходные тексты разработанных библиотек программ.
Локализация неисправных элементарных машин в вычислительных системах
Большие потенциальные возможности построения живучих В С обеспечивает метод активной защиты от отказов, сущность и теоретические основы. которого изложены в работе [112] и развиты в работах [20,120];
Сущность метода активной защиты базируется на структурно-временной избыточности вычислительных ресурсов; когда в системе можно выделить некоторое число дополнительных ЭМ, которые в соответствии с определенной дисциплиной [120] подключаются к основным ЭМ на некоторые периоды времени (такты контроля [132]) и образуют пары ЭМ, дублирующие вычисления. В работе [76] множество ЭМ, загруженных решением одного и того же фрагмента прикладной задачи называется комплексом.
В общем случае машине щ є U, где U= { щ /=1..«}, соответствуют такие объекты диагностирования в вычислительной системе, которые способны осуществлять проверку других ЭМ. Поэтому в качестве ЭМ могут выступать микропроцессоры, микромашины, ЭВМ, кластеры из ЭВМ и т.т Но, например, запоминающее устройство или блок синхронизации ЭВМ соответствуют части-ЭМ„ш самостоятельного значения для системного диагностирования-не имеют [28].
В работах [140, 145] считается, что диагностирование проводится на основе анализа синдрома, полученного выполнением ЭМ специально написанных тестов. Интересным является подход, основанный на сравнении результатов реализации тестов. Метод сравнения удобен тем, что в качестве тестов могут быть использованы фрагменты прикладных задач. Это позволяет сократить специально выделяемое на диагностирование время [145. 149. 141]. Для болынемасштабных распределенных ВС могут быть разработаны эффективные процедуры диагностирования, основанные на методе сравнения [80].
Для обеспечения активной защиты от отказов в ВС предусматривается возможность перераспределения задач между ЭМ. Использование в качестве ЭМ самостоятельных ЭВМ позволяет сделать предположение о фактической независимости отказов отдельных ЭМ.
Модель обеспечения живучего режима функционирования распределенной ВС рассмотрена в [111]. Действие такого режима-осуществляется только средствами вычислительной системы и включает в себя этапы само диагностирования неисправностей систехмного уровня (локализация отказов) и реконфигурации структуры вычислительной системы (изоляция неисправных элементов и перераспределение задач между оставшимися исправными).
При использовании методов активной защиты от отказов в вычислительных системах делаются следующие допущения; 1. Возможны только устойчивые отказовые ситуации, соответствующие синдромы которых не меняются до момента восстановления (замены или ремонта отказавших ЭМ) или реконфигурации системы (исключения отказавших ЭМ из вычислительного процесса). 2. К моменту дешифрации синдрома системы известны результаты всех элементарных проверок, выполняемых в ВС за цикл диагностирования. 3. Выполняемые проверки модулей обладают свойством полноты [152]. Иными словами, различные исправные ЭМ, проверяющие одну и ту же ЭМ, всегда классифицируют ее, как отказавшую. 4. Любая пара вершин диагностического графа {w„ «,} инцидентна не более, чем двум дугам («,-, uj) и (и,-, щ), где / Ф]. Это требование означает, что любая машина щ проводит проверку щ не более одного раза за цикл диагностирования. 5. Возможны отказы только ЭМ, отказы информационных магистралей не предусматриваются. Согласно идее активной защиты появление отказов в работе ЭМ устанавливается одновременным анализом результатов всех элементарных проверок, полученных за цикл диагностирования, т.е. период времени между проверками состояния одной и той же ЭМ. В частности, для некоторых дисциплин активной защиты длительность цикла диагностирования определяется временем, за которое будут однократно проверены все ЭМ [120]. Состав основных и дополнительных (избыточных) ЭМ может изменяться в процессе решения прикладных задач в соответствии с дисциплиной активной защиты или вследствие снижения количества ресурвов ВС из-за отказов отдельных ЭМ [45]. Однако в каждом такте контроля всегда имеется хотя бы одна пара ЭМ {ии uj} с U, в которых дублируются вычисления. По аналогии с работой [59] будем считать, что такая пара ЭМ реализует одну элементарную проверку. При этом длительность такта контроля может быть постоянной или переменной и задается временным интервалом, через который на выходах ЭМ формируется результат, подлежащий контролю [134]. Пусть произведена декомпозиция прикладных задач на множество фрагментов W — {wd}. Решение каждого фрагмента задач wd можно рассматривать как нахождение значения некоторой функции f xj), где xd - исходные данные Если машина Wy, решающая фрагмент задачи wj, исправна, то значение функции fjix) находится верно для любого значения xeMj, где Мд— область определения функции ). Допустим, что в случае неисправности машины uj найденное значение функции /(Ах) будет искажено на всей области определения. Пусть для осуществления контроля функцияЛ(х) вычисляется дважды разными ЭМ в виде функции ffl)(x) n/f2)(x). Предполагается, что при отсутствии ошибок функцииу х) Yifi2\x) совпадают.
Алгоритм распределения задач по элементарным машинам вычислительной системы при коллективных взаимопроверках элементарных машин
При выполнении алгоритма 2.11 можно получить диагностический граф G-{U, Т) с любым значением минимальной локальной степени вершины (до п-1, где п = \U\). Однако для получения полного диагностического графа G„ может потребоваться значительное время, которое превысит максимально допустимое время цикла диагностирования Тцктя1(.
Поэтому в системах, которые должны обеспечивать максимальную степень диагностируемости, целесообразно дешифрацию синдрома производить через определенный интервал времени от момента проведения первой элементарной проверки с единичным результатом.
Если к вычислительной системе предъявляются требования по минимизации времени цикла диагностирования при ограничении на необходимый уровень диагностируемости, то дешифрация синдрома должна производится в тот момент, когда мера диагностируемости для формируемого диагностического графа достигнет (или превысит) заданную величину ґд. Для некоторых диагностических моделей [97] значение меры диагностируемости однозначно связано с минимальной локальной степенью вершин графа degmm. Для таких моделей дешифрацию синдрома следует проводить при выполнении условия
Точная структура получаемого В-результате работы алгоритма 2.11 диагностического графа G = (U, Т) заранее неизвестна. Поэтому затрудняется применение табличных методов дешифрации синдрома системы. Хранение таблицы неисправностей для всех возможных вариантов графов потребовало бы большого объема памяти.
На применение графовых и аналитических методов дешифрации синдрома в системах, использующих алгоритм 2.11, ограничений не накладывается.
В рассмотренных выше алгоритмах планирования вычислительного процесса предполагалось, что трудоемкость фрагментов задач была одинакова для всех фрагментов. Снимем это ограничение и рассмотрим статическое планирование работы распределенных живучих вычислительных систем при различной трудоемкости фрагментов прикладных задач.
Пусть имеется некоторая однородная вычислительная система, состоящая из п однотипных элементарных машин. Эта вычислительная система решает прикладные задачи, выполняя циклически или однократно некоторые алгоритмы.
Пусть заданы два графа: диагностический граф G — (U, 7), где и={и{} -множество вершин,- соответствующее- множеству элементарных- машин-(\U\ — п); Т — множество связей графа, соответствующее множеству элементарных проверок (\Т\ = т), и граф информационных связей [5] D = (W, Р, Г), описывающий используемые для решения прикладных задач алгоритмы, где W={wq} множество вершин, соответствующее множеству фрагментов программы, Г- множество информационных связей между ними, Р - {pq}- множество метрик вершин. Метрика pq вершины wq графа информационных связей D показывает трудоемкость решения соответствующего этой вершине фрагмента. Для однородных систем pq определяет время решения соответствующего фрагмента.
Необходимо построить план решения прикладных задач на: данной вычислительной системе, который обеспечит выполнение всех фрагментов, определяемых графом D, за время не больше, чем Тпртах, и выполнение всех элементарных проверок, предписанных диагностическим графом G, где Гцр1ШХ - заданное максимально допустимое время выполнения одного цикла решения.
Широко известна задача планирования загрузки вычислительной системы по графу D без учета диагностического графа G [24]. Предложен ряд методов по ее решению, в том числе существуют методы планирования, которые позволяют распараллеливать вычислительный процесс на произвольное количество элементарных машин. Таким образом, задаваясь ограничением на количество используемых элементарных машин, можно получить план решения исходных задач предусматривающий использование не более А: машин, где к п:
Логично предположить, что при использовании одного и того же алгоритма планирования загрузки вычислительной системы величина Тщ, зависит от максимального количества машин, используемых одновременно для решения фрагментов прикладных задач: Tnv = Дк). Функция J{k) имеет обратный характер, т. е. чем больше машин используется, тем меньше Тщ,.
Элементарные машины, используемые для решения прикладных задач, называются основными, они образуют множество U\. Остальные образуют множество дополнительных элементарных машин U2. Отметим, что U = -Ui и U2, причем U\ ел U2- 0. Поэтому Ui\= n-\ U2\.
Таким образом, чем меньше элементарных машин используется для решения основных задач, тем большее их количество может быть использовано для выполнения диагностических процедур.
Одним из методов проведения элементарных проверок является одновременное выполнение некоторых фрагментов задач на паре элементарных машин и последующее сравнение результатов. При этом максимальное количество элементарных проверок, выполняемых в системе одновременно, не превышает int {nil).
Оценка необходимых вычислительных ресурсов для хранения таблицы неисправностей
Порядок выбора элементов синдрома (п. 2 алгоритма 3.2) ничем не ограничивается. Поэтому предложенный алгоритм может выполняться по мере сбора диагностической информации (т.е. по мере формирования синдрома системы). Для выделения неисправных элементарных машин может испольт зоваться частично заполненный синдром вычислительной системы, что обу- славливается спецификой данной диагностической модели. Все это дает возможность эффективно использовать его в системах реального времени.
Как видно, алгоритм 3.2 реализует один цикл просмотра синдрома системы, после чего выносится решение о техническом состоянии. Поэтому трудоемкость дешифрации пропорциональна количеству связей т диагностиче-ского графа А = с т. Следует отметить, что т п{п-\) п . Соответственно А с-п2. Здесь с - весовой коэффициент,- учитывающий специфику конкретной системы.
В итоге оценка вычислительной сложности всей процедуры является по-линомиальной и определяется как 0( п ). При этом также минимальны и затраты памяти, так как необходимо хранить только состояние системы. В целом для работы алгоритма требуется всего п ячеек памяти. Модель (0,1,0,1). Иногда эту диагностическую модель называют идеальной, потому что состояние контролируемой элементарной машины однозначно правильно определяется независимо от состояния контролирующей. Аналогично диагностической модели (0,1,0,0) выделение множества неисправных машин Vя = { щ} сводится к поиску тех вершин, в которые входят дуги (щ, и,), взвешенные в синдроме единичным значением sxi= 1. Поэтому для дешифрации синдрома вычислительной системы может быть использован алгоритм 3.2. Оценка трудоемкости и необходимого объема памяти полностью совпадают с рассмотренными выше значениями для модели (0,1,0,0). Модель (0,1,0,Х). Обладает теми же особенностями, что и (0,1,0,1) за исключением того, что не гарантировано верное определение состояния машины неисправной контролирующей машины. Вхудшемслучае влекущем цикле-диагностирования-все элементарные проверки SU, в которых в качестве контролирующих выступают неисправные машины м,- If, всегда имеют результат = 0. При этом работа вычислительной системы может быть описана моделью (0,1,0,0). Если результатом таких элементарных проверок является 5« — 1, то будет иметь место идеальная диагностическая модель. Как в первом, так и во втором случае, используя алгоритм 3.2 можно определить техническое состояние вычислительной системы. Модель (0,1,1,0). Для этой модели характерно получение единичного результата тех элементарных проверок, в которых одна из машин исправна, а другая вышла из строя. Как показано в [97], необходимым и достаточным условием t-диагностируемости вычислительной системы является связанность диагностического графа. Поэтому перед работой алгоритма 3.1 следует из диагностического графа исключить те ребра; без которых он остается связанным, или не рассматривать их при дешифрации. При этом возможно применение алгоритмов Прима [103] и Краскала [104]. Подход к дешифрации синдрома для модели (0,1,1,0) рассмотрен в [38]. Сначала строится граф G0 = (U, Г0), который является подграфом исходного диагностического графа G = (U, Т) и образуется путем удаления дуг (и,-, «,), взвешенных единичным значением sy = 1. Граф Go состоит из таких компонент связности, где состояние вершин, входящих в одну компоненту, одинаково. Каждая компонента связности G0/-в графе G "окружена" компонентами связности противоположного состояния. Если принять, что G0; содержит исправные, вершины, то все компоненты, составляющие ее окружение, содержат неисправные вершины, а последние в свою очередь окружены компонентами, состоящими из исправных вершин, и так далее для каждого очередного «слоя» окружения. В графе Go определяется количество вершин в четных слоях щ. Если щ t, то вершины четных слоев - неисправные, а нечетных - исправные. Если щ t, то наоборот вершины четных слоев - исправные, а нечетных - неисправные. Процедура получения графа G0 выполняется за один просмотр связей исходного диагностического графа. Остальные процедуры также обладают малой трудоемкостью. Модель (0,1,1,1). Свойства этой диагностической модели рассмотрены в работе [59]. Если участвующие во взаимопроверке элементарные, машины исправны, то ее результатом будет «0», во всех остальных случаях «1». Выделим множество вершин U\ — {и,}, U\ a U, для каждой вершины которого имеется хотя бы одно ребро диагностического графа .Уу= 0. Очевидно, что все элементарные машины, составляющие U\, исправны, так как данная диагностическая модель не допускает нулевого значения результата элементарной проверки при неисправном состоянии одной из участвующих в ней машин.
Архитектура и программное обеспечение пространственно-распределенной мультикластерной вычислительной системы Центра параллельных вычислительных технологий СибТУТИ
Впервые термин «кластер» (от англ. cluster - группа), по-видимому, был применен в 1983 году компанией Digital Equipment (DEC) при разработке своего кластера VAX. По определению компании DEC, кластер — это группа вычислительных машин, которые связаны между собою и функционируют как один узел обработки информации. Очевидно, что определение кластера, предложенное компанией DEC, схоже с определением: распределенной; вычислительной системы. Поэтому, можно утверждать, что в архитектурном плане кластерные вычислительные системы нельзя называть уникальным; классом средств обработки информации.
Современное понимание кластерной системы основано на разработке? научно-космического центра NASA (точнее его подразделения - Goddard? Space Flight Center (GSFC)) - системы Beowulf. В их определении кластер или; кластерная вычислительная система —это композиция множества персональных компьютеров и сети связей, программным образом настраиваемая? для решения сложных вычислительных задач.
Проект Beowulf начался летом 1994 года сборкой: в GSFC 16-процессорного кластера (на процессорах 486DX4/100MHz, 16MB памяти?и 3 сетевых адаптера на каждом? узле, 3 "параллельных" Ethernet-кабеля по 10Mbit каждый). Этот кластер, который ш был назван "Beowulf создавался как вычислительный ресурс проекта «Earth and Space Sciences Project (ESS)». Далее в GSFC и подразделениях NASA были собраны другие, более мощные кластеры. Например, кластер the HIVE (Highly-parallel Integrated Virtual Environment) содержит 64 узла по 2 процессора Pentium Pro/200MHz и 4GB памяти в каждом, 5 коммутаторов Fast Ethernet.
Целью создания кластера Beowulf было разработка высокопроизводительной системы, имеющей минимальную стоимость.
Кластерные ВС, или, для краткости просто кластеры, условно подразделяются на физические и логические.
Первые строятся специально для решения сложных задач и не используются для других целей. Вторые организуются из персональных компьютеров, соединенных в локальную сеть и, при необходимости,-программным образом настраиваемых на решение параллельных задач.
Создание кластерных ВС из серийно выпускаемых ПК не вызывает существенных инженерных и математических трудностей. Как правило, требуются незначительные доработки базового программного обеспечения, связанные с реализацией системных операций в виде подпрограмм и с введением систЄхМ НОГО диспетчера в операционную систему. Это же самое можно сказать и относительно организации (логических) вычислительных кластеров на базе существующих компьютерных сетей.
В Центре параллельных вычислительных технологий (ЦПВТ) Сибирского государственного университета телекоммуникаций и информатики совместно с Институтом физики полупроводников, Сибирского отделения Российской академии наук создана и развивается пространственно распределенная кластерная вычислительная система (Grid-система).
В архитектурном плане вычислительная система состоит из двух сосредоточенных кластеров, один из которых располагается в помещении Лабора-ториишараллельных вычислений ЦПВТ СибГУТИ, а другой - в Лаборатории вычислительных систем ИФП СО РАН.
Кластерная ВС эксплуатируемая в СибГУТИ, на сегодняшний день, состоит из 5 сегментов, каждый их которых является сосредоточенным многомашинным кластером. Любой из сегментов способен функционировать как автономно - как обычная компьютерная сеть, или как отдельный кластер, так и в составе ВС (рис. 4.1).
В качестве базовых составляющих для построения системы использованы стандартные персональные компьютеры (ПК), собранные на базе процессоров семейства Intel: кластеры А, В - Celeron 667А, кластер С - Celeron 1100, кластер D- Celeron 667А и; Celeron 1700; кластер Е —Pentium IV. Все персональные компьютеры оборудованы собственной оперативной памятью (кластеры А,В,С - по 128 Мбайт,.кластеры D, Е - по 256 Мбайт), сетевым адаптером стандарта Fast Ethernet (максимальная скорость передачи данных 100 Мбит/с), клавиатурой, манипулятором типа«мышь», жестким диском (10 и 30 Гбайт), видеоадаптером и монитором.
Для организации телекоммуникационной сети использованы четыре коммутатора:(switch) фирмы «3COM». Топология сети относится к «звездообразной». Соединение между ПК организовано с помощью медного кабеля «витой пары» категории 5.
Для взаимодействия с другими кластерами (в частности, с кластером ИФП СО РАН) кластерная В С имеет выходы в Internet и модемные соединения с телефонной линией. Связь осуществляется через один из ПК системы ЦПВТ СибГУТИ и один ПК системы ИФП: СО РАН, которые также могут выполнять функции серверов (файловых или приложений) для всей системы.
Кластерная ВС ЦПВТ допускает масштабирование и способна взаимодействовать с множеством других кластеров. Для межкластерных взаимодействий - через телефонный канал используется пакет программ, реализующий протокол взаимодействия Pointo-Point (РРР). Таким образом, кластерная ВС ЦПВТ является базой: для формирования распределенной в пространстве конфигурации (Grid-система).
Все персональные компьютеры функционируют под управлением ОС Linux (дистрибутив ASPLinux v.9.2, ядро 2.4.26). Для разработки и реализации параллельных программ используется технология MPI (реализация LAM v.7.0.2 или MPICH.v. 1.2.0).
Хотя в программном плане система является однородной, однако технический состав кластерной вычислительной системы неоднороден, поэтому её можно рассматривать как прототип гомогенной Grid-системы. Архитектура кластерной ВС позволяет разрабатывать методы и алгоритмы функционирования,- применимые и в сосредоточенных, и в распределенных системах.
Стандартное программное обеспечение кластерных ВС рассчитано на многопрограммный режим решения сложных задач. Однако это ПО не рассчитано на поддержку оптимального режима и живучести ВС. Поэтому в ЦПВТ разрабатываются программные компоненты (рис. 4.2), которые позволят организовать оптимальное живучее функционирование систем в режимах решения набора и обслуживания потока задач, представленных параллельными программами с различным числом ветвей.
Для обеспечения функций диагностики для кластерных систем разрабатывается программный комплекс, который определяет состояние ВС, выявляя неработоспособные ресурсы, и передает результат программе пользователя. Достоинством данной программы является возможность модификации используемых тестов, проверяющих работоспособность ресурсов, в зависимости от задач, решаемых на вычислительной системе. Кроме того, алгоритм, лежащий в основе дешифрации результатов теста, также допускает адаптацию. Пользователь имеет возможность настраивать параметры, определяющие работу программы, путем изменением файла конфигурации. Последнее обеспечивает переносимость программы на вычислительные системы с различными характеристиками и позволяет учесть особенности решаемых задач. По сути, имеются средства для моделирования функционирования больше-масштабных распределенных вычислительных систем, со средствами диагностики.
