В. П. Корячко, д-р техн. наук, проф.,

С. В. Скворцов, канд. техн. наук, доц., Рязанская государственная радиотехническая академия,

В. И. Шувиков, канд. техн. наук, Военный автомобильный институт, г. Рязань

Характеризация диагностических графов для симметричной модели дешифрации синдрома

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

Введение. Диагностический граф (ДГ) является одной из наиболее известных формальных моделей, используемых в задачах автоматического обнаружения неисправностей в отказоустойчивых многопроцессорных вычислительных системах [1, 2]. Вершины ДГ соответствуют множеству U = (u₁, u₂,…, u_n) однотипных вычислительных модулей (ВМ) системы, а связи задают множество элементарных проверок (ЭП), выполняемых в режиме реального времени. Наибольшее распространение получили ориентированные ДГ вида Н = (U, Т), где каждая дуга  задает одну ЭП и определяет пару ВМ (контролирующий u_i и контролируемый u_j), исполняющих параллельно одну и ту же прикладную задачу или ее фрагмент, причем при совпадении результатов дуге соответствует значение s_ij = 0, в противном случае — значение s_ij = 1. Период времени, необходимый для однократного проведения всех ЭП, заданных ДГ, называют циклом контроля [3], а упорядоченная последовательность значений s_ij образует синдром S системы, описывающий текущее техническое состояние ВМ.

Рассматриваются только устойчивые неисправности, т. е. в каждом цикле контроля любой ВМ может находиться в одном из двух состояний: работоспособном или отказа. Предполагается также, что для нормального функционирования системы требуется не менее m работоспособных модулей, где m < n. Следовательно, в системе допускается одновременное наличие не более t = n - m отказов, а величина t называется степенью отказоустойчивости [2].

Если дешифрация текущего синдрома S позволяет правильно идентифицировать все неисправные ВМ, число которых не превышает t то система называется t-диагностируемой. При этом могут выявляться все неисправные модули одновременно (при параллельном t-диагностировании), или хотя бы некоторые из них (при последовательном t-диагностировании). В дальнейшем будем рассматривать только параллельное t-диагностирование, что обусловлено необходимостью минимизации временных затрат на реконфигурацию системы в режиме реального времени.

Нахождение необходимых и достаточных условий, накладываемых на структуру ДГ для обеспечения t-диагностируемости системы, составляет проблему характеризации [1].

Постановка задачи. Пусть Ф — множество допустимых состояний системы, каждое из которых определяет некоторое множество отказавших модулей и задается как  — множество всех возможных подмножеств из Ф, содержащих  неисправных ВМ. Очевидно, что , где  характеризует работоспособное (исправное) состояние. Тогда , где  соответствуют неисправным состояниям, а общее число состояний системы определяется как .

Чтобы система удовлетворяла условию параллельной t-диагностируемости требуется установить взаимно однозначное соответствие между множествами допустимых состояний Ф и значениями синдрома S, при котором каждому  должно соответствовать уникальное значение S.

Дешифрация синдрома S проводится с учетом ограничений некоторой диагностической модели (ДМ), варианты которых различаются интерпретацией результатов ЭП в зависимости от реального состояния контролирующего и контролируемого ВМ. Формально ДМ задается четверкой переменных вида (s_rr, s_rf, s_fr, s_ff). Первый индекс указывает состояние контролирующего, а второй — контролируемого ВМ (r — исправен ,f — отказал), причем всегда s_rr = 0 и s_ff = 1, а переменные s_fr и s_ff могут принимать любое из значений {0, 1, x}, где x означает непредсказуемый результат (0 или 1) ЭП. Наиболее известными являются модели РМС [4] и BGM [5], которые описываются как (0, 1, x, x) и (0, 1, x, 1) соответственно.

