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

Министерство высшего и среднего специального образовании

РСФСР

Томский институт автоматизированных систем управления и радиоэлектроники

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

Для служебного пользование Зкз. , , „

iw tri i я

фРВШОВ ВИКТОР АНАТОЛЬЕВИЧ

уда бЬ8.ы! .з

КОМПЛЕКС СРЕДСТВ AÖTOMAIIÖAipi ОТЛАДШ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ И ПОВЬШШИЯ ОТКАЗОУСТОЙЧИВОСТИ МИКРОПРОЦЕССОРНЫХ СИСТЕМ УПРАВЛЕНИЯ

Специальность - 05.13.06 -Авгоматизироьшпше систеыч управления

ДПССЕР1 Aii/Ш

на соискании учёноП степени кандидата •гекничсских наук в форме научного доклада

ТОМСК - 1-Л'О

инв.

Работа выполнена в Томском производственном объединении "Контур"

Научный руководитель: кандидат технических наук, с.н.с. Благовещенский B.C.

Официальные оппоненты: доктор технических наук, профессор Рубан А.й.

кандидат физико-математических наук, доцент Матросова А.Ю.

Ведущая организация: Всесоюзный научно-исследовательский и проектный институт информационной технологии управления (ШИИТ), г.Москва

Защита диссертации состоится " 1990 года

в " " часов на заседании специализированного совета

Д.063.05.01 в Томском институте автоматизированных систем управления и радиоэлектроники по адресу: 634050, г.Томск, пр.им.Ленина, 40.

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

Автореферат разослан "// " £ 1990 года

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

.П.Ехлаков

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

Актуальность теш. Необходимость сокращения сроков проектирования и повышения эффективности эксплуатации распределённых микропроцессорных систем управления определяет актуальность решения научно-технической проблемы создания комплекса средств аь-томатизации отладки программного обеспечения и повышения отказоустойчивости микропроцессорных систем управления. Данная диссертационная работа выполнена в Томском производственном объединении "Контур" в рамках задания 04.01.01 "Программы работ на 19861990 гг. по решению научно-технической проблемы 0.16.10", утверждённой постановлением ГКНТ СССР от 30.10.85 г. № 555.

Цель работы. Исследование и разработка моделей и алгоритмов системы автоматизированной отладки программного обеспечения, диагностирования и восстановления аппаратной части распределённых микропроцессорных систем управления (РМПСУ)..

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

Научная новизна. В работе впервые предложены: модель сопряжения и взаимодействия имитируемых и реально-функционирующих элементов РШСУ; новый способ представления в ЭВМ графовых моделей; необходимые и достаточные условия существования гамильтоно-ва контура в графе и рекурсивные алгоритмы решения некоторых Д'Р-полных задач; новые структуры и алгоритмы самодиапюстируемш: и самовосетанавливаемък устройств и систем.

Практическая ценность работы. Предложенные новые имитационные модели и точные алгоритм решения задач комплексной отладки приграммпиги обеспечения и аппаратных средств РшЮУ расширяют

возможности использования микропроцессорной техники.

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

Внедрение результатов работы. Разработанный комплекс программно-аппаратных средств, предназначенных для контроля и диагностирования аппаратной части и отладки программного обеспечения микропроцессорных УЧПУ, внедрён на Томском производственном объединении "Контур1' с общим реальным экономическим эффектом 340 тысяч рублей в год. Результаты работы внедрены в Киевском объединении "Электронмаш" и в Бердянском производственном объединении по жаткам.

Апробация работы. Основные положения работы докладывались и обсуждались на ХП научно-методическом семинаре "Автоматизация проектирования в энергетике и электронике" (г.Иваново, 1988 г.), на зональном семинаре "Микропроцессоры в системах контроля и управления" (г.Пенза, 1985 г.), на научно-техническом семинаре "Опыт и проблемы создания и эксплуатации систем ЧШ металлорежущими станками" (г.Томск, 1989 г.), на научно-практической конференции "Автоматизация" (г.Томск, 1988 г.), на научно-технической конференции "Использование вычислительной техники и САПР в научно-исследовательских и опытных работах" .(г.Владимир, 1989 г.), на всесоюзной конференции "Автоматизация проектирования ЭВМ" (г.Киев, 1977 г.), на научно-техническом семинаре "Интеллектуальные САПР СБИС" (г.Ереван, 1988 г.), на региональной научно-технической конференции "Автоматизированные методы проектирования и производства модулей радиоэлектронной аппаратуры (РЭА) на печатных платах" (г.Новосибирск, 1989 г.).

