Автоматика и телемеханика, № 9, 2014
Безопасность, живучесть, надежность,
техническая диагностика
© 2014 г. В.А. ВЕДЕШЕНКОВ, д-р техн. наук (vva@ipu.ru) (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
О ПУТЕВОМ МЕТОДЕ СИСТЕМНОГО ДИАГНОСТИРОВАНИЯ ЦИФРОВЫХ СИСТЕМ СО СТРУКТУРОЙ СИММЕТРИЧНОГО ДВУДОЛЬНОГО ГРАФА
Представлен подход к организации путевого метода диагностирования цифровых систем (ЦС) со структурой симметричного двудольного графа. Для описания результатов тестирования модулей использована модель Препарата-Метце-Чжена (ПМЧ). Предполагается, что в системе есть диагностический монитор, который инициирует процессы диагностирования. Для оценивания величины диагностируемости анализируемых ЦС применен метод потенциальных синдромов. Показано, что анализируемые ЦС являются не больше чем 1-диагностируемыми ЦС без ремонта. Для системы, включающей семь процессоров и семь блоков памяти, рассмотрен пример с недостоверным диагностированием трех неисправных компонентов.
1. Введение
Симметричным двудольным графом называется граф, состоящий из двух подмножеств вершин X и У равной мощности п и имеющий ребра, одна из концевых вершин которых принадлежит подмножеству X (У), а другая - подмножеству У(X) [1]. В числе возможных областей применения графов указанного семейства называют структуры многомашинных вычислительных систем (МВС), где, например, подмножество вершин X представляет совокупность процессорных элементов или вычислительных машин, а подмножество вершин У - блоки или банки памяти. Пример такого графа для п = 7 показан на рисунке, где вершины подмножества X (процессоры 1-7) обозначены кружками, подмножества У (блоки памяти 8-14) - прямоугольниками, на рисунке показан также ДМ - диагностический монитор. Задача диагностирования компонентов ЦС со структурой симметричного двудольного графа рассматривалась в [2, 3], где для описания результатов проверки компонентов использована модель БГМ [4].
В [5] представлен путевой метод самодиагностирования технического состояния компонентов (модулей и линий связи) цифровых систем (ЦС) с цир-кулянтной структурой, особенностью которого является использование 0-пу-тей (в терминологии из [6]) для выбора проверяющих модулей и передачи результатов выполненных проверок, в [5] для описания результатов проверки компонентов использована модель ПМЧ [7].
Цифровая система £7,3 со структурой симметричного двудольного графа.
В работе представлен подход к организации путевого метода диагностирования ЦС со структурой симметричного двудольного графа.
2. Постановка задачи
Исходная МВС со структурой симметричного двудольного графа Qn,s представлена диагностическим графом, у которого п вершин подмножества X представляют процессоры системы, п вершин подмножества У - блоки памяти, каждая вершина подмножества X(У) связана дугами с в вершинами подмножества У(X). (Для графа на рисунке в = 3.)
Будем считать, что допускаются устойчивые отказы ограниченного числа вершин и дуг, причем их неисправности таковы, что прекращают работу модулей, в которых они возникают, и не влияют на работоспособность смежных модулей.
Для описания результатов тестирования компонентов используется модель ПМЧ. Запуском процессов диагностирования в различных подсистемах ЦС и обработкой полученных результатов занимается исправный диагностический монитор (ДМ), который находится в модуле, внешнем по отношению к диагностируемой ЦС.
Требуется разработать подход к организации путевого метода диагностирования ЦС со структурой симметричного двудольного графа, обеспечивающего ДМ достоверной информацией для дешифрации полученных результатов диагностирования состояния компонентов (процессоров, блоков памяти, линий связи) системы.
3. Оценка величины диагностируемости ЦС со структурой симметричного двудольного графа
Максимальное число одновременно неисправных и произвольно расположенных компонентов, однозначно диагностируемых по результатам однократного тестирования системы, называется степенью £ диагностируемости
№№ п/п Состояние Ш-1 Состояние тк Результат ги
1 исправно исправно 0
2 исправно неисправно 1
3 неисправно исправно х (0 или 1)
4 неисправно неисправно х (0 или 1)
системы. Аналитические оценки степени диагностируемости ЦС, построенных с использованием двух (и более) типов компонентов, неизвестны.
Для получения искомой величины Ь анализируемой ЦС воспользуемся методом потенциальных синдромов [8]. Напомним, что если модуль проверяет модуль Шк тестом ри, то результат проверки обозначается двоичной переменной ги, принимающей согласно модели ПМЧ [3] значения, показанные в табл. 1. Если модуль ш^ при проверке модуля Шк получил результат г,к = 0, то дуга 1]-к, соединяющая эти модули в графе системы, называется 0-путем длины 1.
Последовательность результатов г 1, ги, Г1, записанных в порядке номеров тестов р 1, ри, р1, определяет суммарный результат проверки системы и называется синдромом К. Если эти результаты получены моделированием с использованием табл. 1, то синдром содержит символы 0, 1, х и называется потенциальным синдромом Кх [8]. После проведения диагностирования формируется реальный синдром К, который содержит только двоичные цифры 0 и 1.
Известно следующее
Определение. Система Б из п модулей является однократно диагностируемой относительно Ь отказов, если все отказавшие модули можно идентифицировать (по результатам дешифрации синдрома К) без замещения при условии, что число отказавших модулей не превышает Ь.
В [7] доказано следующее
Утверждение 3.1. Для того, чтобы система Б была Ь-однократно диагностируемой (без замещения отказавших модулей), необходимо и достаточно, чтобы для любой пары отказовых ситуаций N и содержащих не больше Ь модулей, существовала хотя бы одна переменная ги, которая принимает значение 0 в синдроме проверки К(Ж1) и 1 в синдроме проверки К(М2) (или наоборот).
Для оценивания степени диагностируемости Ь* анализируемой ЦС воспользуемся методом доказательства от противного и сформулируем следующее
Утверждение 3.2. Для того, чтобы система Б не была Ь-однократно диагностируемой, необходимо и достаточно найти хотя бы одну пару неразличимых отказовых ситуаций кратности Ь* и Ь* + 1, т.е. таких ситуаций, потенциальные синдромы которых не различаются достоверно ни на одной проверке из выбранной системы проверок.
лгя Ри 1 2 3 4 5 6 7 8 9 10 и 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 X X X 0 0 0 0 1 0 0 1 0
2 3 1 0 0 X X X 0 0 1 0 0 0
3 8 1 0 0 0 0 1 0 0 0 0 1 0
4 1, 3 X X X X X X 0 1 1 0 1 0
5 1, 8, 3 X X X X X X 0 1 1 0 1 0
6 (1-8) 1 0 0 0 0 0 0 0 0 0 1 0
7 (8-3) 1 0 0 0 0 1 0 0 0 0 0 0
8 1, (1-8)=1 X X X 0 0 0 0 1 0 0 1 0
9 (1-8), 8=8 1 0 0 0 0 1 0 0 0 0 1 0
10 8, (8-3)=8 1 0 0 0 0 1 0 0 0 0 1 0
И (8-3), 3=3 1 0 0 X X X 0 0 1 0 0 0
В табл. 2 показаны некоторые потенциальные синдромы для системы, представленной на рисунке. Поясним структуру таблицы. Левый столбец содержит номера N отказовых ситуаций. Следующий столбец показывает состав (номера) неисправных компонентов, входящих в Клетки верхней строки содержат номера ри( 1, 2,..., 12) проверок, выбранных для данного примера.
Строка с номером 0 соответствует исправному состоянию системы (нет отказавших компонентов), а потому все ее клетки содержат 0 (нуль). Строки с номерами 1-3 содержат синдромы КХ(Ы8), соответствующие отказу одного компонента с номером г = 1,3,8. В строках 4, 5 показаны потенциальные синдромы для двух- и трехкратных отказов некоторых из компонентов 1, 8, 3. Наконец, в строках 6-11 показаны потенциальные синдромы для ряда отказов, в состав которых входят отказы линий связи (1-8), (8-3).
На основе утверждений 1 и 2 при анализе различимости потенциальных синдромов, показанных в табл. 2, на выбранной системе проверок можно сделать следующие выводы.
1. Потенциальные синдромы 4-й и 5-й строк не различаются достоверно: в этих строках ни на одной проверке нет пары различающихся цифр: 0-1 или 1 - 0; в результате при диагностировании двукратного отказа компонентов 1, 3 можно получить в числе подозреваемых кратный отказ трех компонентов: 1, 3, 8 (что показано в рассматриваемом ниже примере). Таким образом, анализируемая система не является 2-однократно диагностируемой системой, так как не обеспечивает правильного диагностирования одновременного отказа двух компонентов 1, 3.
Приведенная неразличимость двойных и соответствующих тройных отказов связана со структурой анализируемой системы. Одним из достоинств этой структуры при функционировании по назначению [1] является связь любой пары вершин из подмножества X через одну вершину из подмножества У. Именно эта вершина из подмножества У появляется в составе подозреваемых при отказе двух вершин из подмножества X. Зная это правило, нетрудно най-
ти 21 двойной отказ из пары компонентов 1,..., 7, не различимый ни с каким из 21 тройных отказов, отличающихся от двойных отказов включением соответствующего компонента из 8,..., 14, соединяющего данную пару компонентов из 1,..., 7. В список таких пар неразличимых двойных и тройных отказов входят: 1, 2 и 1, 8, 2; 1,3 и 1, 8, 3; ...; 2, 3 и 2, 8, 3; ...; 5, 6 и 5, 14, 6; 6, 7 и 6, 10, 7 (пропущенные пары нетрудно восстановить, если воспользоваться приведенным выше правилом).
2. В строках 8-11 показаны потенциальные синдромы для некоторых от-казовых ситуаций, содержащих линии связи (1-8), (8-3) и компоненты 1, 8, 3. Сравнение этих синдромов с синдромами для компонентов 1, 8, 3 (строки 1, 3, 2 соответственно) показывает, что значения синдромов строк 8 и 1, 9, 10 и 3, 11 и 2 тождественно совпадают. Эти примеры подтверждают известный факт, что одновременный отказ компонента и прилегающей линии связи не различим с отказом этого компонента. Таким образом, если допускать одновременные отказы компонентов и линий связи, то рассматриваемая система также не является 2-однократно диагностируемой.
Для гарантированного получения правильного диагноза в ЦС со структурой симметричного двудольного графа в системе одновременно должно быть не больше одного отказавшего компонента.
4. Организация путевого метода диагностирования ЦС со стру
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.