Автоматика и телемеханика, № 7, 2015
Безопасность, живучесть, надежность,
техническая диагностика
© 2015 г. Ю.К. ДИМИТРИЕВ, д-р техн. наук (dimi@isp.nsc.ru)
(Институт физики полупроводников им. А.В. Ржанова СО РАН, Новосибирск)
О КОНЦЕПТУАЛЬНОЙ ОСНОВЕ СРАВНИТЕЛЬНОГО АНАЛИЗА И РЕШЕНИЯ ЗАДАЧ САМОДИАГНОСТИКИ МНОГОПРОЦЕССОРНЫХ СИСТЕМ ДЛЯ РАЗНЫХ МОДЕЛЕЙ НЕНАДЕЖНОГО ТЕСТИРОВАНИЯ1
Рассматривается самодиагностика без ремонта на системном уровне для многопроцессорных (модульных) вычислительных систем при множественных устойчивых неисправностях и при использовании ненадежных тестов. Выделена группа моделей тестирования, представляющих системы с полными ненадежными тестами. Формально обосновано отношение включения между моделями ненадежных тестов, дающее возможность объединять модели в группы с одинаковыми диагностическими свойствами. Доказаны утверждения, позволяющие выполнять сравнительный анализ диагностических свойств систем, использующих разные модели ненадежных тестов. Выявлена взаимосвязь между отношением включения и известным представлением связи между синдромом и порождающими его образами неисправностей в виде булевых функций. Показана эффективность использования булевой алгебры для сравнительного анализа диагностических свойств систем с разными моделями тестирования, и для разработки алгоритмов локального самодиагностирования.
1. Введение
В статье рассматривается теоретико-графовая модель диагностики на системном уровне для многопроцессорных (модульных) систем при множественных (далее кратных) устойчивых неисправностях с помощью полных, но ненадежных тестов, описанная в [1]. Модель представляет систему, состоящую из модулей, каждый из которых, используя данные ему средства функционального и тестового диагностирования, в одиночку может проверить и оценить техническое состояние некоторых других модулей. Состояние системы в целом определяется автоматически путем сопоставительного анализа полученных оценок, выполняемого модулями самой системы. Процесс определения состояния системы называют самодиагностированием, а сами системы — самодиагностируемыми [1, 2]. Моделью самодиагностируемой системы (далее — модель самодиагностирования) служит орграф, вершины которого представляют модули системы, а дуги — тестовые связи от тестирующих модулей к тестируемым. Дуги графа взвешены (двоичными) оценками
1 Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект № 14-07-00169а).
состояния тестируемого модуля, которые дает ему тестирующий. В [1] предполагается использование полных, но ненадежных тестов. Это означает, что исходы тестирования, проводимого исправными модулями, достоверно определяют состояние тестируемых модулей, а результаты тестов, выполняемых неисправными модулями, ненадежны. В [1] принято следующее соглашение об исходе ненадежного теста: заключение неисправного тестирующего модуля о состоянии тестируемого им модуля не зависит от фактического состояния последнего (ПМЧ-модель). В дальнейшем появились публикации, в которых рассматривались теоретико-графовые модели самодиагностирования, отличающиеся от предложенной в [1] только соглашениями об исходах ненадежных тестов. В [3] описана модель (БГМ-модель), в которой неисправный тестирующий модуль не может выдать заключение, что неисправный тестируемый модуль исправен. В [4, 5] описаны так называемые модели сравнения, в которых заключение о состоянии тестирующего и тестируемого модулей делается на основании сравнения результатов выполнения ими одной и той же (тестовой) задачи.
Перечисление возможных моделей самодиагностирования, различающихся соглашениями о свойствах надежности используемых тестов для устойчивых отказов, дано в [6]. Однако авторы не проанализировали диагностические возможности, которые представляет использование этих моделей тестирования, ограничившись формальной констатацией существования разнообразия моделей тестирования, и работа не получила развития2.
Классификация [6] закрепила сложившееся ко времени ее публикации разделение исследователей на сторонников той или иной модели ненадежного тестирования. Основные усилия исследователей были направлены на разработку моделей [1, 3-5]. Для остальных моделей известны только полученные отечественными учеными значения кратности допустимых неисправностей и необходимые и достаточные условия диагностируемости [7-9]. Характерным для этих работ — даже тех, в которых рассматривается несколько моделей ненадежного тестирования — является обособленность изучения моделей. Исключением является только работа [7], где была предпринята попытка выявить связь между диагностическими свойствами систем, использующих разные модели ненадежного тестирования3. Однако содержательный уровень рассмотрения привел к тому, что полученные автором выводы, хотя и верные по существу, но лишенные формальной доказательной основы, имеют характер догадки.
Первая цель данной работы — дать формальную основу для выявления и изучения характера связи между разными моделями ненадежного тестирования, а также для сравнительного изучения диагностических свойств систем, их использующих.
2 Косвенным подтверждением правомерности такой оценки является тот факт, что авторы [6] мотивировали введение моделей М010х и Моцх в список возможных моделей тестирования лишь соображениями полноты рассмотрения, в то время как модель успешно М0цх использована в [4] для развития самодиагностирования на основе сравнения исходов тестовых задач, выполняемых разными модулями системы.
3 В [7] приведены также примеры практического использования тестов, соответствующих разным моделям ненадежного тестирования.
Такая возможность открывается благодаря формализации представления модели самодиагностирования в виде двойки < V, А >, где V - диагностический граф, описывающий структуру связей, по которым одни модули могут проверить состояние других модулей, а < А >=< а(д,д)а(д, Ь)а(Ь, д)а(Ь, Ь) > -четверка переменных, описывающая свойства используемых тестов. Четверка < А > перечисляет значения исхода тестирования при всех возможных состояниях тестирующего и тестируемого модулей (соответственно первый и второй символы в круглых скобках); д - исправный модуль, Ь - неисправный модуль. Каждая переменная принимает одно из трех значений: 0, 1 или х, где 0 или 1 означают, что тестирующий модуль оценивает состояние тестируемого как исправное или неисправное соответственно, а символ "х" соответствует непредсказуемому (0 или 1) результату оценки4. Например, модель ненадежного тестирования из [1] описывается четверкой <01хх>. Далее для моделей тестирования используем обозначения Ма(д,д)а(дь)а(ь,д)а(ь,ь).
Зависимость исхода теста от состояния участвующих в нем модулей, представленную четверкой < А >, можно также описать с помощью булевых функций совместности, введенных в [10]. Функции совместности показали свою эффективность при решении разных задач самодиагностики5 [10-19]. В [10, 11] они применяются для синтеза диагностируемых с ремонтом графов различной структуры при использовании модели ненадежного тестирования, описанной в работе [1]. В [12-15] функции совместности используются для решения задачи самодиагностирования без ремонта в случае моделей ненадежных тестов, описанных в [1,3]; при этом в [13] рассматривается модель тестирования из [3] для случая, когда допускаются устойчивые неисправности модулей и связей между ними. В [14, 15] для модели ненадежного тестирования, использованной в [1], описано применение функций совместности при оперативной идентификации неисправностей с помощью децентрализованного алгоритма самодиагностирования в случае устойчивых отказов и сбоев. В [16-19] развивается метод локального самодиагностирования при устойчивых отказах модулей и применении ненадежных тестов, описанных в [1]. В рамках этого метода функции совместности используются при разработке адаптивных децентрализованных алгоритмов самодиагностирования в качестве средства для анализа диагностических свойств типовых подграфов, образуемых в процессе тестирования системы.
Вторая цель данной работы — показать ценность использования функций совместности по новому назначению: для описания моделей ненадежного тестирования и сравнительного анализа их диагностических свойств, а также как средства, которое позволяет свести доказывание свойств "вычислимости" (технического) состояния модуля системы по совокупности исходов тестирования, относящихся к его ограниченной окрестности, к преобразованиям соответствующей булевой функции.
Изучается случай ¿-диагностирования без ремонта (далее ¿-диагностирование), когда по исходам однократного выполнения всех возможных над си-
4 Сказанное означает, что выражение "исход теста" является синонимом выражения "оценка состояния тестируемого модуля, полученная тестирующим модулем".
5 Самодиагностика определяется как отрасль знания, охватывающая теорию, методы и средства самодиагностирования системы.
стемой тестов идентифицируются все неисправные модули, присутствующие в системе, при условии что их число не превышает указанного значения ¿, Ь < N, N — число модулей системы (соответственно граф, в котором достигается ¿-диагностирование, называем ¿-диагностируемым).
В связи с широкой распространенностью ПМЧ-модели и с целью сокращения объема статьи опускаем описание основных понятий самодиагностики. Используемые терминология и нотация введены в [16, 17]. В Приложении дан список используемых обозначений. Для упрощения изложения терминология системы распространена на представляющий ее диагностический граф, что позволяет использовать выражения "состояние графа" вместо "техническое состояние системы", "исправная (неисправная) вершина" вместо "исправный (неисправный) модуль", "исход теста" вместо "вес дуги" и т.п.
2. Классификация и отношение включения для моделей ненадежного тестирования
Перечисление возможных диагностических моделей многопроцессорных систем, различающихся соглашениями о свойствах используемых тестов системного уровня, дано в [6]. Всего выделены 11 моделей, которые делятся на три группы. Первую составляет модель Мхххх, назван
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.