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

МОСКОВСКИЙ ОРДЕНОВ ЛЕНИНА, ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В.ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики Кафедра системного программирования

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

ДРАСУТИС ЭВАЛЬДАС АЛЬГИМАНТОВИЧ

УДК 681.3.06

СИСТЕМА ДИАГНОСТИКИ ЦИФРОВЫХ УСТРОЙСТВ, ОСНОВАННАЯ НА ЗНАНИЯХ

05.13.11 - математическое и программное обеспечение вычислительных машин и систем

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физино-математических наук

/

МОСКВА -1990

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского Государственного Университета имени Ы В. Лэмоносова

.. Научный руководитель: доктор физико-математических наук профессор Э. 3. Лкйкмскнй

Официальные оппоненты:

доктор физико-катеыатичвских наук

профессор Д. Б. Шдшвашв

кандидат физико-математических наук

Ы. М. Горбунов- Посадов

Ведущая организация:

йнститут электронных управлявших ма£шн ( ИВЭУЫ ) Шнрадиопроиа -р

Зашита состоится "^7"' '¿I У*ЯЯ 189£г.

в Ш_С часов на васедании Специализированного совета Л053.(35.38 по иатематике при МГУ им. ЕВ. Ломоносова по адресу: 119899, Москва, ГСП, В-234, Ленинские горы, МГУ, фа--кульгет вычислительной математики и кибернетики, ауд. 685.

О диссертацией ьюжно ознакомится в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан "Ь" 6^/2-Г& 1990г. Ученый секретарь совета

професоор ЕЕ Трифонов

ЗШГШЕШ'Ч - з .

т„-.»¡ш

Отдел А}

ОБЙАЯ ХАРАКТЕРИСТИКА РАБОТЫ туальность темы.

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

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

'. Цель работа

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

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

Научная новиэна.

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

Практическая ценность.

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

Апробация и п/бликации.

По теме диссертации опубликованы 3 работы. Материалы диссертации докладывались на васедании кафедры системного программирования факультета ВМК МГУ (1990) и в научном семинаре кафедры математического обеспечения ЭВМ Вильнюсского Университета.

Структура и объем диссертационной работы.

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Основной (-без приложений) текст, занимает 95 машинописных страниц.

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

ВВЕДЕНИЕ

В п. 1 обсулдается предметная область моделирования логических схем (далее в тексте автореферата - ЛС),

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

1) Наиболее подходящими для решения поставленой задачи являются методы, применяемые в технологии экспертных систем. Описание законов функционирования Ж) является представлением соответствующих 8наний с помощью правил-продукций вида "ЕСЛИ <ситуация> ТО <поведение»". Правила выражают законы поведения отдельных пастей ЛС у имеют "причинно-следственный" вид;

2) Моделирование функционирования схемы осуществляется путем вычисления значений переменных модели с помощью логического вывода;

3) Дерево вывода вначения переменной можно рассматривать как представление в каузальных терминах процесса формирования этого еяачения логикой ЛЗ;

4! Анализ процессов функционирования ЛС организуется в том или ином виде как просмотр дерева вывода значений интересующих переменных. Это соответствует объяснительным средствам в экспертных системах;

5) Для реализации программной модели ЛО наиболее подходящим является ее представление в виде множества воаимодейс-твущих программных объектов. Отдельные объекты реализуют части ЛО. Вовможность такого представления дают методы объектно-ориентированного программирования.

В п. 3 определяется класс рассматриваемых Я) - это синхронные логические схемы.

В п. 4 даётся обаор наиболее характерных систем-моделей ЛС, основанных на вяаииях. Как правило, такие системы откосят к системам ИИ и их целью является ив точное повторвшв (имитация) работы ЛО, а скорее рассуждения над моделью о некоторой целью. Обсуждается система И. 0аУ18' а, оистеш аж и

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

В п. 5 кратко изложено содержание работы.

ГЛАВА 1. Модель логической схемы. Представление пользователя.

Отправной точкой при разработке общей схемы и даже внутренних механизмов системы моделирования является набор тех объектов и операций над ними, которые так или иначе должны быть визуализированы и представлены пользователю. Этот набор, описанный на абстрактном уровне называем моделью интерфейса ( п. 1.1. , п. 1.2 ).

Синхронную ЛЗ всегда можно описать как конечный автомат. Кроме обычных групп переменных конечного автомата X(t) (вектор входных значений), Z(t) (вектор выходных значений), Q(t) (вектор состояния - он соответствует регистрам), вводится вектор внутренних значений V(t), и конечный автомат 'задается в виде уравнений:

