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

^ I) • *,< Ч V"

ЭЛЕКТРОТЕХНИЧЕСКИЙ ИНСТИТУТ СВЯЗИ им проф. М. А. БОНЧ-БРУЕВИЧА

На правах рукописи УДК 621.395.345

РАДОЙЧЕВСКИ Васил Цочев

МЕТОДЫ ТЕХНИЧЕСКОГО

ДИАГНОСТИРОВАНИЯ УЗЛОВ КОММУТАЦИИ С МНОГОПРОЦЕССОРНЫМ УПРАВЛЕНИЕМ

05.12.14—Сети, узлы связи и распределение информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

С.-Петербург 1992

Работа выполнена в Электротехническом институте связи им. проф. М. А. Бонч-Бруевича

Научный руководитель — кандидат технических наук, профессор Р. А. АБАКОВ.

Официальные оппоненты — доктор технических наук, профессор Г. М. ГНЕДОВ, кандидат технических наук В. О. ОЛЬКОНЕ.

Ведущее предприятие указано в решении специализированного совета.

на заседании специализированного совета К 118.01.01 при Электротехническом институте связи им. проф. М. А. Бонч-Бруевича по адресу: 191065, г. Санкт-Петербург, наб. реки Мойки, д. 61.

С диссертацией можно ознакомиться в библиотеке института.

Защита состоится

1992 г.

Автореферат разослан

Ученый секретарь специализированного совета,

кандидат технических н.....

доцент

В., X. ХАРИТОНОВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Основное направление совершенствования коммутационной техники электросвязи в мире, связанное с бурным развитием микроэлектроники п вычислительной техники, заключается в создании качественно ноеого поколения систем коммутации - электронны! коммутационных узлов (ЭКУ) с програкмщш управлением. Вагнейией особенность!) ЭКУ является модульный принцип построения при шроясм использовании процессоров в качестве элегантной базы модулей.

Появление многопроцессорных ЭКУ привело к необходимости исследования и разработки методов обеспечения отказоустойчивости, основанных на использовании таких характерных свойств многопроцессорных ЭКУ, как вычислительная автономиость модулей, возможность их взаимного тестирования, независимость отказов модулей, возможность перераспределения задач, избыточность системных ресурсов ЭКУ. Отказоустойчивость обеспечивается в основном средствами самого ЭКУ и предполагает автоматическую проверку исправности и самодиагностирование, а такге замену отказаишх модулей или их изоляцию для восстановления процесса обслуживания вызовов. '

Важное место при обеспечении надежности и отказоустойчивости ЭКУ занимает система диагностирования. Она состоит из двух уровней - системный и схемный. Диагностирование на системном уровне выполняется в реальном масштабе времени и направлено на определение места неисправности с глубиной до отдельного модуля, как правило, путем взаимного тестирования процессорными модулями друг друга. Диагностирование на схемном уровне предусматривает поиск неисправностей в выведенном из обслузиЕания нагрузки модуле с глубиной до конструктивно-съемных частей.

Oöejm аспектам проблемы диагностирования на систегшсм уровне посвяг^ны работы Пархоменко П.П., Еэдешенкова В.Д., Горелова О.И., Дмитриева Ю.К., Preparata P.P., Barsi F., Kaeson G.II, и др. Однако, по литературным данным отсутствуют какие-либо теоретические работы, отрагащие вопросы диагностирования на системном уровне в многопроцессорных ЭКУ.

Диагностирование на схемном уровне рассматривается в работах Согомопяна Е.С., Сагунова В.И., Щербакова Н.С., Халчева В.Ф., Го-ломатока Л.В., Еалаёва А.Я. и др. Один из перспективных подходов повышения диагностпруеиости устройств состоит в изменении структура (добавление входов, выходов, изменение связей) объектов при их

тестовой диагностировании. В настоящее время отсутствует кэтодшш определения совокупного ыногаства дополнительных входов в выходов кодулей ЭКУ, обеспечивахцзх достпгение трабуеиоЗ глубью диагностирования на схеиккз уроЕнэ.

Цель работы. Цэлыз дассартащтпнтгпТ? работы явлкзтся разработка в исследование иоделей в катодов пттализа в синтеза систем диагностирования июгопроцессорных ЭКУ, а текп) разработка алгоритмов дешифрации результатов диагностирования.

Ыетоды вооледоваввя. Достшаниа поставленной цели основано на прикенении теории техническое диагностики, теории алгоритмов, иатеиатического аппарата теории графов, теории шь хэств, алгебры логика. В ходе вычислительных експэр^энтов использовались елекевты комбинаторики.

Научная н о в и 8 н а работы в целой состоит в том, что впервые проводится теоретическое исследование системного уровня диагностирования в многопроцессорных ЭКУ. Новыми результатами является:

классификация коделей диагностирования слоеных технических систем, обоснованна и разработка моделей, адекватно ошеиващах характерные д£д иногопроцоссорных ЭКУ особенности проверки;

метод анализа параллельной и последовательной дасгностируетс-ти кногопроцессорных ЭКУ с учетш особенностей используекых проверок, в той числа необходимые в достаточные условия обеспечения параллельной и последовательной 1-диагностируекости;

