Графовые модели отказоустойчивости

• Автор: Абросимов, Михаил Борисович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 269 с.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

ГЛАВА Е ОСНОВНЫЕ СВОЙСТВА

1Л. Основные понятия теории графов

1.2. Отказоустойчивость

1.3. Расширения графов

1.4. Вычислительная сложность

ГЛАВА 2. ВЕРШИННЫЕ РАСШИРЕНИЯ

2.1. Основные определения и свойства

2.2. Сложность задачи

2.3. Неизоморфные расширения

2.4. Циклы
2.5. Предполные графы
2.6. Деревья
2.7. Орграфы
ГЛАВА 3. РЕБЕРНЫЕ РАСШИРЕНИЯ
3.1. Основные определения и свойства
3.2. Сложность задачи
3.3. Неизоморфные расширения
3.4. Циклы
3.5. Предполные графы
3.6. Деревья
3.7. Орграфы
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ
Актуальность исследования. Надежность является важнейшим аспектом при использовании вычислительных систем в критических областях. Авиация, энергетика, космос... Количество таких критических областей со временем только увеличивается. Выход из строя хотя бы одного элемента системы может привести к фатальным последствиям.
Движение (Avizienis, 1975) выделил два подхода для повышения надежности (reliability) реальных вычислительных систем: предотвращение ошибок и отказоустойчивость.
Первое направление связано с уменьшением вероятности возникновения ошибки и состоит в разработке высоконадежных компонентов системы. На этом пути можно отметить большие успехи. Время наработки на отказ первых компьютеров измерялось минутами, а современных - годами.
Во втором направлении используется добавление в систему избыточных структур для придания ей дополнительных свойств отказоустойчивости. Понятие отказоустойчивости было определено Авиженисом как обеспечение системы способностью противостоять ошибке и возможностью продолжать работу в присутствии этой ошибки. Выделяют следующие уровни отказоустойчивости:
1) полная отказоустойчивость - система продолжает работать в присутствии ошибок без существенной потери функциональных свойств;
2) амортизация отказов - система продолжает работать в присутствии ошибок с частичной деградацией функциональных возможностей.

Некоторое время назад (Laprie, 1985 ; Dependability 1992 ; Avizienis et al., 2004 ; Харченко, 2006 ; Харченко, 2009) стали рассматривать более общее понятие, чем надежность (reliability), - гарантоспособность (dependability). Под гарантоспособностью понимается комплексное свойство системы предоставлять требуемые услуги, которым можно оправданно доверять. В работе (Avizienis et al., 2004) дается подробная таксономия для гарантоспособности. В частности, надежность является атрибутом гарантоспособности, а отказоустойчивость - одним из средств ее достижения.
В данной работе будет исследоваться конструкция минимального вершинного и реберного расширения графа, основанная на идеях формализации понятия полной отказоустойчивости технических систем, предложенных в 1976 г. Хейзом (Hayes, 1976).
Технической системе X сопоставим помеченный граф G(X), вершины которого соответствуют элементам системы X, ребра - связям между элементами, а метки указывают тип элементов. Под отказом элемента технической системы X понимается удаление соответствующей ему вершины из графа системы G(X) и всех связанных с ней ребер.
Говорят, что система X* является k-отказоустойчивой реализацией системы X, если отказ любых к элементов системы X* приводит к графу, в который можно вложить граф системы X с учетом меток вершин. Построение -отказоустойчивой реализации системы X можно представить себе как введение в неё определенного числа новых элементов и связей. При этом предполагается, что в нормальном режиме работы избыточные элементы и связи маскируются, а в случае отказа происходит реконфигурация системы до исходной структуры. Следует заметить, что процесс реконфигурации в общем случае (с учетом частичной деградации функциональных возможностей системы) является достаточно сложной процедурой и составляет самостоятельную область исследования (см. например, Livingston, Stout, 1988 ; Dutt,

Недостатком полной отказоустойчивости является ее повышенная стоимость, обусловленная необходимостью введения избыточных элементов и связей. Например, суперкомпьютер последнего поколения серии Blue Gene/Q, созданной фирмой IBM в 2011 г., содержит 65 536 рабочих процессоров и 4096 избыточных процессоров, которые активируются при выходе из строя основных процессоров. В обычном режиме избыточные процессоры не функционируют. В текущем рейтинге, составленном в июне 2013 г., этот компьютер занимает 37-ю позицию с результатом 715.6 Тфлопс24. В данное время самый мощный суперкомпьютер этой серии Sequoia был создан в 2012 г. для Ливерморской национальной лаборатории. Он состоит из 1 572 864 рабочих процессоров и 98 304 избыточных. Его производительность составляет —17 Пфлопс, что почти в два раза превышало производительность суперкомпьютера Fujitsu К computer, который на момент появления Sequoia был самым производительным. В данный момент Sequoia занимает третью строчку, почти в два раза уступая по производительности суперкомпьютеру Tianhe-225.
При амортизации отказов система сохраняет работоспособность, возможно, с частичной потерей функций. Например, система считается работоспособной, если соответствующий ей граф является связным. Система называется вершинной (реберной) -отказоустойчивой, если после отказа к элементов (связей) система остается работоспособной. Так как минимально связным графом является дерево, то при исследовании такой отказоустойчивости исследуются задачи определения вершинной и реберной -связности определенных графов (гиперкубы, торы, закольцованные деревья и др.) и вложения в них деревьев (Despain, Patterson, 1978 ; Horowitz, Alessandro, 1981
24 Флопс (FLOPS - от англ. Floating point Operations per Second) - единица, используемая для измерения производительности компьютеров, показывающая, сколько операций с плавающей запятой в секунду выполняет данная вычислительная система.