Автоматика и телемеханика, № 5, 2012
Безопасность, живучесть, надежность, техническая диагностика
© 2012 г. Ю.К. ДИМИТРИЕВ, д-р техн. наук (Институт физики полупроводников им. А.В. Ржанова СО РАН, Новосибирск)
ПРАВИЛА УСЛОВНОГО ЛОКАЛЬНОГО САМООПРЕДЕЛЕНИЯ И АЛГОРИТМ ДИАГНОСТИРОВАНИЯ МУЛЬТИПРОЦЕССОРНОЙ СИСТЕМЫ С ЦИРКУЛЯНТНОЙ ДИАГНОСТИЧЕСКОЙ СТРУКТУРОЙ НА ИХ ОСНОВЕ
Рассматривается локальное диагностирование на системном уровне для мультипроцессорных (модульных) вычислительных систем (ВС) при множественных неисправностях. ВС имеет циркулянтную диагностическую структуру. Исходы тестов, выполняемых неисправными модулями, соответствуют известной модели Препараты, Метца и Чжена. Задача диагностирования сформулирована как задача определения хотя бы одного фактически исправного модуля, с помощью которого определяется состояние системы в целом. Введены условия выделения множества модулей, которое заключает в себе все присутствующие в системе неисправные модули. Описан алгоритм самодиагностирования системы. Доказано, что использование этого алгоритма, позволяет достичь локальной ¿-диагнос-тируемости ВС с циркулянтной диагностической структурой для любых значений числа N модулей и кратности £ неисправностей, удовлетворяющих условию N > + 1.
1. Введение
В данной статье продолжается начатое в [1, 2] исследование возможности диагностирования мультипроцессорных вычислительных систем (ВС) при отказах кратностью не более £ (¿-диагностируемые системы). Используется известная теоретико-графовая модель Препараты, Метца и Чжена [3] (ПМЧ-модель). В этой модели исход теста, выполняемого исправным модулем, правильно определяет состояние тестируемого, а исход теста, выполняемого неисправным модулем, не зависит от фактического состояния тестируемого. В [1] предложены правила, с помощью которых техническое состояние каждого модуля определяется по результатам тестирования только тех модулей, которые имеют с ним физические связи. Эти правила названы правилами самоопределения, а базирующаяся на их использовании диагностика -локальной.
В [2] показано, что в системе, представленной циркулянтным диагностическим графом, для заданного Ь существуют границы по числу модулей, вне которых есть такие состояния системы, при которых введенные правила самоопределения [1] не обеспечивают идентификацию состояния для всех модулей. Подобные состояния ВС названы тупиковыми, а сами системы - частично ¿-диагностируемыми.
В классической постановке [3] проблема ¿-диагностирования ВС решается как задача идентификации всех присутствующих в системе неисправных модулей (¿-диагностирование без ремонта в терминологии работы [3]) по результатам сопоставительного анализа полученных исходов тестирования. Исправные модули идентифицируются по "остаточному" принципу, как модули, не входящие в множество идентифицированных неисправных модулей. Подобный подход соответствует построению теории системного диагностирования, но не учитывает требований, предъявляемых к эффективности использования по назначению и определения технического состояния масштабируемых мультипроцессорных систем.
Для современных мультипроцессорных систем одной из основных эксплуатационных характеристик является отказоустойчивость - способность системы продолжать правильно функционировать после выхода из строя отдельных модулей. Для таких систем перспективна постановка задачи системного диагностирования, как проблемы идентификации хотя бы одного исправного модуля. Выделенные один или группа исправных модулей составляют диагностическое ядро системы и обеспечивают определение состояния других модулей системы. Идентифицированные ядром исправные модули также могут использоваться для определения состояния ещё не проверенных модулей. Тем самым реализуется известный ещё для компьютеров первых поколений принцип диагностирования методом расширяющегося диагностического ядра.
Основные преимущества метода диагностического ядра по сравнению с "классическим" способом системного диагностирования состоят в следующем.
1. При "классическом" подходе для определения состояния каждого модуля необходим сопоставительный анализ исходов тестов над некоторым подмножеством модулей системы, выходящего за границы физического соседства модулей. При использовании диагностического ядра состояние любого модуля, смежного с модулем из ядра, определяется по исходу единственного теста над ним. Это уменьшает число тестов, необходимых для определения состояния системы и, как следствие, увеличивает время использования системы по назначению.
2. Использование метода выделения диагностического ядра обеспечивает более надёжную защиту системы от разрушительного воздействия со стороны ещё не выявленных неисправных модулей и большую оперативность реакции на попытку такого воздействия.
3. Образуемая на базе ядра связная подсистема из исправных модулей может немедленно переключаться на решение прикладных задач, что создаёт основу для совмещения счёта с диагностикой и организации живучего функционирования ВС.
Впервые использование метода выделения диагностического ядра для самодиагностирования описано в [4].
В [1, 2] найдены локальные "точные" условия идентификации состояния исправного и неисправного модулей. В [5] впервые для решения задач самодиагностирования применено локальное условие, позволяющее определить, содержит ли пара модулей, участвующих в тестировании, неисправный модуль.
Авторы [5] не пошли дальше применения этого условия для определения фактически неисправных модулей. Между тем применение этого свойства открывает возможность выделить множество М модулей, включающее в себя все присутствующие в системе неисправные модули. Идентификация хотя бы одного модуля, не принадлежащего множеству М, решает задачу выделения начального элемента наращиваемого диагностического ядра.
В данной работе будет проанализирована возможность использования описанного свойства из [5] и будут предложены новые свойства, представляющие обобщение свойства из [5], для локального самодиагностирования мультипроцессорной вычислительной системы методом выделения диагностического ядра.
2. Обозначения и определения
В данной работе применяются терминология и нотация, введённые в [1, 2]. Поэтому используемые понятия даны без пояснений. Диагностическая структура ВС представлена ориентированным графом Б = (V, Е) с взвешенными дугами. Вершины г € V, \У\ = N, графа отображают модули, а дуги (г,.]) € € Е, г,] € V, - тестовые связи от тестирующего модуля к тестируемому. Для дуги (г, ]) двоичный вес а(г,]) = 0, если модуль г считает, что модуль ] исправен, и а(г.) = 1 - в противном случае. Согласно ПМЧ-модели [3], исход теста, выполняемого неисправным модулем, не зависит от фактического состояния тестируемого модуля. Для модуля, которому сопоставлена вершина г, множества X (г) = {] € V : (], г) € Е}, У (г) = {] е V : (г.) € Е} и Н (г) = X (г) и У (г) представляют в диагностическом графе модули тестирующие, тестируемые и смежные соответственно; X (г) = Хо(г) и Х1(г), У (г) = = У0(г) и У1(г); индекс а подмножеств Ха, Уа соответствует весу а дуг, инцидентных вершине г.
Для упрощения изложения терминология системы распространена на представляющий ее диагностический граф, что делает правомерным использование выражений "состояние графа" вместо "техническое состояние системы", "исправная (неисправная) вершина" вместо "исправный (неисправный) модуль", "исход теста" вместо "вес дуги" и т.п.
Состояние графа описываем перечислением неисправных вершин ^ = = {г1,г2,--.,г\рк\}, называя множество ^ "образом неисправностей". Множество допустимых (кратных) неисправностей ¥(Ь) = {¥1, ,..., (¿)|} составляют сочетания из N вершин по п, где п = 1,1. Значение I называем кратностью неисправностей, а упорядоченное множество а(¥к) = = {а(г,.]) : (г,.]) € Е} исходов тестов, соответствующее заданному , - синдромом состояния графа. Говорим, что синдром ) совместен с образом неисправностей , а порождает синдром ).
В качестве диагностического графа используем циркулянт с параметрическим описанием ^^ = N; 81}82, • • • , 8^), где N - число вершин графа, а {$1, 82, • ••, 8^} - множество целых чисел - "прыжков": 81 = 1, 82 = 2, ..., = = ¿. Такой циркулянт при £ < [(^ — 1)/2] обеспечивает ¿-диагностируемость, а при £ = — 1)/2] является оптимальным ¿-диагностируемым графом [3].
Каждой вершине г диагностического графа сопоставлена метка т(г) Е Е {0,1, 2, 3, 4, 5}. Значение т(г) = 2, если состояние вершины г не идентифицировано (в частности, перед началом диагностирования это условие выполняется для каждой из вершин графа); значение т(г) = 0 или т(г) = 1, если по результатам анализа синдрома и(Ек) вершина г признана соответственно исправной или неисправной (эти состояния называем финальными); метки т(г) Е {3, 4, 5} используются для управления ходом диагностирования. Они соответствуют предварительно определяемому состоянию вершины. Подробнее эти метки рассматриваются в последующих разделах работы. Совокупность найденных финальных меток вершин называем разметкой графа.
Для определения финального состояния вершины г используются правила. основанные на сопоставительном анализе исходов тестирования, относящихся только к вершинам из её ограниченной окрестности (конкретно, к множеству Н(г)) и называемые правилами (локального) самоопределения.
Пусть / (г) - подмножество неисправных вершин, идентифицированных в окрестности вершины г и, следовательно, получивших метку т = 1. Условие самоопределения для вершины г рассматривается на (остаточном) множестве Я(г) = Н(г) — /(г) вершин, имеющих метку т(г) = 2. Для ПМЧ-модели условие самоопределения исправной вершины г, введённое в [1], имеет следующий вид;
(1) \Я(Хо(г))\ > £ — \/(г)\ ^ г Е Ек ^ т(г) := 0-
Здесь £ — \/(г)\ = Q(г) - локально оцениваемое для вершины г наибольшее возможное число (порог самоопределения) ещё не идентифицированных неисправных вершин в остаточном графе. Порог самоопределения в процессе диагностирования изменяется. Значение т(г) = \/(г)\ называем величиной корректировки порога самоопределения для вершины г.
Идентификация исправной вершины г
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.