штод синтеза елтшалышх структур тестовых (проверочных) связей, обеспочиващих ваданнув меру параллельной даагностируекооти многопроцессорных ЭКУ;

аналитические соотношения, опрэделяхцие число тестовых связей а оптималькоЗ параллельно ¿-даагЕостируоыой систыиа, состогдцэй из п содулэй;

алгоритмы .централизованной дос2£рац2й сивдро&а прп диагностировании Еа системной уровне;

ш то дика преобразования структуры иодулей ЭКУ с тона: зрения ухзтЕЕзнпя необходааса глубины поиска'неисправностей (ГПН) на схои-югз уровне диагностирована, основанная на совместной использовании (ОПОЛйИТеЛЬЕЫХ входов и выходов.

Практическая ценность результатов диссертационной работы состоит в слэдупцеы:

теоретические еыбоды в практические регультаты, полученные в

работа, когут быть попользованы при разработке, проектировании п эксплуатации мюгопроцессорных ЭКУ различного типа я назначения;

получешке результаты по спсте!.лс:гу урошт диагностирования являются об^гш для ппрокого класса тогопроцэссошых вычислительных и управллицпх систем;

разработанные программные средства на язшсо Turbo Pascal для 1ЯЗ К7 сог^зстнгях кс:шьптвроз позволяют проводить окспэританталь-иые исследования по системному уровнл диагностирования;

разработанная кэтодика определения дополнительных входов д ВЫХОДОВ ПОДУЛЗЗ ЭКУ С ЦЭЛЬЭ П0ЕНИ6ЕИЯ ДИЗГЛОСТИрувТЮСТЛ на СХ6!гесм уровне доведана до практической реализации. Все алгоритсы, соотаз-ляе^иэ петодику, реализованы в вадэ nporpc-'-i малинного проектнрова-ния на языке Turbo Pascal для IB1 PC соезсголп когшызтеров. Прог-pr.-^i шжавднн в информационно!! фонда ГосЕАП.

.Реализация результатов работы. Основные теоретические п практические результата работы псгользоезеы в НИР по разработка кэтодов и средств техшчаскаЗ диагностики ATO, проводимых ксфедроЗ АЭС н Отраслевой лабораторией электронных ATO 3IÍC пм.проф.и.Д.Бонч-Бруэвича.

ЛпчныЗ вклад автора. Оснозлые научныа пологэ-вяя, теоретические выводы и рекомендации, содержащиеся в ддссэрта-ционеоЗ роботе, получены автором ссаэстоятельно.

Апробация результатов работы. Основные результата днссзртЕцпонноЗ работы сбсуюались н была одобрены из ИэздународпоЗ НТК "Проблема функционирования инфоршнроипых Си-геЗ" (г.НЬвоспбпрск, 199Т г.), на ВсассзззоЗ НТК "Цр^опзнгд цп^ро-гых стстоп по^гутЕЦИН па сетях электросвязи" (r.IíyüfeneB, 1991 г.), и VI Всесоюзной пколе-сзЕзнаре по проблзкем унрзнлзния на сетях п ¡гзлзх свяез (г.Звенигород, 1990 г.), нз Республиканской НТК "Автоматизированный контроль п попсзниз ^фиктивности chctcü связи" (г.Таппонт, 1С85 г.), на XXV научкоЗ сессии "Дзеь рэдио'90" (г.Со-1930 г.), па Сэдъ::сЗ научЕО-практзчзсксЗ копфэрощпн болгарс-сих студзитоз п аспирантов (г.Лзнпнград, 1GG9 г.), а текге на НТК грсфэссорско-прэподаззтэльского состпнз S!ГО н!1.ярс5Л1.А.Бояч-Бруе-ппа в 1939-1992 г.г.

Публикации. Оспопппэ результаты диссертационной рабо-и опубликованы в 12 сэчзтшсс работах.

Структура работы. Диссертационная работа состоит л пгэдзнпя, чэтирзх разделов, ¿Ьклпчзния, списка литературы и ча-

тнрэх ПрИЛОЕВНИЁ.

К защите представлены тезисы:

1. Успешное внедрение электронных кошутационных узлов навоз-кохво без решения проблемы автоматического диагностирования (са'ло-даагностирования) в процессе эксплуатации.

2. Многопроцессорные ЭКУ строятся по модульноглу принципу. Модули обладают достаточными вычислительными и логичаскпми еозиоенос-тями для того, чтобы определять техническое состояние друг друга. Анализ процессов диагностирования ЭКУ позволяет утверждать, что система диагностирования ЭКУ моха г быть представлена в виде двухуровневой структуры. Выделяется диагностирование на уроЕшз ЭКУ в цалом (системный уровень) и диагностирование на уровне модулей (схемный уровень).

3. Применение разработанных методов анализа диагностируе&ости многопроцессорных ЭКУ на системном уровне позволяет для каддой из исследуемых моделей и для любой структуры меиюдулышх тестовых связей определить достигаемую меру даагностируемости при параллельном и последовательном диагностировании.

4. Црименаше разработанного метода синтеза оптимальных структур тестовых связей при диагностировании на системное уровне позволяет обеспечить заданную меру параллельной даагностируоцости при минимальном числе тестовых связей мзаду модулями.

5. Црименение разработанной методики обеспечения диагностируе-кости на схемной уровне, основанной на графовой модели, позволяет выявить связи в объектах диагностирования, наличие которых препятствует достижению требуемой ГПН, а такка найти минимальное число дополнительных входов и выходов, использование которых в процессе тестового диагностирования обеспечивает требуемые значения ГПН.

6. Разработанные лрогразггныэ средства для 1Ш РО соваэстшнх компьютеров позволят проводить экспериментальные исследования и обеспечивают проверку достоверности полученных теоретических результатов.

ООДЕРЕАНИЕ РАБОШ

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

мводены сведения об апробации работы и кратко изложено ее содер-знке.

В первом разделе диссертации, основываясь на ^сведенном с точки зрения организации диагностирования, восстанов-¡нии работоспособности и ремонта, анализе принципов построения СУ, определяется их особенности как объектов диагностирования, тиязсщие на выбор методов, средств и организацию поиска неисправ-зстей. Строятся ЗКУ по модульному принципу. Для систем управления СУ характерна децентрализованная или иерархическая структура на ¡ноне большого количества процессоров. Применяемые в ЭКУ способы зганизации связи мэзду модулями представляют собой рэгулярныа, грого унифщированные интерфейсы, поэтому введение дополнительного ¡агностического интзрфейса обычно на требуется. Для обеспечения гказоустсйчиЕости ЭКУ используются разнообразные способы резерви-;вания оборудования. Функции обслугивпнпя' вызовов и функции технн->ской эксплуатации могут выполнятся одним и тем не или разншш хэцессорными моду л гаси Процессы диагностирования тесным образом тзвны с процессами реконфигурации ресурсов ЭКУ и ремонта при еоз-кновэшш и устранении неисправностей.

По литературным датам анализируется состояние вопроса даааг-ютирования оборудования ЭКУ. Определяются задачи и объект иссле-шания. Под системой технического диагностирования понимается со-«упность аппаратурных и программных средств диагностирования, ¡ъектов диагностирования и, при необходимости, исполнителей; Суще-•венным при исследовании системы диагностирования ЭКУ является вы-|Д о том, что она включает в себя два уровня диагностирования -'.стешшй и схемный.

Проводится клзсофпсацкя моделей системного уровня диагности-¡втакя по слэдугтам пргзлзкям: 1) организация ддст*рзцпи ртзу:гьтгз-з диагностирования (синдрома); 2) способ диагностирования; 3) тип ;енки состояния проверяемого модуля неисправным проверяющим моду-м; 4) характер (модель) рассматриваемых неисправностей; 5) элэ-нты системы, подверженные неисправностям; б) особенности выполне-я тестов. Показано, что модели с централизованной дэЕЕфрзциой ндрома адекватно описывают диагностирование на системном ура изо в огопроцессорных ЭКУ.

На системном уровне диагностирования следует: 1) определить обходимые и достаточные условия для того, чтобы система обладала данной диагностирувмостью (задача анализа); 2) найти структуры

проверочных связей, оЗеспечивапую заданную диагностируемость (задача синтеза); 3) разработать алгоритмы дешифрации синдрома.

Во второй разделе решается задача анализа диаг-ностируемости модульных ЭКУ на системном уровне. Диагностической моделью ЭКУ является связный ориентированный взвешенный граф С=(*»Г), в котором мнохество вершн *={т0,т,,...,тп_,> соответствует модулям ЭКУ, а множество дуг £„/«0,п-1} - тестам над ними. Для дуга ttj из т1 в т^ существует, если и только если модуль п< может проверить модуль п^. Предполагавтся, что * для любого т{еМ, т.е. модули на самотестируемы. Для каждого т^М и 1ГтсХ определяются следующие множества:

Т~1 {т^-^ОНг^^Т}; ■ г'о^ЬО^еШ^еТ};

В(Я1)- и Г"'(т.); Д<*,)- и г'(ш );

Г"' (*, )-В(*, )\Ж1; V1 (*, )-Л(*, )\*,;

К0(Ж, )-(т1€М11Г Л ¿Т.т^ША, К Выполнение теста t(J сопровождается оценкой проверяющим модулем т{ соотояния проверяемого модуля и^. Эта вценка отображается в вео г^ дуги графа С, причем:

если проверяющий модуль т4 считает, что проверяемый модуль исправен; в противном случае. Упорядоченное множество значений двоичных оценок 1,/=0,п-1), определенное на всех элементах Г, составляет синдром технического соотояния диагностируемого ЭКУ. Состояние определяется перечней неисправных модулей, присутствующих в нем. Выявление всех неисправных модулей (при параллельном диагностировании) или хотя бы некоторых из них (при последовательном диагностировании) осуществляется дешифрацией полученного синдрома.

Диагностические модели обозначаются четверкой переменных гвиГ:ипгнагнн" ПеРвый ш индексов указывает на состояние проворящего модуля, а второй - на состояние проверяемого модуля (И - исправное, Н - неисправное). Каждая переменная принимает одно из трех значений {0,1 ,х). При втом О означает, что проверяющий модуль оценивает состояние проверяемого ш модуля как исправное, 1 - как неисправное, х (0\/1) - как исправное или как неисправное. Таким об-разоа, конкретные значения переменных для кзздой модели отражают свойственные ей правила взвешивания дуг. Так например, модель 0100 соотвэтствует проверке доступа к модулям, модель 0111 - сравнению

'и "

(О, е

результатов операции, выполняемой парой однотипных модулей, а модель 0110 - проверке целостности распределенной базы данных и т.д.

Для рассматриваемых моделей приняты следующие допущения: 1) попускаются только устойчивые неисправности; 2) неисправностям под-зэрззны только модули ЭКУ; 3) используемые тесты являются полными (т.е. всегда г^-0 и rm=1); 4) дешифрация синдрома осущесталвптся централизованным средством.