- О -

Публикации: по материалам диссертации опубликовано 18 работ, в том числе V авторских свидетельств на изобретения.

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

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

1. Анализ средств автоматизации отладки микропроцессорных систем управления.

Анализ литературы позволяет сделать следующие выводы:

- традиционные модели и алгоритмы отладки микропроцессорных систем управления (МПСУ) не обеспечивают решения задач отладки распределённых ШСУ, т.к. ориентируются на работу только с одним микропроцессорным объектом;

- использование контрольно-диагностических стендов, логических анализаторов, внутрисхемных эмуляторов, имитационно-модели-рущих стендов позволяет решать лишь отдельные задачи отладки РШСУ;

- применение в ШСУ БИС и СЕЮ ставит трудно разрешимую задачу генерации тестов для них, что требует разработки самопроверяемых, самодиагностируемых и самовосстанавливаемых микроэлектронных устройств и систем.

В связи с изложенным возникла' проблема создания комплекса инструментальных средств, объединённых в единую систему, автоматизирующую процессы автономной и совместной отладки программного обеспечения и аппаратной части на всех этапах проектирования, изготовления и эксплуатации РМПСУ,

2. Структурно-функциональная схема системы отладки распределённых микропроцессорных систем уппявления.

Процесс функционирования РШСУ рассматривается как процесс

- о -

взаимодействия её с внешней средой (ВС) на уровне обмена информацией. Целью системы отладки является организация функционирования как единого целого системы РМПСУ-~"ВС, регистрация информации о состоянии процессов поведения РМПСУ, ВС и процессов их взаимодействия и сравнение полученной информации с эталонной под управлением заданий и данных, поступающих в систему отладки от пользователя. На основе структурно-функционального подхода разработаны Функциональная (рис.1) и структурная (рис.2) схемы системы комплексной отладки РМПСУ.

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

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

^информационные \cpcdcmBa управле- Урункции системы отладка ~| г-по ™ о . ^„^ Шспоиогатемиыё\ основные !

| Функции | функции__|

\взаишвейст6иа

I иия системой отладки

\1

ошзжийзеыгя програ/ч/ча 4* полью5атель

яи/ки задания на. отладки -Ц системы

методика отладки 1 отладки

правила и интерфейс , -г*

\ 1 —■ 1

1 Ч ♦

дохументци!, на систему отладки 1. г| разработчик-системы отладки

Т

I

4-1

1 I

4

подготовка программы л Выполнению

4

1ция ■я на отладку

инрормиро&ш о результатах выполнения

исполнение программы и задания на отладку

сбор индюрмации

обработка информации

Рис. 1 Функциональная схема системы отладки РАЖУ

Рис. 2 Структурная схема системы стлэдни РМПСУ

3. Математическая модель распределённой микропроцессорной системы управления.

В работе предложена оригинальная математическая модель сложной системи, обеспечивающая адаптацию системы отладки к развивающейся модели РМПСУ"**"ВС.

Математическая модель сложной системы £ определяется совокупностью трёх объектов Ма = [7С,Ф,\М(7(,Ф)}, где К - топологи--ческая модель (конфигурация) системы, Ф - модель поведения (функции), VЧ(Т(,Ф)- модель взаимодействия элементов системы. Топологическая модель К задаётся множеством £ элементов, множеством Р выводов всех элементов и схемой сопряжения Я на множестве Р выводов элементов системы, причём:

Л я» , ,

р= ил = ид;

- множество выводов ¿'-го элемента £; системы, Ау - множество выводов у-го оператора сопряжения из Я .

Модель поведения ^-{л^Му, элементов из £ представляется моделями внешней среды внутренней среды /Иу и их взаимодействия Модель внешней среды №(Т,(])) задаётся множеством ^ векторов состояний внешних выводов элементов, множеством 7 точек пространства реального времени и множеством отображений Ц)'. Т-~(]. Модель внутренней среды Му рассматривается как композиция модели дискретного управляющего процесса модели дискретного управляемого процесса ЗГ(1,т)=[2()),ЦЩ и модели У/(Ж(ЫУ),ЗГ(2,тУ1 взаимодействия управляющего и управляемого дискретных процессов, которая определяется векторными соотношениями: .....г„],

ч1хН),и(1-»,и(У)=1, и())еи = [и„иг, ...,ип), + , 9'<,2,..., тф.оо],