'V(t) - Ф1 (Ж t),Q(t - 1)) • t - 1,2,..

I Q(t) - 0K( V(t)) t - 1,2,..

j Z(t) - 48( V(t)) t - 1,2...

.Q(O) - QО

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

Четверка

S(tO) - ( Q(to - 1), X(tO), VCtO).'Z(tO) ) определяет устойчивое состояние схемы в такте to, в котором • она пребывает до начала следующего такта.

Весь ход работы в конкретном случае содержится в трассе состояний SC 1), S( 2),.. , S( N), и анализ хода работы схемы означает анализ этой трассы состояний.

Процесс работы J3C в одном такте Ю отражает набор

(XtO) - ( QCtO - 1). X(tO), V(tO), ZCtO), Q(tO) ), который будем называть обобщенным состоянием. Трассу состояний мокко представить как последовательность таких обобтан-ньк состояний.

Набор 0( L0) рассматривается как множество переменых подели вместе с их значениями. Конкретное обобщенное состояние 0( tO) представляется как множество утверждений вида Р: VAL, означающих, что переменная Р принимает значение VAL.

Переменные моделируются: регистры текущего и следуюде-го такта (они соответствуют Q(t-l) iiQ(t)), соединения (группы соединенных контактов компонент), контакты (с двумя или с тремя состояниями), внутренние вначения шин данных компонент (например значение адресного порта микропроцессора как двоичное число). Каждая переменная имеет свой алфавит значений, который зависит от свойств моделируемого объекта '(разрядности регистра, типа контакта и т.п.).

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

Первая структура соответствует группированию переменных модели в соответствии со структурой ЛС - т. е. она еодерми "указания о принадлежности переменных компонентам, соединениям и т.д. Эта структура позволяет просматривать .обобщенное состояние в терминах структуры ЛС: узнать фрагмент состояния, соответствующий одной компоненте, состояния контактов соединения и т. п.

Вторая структура отражает особенности процесса преобразования в данном обобщенном состоянии, выполняемого логикой ЛС. Она описывается как ациклический ориентированнный граф (О,V), где'О - обобщенное состояние а V - множество ориенти-рованнных дут. Этот граф называем каузальной (причинно-следственной) сетью, или К-сетью.

Интерпретация этой структуры следующая: если ( Pt:VALl, Р2: VAL2 )SW, то это означает, что переменная Р1 участвует в формировании значения переменной Р2 в данном обобщенном состоянии, т.е. первый íera является одной из причин второго.

Для того, чтобы К-сеть соответствовала такой интерпретации, она должна удовлетворять ряду естественных требований. Пусть prediU) - i U'e O! (U',U) e W >.

Тогда должны быть выполнены следующие неформальные условия:

(Каузальность). Если pred(U) * 0, то pred(U) состоит К8 утверждений, соответствующих ситуации, которая однозначно детерминирует поведение определенной части ЛЗ и формирование U.

(Минимальность). Шоввство pred(U) для всякого U должно быть минимальным. Лобов подмножество CCpred(U) не определяет однозначно формирования U.

(Бэпосредственность). pred(U) должно содержать интуитивно непосредственные причины формирования U. Понятие "непосредственности" зависит от введенных в модель переменных. Если pred(U) содержит утверждения о вкачениях переменных pl, .., рп, то в модели не должно быть переменных pl',pm' значениями которых можно (непосредственно) объяснить U и в то же время их формированием объяснялось бы pred(U). Другими словами, в К-сети все причинные цепочки должны бьггь представлены с максимальной для выбранного множества переменнных подробностью.

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

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

В п.* 1.3. формально вводится абстрактный язык описания логической схемы и'формально определяются понятия обобщенного состояния и К-сети отдельной компоненты и всей JÍ5.

ГЛАВА Z. Строение моделирующей системы.

Важная характеристика проблемной области моделирования Ю - возможность моделируемый объект естественно представить в виде композиции некоторых, в значительной мере автономных,

частей - объектов, поэтому мокко считать естественным выбор объектно-ориентированного программирования (ООП) как основной парадигмы для реализации внутренних механизмов моделирующей системы и их описания. Такие традиционные понятия ООП как классы и наследовайие дают мойные средства для описания объекта моделирования и его составляющих частей (п.2.1.). Изложение строения модэлирущэй системы дается в универсальных для ООП терминах, поэтому легко может быть реализована в любой среде ООП.