Если результат  любой ЭП сохраняется при взаимном изменении функций ВМ (контролирующий — контролируемый), то ДМ называют симметричной, а ДГ может быть представлен как неориентированный граф G = (U, D), где каждое ребро  задает одну ЭП, в которой оба ВМ являются взаимоконтролирующими (без жесткой фиксации функций). В работах [6, 7] показано преимущество симметричных ДМ перед несимметричными при организации функционирования отказоустойчивых многопроцессорных систем в режиме реального времени, причем наиболее перспективной представляется модель (0, 1, 1, 1). Ее применение основано на предположении о невозможности получения одинаковых результатов исполнения одного фрагмента прикладной программы над одними исходными данными парой идентичных ВМ в случае отказа хотя бы одного из них.

В данной статье предлагается решение проблемы характеризации для неориентированных ДГ и модели дешифрации синдрома (0, 1, 1, 1), обобщающее и уточняющее результаты [8, 9], полученные для ориентированных графов.

Анализ известных решений. Результаты исследования диагностической модели (0, 1, 1, 1) можно найти в работах [8, 9]. В [8] установлена верхняя граница меры диагностируемости, которая определяется условием t ≤ n - 2, а в [9] доказана следующая теорема, направленная на решение проблемы характеризации.

Теорема 1 [9]. Система является t-диагностируемой, если и только если для ориентированного ДГ H = (U, T) выполняются следующие условия:

1)  для каждой вершины ;

2)  для каждого множества ,

где ;

;

3) существует не больше одного , такого, что множество дуг Т₁, инцидентных всем вершинам из U₁, совпадает с множеством T, где обозначение [a] определяет наибольшее целое, которое меньше a.

Детальный анализ теоремы [9], подтвержденный машинным моделированием неисправных состояний и генерацией соответствующих синдромов для различных ДГ, позволил установить, что приведенные условия являются только необходимыми и не гарантируют достаточности из-за неполноты второго и третьего требований. В этом нетрудно убедиться на примере ДГ, показанного на рис. 1.

Рис. 1. Пример ДГ, противоречащего условиям теоремы 1 [9]

Следует заметить, что представленный граф является неориентированным, поскольку независимо от направления связи между любой парой вершин u_i и u_j результаты ЭП s_ij = s_ji совпадают вследствие симметричности модели (0, 1, 1, 1). Для корректного анализа теоремы [9] можно задать любое направление каждой связи. Однако определяемое по условиям этой теоремы значение меры диагностируемости t = 3 недостижимо из-за совпадения синдромов для состояний  и . Следовательно, реальное значение t = 2, хотя все условия теоремы [9] справедливы для t = 3.

Решение задачи характеризации. Пусть неориентированный ДГ G = (U, D) описывает отказоустойчивую систему с заданным параметром t ≤ n - 2. Если структура проверочных связей обеспечивает параллельную е-диагностируемость в рамках модели (0, 1, 1, 1), то будем считать, что граф  обладает свойством е(0, 1, 1, 1), где M — множество всех возможных ДГ, некоторые из которых могут и не иметь указанного свойства.

Любое неисправное состояние системы определяет разбиение множества U вершин графа G на два непересекающихся подмножества:

,

где В — множество вершин, соответствующих неисправным, a R — исправным ВМ. Тогда изменение состояния системы формально может быть представлено перераспределением элементов  между подмножествами В и R, каждое из которых также состоит из двух подмножеств:

При переходе к новому состоянию состав В₁ и R₁ не изменяется, а В₂ и R₂ изменяется путем перехода всех элементов из В₂ в R и всех элементов из R₂ в B. Обозначим число элементов каждого из указанных подмножеств следующим образом:

Представим ДГ в виде четырех подграфов, построенных на множествах вершин В₁, R₁, B₂, R₂ и связанных произвольным образом (рис. 2), где ребрам сопоставлены результаты  ЭП.

Рис. 2. Представление ДГ в виде графа замены

Без потери общности будем считать, что b₂ ≥ r₂. Тогда справедливы соотношения, следующие из предположения о t-диагностируемости системы:

b₁ + b₂ = b; b ≤ r, 1 ≤ b₂ ≤ r;

r₁ + r₂ = n - b; 0 ≤ r₂ ≤ min {b₂, n - b}.

Такое представление ДГ будем называть графом замены, поскольку любой переход из одного состояния в другое может быть описан как перевод элементов  из неисправных в исправные, а  наоборот — из исправных в неисправные.