Модульный ЭКУ, описываемый при помощи указанных диагностичес-шх моделей, называется системой S. Мерой даагностирувности являет-:я максимальное число i одновременно неисправных модулей, наличие гаторых не препятствует достижению правильного диагноза.

Определение 2.1. Система S называется параллельно ^диагностируемой, если тестовые связи назначены так, что в результате однократного выполнения тестов и дешифрации синдрома всегда возмошо определить все неисправные модули, при условии, что их число но 1ревышает t.

Модель 0101. Теорема 2.1. Система S является параллельно ^диагностируемой, если |Г-,(п{)|>1 для кавдого mttt а параллельно J-диагностирувмой, если |Г-,(п{)|-0 хотя бы для одного n{cif.

Модель 0100. Теорема 2.2. Система S является параллельно :-диагностируемой, если и только если для любого cff, |*,|<t вы-галняютс'я условия:

1)

2) из кавдой вэрзпны nt€if(\C{Ji;) существует путь к хотя бы од-гой вершине мно&ества C(i/f), проходящий только через вортины ыно-яства ffj.

Нодель 010т. Теорема 2.3. Оястема S является параллельно -диагностируемой, если и только если IP-' (nt) I >t для кеддого я^Ы.

Модзлъ 0111. Тоорзг'з 2.4. Система S является псраллвльЕо -диагностгруексй, если п только если:

1) ir~'(nit)Ur'(n{)|>t для каздого пtea;

2) |Г~'(if7)Ur'(2ff)l>t для каздого IJf,l-2;

3) существует на больгэ одного fi?cli, lif,l-t, \п/2.\<i<srx-2, та-:ого, что множество дуг инцидентных всем вершяам кгхшэства Д(, ОЕпадает с множеством Г (через |_а| обозначено наибольшее целое эньпее а).

Модель 0110. Теорема 2.5. Система S, опасывазмая связным грз-ом G, Есегда обладает марой параллельной дивгностируекости t, рав-ой |.(п-1 )/2J.

Модель 011х. Теорема 2.6. Система 5 является параллельно Г-диагностируемой, если и только если:

1) |г"'(я4)иг'(т4)|>{ для любого т^Я;

2) для каздой пары т^М, т^М, |Г"'(Я1()иг'(ш4)| =

и п^еГ~'(т{)иг'(т4) существует хотя бы одна варшина в^сГ-'Оп^иг'^) такая, что т^<г~,(т4)иг,(т|).

Модель 01 дО. Теорема 2.7. Система 5 является параллельно {-диагностируемой, если и только если:

1) для каждого имеет место неравенство

2) для каждой пары таких, что |*;1, \И2\& и существует хотя бы один тест из в (К;\Н2)и(М2\*?) или хои бы один тест из (*7\*2)и(*2\1Г,) в