Программная модель конкретной ЛС в моделирующей системе представляется как совокупность объектов трех основных классов: соединений, компонент и моделей функционирования компонент. Совместная работа всех программных объектов управляется объектом УСТРОЙСТВО (п. 2.2.). Программная модель Ж создается в процессе инициализации объекта УСТРОЙСТВО, который читает описание ЛС (перечень компонент с их типами и перечень соединений контактов), создает объекты соответсвуюцкх классов и связывает их в сеть (п.2. 3.).

Объект-соединение соответствует соединению контактов компонент и может принадлежать к одному из нескольких подклассов ( ШНТАЕНОЕ_йЛИ, ОБПШЦПИНА и т.д., ). Б статических переменных объекта-соединения хранится его значение в теку-"¡шм такте моделирования (значение сигнала на нем).

Объект-компонента соответствует конкретной компоненте ЛС. В его статических переменных хранятся значения (состояния) контактов, внутренних переменных и вначения регистров в текущем и следующем такте.

Объект-модель соответствует одному типу компоненты и содержит внутреннее представление описания функционирования компоненты этого типа. Все объекты-компоненты одного типа "разделяю?" единственный экземпляр объекта-модели в процессе вычисления значений переменных.

Обобщенное состояние одного такта хранится в статических переменных объектов-соединений и объектов-компонент.

Алгоритм вычисления обобшенного-состояния может Сыть охарактеризован как алгоритм "обратной волны". Опишем кратка локальные действия программных объектов в процессе вычисле-

НЙЯ.

В очередном такте все значения регистров текущэго такта должны быть заданы. Запрос на значение переменной осуществляется путем посылки сообщения ДАЯ_ЗНАЧЕНИЕ тому объекту, который ее содержит. Объект аналогично запрашивает значения других переменных (вовмокно у других объектов), вычисляет запрошенное значение и возвращает. При этом объект-компонента "пользуется" своим объектом-моделью.

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

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

ГЛАВА 3. Язык описания типовой компоненты.

Язык описания типовой компоненты предназначен для описания функционирования компоненты данного типа. В основу ненка положено понятие правила-продукции. Одно такое правило определяет поведение части компоненты в определенной ситуации.

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

Описание типовой компоненты - -это последовательность операторов (п. 3.2.). Операторы могут быть трех видов: описания типа элемента, введения синонима и описания правила.

- 11 -

В описании через О обозначаются переменные-контакты, черев VI - внутренние переменные, й - переменные регистры.

Оператор описания правила имеет вид: Я определяемая переменная» - <выраяение> [ <-- <условие? 3; (скобки "П" выделяют необязательную часть конструкции, сочетание "< —" является лексемой языка правил и читается "осот").

Правило определяет способ вычисления значения переменной в том случае, если выполнено некоторое условие. Условие может отсутствовать. Тогда правило считается безусловным и может интерпретироватся кг« оператор присваивания. <условив> - это список условий-сравнений вида

<пер>С1] - <зн>,.., <пер>СП - <эн>. (скобки "£3" выделяют необязательную часть конструкции)

Условие-равенство <пер> - <8н>, где <пер> - переменная, <зн> - целое неотрицательное число, выполнено, если .значение переменной <пер> равно константе <ан>.

Условта-неравенство <пар> !- <8Н> выполнено, если значение переменной <пер> не равно <зн>.

Запятая интерпретируется как коньгакция, поэтому условие правила выполнено, если все условия-сравнения выполнены.

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

5? СЗ - 1 <— С1 - 1, С2 - 1; означает, что выходной контакт СЗ будет равен 1, если входы С1 и С2 равны 1.

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

й -И - КО <— С1 - 0; овначает, что регистр И в следующем такте становится раБ;шм значению регистра ИЗ в текущем такте, если С1 - 0. Все гистры в выражении н в условии соответствуют текущему такту, а в позиции определяемой переменной - следующему.

Для избежания повторение повторения однообраяных частей

описания в язык введены простые препроцессорные средства в виде конструкции макрогруппы. Шкрогруппа - это записанная одной строкой группа операторов. Например, макрогруппа

(0-У) R RS - R$ <— Са - О; означает, что регистры RQ... R7 не меняется при переходе на следующий такт, если С1 - О. Символ '8' играет роль макропеременной, а префикс "(0-7)" укааывет пределы изменения макропеременной. Препроцессор разворачивает эту макрогруппу в 8 обычных правил.

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

Оператор описания типа переменной позволяет задавать разрядность внутренних переменных и регистров, а таюке типы контактов (различаются, например, контакты "с тремя состояниями", "с открытым коллектором"). Этим оператором определяется алфавит значений переменной.

Оператор введения синонима позволяет задавать мнемонические имена переменным.

