Введение к работе
. Ї.ВВЕДЙШ
Актуальность.Мощным катализатором научно-технического прогресса во всех отраслях экономики является использование вычислительной техники. От ее качества и надежности в большой степени зависит
ЭффеКТИВНОСТЬ СОВремеННОГО ПрОИЗВОДСТВа.В СВЯЗИ С ЭТИМ В8ЖН8ИШЄ8
значение имеет исследование й разработка новых современных методов технической диагностики.направленных на повышение надежности и эффективности использования цифровых устройств.
Использование прогрессивных технологий в микроэлектронике,переход на новуг> элементную базу и архитектурные решения не возможны без современных систем автоматизация проектирования и диагностирования дискретных устройств(ДУ).Они позволяют существенно сократить сроки разработки и запуска в серив новых образцов вычислительной техники,повысить их качество и надежность.
Проведение Всемирных симпозиумов по отказоустойчивым вычислительным системам (FTCS) и тестированию (ШЕ Teat Conference), Европейских конференций по системам автоматизированного проектирования (Euro САБ) и тестированию (їиго Test Conference),международных конференций " Системы , допускающие неисправности , и диагностика" (?TSD),отечественных совещаний и школ-семинаров по технической диагностике ДУ также свидетельствуют об актуальности исследования этих проблем.
В настоящее время в технической диагностике ДУ разработаю множество различных математических моделей и методов,которые часто плохо связаны между собой и теоретически слабо обоснованы.Отсутствие единой методологии в конечном счете затрудняет создание и внедрение систом автоматизированного проектирования и диагностирования
_ 4 -ДУ. Из этого следует актуальность разработки единого комплексне подхода к задачам моделирования и построения тестов.
Целью диссертационной работы является создание единой системы математических моделей,методов и алгоритмов,позволяющих решать широкий класс задач технической диагностики ДУ, и в конечном счете разработка на этой базе программных систем моделирования и генерации тестов.
Основные направления выполненных исследовании следующие: -разработка троичных моделей ДУ логического и функционального уровней;
-исследование и разработка единой системы многозначных алфавитов и математических моделей,позволяющих решать основные задачи технической диагностики ДУ;
-разработка методов и алгоритмов моделирования исправных ДУ; -разработка 'методов и алгоритмов моделирования неисправных ДУ, направленных на повышение эффективности процедур анализа полноты тестов и расширения класса диагностируемых устройств и неисправностей:
-исследование и разработка методов и алгоритмов построения тестов .направленных на сокращение перелора при поиске тестовых наборов и расширение границ применимости структурных методов; -разработка программных систем моделирования и генерации тестов с применением полученных в диссертации результатов. Методы исследования.Теоретическую основу выполненных исследований составляют теория булевых функций,теория конечных автоматов,теория множеств,теория переключательных схем и методы технической диагностики ДУ.
В основе решения многих задач технической диагностики ДУ лежит исследование различішх логических зависимостей. Булевы дшНиронци-
- 5 -алыше операторы позволяют аналитически выразить эту зависимость и поэтому широко применяются при решении указанных задач . С другой стороны,специальные многозначные логики являются эффективным математическим инструментом,позволяющим решать то же задачи с помощью локальных вычислений на структурной модели логической схемы. Научная новизна и основіше положения.выносимые на завдату.Диссертация посвящона разработке теоретических осноп для создания комплекса взаимосвязанных моделей .методов и алгоритмов моделирования ис-пр.чпішх и неисправных ДУ и построения проверяющих тестов,позволяющих повысить надежность изделий вычислительной техники,а также зф-ііпктивпость и качество их проектирования и эксплуатации.
Для решения задач диссертации предложена система взаимосвязанных математических моделей ДУ а также подход, использующий многозначные алфавиты и булевы дифференциальные операторы.Новые научные результаты,полученные при этом подходе, и основные положения, выносимые на защиту,сводятся к следующему.
Впервые установлена связь между булевым дифференциальным исчислением и троичными функциями. На этой основе разработаны метода построения троичных моделей логического уровня. Далее эти методы распространены на уровень языков регистровых передач (ЯРП).Разработаны компактные троичные модели (не зависящие от числа переменных аргументов) для основных операторов ЯРП, к которым относятся отно-ношения ( больше,меньше,равно и т.п. ), арифметические операторы (сложение,вычитание,инкремент,декремент) и условные.операторы.Предложенные модели построены для четырех наиболее часто применяемых па практике методов кодирования троичного алфавита с использованием двух двоичных компонент.
Полученные модели распространены па алфавиты большей значнос-ти.Предложены трехкомпонентпно модели логического уровня для пяти-
- 6 -значного алфавита. Разработана единая система многозначных алфави тов.применяющихся в технической диагностике ДУ.Она включает в себй 3-,5-,6-,8-значные алфавиты,используемые при моделировании ,и 6-., 10-,12-,16-значше алфавиты .применяемые при генерации тестов . На основе этой системы алфавитов впервые разработана универсальная математическая модель в виде многозначных функций,которая позволя-ет решать основные задачи технической диагностики ДУ с использованием указанных многозначных алфавитов.многозначные функции при этом представляются с помощью четырех двоичных (булевых) функций. Определены прямые и обратные многозначные функции. Установлена связь мезду многозначными функциями и булевыми дифференциальными операторами.Построены многозначные модели для ДУ с тристабильными элементами и МОП-схемами,Впервые разработаны многозначные модели на функциональном уровне.
На основе построенной универсальной математической модели предложены новые методы и алгоритмы моделирования, и генерации тестов.Разработаны метода моделирования неисправных ДУ в много- . значних алфавитах, включающие параллельный (по неисправностям) и дедуктивный методы. Разработан паралелльный по наборам метод ода- . ночного распространения неисправностей в. многозначных алфавитах. Предложен новый метод проверки неисправностей, типа задержка распространения сигналов .характерных для современной Технологии производства ДУ.Следует подчеркнуть,что для всех указанных методов используется единая многозначная модель ДУ в отличив от ранее известных, где практически каждый метод требует построения своей модели.
Разработаны методы построения проверяющих тестов для комбинационных ДУ,которио также используют предложоїшую единую модель и. универсальный шестнадцатизначный алфавит.Предложены новые подходы к сокращению порббора при поиске тестовых наборов за счет увеличе-т
- 7 -ния мощности алфавита и применения различных процедур импликации в многозначных алфавитах.Разработан также структурно-аналитический метод построения тестов с использованием булевых производішх первого порядка.
Исследованы проблемы построения проверяющих тестов для после-довательпостішх ДУ.Предложен новый метод построения тестов в шестнадцатизначном алфавите,основанный на преобразовании последователь-постлого ДУ в итеративную комбинационную схему. Разработан новый метод построения тестов,основанный на символьном моделировании в троичном алфавите.Разработан новый подход к построении синхронизирующих последовательностей,основанный на связи булевых диффоренци-альных операторов и троичных функций. Для послэдовательпосгных ДУ показана граница применимости структурных методов построения тестов, основанных на локальных вычислениях в многозначных алфавитах. Впервые разработаны структурно-аналитические методы,тараптарующио построение тестов и преодолевающие принципиалышо трудности .присуще применяемым до этого структурным методам,использующим локальные вычисления.
Практическая ценность результатов,полученных в диссертационной работе,состоит в разработке единой системы многозначных моделей, позволяющей проектировать система моделирования и генерации тестов,нс-юльзупцие в зависимости от применяемых методов различные алфавита. Тредложенные метода и алгоритми доведены,в основном,до инженерного фовня и программно реализованы.Формальные методы построения мяо-тазначных моделей позволяют автоматизировать пополнение библиотеки фограммных моделей логических элементов с помощью специализирован-их трансляторов.Многозначные модели функционального уровня позволит обрабатывать ДУ большей размерности,уменьшить затраты памяти и говысить скорость моделирования и генерации тестов.
- 8 -Метода реализованы в виде программных систем автоматизации проектирования и диагностирования Ш .отличающихся от известных лучшими эксплуатационными характеристиками , в частности расширением области применения,снижения требуемого объема памяти и увеличением производительности.
Реализация результатов.Представленные в диссертации результаты проводились в рамках следующих госОвджотных НИР Института прикладной математики и механики АН Украины:
"Разработать методы построения тестов для систоми базовых ТЭЗов и модификации структуры ТЭЗов с целью улучшения их диагиостируомости и выдать рекомендации организациям минавиапрома по их использова-нию"(1Э79-1981,Л Госрегистрации 79033304);
"Анализ непрерывных и дискретных систем с применением в задачах управления и оптимизации" (I982-I985.JS Госрегистрации 01820073577); "Разработать математические методы оптимизации управления с приложением в технической диагностике,транспортных и .технологических процессах" (I986-I989.JJ Госрегистрации 01.860.042947); "Исследование математических вопросов теории цифровых устройств и создание программных систем их контроля и диагностирования"(1990-1993,* Госрегистрации 01.9.00.018.556). .
Кроме этого разработка и внедрение результатов проводились
при выполнении следующих хоздоговорных работ:
"Разработка алгоритмов и системы математического обеспечения для
моделирования и диагностики цифровых систем"(1982-1984,5420673.
06004-01), .
"Внедрение алгоритмов и системы математического обеспечения для моделирования и диагностики цифровых устройств" (I984-I987.J* Госро-гистрации 01840084752), "Разработка модоЛей,алгоритмов и математического обеспечения диаг-
- 9 -юстирования цифрових устройств" (I987-I989.J6 Госрегистрации 01.870. 055.678), заключенных между Саратовским производственным объединением им.С.Орджоникидзе и Специальным конструкторско-твхнологическим бюро систем управления ИПММ АН Украины;
"Исследование мотодов,алгоритмов п разработка программного обеспечения контроля и автоматизированного поиска неисправностей МСВТ" (I989-I990,J* Госрогистрации 5540107.00045),заключенного между Мос-копским НИИ Научный центр и Специальным конструкторско-твхнологическим бюро систем управления ИПММ АН Украины.
На основе предложенных в диссертации методов и алгоритмов под руководством и непосредственном участии автора разработаны программные системы моделирования и генерации тестов.Первая автоматизированная система моделирования и диагностики (АСМИД) реализована на ЕС ЭВМ,вторая (АСМИД-П) на персональных компьютерах IBM PC/AT.Апробация и эксплуатация этих систем показала их высокую эффективность. Система АСМИД использовалась при построении тестов для нескольких сот цифровых плат устройств вычислительной и измерительной техники,бортовой,промышленной и шахтной автоматики в Саратовском производственном объединении им.С.Орджоникидзе , НИИ Научный центр (Зеленоград) и некоторых других предприятиях.Экономический эффект от внедрения методов и алгоритмов,разработанных в диссертации составляет болев 800 тыс.руб. в год.
Система моделирования АСМИД-П используется в Донецком государственном университете в учебном процессе.Научные и практические результата диссертации применяются при чтении автором курсов лекций в Донецком государственном университете "Моделирование вычислительных систем" и "Техническая диагностика цифровых систем ". Соответствующие документы о внедрении приложены к диссертационной работе.
Апробация работы.Основные положения и результаты диссертации
- 10 -были представлены на III,IV,VI,VII Всесоюзных совещаниях по технической диагностике(Минск-1975г.,Черкассы-1979г. , Ростов-на-Дону-1987г., Саратов-1990г.) ; IV Всесоюзной конференции " Однородные вычислительные системы и среда"(Киев-1975г.); III,IV,VII.VIII,IX, XI,XII международных конференциях "Системы,допускаищиэ неисправнос-«i"("Fault tolerant .systems and dlagno3tlc3":KaT0Bmie-I980r.,EpHO-1981г. ,София-І984г. ,Катовицо-І985г. ,Ерш-І98Єг. ,Зуль-І988г. ,Прага-1989г.);Международной конференции "Микроэлоктроиика-1984" ( Прага-1984)всесоюзном семинаре "Контроль изделий микроэлектроники и применение микропроцессорных средств вычислительной техники "(Цахкад-зор-1984г.);Республиканской конференции "Проблемы диагностирования микропроцессорных систем"(Ужгород-1987г.)республиканской конференции "Автоматизация контроля вычислительных устройств и систем"(Вин-ница-1988г); Всесоюзном семинаре по дискретной математике (Москва-1989т)всесоюзной конференции"Диагностирование,надежность,нэразру-шающий контроль электронных устройств и систем" (Владивосток-1990г); XV Всесоюзной школе-семинаре по технической диагностике (Туапсе-1990т); XI Всесоюзной конференции "Проблемы теоретической кибернетики" (Волгоград-1990г.); Международной конференции но информатике ("Inrormatlk-Pachberlchte",Stuttgart-)990);Ha общемосковском семинаре по технической диагностике;научном семинаре лаборатории тех-, нической диагностики ИПУ (Москва);семинаре "Техническая диагностика управляющих и вычислительных машин" Института проблем моделирования в энергетике АН Украины (Киев); семинаре " Методы и средства технической диагностики" СГУ (Саратов); семинаре "Дискретные системы и формальные языки" ИПММ АН Украины (Донецк) , а также на ряде республиканских и.региональных конференций и.семинаров.
Публикации.Основные научные результаты опубликованы в 45 печатных работах, включая 2 монографии,из которых 20 выполнено в со-
- II -авторстве.
Объем работа.Диссертация,изложенная на 275 страницах .состоит из 9 разделов,списка литературы из 178 наименований и приложения,в котором представлены акты о внедрении и использовании результатов.