Например, если в i-м цикле контроля состояние системы определяется как  , а в (j + 1)-м — как  , то соответствующие подмножества вершин графа замены определяются следующим образом:

где {X} — подмножество вершин ДГ, соответствующих неисправным ВМ для состояния X.

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

Лемма. Любое изменение состояния системы, представленной неориентированным диагностическим графом G = (U, D), приводит к получению нового значения синдрома, если и только если выполняется хотя бы одно из следующих условий:

                                           (1)

                                           (2)

                                           (3)

                                           (4)

где .

Доказательство. Необходимость. Пусть переход к новому состоянию системы, заданный графом замены, приводит к изменению синдрома S. Это означает, что найдется ребро , для которого выполняется хотя бы одно из следующих условий:

            (5)

            (6)

где  и  — элементы синдрома S для текущего и следующего циклов контроля соответственно, сопоставленные ребру .

Тогда с учетом требований диагностической модели (0, 1, 1, 1) получаем:

·        условие (5) может быть истинно только для  или , что, в свою очередь, означает спра­ведливость (2) или (4) соответственно;

·        условие (6) может быть истинно только для  или , что означает справедливость (1) или (3).

Достаточность. Предположим, что при переходе к новому состоянию хотя бы одно из условий (1)—(4) истинно, но синдром не изменяется. Это невозможно, так как:

·        если истинно (1), то хотя бы для одного ребра  должно выполняться условие (6);

·        если истинно (2), то хотя бы для одного ребра  должно выполняться условие (5);

·        если истинно (3), то хотя бы для одного ребра  должно выполняться условие (6);

·        если истинно (4), то хотя бы для одного ребра  должно выполняться условие (5).

Таким образом, при выполнении любого из условий (1)—(4) синдром изменяется и исходное предположение неверно.

Лемма доказана.

Следствие. Изменение состояния системы, представленной ДГ G = (U, D), для которого в соответствии с теоремой [9] все вершины  удовлетворяют условию deg(u_i) ≥ t, всегда приводит к изменению синдрома, если выполняется любое из сле­дующих неравенств:

                      (7)

                                            (8)

                                                 (9)

В качестве примера можно показать, что ДГ, приведенный на рис. 1, не удовлетворяет условиям леммы, если представить его как граф замены (рис. 3) с множествами  и .

Согласно [10] характеризационная проблема сводится к поиску множества  запрещенных фигур, т. е. таких графовых моделей , отсутствие которых в , где  — подмножество допустимых ДГ, является необходимым и достаточным условием того, что G обладает свойством /(0, 1, 1, 1) и при этом никакая из моделей

Рис. 3. Граф замены для ДГ, показанного на рис. 1

 не присутствует в другой запрещенной фигуре . Присутствие и отсутствие одной модели в другой задаются отношением подчинения π, правильный выбор которого позволяет конкретизировать проблему в разрешимую характеризационную задачу. Отношение π, задаваемое на множестве М = {G_i}, упорядочивает графовые модели таким образом, что (G_i, G_j)  π, если G_i присутствует в G_j. Модель G_i является подчиненной модели G_j и образуется из G_j удалением вершин или ребер [10].

Для решения задачи будем использовать класс M ДГ, где каждый G  М является покрывающим суграфом полного неориентированного графа G_p = (U, D_p). Рассмотрим два вида отношения подчинения: π₁ — быть частичным подграфом и π₂ — быть суграфом. В обоих случаях характеризационная задача разрешима, так как π₁ и π₂ удовлетворяют принципу локальности [10], в соответствии с которым для класса моделей М с заданным отношением подчинения и свойства t(0, 1, 1, 1) множество запрещенных фигур M_z существует тогда и только тогда, когда любая модель G_i, подчиненная модели G_j, обладающей свойством t(0, 1, 1, 1), также обладает этим свойством.