Определила 2.2. Система Б называется последовательно {-диагностируемой, если тестовые связи назначены так, что в результате однократного выполнения тестов и дешифрации синдрома всегда возмо: но определить хотя бы один из неисправных модулей при условии, чт< их число не превышает t.

Модель 0101. Теорема 2.8. Система 5 является последовательно п-диагностируемой, если Г"'(п4)><0 для каждого т1е* и последовател ко О-диагноотируеыой, если Г~'(т4)»0 хотя бы для одного п{€*.

Модели 0100 и 010г. Теорема 2.9. Система Б явмется последоз тельно {-диагностируемой, если и только если Г*"' (Я,)»^ для каждог

Иодаль 0111. Теорема 2.10. Система 3 является последовательн (-диагностируемой, если и только если I- шах [/ (т )1-1,

где I; 2° - любое максимальное независимое подано

вество вершин в подграфе <3° с вершинами *\(г"'(т{)иг'(и{)).

Модели 0110 и О) и. Теорема 2.11. Система г, описываемая свя ннм диагностическим графом, всегда обладает мерой последовательно диагностируемости t, равной |_(п-1)/2.|.

Модель 01x0. Теорема 2.12. Пусть связный граф С системы Б не

является сильно связным, и ,С2.....Сь - сильно связные кошонве

графа в, такие, что Гдля каздого 1<{<&, где - мнокес во версшн компоненты и пусть t i - мэра последовательной диагнс тируомооти подоиотека соответствующей компоноыте С{ Тогда мора последовательной дпагнооткруекости систолы 5 будет

1=я(П(1т,12.....

Теорема 2.13. Система Б, нмэпцая сильно связный диагностический граф, всегда обладает мерой последовательной диагностируеаости 1, равной 1.(п-1 )/2\.

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

Задача синтеза структуры тестовых связей формулируется следутн цкн образом. Построить параллельно 1-дааггостируомуп систему 5, состоящую из п модулей и имеющую минимально возжстоо число 154 тестовых связей мезду модулями.

Определение 3.1. Параллельно ^-диагностируемая система 5, состоящая из п модулей а 171 тестовых связей, является оптимальной, если любая другая система, состоящая из п модулей и меньшего, чем |!Г| числа тестовых связей, является не более чем (1-1)-диагностируемой.

Модель 0101. Теорема 3.1. Система Б, обладащая кэрой параллельной диагностируеаости п, является оптимальной, если |Г~'(п{)(-1 для каздого п{е4.

Теорема 3.2. Длл произвольного п, диагностический граф С-(2,Т) оптимальной параллельно п-даагностируомой систем Э строится следующим образом: из каздой верзпны п{, 0^1<л-1, исходит дуга к вэрзнпа ПН+» I (чорэз |а|л обозначен неииэньаий полсютэлышй остаток делания а на п).

Модель 0100. Теорема 3.3. Для произвольных ае 1, 1*1«ъ-1, диагностический граф С=(Й,Г) онтгаальной параллельно ^диагностируемой систем! Б строится следующем образом:

1. Если 1=1, причем 1<п-1, то из калдой Еерстш п{, 0£1<п-2, исходит дуга к верхние (, а из ззргиш п( - к вэргшэ п0;

2. Если 1-2, прзчем 1<п-2, то из каздой вэрезга п{, СК1КП-2, исходит дуга к вэрзпнз (, из каздой Еэргиш 1<{«п-3, пегодлт дуга к езрипиа п( 1, а из взрпины пп_{ исходит дуга к взпппте я^ г,

3. Если 1-2, причем 1-п-2, либо если 2<1<п-1, то квгдвя ворзя-на п,, л 1+1 связана двумя противоположно пгпразлея-теп'дугеп с вершиной п(+>, из вер^гнн исходит дуга к вэреию

аз вершины яп_; исходзт дуга к горзнпэ

4-. Если 1»п-1, то кездоя еоригаа п{, 0<(с1-2, сеяздгз дзукл протиЕоголсзта направлэшлпи дугезлз с нзрзппоа п. + ).

Теорема 3.4. Для диагностического графа С=(*.Т) оптимальной параллельно (-диагностируемой системы г, состоящей из п модулей, выполняется условие:

Е, если 1-1, причем (<п-1; п-3, если 1=2, причем t<n-2; п-2 - во всех остальных случаях. Модель 010г. Теорема 3.5. Система 5, обладапцая мерой параллельной диагностируемое™ t, является оптимальной, если |Г~'(т{)|=? для каждого

Теорема 3.6. Для произвольных пи t, К191-1, диагностический граф С"(*,Г) оптимальной параллельно 1-диагностируемой системы 5 строится следующим образам: дз каждой вершины п{, 0$1<п-1, исходят дуги к вершинам Я1| 1+;| «И|С+2| -

II Л Л

Модель 0111 ■ Теорема 3.7. Для произвольных п л t, 1 , диагностический граф С-(1?,Г) оптимальной параллельно -диагностируемой системы г строится следующим образом:

1. Если , то из каждой вершины ш(, 0<(е1-2, исходит дуга к варшне

2. Если 1<(<п-2 и ( четное, то из каадой вершины и{, 0<1ф1-1, исходят дуги к вершинам И| 1 >т| {+2| *

п п п

3. Если 1 <{<п-2 и t нечетное, то каждая вершина и{, (Х£<П-1,

соединяется исходящими дугами с вершинами Ш|{+>| ,Щ| ,...,

Т* п

П1«+Г1/2"Ч (чвР03 Га1 обозначено наименьшее целое большее а). ЗаП

тем, если л кратное 4 и 1=п-3, удаляются дуги, исходящие из вершин Ид.г^....»»»^^ соответственно к вершинам й(,т3,...,ип/г ), а такса дуги, исходящие из вершин пп/2<пп/г+7» — 'шзп/4-1 соответственно к ЕвркЕзеа ■ • ■ • >пп-7" Д-ти ЕСЭХ остольниг значений п к

I удаляются дуги, исходящие из Еерсин ш0,пг,...,шг п/г соответственно к вершинам т1 ,а3,... ,пг п/2 _г.

4. Если 1-л-2 и t четное, то каждая вершина п{1 , соединяется исходяцизаи дугами с вершинами И|»•••»

Л

■ то'а1'"'*тЬ/2-1 соединяются исходящими дугами

п

соответственно с вершинами т^/2гт±/г+1'"',тп

5. Если г-п-2 и t нечетное, то каждая вершина и{, 0£1фг-1, оооданяется исходящими дугами с вершинами Я| {+>| ,...,

п

Я|1+г4/2т| ■ Затем произвольно удаляется одна дуга.

П

Теорема 3.8. Для диагностического графа С»(И,Г) оптимальной

араллельно ^диагностируемой системы Б, состоящей из п модулей,

ыполняется условие:

гп-1, если {=1;

'П

Г*/2"|-Ьт 1п/г\+Ъг^/2\ , если г>1;

дэ

-С:

Í1, если { нечетное; Г1, если причем Г>1;

ecли<t четное; (О - во всех остальных случаях.

Модель 0110. Георема 3.9. Для произвольного п диагностический рвф 0={Л,Т) оптимальной параллельно {-диагностируемой системы Э, да г=-1_(тг—1 )/2.\, строится следущим образам: из вершины и0 исходят огги к вержнзм ш1,п2,т3,...,шп_1.

Теорема 3.10. Для диагностического графа С-(Н,Г) систеш Я, ¡остоящей из п модулей и являющейся оптимальной параллельно ^диагностируемой, где {-|_(п-1)/2_|, выполняется условие 1Т1-П-1. Модель 011 х. Теорема 3.11. Для произвольных п и t,

)/2], диагностический граф (¡={М,Т) оптимальной параллель-га {-диагностируемой системы Э строится следующим образом:

1. Если {=1, то из кадцой верпины п{, 0$ 1^1-2, исходит дуга к ¡ерщше

2. Если и { четное, то из каждой верпшы , юходят дуги к вершинам И| 4+Т| ,П|1+2| t•••^mll^.t/г^ »

п п тг

3. Если (>1 и ( нечетное, то каздая вершина п{, 0<1<п-1, зоединяется исходящими дугами с вврзинами •т\1+2\ ••••»

Т\ л,

5|*+гЧ/21 I ' затем УДалягтся дуги, исходное из ветчин п0,п2,...»

п

1. _ соответственно к вершинам п,,п_,...,п„ ,_

2 2^ —2 13 2 - 7

Теорема 3.12. Для диагностического графа С=г(Н,Г) оптимальной

гараллельно {-диагностируемой систеш Б, состояний из п модулей,

зыполняатся условие:

т-1, если {=1; 1Г1Н

[п^/г^-Ъ^п/г], если {>1.

Модель 01 дО. Утверадеииэ. Для диагностичоского графа

зптгмальнай параллельно {-диагностируемой систеш э, состояла из п

модулей, выполняется услоеео: гп, если {=1; |Г1=|

12п-2, если 2<{<1_(л-1 )/2]. Теорема 3.13. Для произвольного п диагностический гр&5 С=(2Г,2") оптимальной параллельно 1 -диагностируемся систэмы Б стролтся слэду-птн образом: из каядой варлины л{, 0^(^-1, исходят дуга к версшнз

Ш| ( + f I . Диагностический se граф оптимальной параллельно

TV

( LOt.—1 )/2J)-диагностируемой системы S строится следующим образом: каждая вершина , 0<i#i-2, связана двумя противоположно направленными дугами с вершной ml+J.

Для моделей 0100, 01 Ох, 0111 и 0110 разработаны алгоритмы централизованной дешифрации синдрома, вычислительная'сложность которых составляет 0(п2).

Четвертый раздел диссертационной работы шсея-щен схемному уровню диагностирования модулей ЭКУ. При этом решается задача формирования структуры модулей, пригодной к автоматическому поиску неисправностей с необходимой глубиной.

Для решения поставленной задачи разработана методика оценки и преобразования структуры модулей ЭКУ с точки зрения поиска неисправностей с любой заданной глубиной.'Структура рассматриваемого в качестве объекта диагностирования модуля задается ориентированным графом G=(V,t7), в котором вершины графа соответствуют функциональным узлам модуля, а дуги - связям наяду ними. Входными ((-ТТШГ) и выходными t-lnij} (J-TTTFT) называются такие вершины графа G, которые соответствуют узлам, связанным со средством диагностирования по приему и выдаче информации в ходе выполнения тестовых проверок. Показано, что каждый элемент z^ множества Z тестовых проверок описывается парой вершин (п(,л^), причем nij достижима из п(. Физически это означает, что входной набор теста, поданный на узел, которому сопоставлена Еерошна п(, вызывает ответ на выходе модуля в узле, описываемом вершиной rtj.

Необходимая ГПН задается разбиением множества V на подмножества Рг (Z-T7q) вершин, неисправности которых не требуют различения между собой, причем

U Г «V, (РПР-Ü,

1.1 ' ^ и указанием требуемых зезчзний ГПН Х(?г) (1=ГГд). Значение 1(?г)

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

Выделано два этапа решения задачи. На первом из них по графу G без учета множества Z анализируется возможность достижения заданных значений Ъ{Рг) при известных (t=T7q) и определяются необходимые услоняя, выполнение которых связено с преобразованием структуры модуля и направлено на достижение заданной ИШ. Показано, что, выявив в графе G каждую сильную компоненту (CK) и сопоставив входящее в

(9 нодкноаэство верпш В% о подмйогэствами Р1 (1-1 , учитывая п этом заданные ЦРг), могно оценить достигаемую ПШ. Предложен ггоригм анализа поджогеств Вт, идея которого состоит в разделении [ на две группы. Те СК, которые препятствуют достижении заданной И, подвергается дальнейшему анализу. Этот анализ сводится к наценка дуг и*2 в графе, разрыв которых устраняет контуры, препят-:вушрв достегэеев заданных значений ). Выделение контуров (а шке СК, в которые она входят) осуществляется по списочному описа-зз графз. После зтого формируется матрица контуров, для поиска жрытия которой системой столбцов (дуг) в работе предлоген итера-кзнный алгоритм, оптикизирущий число разрываемых дуг с учетом 1трзт на разрыв ссютветствукдах та связей в схенэ га дуля.

На втором етапе по полученному после первого этапа остовнску эафу Ср-(7,СГр), ир~Я\Цл, с учетом кногества Я-Ся (п{,п^)} НТГгГ) оценивается получаемая ПЗН н находятся дополнительные >стовыа проверки Z, необходимые для обеспечения заданных значений (Рг). После перехода от графа к его конденсации О* (предлокен сорита перехода от Рг к Рр п упорядочивания вершл графа С* формуется, если ето нугно, кнояество дополнительных входов и выходов которые вместе о основныня входама и находвш обеспэ-пзают так называемое условие тестируемости. В соответствен о этим зловием неисправность каядсй верпнпы и4еУ долзна проявляться хотя I на одной тестовой проверке г^еЯи^,.

Затем строится матраца тестовых проверок элементы ко-

зрой определяются следзтегм образом:

'1, если неисправность вердикт! «г проявляется

на тестовой проварке [о в противном случае, зисправностп вершин графа неразличимы па иногзствэ тестошх прозз-зк тогда и только тогда, когда совпадай? сооткэтстпугг^з зтах першам столбцы матрицы !7. Моано по последней получить рЕЗбконпе пэр-ш графа С* на непересекающиеся ноджгажэства (у»1 ,в), где £ -зело классов версии, нэкспранноста которых неразличимы. Анализ 7* у=Т75) с учетом Р^ и Ь(Р^) позволяет оценить достигаемую па гг;ээ-эмсп кногества проверок ПШ, а такте найти такое кноаэство 9 пар зрзЕН, что пара (и*,и*)€0 в том случае, когда дслгнэ бить оОэсно-эна различимость неисправностей сараин и* и и* с цельв доотагания аданяах Б(Рр. _ „ „

Если теперь икгаство выбрать так, чтобы всо двух-

элементные мноаества воряпн, входящие в иноеэство в, могли быть разбиты на одноэлементные при поиска неисправностей с помоцы) мно-^эстпа проверок ZUZfUZ2, то будот сбаспечэно достесэниэ требуемой ПШ. Для каздой пары (и*,и*)еВ находится поданогэство H (F) варплтн, любая из которых, будучи включенной в множество входных (выходных) Еэрйг.тн 1<г (Uz), разбивает, эту пару пополем.

Ка о слово множеств H и F строится булавая матрица С. Строки из трэды соответствуют парам вэрпин грЕфз, Еэпсправяостп которых долгны различаться для достееэния требуемой ИИ. Столбцы матрицы соответствуют вериипсы графа, которые будучи использованы как дополнительные входные и/нли выходные обеспечивают различение неисправностей хотя бы одной пары верзил. Прл этогл, если нэкоторая Еар-пшна moist использоватся п как входная и как выходная, то в матрице ей соотватствувт два различных столбца.

Нахождение множества (Ш)2 дополнительных входов и выходов сводится к поиску столбцов, покрывающих все строки матрицы С. При атом, в зависимости от конкретной постановки задачи, а такге ее размерности рассматриваются два случая: 1 ) находцение оптшЕзнро-ванного покрытия; 2) Еыявленне строго оптимального (минимального п; мощнооти) покрытия.

Объединив множества (1Ш) ( и (Ki)2 получим псксьюа многаство Ш дополнительных входов и выходов. После втого минимизируется число тестовых проверок на полученном шоеэстеэ входов и выходов.

CoBîiacTHoe использованию дополнительных входов и выходов позволяет , по сравнэшш с кзвэотныыи мэтодшека, снять требование на Ешолнэнго условия тестируемости на исходами шохастве входов и ен-ходов и тем самым обеспечить лгбую ваданнув ИШ.

Программная реализация предлагаемой методики осуществлена на языке Turbo Pascal для IEU FC сокоэстиxhz ко^тютеров.

В заключении сфордулпроваяы основные теоретические п практические результаты диссертационной работы:

1. На основе проведанного анализа принципов построения современных ЭКУ выявлены их особенности как объектов диагностирования. Определена структура системы диагностирования многопроцессорных ЭКУ, включаядая в себя два тазвня диагностирования - снстег^шй и схемный.

2. Прэдлохана классификация удалой диагностирования на системном уровне в многопроцессорных системах. Оцрэделана совокупност; моделей, адекватно сппсываидих диагностирование на системном урова

i многопроцессорных ЭКУ. ВыСр^ш модели, учитывавшие особенности фовэрок, используемых при диагностировании неисправностей в ?го дута 31СУ.

3. Обоснована целесообразность учета характерных особенностей гсгользуогах провэрок при диагностировании неисправностей на сис-'вмнсм уровне в шогопроцессорпых ЭКУ и централизованной дешифрации ютдрома. Показано, что этот учет, по сравнению с классической ио-;зльз, в ряде сдучеев: а) увеличивает верхнст границу мэры диагнос-■ируемости; б) упрощает условия обеспечения заданной меры диагнос-ируемости; в) унэньиает число тестовых связей в оптимальной сясте-:э, обладащэй заданной мерой параллельЕОй-диагностируемости; г) риводит к уменьпенив вычислительной сложности алгоритмов цэнтрали-ованной дешифрации синдрома.

4. Брадлогэн метод анализа диагностических свойств различных труктур теотового графа для группы моделей централизованного диаг-остирования многопроцессорных ЭКУ на системном уровне.

5. Предлогэш алгоритма централизованной декларации синдрома рп параллольпсм и последовательном диагностировании на системном ровне многопроцессорных ЭКУ для различных моделей диагностирована. Вычислительная сложность предложенных алгоритмов меньпа по равнении с известными аналогичными алгоритмами.

6. Для всех исследуемцх модолэй диагностирования непсправнос-зй ЭКУ получено описание структур оптимальных систем, обэспачивап-их задвинув меру параллельной диагностирувмости.

7. Получены соотношения, определящие число тестовых связей в птимальной системе, обладагвдй заданной мерой параллельной дааг-эстируемости и описываемой лззбой из исследуемых моделей диагностп-ггсх-лгя m сг:стогасм уровня.

8. Разработана методика анализа и преобразования структуры г:о-/лай ЭКУ, позволялся оценить их тестопригодпость при диагностиро-внии пеисправностэй на схемном уровнз, а такгэ еейти игмзнэнил и зполнэнзя, которое целесообразно внести з них, чтобы обеспечить эобходпмув ПИ.

9. Разработаны црогра'гшыэ средства на языка Turbo Pascal для 3-7 PC соемэстп:;ых компьютеров, позволяемо проводить экспэримэ?-злыше исследования по системному уроЕпа диагностирования, a teict рограмма автоматизированного проектирования структуры модулей, 5оспэчнвап5ая достигэние заданной ГПН при диагностировании на семном уровне.

ПУБЛИКАЦИИ

1. Радойчовскл В.Ц., Шалаев А.Я. Машинная реализация диагностического анализа структуры управляющих устройств влектронных коммутационных узлов//Респ. НПС "Автоматизированный контроль и повыше ние эффективности систем связи": Тез. докл. - Ташкент, 1985. - 4.1 - С.38.

2. Шзлаев А.Я., Радойчевски В.Ц. Диагностический анализ и цра образование структуры управляющих устройств в электронных систек:аз коммутации//Инф. бил. "Алгоритмы и программы". - 1987, JJT. - С. 1011. (ГООФАП. - Per. номер 50870000131.)

3. Шалаев А.Я., Радойчевски В.Ц. Анализ на структурата на сис темата за диагностика в комутационните възли с многопроцесорно уп-равлвние//Седма науч.-практич. kohJ. на българските аспиранта и студента: Резюм. на докл. - Л., 1989. - С.24-25.

4. Радойчевски В.Ц., Шалаев А.Я. Обеспечение контролепригодности блоков электронного оборудования//Инф. бил. "Алгоритмы и программы". - 1990, #11. - 0.10-11. (ГООФАП. - Per. номер 50900000619.)

5. Аваков P.A., Радойчевски В.Ц., Шалаев А.Я. Диагностирован! цифровых систем коммутации//ВСес. НТК "Применение цифровых систем коммутации на сетях электросвязи": Тездокл. - Куйбышев, 1991. -0.6.

6. Радойчевски В.Ц. Последовательное диагностирование многопроцессорной системы управления цифровой системы ко1эаутации//Всес НТК "Применение цифровых систем коммутации на сетях электросвязи" Тез. докл. - Куйбышев, 1991. - 0.7.

7. Андриаыиаси В.З., Радойчевски В.Ц., Шалаев А.Я. Обеспечен заданной контролепригодности блоков оборудования электроиных комм; тацяонных узлов//Ыездунар. НТК "Цробламы функционирования информационных сетей": Матер, конф. - Новосибирск, 1991. - 4.2. - С.10-1'

3. Радойчевски В.Ц., Шалаев А.Я. Определяло на тестовите съе динэния при диагностиране на системно ниво в комутационните възли модулна структура//Сб. от науч. тр./НШ'С "Х.Трайков". - София, 1991 . - С. 73-81 .

9. Радойчевски В.Ц. Исследование одной модели диагностирован многопроцессорных узлов коммутвцииУ/Тр. VI всесоюзной школы-семин ра по проблемам управления на сетях и узлах связи. - М.: Наука, 1991. - С.72-77.