Интерпретатор правил (п. 3.3) реализует обратный логический вывод, подобный используемому в PROLOG'е. Получив запрос на значение переменной, интерпретатор перебирает определяющие ату переменную правила, проверяет их применимость и применяет первое применимое правило. Проверка применимости влечет рекурсивные запросы значений переменных в условии правила, а применение правила - рекурсивный sanpoc на значения переменных выражения.

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

Пример описания простого коньюнктора с входами С1 и 02 и выходом СЗ мажет быть таким:

Р СЗ-0 <--' С1 - 0;

й СЗ-0- <-- С2 - 0;

8 СЗ - 1 <-- С1 - 1, С2 - 1;

Опыт показал, что разработанный явык позволяет описывать самые сложные компоненты, например, микропроцессоры. В Приложении 2 даны примеры таких описаний.

ГЛАВА 4. Реализация.

С целью демонстрации и проверки разработанных принципов для моделирования ЛС практической сложности была реализована экспериментальная система.

Система реализована з среде ООП, реализованной в рамках стандартного языка Си и позволяющей пользоватся всеми основными средствами ООП: классами, наследованием свойств и методов, возможностью динамически создавать объекты. Использование данной среды показало высокую эффективность подобного способа регламентации программирования на явыке Си (п. 4.1.).

Программа занимает около 7000 строк и работает на ЭШ СМ1700 под управлением операционной системы ЮС ВП.

Система позволяет: ■

- вычислить трассы состояний моделируемой Л'З для любых заданных начальных значений регистров и входных сигналов. Трасса состояний запоминается в дисковом файле и моявт далее быть просмотрена средствами системы;

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

I

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

- просматривать К-сеть (дерево вывода). Это средство позволяет анализировать ход формирования значений перемэн-нкх. Реализован просмотр К-сети на двух уровнях: на уро ше правил и на уровне компонент.

На уровне правил просматривается собственно дерево вывода, "состоящее" на правил. Это позволяет анализировать

процессы, происходящие внутри компонент, и отлаживать саму модель.

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

В обоих уровнях просмотра предоставляются две примитивные опрерации: переход вглубь дерева по выбранной ветке и возврат назад. При переходе через границу такта (через переменную-регистр) автоматически происходит загрузка предыдущего такта в модель. Таким образом К-сеть распространяется па всю трассу состояний. Это дает возможность просмотреть -всю "историю" формирования сигнала до самого начала работы ЛО.

Кроме перечисленных средств, система предоставляет возможность трассировать значения заданных переменных в процессе вычисления обобщенного состояния.

Диалоговое общение с системой организовано через систему меню.

■ 0 помощью реализованной системы была смоделирована и 'отлажена сложная реальная ЛС - лроцессор арифметики плавающей запятой ЭВМ СМ1700 СМ 2700.2008. 'Эта большая ЛС содержит около 130 компонент различной сложности (от вентиля до микропроцессорной секции) и около 600 соединений контактов. Описание 40 типов в ней используемых компонент занимает более 1500 строк текста на яаыке правил.

Опыт показал большую эффективность системы в отладке моделей сложных ЛС. Этому особенно способствует возможность анализа хода вычисления значения любой переменкой.

В приложениях содержится формальное изложение синтаксиса языка описания компонент, примеры описания компонент различной сложности. Приведена структура описания класса в среде ООП, реализованной в языке Си.

Основные результаты диссертации.

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

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

2) Разработаны методы реализации модели логической схемы о помощью средств объектно-ориентированного программирования. Предложены способы поддержки интерфейсных понятий о помощью программных объектов и нетрадиционный алгоритм вычисления состояния схемы.

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

4) Реаливована экспериментальная система, предназначенная для проверки и демонстрации предложенных методов. Система, в частности, включает в себе компилятор и интерпретатор явыка правил

5) С помощью реализованной системы смоделирована сложная реальная логическая схема - плата процессора арифметики

' плавающей запятой ЭВЫ СШ700. Соответствие модели реальной схеме проверена на основе известных контрольных значений, снятых с платы с пошнью аппаратуры.

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

1. Драсутис Э. Причинно-следственное моделирование электронно- цифрового, устройства// Тезисы XXX конференции Литовского

Уатематического Общества.- Вильнюс, 1989. с. 217-218.

2. Драсутис Э. Применение объектно-ориентированного подхода для моделирования цифровых устройств// Теаиси XXX конференции Литовского Математического Общества, - Вильнюс, 1989. с. 215-216.

3. Драсутис Э. Любимский Э. 3". [Моделирование логических схем с помощью правил-продукций. - Ы.: Препринт ИПМ АН СССР, N. 56, 1? с. , 1990.