Справедливость принципа локальности для отношений π₁ и π₂ нетрудно показать на основе анализа процедур формирования суграфа и частичного подграфа [10, 11]: суграф образуется удалением только ребер исходной модели; частичный подграф получают удалением вершин вместе с инцидентными им ребрами и затем любых из оставшихся ребер. Следовательно, подчиненная модель G_i может быть сформирована из G_j только обратными действиями, что всегда сохраняет свойство t(0, 1, 1, 1), так как введение ребра задает одну дополнительную ЭП, а вершины с инцидентными ребрами — избыточный ВМ, реализующий некоторое множество дополнительных ЭП.

`Таким образом, для ДГ G = (U, D) в целом запрещенные фигуры образуются из минимальных элементов отношений те i и л2 на множестве M\M_d и представляют собой элементы графовых моделей (части ДГ) с совпадающими значениями S для двух или более неисправных состояний. Вид запрещенных фигур устанавливается следующей теоремой.

Теорема 2. Диагностический граф G = (U, D) с числом вершин n > t + 2 обладает свойством t(0, 1, 1, 1), если и только если в G отсутствуют запрещенные фигуры следующих видов:

1) вершина , для которой deg(u_i) < t (фигура вида );

2) симметричный полный двудольный граф , где 1 ≤ v ≤ t, для которого выполняются условия:

                                            (10)

               (11)

                                                  (12)

Доказательство. Необходимость. Пусть ДГ G = (U, D) обладает свойством r(0, 1, 1, 1). Тогда в соответствии с теоремой [9] в нем отсутствуют запрещенные фигуры первого вида . Покажем, что в этом случае также отсутствуют и запрещенные фигуры второго вида .

Действительно, присутствие в G запрещенной фигуры второго вида порождает два неисправных состояния с одинаковыми значениями синдрома. В этом нетрудно убедиться, если представить ДГ, содержащий , как граф замены, для которого

         (13)

а также

                                                                 (14)

что непосредственно следует из (12).

Тогда в соответствии с леммой условия (13) и (14) показывают, что ДГ не обладает свойством t(0, 1, 1, 1), а это противоречит принятому предположению. Таким образом, если ДГ G = (U, D) обладает свойством t(0, 1, 0, 1), то в нем отсутствуют запрещенные фигуры первого и второго видов.

Достаточность. Для доказательства достаточности предположим противное, т. е. запрещенные фигуры  и  в ДГ отсутствуют, но G = (U, D) не обладает свойством t(0, 1, 1, 1). В соответствии с теоремой [9] имеем deg(u_i) ≥ t для всех , а это означает, что отсутствие свойства t(0, 1, 1, 1) могут определять только запрещенные фигуры второго вида. Но при этом, во-первых, не выполняются все условия (1)—(4) леммы. Во-вторых, отсутствие свойства t(0, 1, 1, 1) при одновременном отсутствии запрещенных фигур первого вида в соответствии со следствием из леммы означает, что deg(u_i) = t для  и b₂ = r₂. Таким образом, выполняются все условия присутствия в G запрещенной фигуры  второго вида, что противоречит предположению.

Теорема доказана.

Например, в ДГ, показанном на рис. 1, отсутствуют запрещенные фигуры первого вида, но присутствует одна запрещенная фигура , для которой  что нетрудно заметить на соответствующем графе замены (см. рис. 3). Исключить  можно введением хотя бы одного ребра, удовлетворяющего условиям леммы, например,  или  что позволит получить значение t = 3.

Рассмотрим предельный случай n = t + 2, который не учитывается теоремой 2. Здесь запрещенной фигурой является граф , удовлетворяющий условиям

,

что устанавливается следующей теоремой.

Теорема 3. Диагностический граф G = (U, D) с числом вершин n = t+ 2 обладает свойством t(0, 1, 1, 1), если истинно условие |D_n\D| ≤ 1, где D_n — множество ребер полного графа K_n = (U, D_n).

Доказательство. Два неисправных состояния  и  различимы, если их синдромы отличаются хотя бы одним значением . Это возможно только в том случае, когда пары вершин  и  связаны ребрами  и , для которых s_ij = 0 и s_kl = 0 соответственно. Поскольку неисправными могут быть любые n - 2 ВМ, то ребро [u_i, u_j]  D должно существовать для любой пары вершин u_i, u_j  D. Следовательно, в этом случае граф G является полным графом K_n, построенным на n вершинах, для которого синдром всегда содержит только один нулевой элемент s_ij = 0, определяющий пару исправных ВМ и u_i, u_j  U, а все остальные значения s_ij = 1. Отсюда, допуская возможность существования одного варианта синдрома S, для которого все s_ij = 1, можно исключить только одно любое ребро из множества D_n что означает справедливость условия |D_n\D| ≤ 1. Теорема доказана.

Рис. 4. Компоненты связности ДГ при t = 1:

а — минимальная компонента связности; б — виды дополнительных компонент связности; в — возможные виды ДГ для n = 5

Таким образом, при t = n - 2 ДГ с минимальным числом связей (минимальный ДГ) представляется как полный граф на n вершинах без одного любого ребра.

При t = 1 также достаточно просто определить вид минимального ДГ, обладающего свойством t(0, 1, 1, 1). Очевидно, что в соответствии с теоремой 2, для deg(u_i) = 1, u_i  U граф G является несвязным и включает компоненты связности, которые являются полными двудольными графами K_1.1 = K₂, построенными на парах вершин u_i, u_j  U. Однако компоненты K_1.1 являются запрещенными фигурами второго вида, поскольку состояния  и  неразличимы. По требованиям леммы каждая такая фигура должна быть дополнительно связана хотя бы одним ребром с любой вершиной . Следовательно, минимальные компоненты связности ДГ являются подграфами, показанными на рис. 4, а, причем, если n mod 3 ≠ 0, то дополнительно могут использоваться одна или две компоненты, показанные на рис. 4, б и 4, в.

* * *

Исключение запрещенных фигур первого  и второго  видов гарантирует наличие свойства

t(0, 1, 1, 1) при построении диагностических графов с заданными характеристиками. При этом запрещенные фигуры  обобщают положения теоремы [9], второе условие которой соответствует случаю v = 1, а третье условие выполняется при  и .

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

Список литературы

1. Баранов В. Г., Гладков В. В., Махалин Б. Н. Математические модели для системного уровня диагностики неисправностей в мультипроцессорных системах // Обзоры по электронной технике. Сер. 8. Управление качеством, стандартизация, метрология, испытания. 1991. Вып. 2 (1601). 58 с.

2. Принципы обеспечения отказоустойчивости многопроцессорных вычислительных систем: Сб. трудов. М.: Ин-т проблем управления, 1987. 82 с.

3. Гершанов В. И., Скворцов С. В., Телков И. А. Методы повышения отказоустойчивости вычислительных систем, основанных на принципе ассоциативной селекции потоков данных // Вопросы радиоэлектроники. Сер. Электрон, вычисл. техн. 1992. Вып. 7. С. 50—58.

4. Preparata F. P., Metze G., Chien R. Т. On the Connection Assignment Problem of Diagnosable Systems // iEEE Trans. Electron. Comput. 1967. V. EC-16. N 6. P. 848-854.

5. Barsi F., Grandoni F., Maestrini P. A Theory of Diagnosability of Digital Systems // IEEE Trans. Comput. 1976. V. C-25. N 6. P. 585-593.

6. Крамаренко М. Б. Анализ самодиагностирования отказов вычислительной системы // Электронное моделирование. 1987. №6. С. 61-64.

7. Скворцов С. В. Применение симметричной диагностической модели при организации активной отказоустойчивости многопроцессорных систем // Вестник Рязанской государственной радиотехнической академии. 1998. Вып. 4. С. 57—64.

8. Крамаренко М. Б. Модели диагностирования отказов параллельной вычислительной системы // Электронное моделирование. 1989. № 3. С. 60—65.

9. Радойчевски В. Ц., Шалаев А. Я. Параллельная диагностируемость модульных систем при централизованной дешифрации синдрома // Электронное моделирование. 1992. № 1. С. 57—63.

10. Горбатов В. А. Основы дискретной математики. М.: Высш. шк., 1986. 311с.

11. Оре О. Теория графов. М.: Наука, 1980. 336 с.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 6, 1999

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