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

Министерство образования РБ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ. ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

(ЕГУИР)

«л ч '''»)

. . -УДК 681.326.7 на правах рукописи

Закревский Лев Аркадьевич

СИНТЕЗ К ДИАГНОСТИКА КОНТРОЛЕПРИГОДННХ ШФОПРОШЬШНЫХ УСТРОЙСТВ УПРАВЛЕНИЯ

специальность 05.13.05. "Элементы и устройство вычислительной техники и систем управлении" .

АВТОРЕФЕРАТ

.диссертации на соискание ученой степени кандидата технических наук

научный руководитель доктор технических наук профессор Ярмо пик Р-Н.

Минек 1994

Рабата выполнена на кафедре влектронных вычислительных машин Белорусского государственного университета информатики и радиоэлектроники

Научный руководитель -доктор технических наук.

профессор Ярмолик В.Н.

Официальные оппоненты -доктор технических наук,

ведущий научный сотрудник Садщхов Р.Х.

-кандидат технических наук, докторант Татур М.М.

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

Защита состоится " /У " 'с&р^ю/Я 1994 г. в часов на заседании специализированного Совета К 056.05.01 в Белорусском государственном университете информатики и радиоэлектроники по адресу 220027, г. Минск, ул. П. Бровки,. б.

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

Автореферат разослан " // " января 1994 г.

Учений секретарь социализированного Совета, кандидат технических- наук, доцент

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

Актуальность работы. На современном этапе развития устройств вычислительной техники одной из важнейших проблем является проектирование систем их диагностирования, как внешних (внешнее оборудование) так и внутренних (средства диагностирования находятся в самом устройство).

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

На сегодняшний день предложено большое число методов диагностирования УЛУ. Одним из наиболее перспективных направлений исследований является развитие единого подхода к контролю исправности программного и аппаратного обеспечения. Целесообразно поэтому использовать и разрабатывать методы, позволяющие обнаруживать как структурные так и функциональные неисправности. Обширная библиография по данному вопросу свидетельствует как о его актуальности, так и о наличии значительного числа нерешенных задач.

В диссертационной работе проводится анализ различных существующих методов функционального контроля исправности МПУУ, Делается вывод, что наилучшими характеристиками обладает метод контроля последовательности генерируемых УЛУ команд, развитый в работах Робинсона, Нэмуо, Маккласки, Шена, Балакина. Барзшенкова, Иванова и ряда других ученых. Для контроля этой последовательности перспективным. является использование сигнатурного анализа, основными 'достоинствами которого являются высокая достоверность контроля, максимальное быстродействие и простота аппаратурной'реализации. .

•К настоящему моменту существует целый ряд методов и алгоритмов. синтеза МЛ.УУ. Большинство из них использует представление алгоритма работы устройства в некотором {ормальном виде. Часто длч '•той цели применяют язык граф-схем алгоритмов (ГОД).

-ДЛЯ ЛОЬШМЖИЯ ЭффеКТИтЮСТИ ЛЛГОрИТМЯЧесЬОГО КОНТрОЛЯ исщпв-

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

Целью настоящей работы является разработка методов и алгоритмов контролепригодного синтеза и диагностирования МПУУ .При этом контроль исправности МПУУ. осуществляется на алгоритмическом уровне путем проверки корректности последовательности генерируемых микрокоманд с помощью сигнатурного анализа.

Для достижения указанной цели решаются следующие задачи:

- исследование существующих методов диагностирования и контролепригодного синтеза устройств логического управления;

- разработка методов и алгоритмов контролепригодного синтеза МПУУ, основанных на использовании сигнатурного анализа последовательности кодов генерируемых микрокоманд.для контроля исправности устройства управлешя;

- разработка алгоритмов тестирования контролепригодных МПУУ;

- разработка методов и алгоритмов определения оптимальных значений вероятностей появления единицы на входах МПУУ при использовании вероятностного тестирования для контроля исправности МПУУ.

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

Научная новизна исследований заключается в следующем:

1) предложена новая схема контроля исправности микропрограммных устройств управления, а также проведен сравнительный анализ различных '..вариантов этой схемы;

2) предложена методика синтеза контролепригодных МПУУ;

3) разработан алгоритм оптимального кодирования микрокоманд;

4) разработаны алгоритмы выбора проверяющего сигнатурного поли

нома для контроля исправности МПУУ при использовании различит моделей неисправностей;

5) предложен алгоритм выбора значений вероятностей появления на входах МПУУ единицы при использовании вероятностного тестирования;

6) разработаны алгоритмы построения детерминированного теста и кратчайшей детерминированной тестовой последовательности сканирования для контроля МЮТ;

7) разработана исследовательская программная система,, предназначенная для синтеза контролепригодных МПУУ, проведены экспериментальные исследования предложенных алгоритмов.

Практическая ценность. Разработанные методн и алгоритмы мо -гут быть использованы при проектировании контролепригодных УЛУ. Отдельные из них реализованы программно. Соответствующие программные средства могут применяться для решения задач проектирования УЛУ на IBM-совместимых персональных ЭВМ.

Реализация и внедрение результатов работа. Результаты работы связаны с выполнением хоздоговорных: и госбюджетных НИР, проводимых на кафедре ЭВМ БГУИР. Полученные результаты были внедрены в учебный процесс БГУИР.

Апробация работы. Основные теоретические и практические результаты работы докладывались и обсуждались на ряде конференций, в том числе: НТК "Вероятностно-физические методы исследования надежности машин и аппаратуры" (Киев, 1992); межреспубликанском семинаре по объектно-ориентированному программированию (Минск, 1991); 47-ой и 48-ой научных сессиях, посвященных дню радио (Москва, 1992, 1993); международных конференциях молодых ученых и специалистов "САПР-92,93. Новые информационные технологии в науке, образовании и бизнесе" (Гурзуф, 1992, 1993); международной конференции "Design Automation Conference 92" (Каунас, .1992); НТК "Контроль и управление технических систем" (Винница, 1992); шкопе-семинэре по технической диагностике (Москва, 1993); конференции "Техническое диагностироватщ~93" (Санкт-Петербург, 1993).

Публикации. По теме диссертации опубликовано 17. печатных работ, в том числе 5 статей, 10 тезисов докладов, 2 отчета.по НИР.

Структура и объем диссертации. Диссертация состоит из. введе ния, 5 глав, заключения, списка литературы (.191 'илименоотние) и приложения; содержит 150 страниц основного текста. 2Ь рисунков и 7 таблиц.

- * -

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

В большинстве существующих подходов к задаче функционального контроля в качестве критерия исправности объекта диагностирования рассматривается правильность реализации им соответствующего алгоритма управления, заданного.ь некотором формальном виде. 3 диссер-тациошюй работе алгоритм функционирования МПУУ представляют в виде ГСА, узлы которой соответствуют отдельным микрокомандам, а дуги показывают пути передачи управления. В этом случае контроль работы устройства заключается в проверке последовательности генерируемых команд путем сравнения ее в реальном времени с контрольной ГСА.

. Таким образом, неисправности МПУУ идентифицируются путем слежения за последовательностью выполняемых микрокоманд и ее сравнения с ожидаемой последовательностью, обусловленной структурой микропрограммы. Целесообразно рассматривать задачу контроля исправности -МПУУ на уровне схем алгоритмов, представляя неишгравности устройства как изменения соответствующей ему ГСА. Удобно ввести понятие алгоритмических дефектов устройства управления, проявлением которых служат искажения последовательности наборов сигналов, генерируемых УУ. Выделяются следующие титш искажений:

1) пропадание оператора в последовательности операторов, вырабатываемых М11УУ ("пропадание микрокоманды");

2) появление в последовательности лишнего оператора;

3) замена одного оператора последовательности другим;

4) неверный переход по логическим условиям.

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

При контроле правильности выполнения ГСА каждой вершине ГСА ставится в соответствие некоторый признак. Использование признаков вершин позволяет представить алгоритм работы устройства в виде размеченного ориентированного графа. При этом корректность работы МПУУ можно проверить по последовательности признаков выполняемых, вершин (микрокоманд).

В диссертационной работе проводится сравнительный анализ различных методов формирования признаков. На основании этого анализа предлагается выбирать в качестве признака код микрокоманды, соответствующей вершине ГСА. Таким образом, при контроле исправности МПУУ вершинам ГСА, соответствуй®™ одинаковым микрокомандам, сопоставляется один и тот же код. Последовательность выполнения микрокоманд взаимно однозначно определяет кодовую последовательность, получаемую конкатенацией кодов выполняемых микрокоманд. В результате задача диагностирования .ГСА сводится к задаче проверки корректности получаемой последовательности. В связи с ее большой длиной при этом целесообразно использовать ' один из методов сжатия информации, например сигнатурный анализ или метод счета единиц.

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

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

1) соответствующий выбор признаков и сигнатурного полинома;

2) "выравнивание" сигнатур. Этот метод применяется в большинстве существующих разработок и заключается в введении в структуру ГС/ дополнительного блока. "Выравнивающая" сигнатура может располагаться в любом месте между тачками разветлешя и схождения.

На уровне ГСА выравнивание может осуществляться путем введения дополнительных вершин в структуру ГСА. При этом признаки этю вершин должны выбираться специальным образом, чтобы обеспечим равенство сигнатур по двум параллельным путям. Естественным критерием оптимальности в этом случае является количество вводимых f схему дополнительных вершин. Для минимизации этого числа долин; решаться указанная выше задача оптимального выбора значений признаков и проверяющего полинома СА.

. В первой главе приводится также общая методика синтеза алгоритмически контролепригодных МПУУ. Отмечается, что при проверю исправности МПУУ возможно применение трех евдов контроля:

- встроенный текущий контроль ("oil-line");

- внешнее диагностирование ("oii-llne");

- самотестирование, ("oii-llne").

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

Будем считать, что исходная ГСА уже задана и вносить в hqi изменения нежелательно. Тогда для диагностирования Г'СА необходимо

1) выбрать проверяющий полином сигнатурного анализатора (СП);

2) выбрать кодировку всех встречавшихся микрокоманд;

3) модифицировать ГСА. Будем рассматривать только один вид из менений, заключающийся в добавлении в ГСА некоторых фиктивных вер шин, предназначенных только для генерации определенных признаков.

4) провести собственно тестирование ГСА. В результате получает ся некоторая сигнатура кодовой последовательности, которая сравни ."аетсл с эталонной. При их несовпадении делается вывод о иеистрнв

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

Рассмотрим задачу синтеза контролепригодного МПУУ с использованием описанной схомн организации встроенного текущего- контроля исправности. Процесс синтеза разбивается на следующие этапы:

1) строится исходная ГОЛ;

2) ГСА модифицируется для обеспечения контролепригодности;

3) по модифицированной ГСА синтезируется микропрограммный автомат (ШТА);

4) синтезируется реализующая этот автомат цифровая схема. На каждом из этэгож синтеза может решаться задача мшжмизвшш.

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

Во второй глазе ставится задача синтеза оптимальной структуры контролепригодного МПУУ и предлагаются некоторые алгоритмы ее ре -пения. Проводится сравнительный анализ различных схем организации встроенного текущего контроля исправности и самотестирования М11.УУ. Дается постановка задачи оптимального кодирования микрокоманд, а также синтеза оптимального сигнатурного анализатора (СА). Рассматривается решение этой задачи для линейных схем и схем с одним разветвлением.

■Упгы С7.0Ш9 рвддекил сигкмурисго пгога

- & -

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

Работа СА происходит в режиме реального времени, параллельно с основной работой схемы. По окончании работы МПУУ сформированная сигнатура сравнивается с контрольными; если она не принадлежит к их числу, то выдается сигнал об ошибке.

Таким образом, в качестве осноеной далее принимается следующая схема встроенного текущего контроля исправности МПУУ:

С начала работы МПУУ до момента окончания работы все формируемые на выходе устройства сигналы у параллельно с основной работой схемы подаются на вход сигнатурного анализатора. На практике проще использовать многовходовый СА, однако для удобства анализа рассмотрим случай анализатора с одним входом, на который подается последовательность двоичных сигналов;

У,(1). У3(1),.----Уп(1). У4(2).....у-(2).....УпЩ.

Здесь рассматривается синхронная схема с п выходами, работающая I тактов, у и)' - значение сигнала на (-ом выходе на 1-ои такте.

Полученная в результате сжатия сигнатура сравнивается с контрольной, при их рассогласовании подается сигнал об ошибке. Набор

сигналов у4(к).....у (к) представляет собой код микрокоманды,

генерируемой на к-ом такте.

Полнота предложенного метода контроля исправности иллюстрируется следующим утверждением:

Утверждение 1. Предложенная схема контроля обеспечивает гарантированное обнаружение всех одиночных неисправностей типа "замена микрокоманды".

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

При использовании горизонтального микропрограммирования на кахдоМ такте работы МПУУ.некоторые микрооперации принимают безразличное значение, т.е. могут принимать как нулевое, так и единичное значение. Соотьетственно,.каждой микрокоманде у ((=1,...Д) может

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

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

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

1) введение дополнительных разрядов в код микрокоманды. Этим разрядам соответствуют символы X в векторе в ;

2) введение дополнительных микрокоманд, соответствующих дополнительным вершинам в модифицированной ГСА.

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

Итак, удобно применять два вида ограничений.на кодировку микрокоманд:

1).ограничения, заданные в виде троичных векторов:

2) требование несовпадения кодов различных микрокоманд.

Эти ограничения, могут задаваться как раздельно, так и совместно.

Для синтеза контролепригодных МПУУ, контроль исправности которых осуществляется на алгоритмическом уровне, необходимо включить в общую схему синтеза устройства этап модификации исходной ГСА. На этом этапе решаются следующие задачи:

1) выбор проверяющего полинома;

2) включение в ГСА дополнительных вершин;

3) выбор кодировки микрокоманд.

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

пар&турвая избыточность синтезируемого МПУУ уменьшается приблизительно вдвое по сравнению с результатами применения существующих методов, при сохранении тех же показателей контролепригодности.

Задача кодирования микрокоманд сводится к решению оистемн уравнений следущего вида:

а(1|) а(Ц)...а(11) - а(3|) а(,)М...а(31) (з1в Р.Р.)

1 «Д П 1 л. 1П 1

■ ■ ... (I)

а(1М а(1*)...а(1к) * а(3*) а(^)...а(Зк) (81« Р,Р.)

Г» ГО н

Размерность системы равна числу к условных вершин ГСА, каждое уравнение соответствует определенной точке разветвления. Две части произвольного уравнения системы соответствуют, таким образом, двум параллельным цепям, имеющим общие начальную и конечную вершины. Сигнатура р есть контрольная сигнатура, соответствующая /-ой точке разветвления, т.е. /-ой условной вершине ГСА и определяемая однозначно в соответствии с уравнением:

Р, » а(1) а(1за)...а(1л), (2)

где последовательность '(1 >. 1 $ г « 1- есть путь от начальной вершины ГСА до ./-ой точки разветвления. Вообще говоря, к уравнений вида (2) должны бить включены в систему (1).

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

Утверждение 2. Набор кодов {а(} является решением системы (1) тогда и только тогда, когда значения сигнатуры (В Р) будут

одинаковы для всех допустимых путей В.

Утверждение 3. Всегда существует хотя бы одно решение системы (1).

В третьей главе дается математическая формулировка общей задачи синтеза контролепригодного МПУУ. Предлагаются алгоритмы выбора кодировки микрокоманд и проверяющего полинома са при синтезе МПУУ. Подробно рассматривается методика решения систем вида (1).

Рассматривается задача определения решения системы (О, минимального по числу вводимых.дополнительных вершин. Поскольку данка> задача имеет экспоненциальную трудоемкость, доменке концентрируется на квазиоптимальных алгоритмах ее решения. Предлагается мето; решения системы (1), основанный не последовательном рвжлш входя-

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

При применении указанного метода порядок решения уравнений системы должен быть выбран специальным образом, в противном случае очередное уравнение может оказаться не имеющим решения. В диссертационной работе предлагается соответствующий алгоритм определения последовательности решения отдельных уравнений системы. Показано, что при этом может возникнуть необходимость специальным образом выбирать местоположение дополнительных вершин, вводимых в ГСА. Приводится соответствующая процедура, позволяющая для любой ГСА свести решение системы (1) к решению отдельных входящих, в нее уравнений.

В третьей главе также подробно рассматривается задача выбора проверяющего полинома сигнатурного анализатора для различных режимов работы схемы. Для рекима встроенного текущего контроля исправности сигнатурный полином выбирается так, чтобы обеспечить равенство значений контрольных сигнатур по всем допустимым путям. При организации внешнего диагностирования решается задача определения проверяющего сигнатурного полинома, который может быть применен для контроля исправности условных вершин. Математически возникающую задачу можно поставить следующий образом: известна ГСА, каждой операторной вершине которой сопоставлена микрокоманда, а также котировка микрокоманд. Необходимо найти полином , для которого контрольные сигнатуры для всех допустимых путей были бы различны.

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

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

позволяющие повысить достоверность обнаружения рассматриваемых неисправностей.

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

Четвертая глава посвящена вопросам организации самотестирования и внешнего диагностирования МПУУ. Все виды диагностирования рассматриваются на алгоритмическом уровне. При этом учитывается модификация ГСА,- проведенная для обеспечения эффективности встроенного текущего контроля исправности, а также применяется та же схема сигнатурного скатия информации, что и при встроенном текущем контроле. В результате появляется возможность существенно снизить аппаратурную избыточность, а также повысить результирующую достоверность контроля благодаря совместному анализу достоверности обнаружения алгоритмических неисправностей для различных видов контроля исправности. .

Предлагаются алгоритмы поиска детерминированного теста, ориентированные на описание работы МПУУ в. виде ГСА. Они позволяют строить тест для обнаружения как выделенной неисправности, так и всех неисправностей заданного множества. Рассматривается также задача построения кратчайшей тестовой последовательности сканирования, имеющая следующий вид:

Найти для заданной структуры схемы, имеющей к входов, и заданного множества неисправностей М последовательность тестирования минимальной длины А, Для которой всякая неисправность класса М проявляется на одном из 1-к+1 тестовых наборов вида (а ,...,а где'1 £ ,) « 2-к-И, I - длина тестовой последова-

тельности. При этом обычно известно некоторое множество тестовых наборов {Б , ...Б^}, для которого любая неисправность из М обнаруживается хотя бы на одном из .

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

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

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

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

причем должно выполняться условие г Ч(р)бр =1. Доказано, что

о

оптимальное распределение может быть представлено в виде:

q(x) = а*б(Х-р1) + (1-сО*5(Х-р2> (3)

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

- н -

проведенных программных экспериментов, проводится сравнение с результатами теоретического анализа.

Описываемая система реализована на языке программирования Турбо-Пвскаль и позволяет решать на 1ВМ-совместимых ПЭВМ задачи модификации ГСА устройств логического управления для обеспечения алгоритмической контролепригодности разрабатываемых устройств.

Разработанная система позволяет проводить модификацию ГСА с числом вершин не более ЮС. На основании проведенных экспериментальных исследований трудоемкости реализованных алгоритмов можно сделать вывод, что с использованием предложенных в диссертационной работе методов может осуществляться Модификация ГСА с числом вершин до нескольких тысяч. При большей размерности ГСА необходимо проводить ее разбиение на отдельные фрагменты. Проведенные экспериментальные Исследования также показывают корректность предложенных, алгоритмов.

ЗАКЛЮЧЕНИЕ .

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

1) предложены методы и алгоритмы модификации ГСА для обеспечения контролепригодности синтезируемых по ним устройств;

2)- разработаны метода, алгоритмы и программы кодирования микрокоманд, пригодные как для горизонтальной, так и для вертикальной структуры микрокоманд;

3) предложены методы и алгоритмы выбора .проверяющего, полинома сигнатурного анализатора для организации встроенного текущего контроля исправности и внешнего диагностирования МПУУ;

4) разработаны методы и алгоритмы построения детерминированных тестов для диагностирования различных типов неисправностей МПУУ,.а также алгоритмы синтеза минимальной тестовой последовательности..

5) рассмотрена задача оптимизации значений вероятностей появления на входах МПУУ единицы при использовании вероятностного тестирования для организации самотестирования, предложены соответствую-

щий алгоритмы.

6) разработана исследовательская программная система синтеза контролепригодных ГСА, проведено экспериментальное исследование предложенных алгоритмов кодирования микрокоманд и выбора оптимального сигнатурного полинома.

Основные результаты диссертации опубликованы в следующих работах:

1. Быков Ю.В., Закревский Л.А. Оптимизация значений вероятностей входных переменных при вероятностном тестировании цифровых схем. /Тезисы докладов конференции 'Контроль и управление технических систем". Винница. 1992. с.47.

2. Быков Ю.В, Закревский Л.А., Меметов Г.Р. Одно- и многопараметрические методы определения■оптимальных значений вероятностей входных переменных, /депонировано в НИИ ЭИР. -М. 1992. Регистрационный N.3-8928 - 12 С.

3. Закревский Л.А. Оптимизация параметров метода вероятностного тестирования. //Электронное моделирование. -1992. N.4. с.70-74.

4. Закревский Л.А. Применение объектно-ориентированного подхода при создании программных моделей . тестопригодных схем. /Материалы 1-го межрегионального семинара по ООП. - Минск. 1991. с.79 81.

5. Закревский Л.А. Синтез контролепригодных микропрограммных устройств управления с использованием сигнатурного анализатора. /Материалы международной конференции "Design Automation Conference 92". - Каунас. 1992. с. 262-265.

6. Закревский Л.А., Захаров В.Н. Синтез легкоконтролируемых дискретных схем. //Техническая кибернетика. 1991. N.3. с.126-141.

7. Закревский Л.А. Автоматизированный синтез самотестируемых автоматных устройств управления. /Тезисы . доютдов международной конференции молодых ученых и специалистов "САПР-93". - Гурзуф. 1993. с.52-53.

8. Закревский Л.А. Контроль исправности микропрограммных устройств управления с использованием компактной схемы вероятностного тестирования. /Тезисы докладов 48-ой научной сессии, посвященной дню радио. - М. 1993. с.б 1-62.

9. Закревский Л.А. Минимизация длины тестовой последовательности при использовании методов сканирования. //Автоматика и выч.техника. 1993. N.2. с.3-8. .

10. Закревский JI.А. Оптимизация характеристик сигнатурного анализатора при контроле исправности микропрограммных устройств управления. /Тезисы докладов международной конференций "Информатика и вычислительная техника". - Кишинев. 1993.

11. Закревский Л.А.. Калоша Е.П., Качан И.В., Хаткевич H.H., кролик В.Н. Метод граничного сканирования и его применение при тестировании цифровых устройств, /депонировано в НИИ ЭИР. -М. 1992. Регистрационный N.3-8929.

12. Разработать.метода и средства для реализации самотестируемых микропрограммных устройств управления. /Ярмолик В.Н., Калоша Е.П., Качан И.В., Быков Ю.В., Закревский Л.А., меметов Г.Р., Хаткевич H.H. Отчет по х/д 91-3058, Минск. 1991. инв. номер 02920003288. номер гос. регистрации 01910022843.

13. Разработать методы и средства для реализации самотестируемых цифровых устройств. /Ярмолик В.Н., Закревский Л.А., Меметов Г.?., Мещеряков Ю.В., Мурашко И.В., Тедеев А.Р. Отчет по х/д 92-3023, Минск. 1992. номер гос. регистрации 0192001 "1447.

14. Ярмолик В.Н., Закревский Л.А. Синтез контролепригодных цифровых схем на основе .сигнатурного анализа . последовательности кодов выполняемых команд. /Тезисы докладов 47-ой научной сессии, посвященной дню радио. - М.- 1992. с.32-33.

15. Ярмолик В.Н., Закревский Л.А. Система проектирования самотестируемых цифровых схем H8 основе сигнатурного анализа последовательности кодов выполняемых команд. /Тезисы докладов международной конференции молодых ученых и специалистов "САПР-92.". -Воронеж.. 1992. с.15-17.

16. Ярмолик В.Н., Закревский.Л.А., Меметов Г.Р. Быстрая проверка качества работы цифровых схем путем сигнатурного анализа кодовой последовательности выполняемых команд. /Тезисы докладов НТК "Вероятностно-физические методы исследования надежности машин и аппаратуры". - Киев. 1992. с.14-15.

17. Ярмолик В.Н., Закревский Л.А. Построение кратчайшей тестовой последовательности сканирования. .-/Тезисы докладов конференции "Техническое диагностирование-93". - Санкт-Петербург. 1993. с.90.

На правах рукописи

Зякревский Лев Аркадьевич

СИНТЕЗ И ДИАГНОСТИКА КОНТРОЛЕПРШ'ОДНЩ: МИКРОПРОГРАММНсК УСТРОЙСТВ УПРАВЛЕНИЯ

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

Подписано в печать 1С.01.94. . Формат 60x84 1/16

Объем 1,0 усл. печ. л. 1,0 уч. -изд. л. Тираж 90 экз. Заказ 8.

Отпечатано на ротапринте БГУИР Р2002Т, Минск, П. Бровки, б