где I - символ истинности предиката V) , ^ - некоторая вектор функция со значениями в п -мерном евклидовом пространстве, -время перехода управляемого процесса из текущего состояния 2.(0-/) в новое состояние ¿(д).

Модель взаимодействия внешней и внутренней среди

элементов £7 е £ задаётся отображениями № алфавитов описания их моделей:

\nAT.ty.T~t;]

Модель взаимодействия элементов

системы описывается праймом: любое изменение состояния

п1'1 ■ о

¿-го вывода , принадлежащего ^ -му оператору -у сломы сап-

ряжения К передаётся мгновенно на все остальные выводы из т.е. Ч(р}1\ Р]" )б$ : М(Т,9 ^ (Р/)) .

3. Многоуровневая имитационная модель распределённой микропроцессорной системы управления.

Для выполнения требования адаптации системы отладки к развивающейся в процессе проектирования модели РШ1СУ ВС разработана новая имитационная модель сложной системы, которая задаётся многоуровневой топологической моделью (МТМ) и многоуровневой моделью поведения (!1'<1П).

ШМ (рис.3) является композицией базовых топологических моделей (БШ1. ВИ представляет собой отображение топологической модели Л" в граф и имеет структуру типа "звезда" (рис.-1) с тремя классами элементов: коммутирующая среда (КС) - центр звезды, приёмо-передающая среда (ГШС) и структурно-функциональные злемен-ты (С£Э). ИЗ имитируш сложные функциональные элементы объекта моделирования (СМ), ППС - взаимодействие внутренней и внешней среды сложных алементав, ¡'С - схсьу сопр,1"С!:::;: функционй'!ънмх элементов ОМ. Имитационная модель внутренней среды Б1Э задаётся

Рис.3 Многоуровневая топологическая модель системы

Рис А Базобая топологическая модель системы

ориентированным нагруженным графом в-{и,¡а^(и), V/(Л)} , где Н={и/Г иг> - ■ип ) - множество вершин графа, совпадающее с множеством управляющих точек из и модели . сХ>£г/л2/

множество дуг графа, совпадающее с множеством возможных переходов

от управляющей точки и; к управляющей точке иу . №/<£>) -отображения, сопоставляющие каждой дуге из Й) элементы из множеств модели Му . №(и)~ отображение, сопоставляющее каждой вершине из И один из элементов множества Х = {/,2~\ . Отображение разбивает множество II на два подмножества: Ь- И1 и иг 1 где

и{ - подмножество точек управления, в которых происходит передача фазовых состояний во внешнюю среду. Множество путей в графе в по дугам, у которых У(2)=[, определяет все возможные дискретные процессы внутренней среды ВЬЭ. Представление МТМ композицией БТМ основано на теореме автора об эквивалентности графовой модели 5 и топологической модели Л~.

Теорема. Графовая модель заданная мно -

жеством вершин ия] , множеством гиперрёбер (дуг)

= сСл} и двуместным предикатом ¿(и,й) , удовлетворяю-

щим условию У((/£Х))3(и'еи)'.1(и',с{)=11 где символ истинности предиката, эквивалентна топологической модели Ж , заданной множеством элементов ...,£„] , множеством их выводов

Р~{Р/,Рг ,■■•> Рп\ и схемой сопряжения [Я/.&г , удовлет-

воряющих условиям Р~ Д Р, = и ^;. Р£ Пр, =Д /г, =0, г .

Следствие. Любому графу

взаимно однозначно соответствуют две перестановки У*, и Ч^ на множестве

) каждая из которых состоит из взаимно-простых циклических перестановок. Одна из перестановок У' определяет разбиение (РиРг.....Ял}, а другая - разбиение [ /л2).. .,.?т] множестве Л

Новый способ задания графопих моделей таблицами пиитических

перестановок (рис.6) по сравнению с известными (матричными, списковыми) позволяет сократить время поиска информации о графе, за счёт произвольного доступа к информации заданной таблицами . Бремя выборки элементов Р^ л ^ определяется формулой ¿(вПр1\'Т> где Т - время считывания единицы информации из таблицы.

Многоуровневая модель поведения ( М М П ) имитационной системы- определяет алгоритмы имитации взаимодействия элементов, имеющих структуру, заданную ЕГМ. Управление процессом имитационного моделирования элементов внутри ВГМ осуществляется по централизованному, а между БГМ - по децентрализованному принципу управления. Децентрализованное управление обеспечивает возможность построения распределённой системы имитационного моделирования (РСИМ)[ 4 ] .

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

4. Алгоритм статической отладки программного обеспечения микропроцессорных систем управления.,

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

Базовыми задачами формализованной проверки структурной корректности алгоритмов и программ являются Л'Р-полные задачи поиска всех простых путей и контуров (включал гамильтоновы), поиска всех минимальных покрытий и Есех минимальных разрезов в графе. Известные точные алгоритмы решения перечисленных задач требуют, в общем случае, полного перебора. Разработанные на основе метода

рг рз в ' Рп

л

Рис. 5 Внутренняя структура коммутирующей среды

г/хЮ 'и,Л) кА) М 'и,А) м Мл)

N Чп V 1 Л. 1. 4 Л - I б 7 9 А //

{$1 / / 4 / 2 А 9 ю -V I/ 1 N71 \| //

М 2 / 4 II б 1 5 'б ч 9 * и

6)

Рис. 6 Задание грасра таблицами циклических псрестанобох

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

Б работе впервые сформулирована и доказана теорема о необходимых и достаточных условиях существования гамильтонова контура в графе [ 7 ] .

Обозначим сЬ*(и) - множество всех заходацих в вершину и дуг, £)~(и)- множество всех исходящих из вершины и дуг, Л(и) - множество всех дуг, инцидентных: вершине и в графе в . оО^-^Ц^ о^х^.и^^ ] - множество дуг , транзитивно

замыкающих каждый путь длины 2, проходящий через вершину и , где й\ - вершина, из которой исходит дуга <1*(и) , - вершина, в которую заходит дуга Л (и).

Теорема. Для того, чтобы в графе существо-

вал гамильтонов контур С (о--и), ив И необходимо и достаточно, чтобы в графе , где и'=и\и, 2>'=Я(и) их>\Ъ[и),

существовал гамильтонов контур , и'еП' такой, что вы-

полняются условия:

В соответствии с теоремой задача поиска гамильтонова контура в графе , \и\=п решается в два этапа каждый из которых состоит из последовательности П-2 шагов ( 7 ] . На каждом шаге /е{/,...,/7-2} первого этапа по известному графу (/(¿-^=(^{¿-^,^(¿-0) строится граф в'(0=(и'(<),Л'(0), где и'(0=и({-0\и {1-0,

- /Да (иЦ-п) ■

После выполнения последнего шага 1 = а-2 первого этапа вгра-фе б'(п-2)=(и'(п-2),Х>Гл-2)), где »'(л-г)^',^] йара дуг & ~(ие> ик), <2'-{ик,ис) определяет гамильтонов контур с(п-2) длины два в графе В'(п-2).

На втором этапе последовательно находятся (если они с,\щсот-

в уют) гамильтоновы контуры с(п-1) длины ' в графах <--3,4, ..., п соответственно.

Процедура построения гамильтонова конту-ра С(п-с) в графе Э(п-1) по известному гамияьтонову контуру ) графа

одинакова для каждого шага ¿=3,4,...,/г второго этапа и сосглт либо в замене дуги (ик,ис)=с(п-{¿-/})\(й(я-¿), если либо в замене одной из дуг {ик>ис)1

если{ с(/1-(1-0)\Ю(л-1^'0 на пару дуг (ик,и(п-1)),(и(п-0,ие) в гамильтоновом контуре С(п-(1-1)},

Задача о поиске всех минимальных разрезов в графе решается также методом структурных преобразований графа [ I ] .

Пусть ^т] шожество минимальных рёберных

разрезов в графе в(и,£>) , а - количество рёбер в ми-

нимальном разрезе еЯ графа 5 .

Теорема. Если в графе найдётся множество

Чей попарно 9(6) неотрезаемых вершин, то граф 0'(и',&), полученный из 6 стягиванием V , имеет то же множество

■> Рт] минимальных разрезов, что и граф б(и,!Ь) Под стягиванием множества вершин У^и в графе 5 в данном случае понимается операция удаления рёбер между вершинами из У и отождествления всех вершин из V .

Алгоритм стягивания вершин графа.

1. Вычисляется верхняя оценка

ш для рёберной связности Ф)графа £'в(£) = , где 6(и) _ степень вершины^.

2. С помощью алгоритма определения II вычисляется величина для каждой пары смежных вершин. При этом, если окажется, что: 9(и1)иу)> §(0) , то верпинът и^¿¿у стягиваются;

9(6) , то паре приписывается число, равное

у); в('-'¿,< . то паре (и;.и, ) приписывается число,

равное , а оценке приписывается новое значение, рав-

ное в(и;гц^) и все просмотренное ранее пары вершин (и*,Не) > которым приписано число подвергаются стягиванию.

3. Выполняется процедура, изложенная в пункте 2, для пар несмежных вершин.

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

Задача о поиске минимальных покрытий.

Пусть Л1 - \т<, . ■■■1тп\ - множество, состоящее из ¡1 элементов, а Р~{М1,М2, Ме) _ множество Пидмножеств М .

Подмножество I множества индексов

{/.г,..., г}

задает покрытие множества М , если выполнено условие: , или в другой форме; Ч(т3 е Л1) 3 ('е : ^ е ■

Теорема. Для того, чтобы подмножество {/,2,..., £] задавало покрытие множества /VI , необходимо и достаточно выполнение условия:

где ( ¿=/,2,заданные подмножества множества М .

Необходимость. Пусть задаёт покрытие множества А1 , т.е. выполняется условие М £ ^М; , Тогда выполняется:

Достаточность. Пусть условие теоремы выполняется, тогда [ (/ЛЦ-)и/^'] £[( )и] . Учитывая, что

, получим

На оснований доказанной теарьмы предлагается новый точный алгоритм нахождения всех минимальных покрытий множества А! .

Построим двудольный граф (? -(М I)Р,, где/VI ия - множество вершин, а ЙЕЛ1*/° - множество рёбер графа в , при-

чём (/77^/^еЯ , если п\ е /И;- и если Щ ф Л1у.

Обозначим: Я,- - 1-ое подмножество вершин из Я графа 5 , сформированное на К-т шаге алгоритма; подмножество вершин из М графа 9 , смежных ; =Д|\Л1£- _ подмножество вершин из Л1 графа , не смежных ; т-"- вершина из Л?/*' с минимальной локальной степенью в графе <? ; - тожество вершин из/* графа в , смежных вершине /п'*'.

Алгоритм поиска всех минимальных покрытий.

1. Найти среди вершин из М графа <? вершину т с минимальной локальной степенью, найти для вершины т все ей смежные вершины , сформировать вектор

р">--{р)(",р?:....р;;>},р/'^м';', ¡^....п,

2. Построить вектор т*^ ..., .

3. Построить вектор Рю= {?/*■', Р1/',

4. Если в векторе Р " имеются компоненты Р'^р" , то перейти на пункт 7, иначе - на пункт 5.

5. Построить вектор * Р™,.. , ] •

6. Положить , перейти на пункт 2.

7. Компонентам Р[">=Р' вектора Р1"'однозначно соответствуют компоненты Р?"1 вектора РМ. Подмножества вершин из Р графа в ,

п(г)

заданные каждой выделенной компонентой п )определяют все минимальные покрытия. Конец алгоритма.

Предложенные ноете точные алгоритмы решения /*Р -полных задач используются для решения задач статической отладки программного обеспечения Ш1СУ. Для динамической отладки РШСУ разработан специализированный комплекс аппаратно-программных средств.

5. Структура и функции аппаратных средств динамической комп-лсясиой отладки микропроцессорных систем управления.

Г 1

Предлагаемые! 3, о, о, 3) срсдстга автоматизации динямичес-

ком комплексной отладки (САДКО) микропроцессорных УЧПУ явллются одним из вариантов реализации системы отладки, функциональная и структурная схема которой приведена на рис Л, 2. УЧЛУ подключается к САДКО через блоки отладки программ (БОПО), реализующие совместно с управляющей микро-ЭВМ (УЭВ'Л) модифицирующую и следящую системы. В минимальной конфигурации ядро УЧПУ может содержать только микро-ЭВМ. По мере реализации аппарата^ блоков сопряжения микро-ЗШ со станком, ядро УЧПУ расширяется и в полной конфигурации представляет многопроцессорную систему управления.

При выполнении отлаживаемой программы одновременно с выборкой инструкций, операндов, переменных производится выборка их "меток" из блока памяти информационных датчиков, адресное поле которого взаимно-однозначно соответствует адресному полю ОЗУ микроЭВМ УЧПУ. Блок дешифрации и запоминания трассы программы дешифрует метки и выполняет соответствующие действия по запоминанию адресов, кодов ц моментов времени их выборки и передаёт полученную информацию в УЭВМ через блок прямого доступа (ЕПД). Таким образом реализуется режим трассировки по меткам в реальном времени. Выбор типов и расстановка меток осуществляется системой подготовки данных, входной информацией для которой является текст программы и задание на отладку.

Для обнаружения и локализации неисправностей аппаратных средств на этапах проектирования и изготовления УЧПУ применяются стенд проверки субблоков СПС-4 ( 8, 9] и логический анализатор [2, 10] . На этапе эксплуатации УЧПУ автоматическое обнаружение, локализацию и устранение неисправностей аппаратуры можно обеспечить средствами встроенного контроля, самодкагностирования и самовосстановления.

В результате анализа средств и методов диагностирования предложено использовать базовой топологическую модель (БГМ) для пост-

роения самодиагностируемых, самовосстанавливаемых, отказоустойчивых систем (СДВОС). Корректность представления отказоустой'*и-вьгх систем в виде БГМ вытекает из теорема об эквивалентности графовой модели G и топологической модели Л" сложной системы.

Для технической реализации СДВОС в виде устройства со структурой ВГМ^гребуется создание нового функционального элемента -программируемой коммутирующей среди (ПКС).

ИКС предлагается создать на базе известного коммутационного элемента: матричного коммутатора [ 12] . Матричные коммутаторы имеют регулярную структуру и обычно выполняются в виде больших интегральных схем (ШС). Одним из вариантов ПКС является адаптивный коммутатор ¡ 14 ] , позволяющий реализовать внутреннюю структуру КС, представленную на рис.5.

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

Пример реализации алгоритма диагностирования коммутирующей среды на основе метода структурных преобразований описан в [ II } , различные варианты реализации СДВОС и алгоритмы диагностирования и восстановления устройств и систем предложены в [ 13, 15, 16 ] .

6. Основные результаты работы.

1. Предложена оригинальная математическая модель распределённой микропроцессорной системы управления.

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

Предложен пепый гппг.об представления в ЭВМ графовых меда-

лей в виде таблиц перестановок на множестве натуральных чисел.

4. Впервые сформулирована и доказана теорема о необходимых

и достаточных условиях существования гамильтонова контура в любом графе.

5. На основе метода структурных преобразований разработаны новые точные алгоритмы решения /'/'-полных задач теории графов: поиска гамильгоновых контуров, поиска всех минимальных покрытий, поиска всех минимальных рёберных разрезов в графе.

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

7. На основе предложенных моделей и алгоритмов разработан комплекс средств автоматизации отладки и контроля серийно выпускаемых микропроцессорных УЧПУ, внедрение которых позволило получить ре&льннй экономический эффект 340 тысяч рублей в год.

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

1. Корниенко A.B., Погребной В.К., Щербаков В.А. 0 минимальных разрезах графа. - Кибернетика и ВУЗ. Сборник работ, выпуск4.-Томск: TIM, I97I. - с.141-147.

2. Андреев Ю.А., Ким О.Х., Савчук Г.Г., Щербаков В.А. Встраиваемый логический анализатор. - Микропроцессоры в системах контроля и управления. Тезисы докладов к зональному семинару ('J-I0 сентября IS85 года). - Пенза, IS85. - с.28-29.

3. Щербанов В.А. Средства тестового контроля устройств ЧПУ.-Автоматизированные методы проектирования и производства модулей радиоэлектронной аппаратуры (РЭА) на печатных платах. Тезисы докладов региональной научно-технической конференции (14-16 апреля 1989 г.). - Новосибирск, 1985', - с.26.

'1. Щербанов В.А. Распределённая система моделирования микро-

процессорных устройств управления. - Использование- вычислительной техники и САПР в научно-исследовательских и опытных разработц^. Тезисы докладов научно-технической конференции. - Владимир, 1989.-с.45-46.

5. Щербаков В.А. Система имитационного моделирования микропроцессорах устройств ЧПУ. - Автоматизация, математические методы и управление народным хозяйством. Сборник статей. - Томск, 1=50. - c.IOS-114.

6. Жульмин В.И., Щербанов В.А. Автоматизация проектирования функционального программного обеспечения устройств ЧПУ. - Автоматизация, математические методы и управление народным хозяйством. Сборник статей. - Томск, 1990. - с.105-109.

7. Щербанов В.А., Яульмин В.И. Алгоритмизация поиска гамиль-тонова контура в графе. - Автоматизация проектирования ЭА. Межведомственный тематический научный сборник статей, выпуск 6. -Таганрог: TFTW, I98S. - с.84-88.

8. Щербанов В.А., Яульмин В.И. Средства проектирования тестового программного обеспечения в САПР УЧПУ. - Автоматизация проектирования ЭА. Межведомственный тематический научный сборник статей, выпуск б. - Таганрог: ТРГИ, 1989. - с.88-92.

9. Щербанов В.А., Яульмин В.И. САПР программного обеспечения устройств ЧПУ. - Автоматизация проектирования ЭА. Межведомст венный тематический научный сборник статей, выпуск б. - Таганр"' • ТРТИ, 1989. - с.92-96.

10. Андреев Ю.А., Ким ОД., Савчук Г.Г., Щербанов В.А. О новние принципы агрегатированных средств экспериментального ло1 ческого анализа. - Проблемы радиотехники, электроники и связи. Тезисы докладов областной научно-технической конференции, 4.2. Томск, 1989. - с.37.

11. A.C. > 737835, СССР, кл.в 01 Р 31/0?, Ким О.Х., Щерба-

нов В.А. Способ и устройство контроля печатных плат. Заявка № 2437598. Приоритет 24.12.76. Зарегистрировано 07.02.80. Опубликовано 30.05.80. Бюл. Jf 20.

12. A.C. № 1275753, СССР, кл. Н03 К 17/00. Ким'О.Х., Щерба-нов В.А., Савчук Г.Г., Шарыгин С.Н. Матричный коммутатор. Заявка № 3944574. Приоритет 15.08.85. Зарегистрировано 08.10.66. Опубликовано 07.12.86. Бол. № 45.

13. A.C. № 1227030, СССР, кл.ff Оо В 23/02. Ким О.Х., Щерба-нов В.А. Самодиагностируемая и самовосстанавливаеыая система. Заявка № 3787670. Приоритет 17.07.84. Зарегистрировано 22.12.85.

14. A.C. » I400438, СССР, кл. НОЗ К 17/00. Ким О.Х., Щербаков В.А., Савчук Г.Г. Адаптивный коммутатор. Заявка № 3973052. Приоритет 04.11.85. Зарегистрировано 01.02.88.

15. A.C. № I353I44, СССР, кл.605 В 23/02. Ним О.Х., Щерба-нов В.А., Савчук Г.Г, Устройство для резервирования сложного объекта. Заявка ¥■ ЗЭ44Э-Л. Приоритет 15.08.85. Зарегистрировано 15.07.87.

16. A.C. № 1431545, СССР, кл. G05 В 23/02. Ким O.K., Щерба-нов В.А. Самодиагностируемое и самовосстанавливаемое устройство. Заявка № 4159666. Приоритет 31.10.86. Зарегистрировано 15.06.88.

17. Заявка № 314Ö253/24-2I. Приоритет 16.06.85., Ким О.Х., Щербанов В.А. Коммутатор электрических цепей. Положительное решение от I9.I0.6S.

18. Щербанов В.А., Благовещенский B.C. Формализованная модель сложной системы. - Деп. в ВИНИТИ.