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

"•> - '/" ! ' '' . /: г' ' I •

АКАДЕМИЯ НАУК УКРАИНЫ Институт проблем моделирования в энергетике

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

УДК 681.326:621.317

Грсмальский Анатолий Александрович

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

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

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

Кчев 1992

Работа выполнена в Кишиневском Политехническом Институте

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

д-р. технических наук, проф. Байда Н. П., д-р. технических наук, проф. Гуляев В. А., д-р. технических наук, проф. Тоценко В. Г.,

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

Киевский Политехнический Институт

Защита состоится И Н? Н ^ 1992 г. в ^ часов на заседании Специализированного Совета Д 016.61.01 Института проблем моделирования в энергетике Академии наук Украины по адресу:

252680, г. Киев-!64, ул Генерала Наумова, J5.

Отзывы на автореферат диссертации, заверенные печатью

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

Автореферат разослан ^ 1992 г.

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

кандидат технических наук Семапша Э. П.

■ЗТгПЗИ

Ai

TAv'-fl 5ртаций

-з-

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИОННОЙ РАБОТЫ

Актуальность проблемы. Рост сложности и ответственности задач, решаемых с помощью дискретных устройств вычислительной техники и систем управления, предъявляет высокие требования к надежности и достоверности их функционирования. Качество, надежность и достоверность современных дискретных устройств (БИС, СВИС, микропроцессоры и изделия на их основе) о значительной степени определяются возможностями существующей теории в соответствующих программно-аппаратных средств для их контроля .и диагностики.

К настоящему времени сложилось два подхода к контролю и диагностированию дискретных устройств. Первый основан па построении детерминированых (регулярных) тестов для заданного класса неисправностей дискретных устройств. Теория, методы и алгоритмы детерминированного подхода к контролю дискретных устройств изложены в работах Пархоменко П. П., Гулаева В- А., Клисторина И. Ф., Немолочного О. Ф., Байда Н. П., Савченко 10. Г., Тоценко В. Г., Шаршунова С. Г., ШеГшаускаса Р., Савдяна Г. А., Убар P. P., S. Thatte, Y. Abraham, M. Breuer, A. Friedman, I. Levendel, P. Mennon, S. Su, T. Lin и др. Несомненными достоинствами детерминированного подхода является компактность получаемых тестовых воздействий, точность и однозначность критериев качества соответствующих методов контроля. К недостаткам детерминированных методов контроля относятся сложность и трудоемкость алгоритмов построения регулярных тестов, жесткая ориентация на заданный класс неисправностей, высокая стоимость систем контроля.

Второй подход к контролю и диагностике дискретных устройств включает методы стохастического контроля и основан на использовании псевдослучайных (случайных) входных воздействий. Ряд важных теоретических и прикладных результатов в рассматриваемой области получен в работах Романкевича А. М., Барашко А. С., Ярмолика В. И., Жукова М. В., Вейцмана И. Н., Боршевича В. И., R. David, Р. Thevenod - Fosse, Е. McCluskey, К. Parker, V. Agrawal, Е. Eichelberger, • J. Savir, H. Wunderlich и др.

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

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

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

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

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

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

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

Задачи исследования. Для достижения поставленной цели небходимо решить следующие задачи:

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

- исследование и разработка алгоритмов синтеза, порождения н оценки качества тестовых последоштельностей, • задаваемых однородными цепами Маркова;

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

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

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

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

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

Автор защищает:

- основную концепцию псевдослучайного функционального контроля

-вс помощью тестовых последовательностей, описываемых одно- и миогосвязпыми цепями Маркова;

- теоретические основы, методы и . алгоритмы синтеза псевдослучайных тестовых последовательностей по различным моделям дискретного устройства: логическая сеть, граф переходов-выходов, описание на языке регистровых передач, структурно-функциональный граф ' пли граф информационной связности;

- критерии, методы и алгоритмы оценки качества псевдослучайных тестовых последовательностей, задаваемых однородным» цепями Маркова;

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

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

- структуру, принципы и алгоритмы функционирования систем имитационного моделирования процессов псевдослучайного функционального контроля дискретных устройств;

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

Связь с государственными программами и НИР. Результаты, изложенные в дисертации, получены в процессе исследований и разработок, осуществленных в соответствии с координационным планом научно-исследовательских работ АН СССР по проблеме 1.12.8 «Измерительные процессы и системы», раздел 1.12.8.3 «Теория и методы построения измерительных информационных систем», тема «Автоматизирование системы проектирования контроля и диагностики микропроцессорной техники», N ГР 01860022457, а также хозяйственных договоров ( НИР N ГР 81013731, 01840004673, «Диагностика - 90», «Система - 91»).

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

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

Реализация результатов диссертационной работы. Результаты теоретических исследований нспользсвапы при создании математического и программного обеспеченна систем контроля цифровых блоков; микропроцессоров ц шжропродессоршлх комплектов, при разработке структуры ряда систем стохастического контроля п имитационного иодслпровшшя дискретных устройств. Результаты днсссртгцношгсш работы вледрспы ги ряде предприятий г. Кишинева, Одессы, Новосибирска. Экономический гффскт от впсдрешш результатов диссертационной работы составил 600 язе. рублей в год.

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

По защтипемому научному паправлгнгао под руководством автора подготоплекпи л успешно ззздпщепи 3 кан/игдагекпе диссертации.

Апробация работы. Осгюшшс волохеппя п результаты диссертационной работы были предегаплепш и одобрены на Международном симпозиуме 1МЕКО (г. Паи, ГДР, 1986), па международном ссмшгарв по проблеме реализации комплексной программы НТП страа - членов СЭВ до 2000 года (г. Кишинев, 1937), па Всесоюзной НТК «ИИС - 81» (г. Львов, 1981), на Всесоюзной НТК »Автоматизация проехтнроватшя микропроцессорной аппаратуры» (г. Москва, 1953), па Всесоюзной НТК «Ш1С - 85» (г. Винница, 1985), па V Всесоюзном остозиумс по модульным информационно вычислительным сястемам (г. Кишинев, 1985), па Второй Всесоюзной конференции «Физические основы надежности и деградации полупрозодпикозых приборов» (г. Кистие-в, 1956), иа Всесоюзной школе-ссмширг «Надежность и безопасгость технических средств п программного обеспечения гибких пропзгодстеипых систем РЭЛ» (г. Мосхва, 1986), из научно-техническом семинаре «Вероятностные методы тестпровапяя» (г. Мнисг, 1987), иа НТК «Проблемы диагностирования микропроцессорных систем» (г. ' Ужгород, 1987), йа Всесоюзной НТК «ИИС - 87» (г. Ташкент, 1987), ка Всесоюзном совещашш по

технической диагностике {г. Ростов; 1987), на Всесоюзной конференции «Теория и практика построения интеллектуальных интегрированных систем автоматизированного проектирования РЭА и БИС» (г. Алушта, 1987), ш Всесоюзной школе - семинаре им. Ы.' А. Гаврилова «Развитие теории дискретных систем и проблемы логического проектирования СБИС» (г. Кишинев, 1988), на III Всесоюзной НТК «Техническое п программное обееяечелие. комплексов полуиагуршго моделирования» (г. Москва, JOSS), на Всесоюзной НТК «.Методы синтеза топовых модулышх спстеы обработки данных» (г. Москва, 1988), ш Ш Всесоюзной конференция «Физические основы надежности а деградации полупроводниковых приборов» (г. Кишинев, 1991), а также на раде других конференций, совещаний и семинаров.

По теме диссертации опубликованы 74 научные работы, включая 20 авторских свидетельств СССР на изобретения, 1 монография и 1 учебник для ВУЗ-ов.

Структура и объем диссертации. Диссертация состоит кз оведеишг, шести глав и заключения, содержание которых наложено на 342 j страницах, списка используемой литературы, включающего 341 наименований, приложения с актами о внедрении, иллюстрирована 59 рисунками.

Автор выражает искрешом благодарность члеиу-корреспондеигу Академии наук . Республики Молдова, Заслу*;сшюму деятелю наука Республики Молдова, д. т. н., профессору Клисгорнну И. Ф. за помощь и поддержку, оказанную км в процессе проведения научных исследований по тематике диссертационной работы.

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

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

Первая елааа диссертационной работы посвящена анализу

-о-

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

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

Обозначим через X = { , Хч, Л1,, } ыпожество входных епшешов дискретного устройства, а через « - та ало таких символов. Множество всевозможных входных последовательностей длины Л' обозиачш через Т. Любая входная последовательность Т;, Т^Т, имеет вид ...

Г, Х^..... Хк), ...,Хкн>, (1)

гае Х/: - любой входной символ дискретного устройства, т. с. А'^еХ ; ( - дискретное время; N - длина последовательности. При стохастическом тестарокипш " выбор ( генерация, порождение ') конкретной последовательное!!! Т{ определяется версагпоСшыми. характеристиками соответствующего механизма порождения тестовых последовательностей. В частности, при неуправляемо!! псевдослучайной ■ генерации все последовательности Т1, Г(6Т, являются равновероятными.

С целью • повышенна эФФскгвшосгп стохастического коптроля представляет гаггерсс породденпе таких псевдослучайных последовательностей ' Т/, для которых полпота коптроля р; относительно некоторого заданного класса пеиспрашюстсй Р превышает требуемый порог р3 ., Друп!ми словами, процессом порождения псевдослучайпых тестовых последовательностей необходимо управлять в том смысле, что вероятность порождения псевдослучайных последовательностей с высокой

полнотой контроля должна быть больше, чем вероятность пороаденля остальных последовательностей. Для порождении псевдослучайных тестовых последовательностей вида (1) воспользуемся вероятностным автоматом М - <£, Р, Я®, Х>, хде - множество состояний автомата;

Р - || рц || „,„ - матрица переходных вероятностей; рц - вероятность перехода из состояния в состояние 5/; Р** ■ || р* || „ - вектор начальных вероятностей; - начальная вероятность состояния ^ ;

X - {^у - выходной алфавит пероятностного автомата. Каждому состоянию вероятностного автомата соответствует выходной символ Лд , являющийся одновременно входным символом контролируемого устройства. Необходимо подчеркнуть, что алфавит К включает только входные символы, которые, исходя из закона функционирования дискретного устройства, це вызывают его цедетеришшрованкого поведения. Следовательно, вероятшетаый автомат М порождает на своем выходе одыосвязную однородную цепь Маркова < X, Р, >, состоящую из функционально допустимых входных символов дискретного устройства.

Для заданной цепи < X» Р, Р° > некоторые последовательности являются более вероятными, чем остальные. Обозначим множество более вероятных последовательностей (назовем их типичными) - через Тт , а менее вероятных (назовем их иетипчпыыи) • через Тнт . . В диссертационной работе показано, что при порождеиии псевдослучайных тестовых последовательностей с помощью вероятностного автомата' !Я математическое ожидание полноты коптроля

2тт

МЮ-^тЪ-фщ 2 р„ . . (2)

где ЩР) - энтропия матрицы переходных вероятностей Р. Формула (2) показывает, что при псевдослучайном функциональном контроле математическое ожидщще полноты контроля р есть средиее значение полноты типовых последовательностей Тт . Таким образом, задача синтеза псевдослучайных тестовых последовательностей сводится к поиску такой стохастической матрицы Р и вектора начальных вероятностей Р° , при которых множество типичных последовательностей Тг включало только последовательности, обеспечивающие требуемую полноту контроля, причем энтропия матрицы переходных вероятностей Н(Р)-*0.

Аналогичным образом, при генерации многосвязных последовательностей, псевдослучайная тестовая последовательность (I) рассматривается как некоторый процесс, задаваемый г-связной цепью Маркова вида < К, Рп<г> >, где Рп<г> " || || - матрица порядка п*п

переходных вероятностей; /yj - вероятность порождения символа Xi прн условии, что я предыдущих г-тагах на дискретное утройство подавалась цепочка символов < Х^ , Х^ >, У" < , fc, >.

Естественно, при г « 1 цепь становится одвосвязяоП.

Многоспязные тестовые последовательности порождаются с пог.ощью вероятностного автомата M - < , Cnlr* , X >, где - множество состояний автомата, совпадающее с множеством сложных событий, связывающих две цепочки выходных символов длины г ; Сп(г> - матрица переходных вероятностей односвязной цепи Маркова для сложных событий. Следует подчеркнуть, что порождение очередного тестового воздействия Х^ , t - I, 2, ..., N, выполняется за время одного перехода

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

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

Предположи?!, что обьект , контроля ' задается с помощью абстрактного еильпосвязиого конечного автомата А » < X, Z, Y, ô, X >, где X - входной алфавит, Z - мпокество гшутрешшх состояний; Y -выходной алфавит; <к X*Z-*Z - функция переходов; Л: X*Z-*Y -функция пыкодоа. Синтез псевдослучайных тестов выполняется по неявной модели, при которой рассматривается только исправный автомат, а моделью неисправностей являются любые искажении таблицы (графа) нереходОЕ-вшодов. С целью спикешн трудоемкости процедур синтеза, в работе используется пшотеза Ii. Tellcz-Giron к R. David, в соответствии с которой автомат считается проверенным, если каждый переход между любыми двумя состояниями выполнен хотя бы один раз. При синтезе псевдослучайных тестов, в качестве -оптимизируемого критерия предлагается использовать математическое ожидание отношения чиста выполнены* переходов к^ к пх общему чпелу к, т. с. величину M(i}*M(k0rJk).

Для анализа стохастических • процессов, совместно протекающих п генераторе тестовых воздействий - вероятностном автомате ГЛ н объекте коытроля - детерминированном автомате А, в диссертационной работе вводится операция композиции автоматов M я А. Результатом операции композиции являеея цепь Маркова < U, Q, çP >, множество состояний U - {и,-} которой сов-адает с множеством переходов автомата А. Стохастическая матрица Q и вектор начальных вероятностей <2°

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

Утверждение I. Пусть Г - псевдослучайная последовательность, порождаемая вероятностным автоматом М, причем (Р * <2* . Тогда

Щу)~7 2 П-О-^Уь »)

* /-1

где ■■ || д,* || к - финальные вероятности цепи <£/, С, (2° >.

Утверждение 2. При произвольном векторе начальных вероятностей 0° , малых и достаточно больших # критерий качества

I И-а(4)

А

Утверждение 3. Для больших // и малых критерий качества М(у) достигает своего максимального значения при равновероятности выполнения переходов и} , т. е. др н <12^ " — " " 1/А.

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

равномерному, ие обеспечивает максимизации критерия качества М(V).

На основе доказанных утверждений, в работе предложены алгоритмы поиска стохастических матриц Р, обеспечивающих оптимизацию критерия М(у). Опытная эксплуатация программ, реализующих предлагаемые алгоритмы, показала, что наиболее эффекпшкой является ' стратегия дискретного глобального поиска. Время получения стохастических матриц Р при к 5 200 находится в пределах от 15 до 3 час (ЭВМ СМ1420, язык программирования - ФОРТРАН).

В случае, если обьект контроля задается синхронной логической сетью А, синтез псевдослучайной тестовой последовательности выполняется по комбинационному эквиваленту Кг получаемому путем многократного (I раз) повторения комбинационной части К схемы А. При этом псевдослучайная тестовая последовательность Т представляется в виде

т.- ту II ту 11 ... II Т/, Г/ - <Х0, Х1г, .... Хк>, (5)

где || - знак конкатенации; г - чисто испытаний; А"о - установочный (детерминированный) набор; Х^, ..., - псевдослучайные тестовые

воздействия. Фрагмент Т/ псевдослучайной тестовой последовательности Т

порождается поразрядно с помощью семейства вероятностных автоматов {Му> вида

Г>1у « < Я, {0, 1}, {/</(0/^), /<у(1/^)} >, (б)

где 5 = { , 5|, й}} - множество состояний вероятностного автомата; {О, 1} - выходной алфавит автомата; ^(О/яр - вероятность порождения выходного символа "О" при условии, что вероятностный автомат находится в состоянии ^ ; ;1у(1/%) - условная вероятность порождстш выходного символа "1".

В работе предложены способы построения семейства вероятностных автоматов {ГЛу}, основанные па вычислении входного вероятностного распределения Р =» ¡] р' ¡!, / = 1, 2, .... I, комбинационного эквивалента ¡С' с помощью топологических методов синтеза стохастических тестов комбннашгопных схем. Получены также выражения, позволяющие определись число испытаний г и длину N псевдослучайной тестовой последовательности, обеспечивающей полноту контроля не менее р3 :

_^-р»)_: (7)

т-1а[1-Рг(/тЫ, 01' и'

N й ]л (1 ~ ¿о, ) , (8)

гда а , I) - вероятность обнаружения наихудшей неисправности

комбинационного эквивалента Кг последовательностью Т ; X - константа псевдослучайного тестирования комбинационного эквивалента.

Опытная эксплуатация пакета прикладных программ, реализующего сшгтсз псевдослучайных тестогых последовательностей по комбинационному эквиваленту показала, что время построения теста ие превышает одного паса (СМ 1420), а управление процессом геперации уменьшает длину тестовой последовательности на два-три порядка.

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

G(L, V), множество вершин L которого соответствует операторам программы, а множество ребер V - связям операторов по управлению. Разметка ребер выполняется в соответствия с логическими выражениями из операторов условного перехода. Для каждого пути q, q&Q, где Q -минимальное множество путей, покрывающих граф G(L, V), составляется система булевых уравнений U4 , решения которой содержат всевозможные управляющие' последовательности, активизирующие операторы рассматриваемого пути.

Множество состояний S, стохастическая матрица Р и вектор вероятностного автомата М получаются путем подсчета соответствующих частот непосредственно по множеству Xg управляющих последовательностей дискретного устройства.

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

Основное преимущество предлагаемого подхода заключается о формализации процедуры : синтеза псевдослучайных тестовых последовательностей . и в возможности совмещения процедур синтеза с процессами проектирования дискретного устройства, что ведет к сокращению сроков их внедрения в производство. С помощью предлагаемых алгоритмов были получены вероятностные автоматы и сгенерированы псевдослучайные тестовые последовательности для микропроцессорных СБИС серий 1802, 1804, 5S0, 589. При этом число состояний соответствующих вероятностных автоматов находится в пределах, от 16 до 256,. а время составления матрицы переходных вероятностей -от 10 мин до 5 час (ЭВМ CMI420). Полнота получаемых тестовых последовательностей изменяется в пределах 95-100% для класса функциональных неисправностей к в пределах 85-98% для неисправностей =0, sl. .

Синтез псевдослучайных тест-программ микропроцессорных устройств основан на представлении объекта контроля с помощью одной из графовых моделей - структурно-функционального графа G(Р, W) или графа информационной связности G(E, V). Структурно-функциональный граф моделирует микропроцессор по принципу «серого ящика», причем множество F включает вершины, соответствующие основным узлам объекта контроля, а именно, регистрам, мультиплексорам, демультиплексорам, АЛУ и т. п. Множество ребер W отражает информационные связи между актетсип-юшими, иолможио гипотетическими устройствами микропроцессор).

При представлении микропроцессора графом информационной связности С(Е, V), множество Е включает вершины, соответствующие командам микропроцессора, а также входным и выходным магистралям. Множество ребер К отражает информационные связи (связи по данным) между командами микропроцессора. Очевидно, п>аф С(Е, V) моделирует микропроцессор по принципу «черного ящика» к может быть построен непосредственно по описанию микропроцессора на уровне выполняемых команд.

Псевдослучайная односпязная тест-программа Т порождается с помощью вероятностного автомата М = <S, Р, />, где J -

множество команд контролируемого макропроцессора. Стохастическая матрица Р и вектор Я® гшлуч?к»тся путем подсчета частот вида ру* по минимальному множеству путей Q, покрывающих граф С(F, W) или G(E, V). Частоты рф могут также определяться по имеющимся прикладным программам, которые будут выполняться на рассматриваемом типе микропроцессора либо по детерминнроаашшп тест-программам, составленным для так называемых «труднообнаруживаемых» неисправностей.

С целью снижения трудоемкости процессов синтеза псевдослучайных тест-программ, а также сложности соответствующих ¡ероятностпых автоматов в диссертационной работе рассматриваются вопросы разбиенич множества <оманд J на классы эквивалентности и порождения псевдослучайной тест-программы 7 с . помощью двух, каскадио-соедннснных вероятностных автоматов М' к М". При этом вероятностный автомат М' порождает псевдослучайную последовательность кодов классов эквивалентности, а автомат М* для каждого кода, в соответствии с полученными в процессе сяктезз условными вероятностями, порождает кома!зды из соответствующего класса.

При синтезе . многоспязных псевдослучайных тест-программ последовательность Т рассматривается как некоторый процесс, задаваемый r-свазпой цепью Маркова вида <!, РпГ>>. Диалогично случаю односвязных тест-программ, с целью снижения размерности задач синтеза я порождения тестовых воздействий, множество команд' / разбивается на классы эквивалентности.

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

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

М - <5, Р,

исправном объекте контроля - детерминированном автомате А° *" <Х, 2° , V0, «5°, Я0

> и неисправном объекте контроля - детерминированном автомате А-^ - <Х, т! , Н1, </, х! > , в работе вводится понятое вероятностного наблюдателя. Вероятностный наблюдатель автоматов

М. А0

и А' представляет собой поглощающую цепь Маркова <(/, , ф >, множество состояний (/ которой, соответствует всевозможным парам переходов автоматов А° и А', а стохастическая матрица $ и вектор $ определяются функциями переходов <5° и д?, стохастической матрицей Р и вектором Р® . Следует подчеркнуть, что понятие «вероятностный наблюдатель» обобщает понятие «автомат латептностп ошибки», введенной Е. МсС1и5кеу, па случай тестовых последовательностей, порождаемых марковскими вероятностными автоматами. Вероятностый наблюдатель <!/>(/> представляет

собой математическую модель процессов порождения псевдослучайной последовательности Г вероятностяыы автоматом М, ее отработки автоматами А0 , А' и принятая решения по результатам сравнения отклика эталонного А0 и контролируемого А/ автоматов. При этом вероятностным характеристикам поглощающей цепи < (/, (¡?, > соответствуют вероятностные характеристика процесса псевдослучайного тестирования неисправности /,

В работе доказаны следующие' утверждения.

Утверждение 4. Математическое оленданае полноты контроля

М(р)=-щ Щ, . (9)

где Рг(/0,

//) - вероятность нахождения наблюдателя •« (У, , сР^ > па шаге N в поглощающем состоянии

Утверждение 5. Пусть класс • неисправностей Г содержит всевозможные одиночные искажения функции выходов X исправного автомата А0. Тогда математическое ожидание полноты контроля М(р) = М(у).

Следствие 5.1. При стационарных процессах генерации

М(р)=4 2 П-(1 -gffb U0>

* («i

Следствие 5.2. При нестационарных процессах генерации, малых qf и достаточно больших N

I [ 1 -(1 -qf f] . (11)

* («1

Следствие 3.3, Математическое ожидание полноты контроля

М(р) г I - (1 - min {gf))N. (12)

i

Длина псевдослучайной тестовой последовательности, обеспечивающей полноту контроля не менее р3

N* 1,1(1 . (13)

In (1-min {gf}) ■ I

К сожалению, попытки получения теоретических оценок вида (10)-(13) для класса. неисправностей F, включающего и искажения функшш переходов д, закончились безрезультатно. Поэтому, с целью проверки гипотезы о том, что критерий М( v) позволяет оценивать качество псевдослучайных последовательностей и в случае искажений функции переходов <5, исследовалась корреляция между критерии M(v) и полнотой р соответствующих последовательностей. Рассматривались автоматы, число переходов к которых удовлетворяло условию, kä200, Коэффициент корреляции между М( v) п р находится в пределах 0,90...0,98, что вполне приемлемо для оценки качества псевдослучайных последовательностей. Более того, при числе состояний автомата «а 10 и одиночных искажениях функции переходов <5, критерий M(v) находится в пределах доверительного интервала для полноты р, т. е. М(v)"=p.

Методы оценки' качества псевдослучайных тест-программ, синтетизированяых по графовым моделям С(Е,У), G(F,W) пли C(L,V) видоизменяются в зависимости от способов проведения контролирующих экспериментов.

Первый способ ориентирован на обнаружение неисправностей механизмов обработки, хранения, управления и передач» данных и заключается в следующем. Будучи запущен с начального состояния, вероятностный автомат М « <S, Р, Р® , 1> выполняет L^a переходов, где Lgax - число команд в наиболее длинном пути из множества путей Q. Далее автомат М опять запускается с начального состояния и т. д. Через .%'- обозначим число таких запусков, которые будем называть

-и-

испытаниями. Процесс генерации завершается при выполнении заданного числа испытаний. Вероятность того, что автомат М вырабатывает за одно испытание последовательность команд 1(у) т </* , //, 1т , ..., 1Т , ¡4 >, соответствующую некоторому пути д, 4Е& определяется хдк

к

Р{д) = 2 р^Р/кРиР1т -ры • <14>

/»1

Выберем такой путь ^^ , ?т1пе2- Для которого

Я(9т1п) - шт ?(?) . (15)

?е<2

В качестве критерия качества тест-программы Т, состоящей из т испытаний, выберем вероятность Рх' того, что путь покрывается

(т. е. генерируется последовательность Л<7Ш!П) ) хотя бы один раз. Очевидно, при таком выборе критерия качества, вероятность покрытия остальных путей будет выше чем Р/ .

Утверждение 6. При заданном значении Ра' критерия качестаа, требуемое число испытаний т определяется как

Второй способ, кроме неисправностей, контролируемых в первом способе, ориентирован также на обнаружение неисправностей типа «чувствительность к определенным последовательностям комацц». В рассматриваемом способе вероятностный автомат ГЛ запускается с начального состояния и выполняет N переходов, причем //>>£шах. Процесс генерации завершается при выполнении заданного числа переходов. В принципе, оценку качества тест-программ, получаемых при втором способе контроля можно осуществлять путем вычисления вероятностей генерации заданных «нелюбимых последовательностей», т. е. последовательностей команд, которые могут выполнятся неверно. Однако к настоящему времени не существует приемлемых методов нахождения таких последовательностей даже при наличии полной информация о внутренней структуре микропроцессора. Вместе с тем, при эксплуатации микропроцессора существенны лишь те «нелюбимые последовательности», которые могут встретиться в выполняемых программах, т. е. информационно связанные «нелюбимые последовательности». Другими словами, существенные «¡нелюбимые последовательности» находятся, как правило, среди информационно связанных последовательностей, что

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

Обозначим через вероятность покрытия пути </, т. е.

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

/

Рт « т!п Р(?). (17)

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

Утверждение 7. Если длина N тест-программы Т, порождаемой

вероятностным автоматом И, удовлетворяет условию ) -

N^-7--, 1г..+ I . (18)

^(<7гп1п) 1 ~

то се критерий качества Рт* г Р3*.

Утверждение 8. Для тест-программы Т, задаваемой «мягкой» цепью Маркова </, Р, 'Р^ >, значение ее критерии качества Рт" удовлетворяет приблюхепному равенству

Рт'-1-ехр1-^т1п)(Л'-Л+1)]. (19)

Следствие 8.1 Необходимая длина тест-программы Т с критерием качества Рт" , Рт"гР," , определяется из приближенного неравенства

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

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

имитационного моделирования на рабочей станции Metheus. В процессе имитационного моделирование проверялись следующие гипотезы:

- обладают ли системные и прикладные программы контролируемого микропроцессора теми же стохастическими свойствами, что и тест-программы, получаемые по графам C(F,W), G{E,V) и G(L.V);

- можно ли рассматривать системные и прикладные программы контролируемого микропроцессора ках многосвязные марковские процессы;

- существует ли корреляция между связанностью системных и прикладных программ и длиной пути в графах G(F,W), G(E,V) и G(L,V).

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

Правомерность применения предлагаемых критериев Р' и Р" исследовалась как статистическими методами, так и моделированием всевозможных логических неисправностей типа sO, si вентилей микропроцессоров INTEL8080, INTEL8085, INTEL8086, МС6800, МС68000. При моделировании соответствующие псевдослучайные тест-программы выполнялись на исправном и неисправном микропроцессорах, описанных на языке Hilo. В качестве операндов команд использовались ходы 00...000, 11...111, 1010...10, 0101...01, бегущий ноль, бегущая единица. В результате проведенных машинных экспериментов установлено, что степень корреляции между полнотой и критерием Рт' составляет 0,8...0,9. Для второго способа контроля дополнительно выборочно моделировались неисправности типа «чувствительность к определенным последовательностям команд», определяемые путем экспертных оцеиок. Степень корреляции между полнотой и критерием Р/ составляет 0,7...0,8 , что вполне приемлемо для оценки качества псевдослучайных тест-программ.

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

Четвертая гласа посвящена «следованию и разработке генераторов одно- и многосвязных тестовых последовательностей. Для построения генераторов цепей Маркова используется метод раздельного синтеза, при котором вероятностный автомат М состоит из первичного источника равномерно распределенных случайных чисел G я детерминированного автомата DA, обеспечивающего выполнение соответствующих переходов между состояниями s¡ , s,6S. Структура детерминированного автомата DA определяется из следующих рассуждений. Предположим, что на некотором

такте t вероятностный автомат М находится в состоянии 5/ . Состояние следующего (Ж) такта определяется вероятностным распределением рц, рд, Pin, т. е. строкой Р( стохастической матрицы Р. Переход в следующее состояние выполняется в соответствии с методом обратных функций. В указанном методе для каждого равномерно распределенного числа х, Osx<l, с выхода генератора G и вероятностного распределения Р( находится значение Л, Л6{1, 2, .... п}, при котором выполняется двухсторонее неравенство

А-1 А

1 Рц*х<2 Рц . (21)

/=0 /-1

гДе Р(0 " О. Полученное значение Л определяет код 5д следующего состояния вероятностного автомата М.

При псевдослучайном функциору^шм контроле дискретных устройств возникает необходимое. порождения тестовых

последовательностей, 'задаваемых матрицами переходных вероятностей Р, порядок которых достигает значений 100 ... 200. При этом объем памяти, необходимый для хранения сумм (21), резко возрастает, что затрудняет аппаратную реализацию соответствующих генераторов. Проведенные исследования показывают, что снижение требуемого объема памяти можно обеспечить путем учета следующих особенностей стохастических матриц, получаемых при синтезе псепдослрййных тестовых последовательностей :

- матрица Р является разреженной, т. е. содержит значительное число нулевых злеиеш'оо;

- матрица Р является квазиргзрез.'ешюй, т. е. часть элементов матрицы имеет одно и то же значение А, Д^О;

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

В диссертационной работе предложены способы компактного хранения и обработки стохастических матриц,. алгоритмы порождения псевдослучайных тестовых "последовательностей, а также структурные схемы соответствующих генераторов одно- и многосвязных цепей Маркова. В работе получены аналитические выражения, позволяющие оценить относительное сокращение q объема памяти, необходимого для реализации детерминированного автомата DA. В частности, для разреженных матриц относительное сокращение требуемого объема памяти 48Si;S91, для квазиразреженных матриц 86<f/£l64, а для стохастических матриц с повторяющимися элементами 75Sj/:S 162.

Временные параметры генераторов одно- и многосвязных

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

Назовем заданием пункты алгоритма,- одновременное выполнение которых требует отдельных временных затрат устройства управления. В общем случае заданиям» являются микрооперации присваивания, анализа условий выполнения переходов, запуск других микропрограмм, ожидание завершения параллельно выполняемых микропрограмм а т. п. Представим анализируемый алгоритм в виде граф:!, называемого в дальнейшем граф-схемой заданий. Каждому заданию алгоритма соответствует некоторая вершина V/ граф-схемы. Вершина V/ характеризуется парой ("М/ ,£>;), где М[ - математическое ожидание, а О; - дисперсия времени выполнения заданна ¿ Передача управления от одного задания к другому моделируется с помощью дуг граф-схемы. Каждая дуга отмечается вероятностью перехода по данной дуге или, в случае циклов, функцией распределения вероятностей случайной величины - числа выполнений цикла.

В общем случае в граф-схемах заданий можно выделить следующие типы элементарных отношений между вершинами: последовательное выполнение, альтернативное выполнение, циклическое выполнение (с вероятностью Р(к) цикл выполняется к. раз, к а 0, 1, 2, ..., т ; Р{к > т) = 0). Введем в рассмотрение операцию склеивания верпнш граф-схем заданий. Склеивание осуществляется заменой каждого элементарного отношения одной вершиной с эквивалентными характеристиками. Справедливы следующие утверждения.

Утверждение 9. Характеристики И и £) вершины v, полученной в результате склеивания двух последовательных верпнш v] и у2 , определяется как

М М\ + ; Ь ■= + 1>1 ... <22)

Утверждение ¡0. Для альтернативных вершин V] п

М ■ Р|М1 + р2А/2 ;

О - + + РМШ\ - М2)2 > ■ (23)

где Р1 и р1 - соответственно вероятности перехода к вершине ми

Утверждение 11. Характеристики M « D вершины v, полученой в результате -склеивания циклической вершины уц , находятся как M — Мх(к<*тУ и D" Dj^k^m), где Dz(k) определяются

реккурентно:

- Pz(k- 1) + Р(к)-

ад - ^W"1) + ; «■«>

Таким образом, временные характеристики M (г) и £>(т) определяются путей последовательного склеивания вершин граф-схемы заданий, представляющей алгоритм функционирования изучаемою дискретного устройства. На основе разработанцого метода определены временные характеристики генераторов и. предложены способы повышения их быстродействия. В частности, при разреженной стохастической матрице М(г) 27.5Д и D(r) •» 191.25Д2 ; при квазнразрежешюй матрице М(г) » (40...100)Д, D(r) ■ <900...2000)Д2 ; для ыатр1Щ с повторяющимися элементами M (г) " <12...1С0)Д и D(r) » (80...600)Д2 , где Д -длительность такта устройства управления. Относительное повышение "быстродействия' предлагаемых генераторов, по сравиешпо с известными, составляет у - 2,5—7,6 раза.

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

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

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

Предложены и исследованы специализированные процессоры вентильного событийного моделирования дискретных устройств, реализующие двухпроходиой алгоритм троичного моделирования с единичными задержками. Специализированный процессор представляет собой конвейер, включающий следующие блохи: обновления (Б1), памяти индикаторов активности элементов (Б2), поиска активных элементов <БЗ), троичного моделирования элементов (Б4), поиска последователей элементов (Б5). Для временного согласования работы блоков специализированного процессора, на сход каждого блока Б1, Б4 1; Б5 включается входная буферная память типа «первый пришел - первый вышел».

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

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

вероятносгь отказа в передаче сообщений.

На основе полученных теоретических результатов разработана система функционального моделирования дискретных устройств, ядром которой являются восемь процессоров типа МС-1280. Производительность предлагаемой системы составляет 3700 - 3800 компонент в секунду. Моделирование цифровых устройств, построенных на базе наиболее распространенных серий микропроцессорных БИС, показало, что скорость моделирования составляет в среднем 800 - 900 наборов в секунду. Достигнутая производительность позволяет решать большинство задач, связанных с псевдослучайным функциональным контролем дискретных устройств.

Шестая глава диссертационной работы посвящена попросам практической реализации результатов" теоретических исследований. Практическая значимость предлагаемо«' концепции псевдослучайного функционального контроля подтверждается созданием специализированных технических средств, непосредственно обеспечивающих проведение диагностирующих экспериментов с объектом контроля: формирователь одно- и М1ЮГСС15ЯЗПЫХ псевдослучайных тест-про грамм, устройства (тестеры) для контроля микропроцессорных СБИС, ,и тоыатизнрованные системы контроле и диагностики цифровых устройств.

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

Структуры предлагаемых технических средств для псевдослучайпого функционального контроля дискретных устройств защип пял 11 авторскими свидетельствами на изобретения. Реальный экономический эффект от внедрения результатов диссертационной работы в промышленности составляет 600 тысяч рублей. Акты о внедрении приведены в приложение к диссертационной работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

При решение указанных задач получены следующие результаты:

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

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

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

длипу псевдослучайной тестовой последовательности, обеспечивающей заданную полноту коатроля.

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

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

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

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

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

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

10. Предложены и исследованы специализированные процессоры для имитационного параллельного моделирования процессов псевдослучайного функционально.!) контроля дискретных устройств. Разработаны методы и

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

И. Результаты теоретических п экспериментальных исследований использованы при создании формирователей одно- и ■ мпогогвязных тестовых последовательностей, устройств (тестеров) для контроле микропроцессорных СБИС, автоматизированных систем псевдослучайного функционального контроля.

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

ОСНОВНЫЕ ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Клисторип II. Ф., Гремальсхий Л А, Сскрисру И. Г. Организация мультипроцессорных шюгоиостовых автоматизированных систем контроля радиоэлектронной аппаратуры // Всесоюзное совещание «Высокопроизводительные в и числительные системы»: Тез. докл. - Москва, Институт проблем управления, 1981. - Том 3. - С. 23-25.

2. Клисторип II. <!>., Грсмальстй А, А., Сскриеру II.- Г. Мультипроцессорные авго.магизнровашше системы контроля радиоэлектронной аппаратуры П Всесоюзная конференция по измерительным информационным системам ИИС-81: Тез. докл. - Львов, 1981. - С. 17-19.

3. Клисторип Л. Ф., Грелильский А. А, Секриеру ' II. Г. Многопостовая автоматизированная система контроля качества п диагностики больших интегральных схем // Первая Всесоюзная конференция «Физические основы . .надежности и деградации полупроводниковых приборов»: Тез. докл. - часть 1. - Кишинев, 1982. -С. 81.

4. Гремальский А. А., Паскарь А. Д. Система программного обеспечения для моделирования цифровых устройств на микропроцессорных БИС // Всесоюзное научно-техническое совещание «Автоматизация проектирования мнкрозлектронной аппаратуры». - Тез.

докл. - Москва, 1983, - С. 38.

5. Гремапъский А А, Клисторип И. Ф. Построите различающих последовательностей синхронных цифровых устройств П Электронное моделирование. - 1984. - N б. -С. 49-53.

6. Грсмапьскш% А А, Станчу II. И. Аппаратная реализация алгоритмов моделирования в ИИС контроля цифровой РЭА // Всесоюзная иаучно-техп. конференция «Информационно-измерительные сисгемы-85» (1ШС-85): Тез. докл. - Винница, 1985. - С. 121-122.

7. Грелмльский А А, Станчу И. II. Мультипроцессорная ипформагнюнно-вичкопгтелыгая система // Всесоюзный симпозиум по модульным информационно-вычислительным системам*. Тез. докл. Кишинев: Штшгаца. - 1985. - С. 65-66.

8. Клисторип II. О., Бсрщсвич В. II., Гремапъский А А Алтоматизнросашшй контроль микропроцессорных средств И В С // Всесоюзный симпозиум по модульным информационно-вычисиггельным системам: Тез. докл. - Кишинев: Штшгаца. - 1935. - С. 94-95.

9. Klistorln !. &, Borshchevich V. I., Cremalsky A. A. Intelligent test system for microprocessor-boards // 5th International IMEKO Symposium: Intelligent Measurtment. - Fridrich-Schilerr - University JENA, GDR, 1986. -P. 7.

10. Клисторип И. Ф., Гремальский А А, Андроник С. М. Генерация тестовых программ для контроля БИС // Вторая Всесоюзная конференция «Физические основы надежности и деградации полупроводниковых приборов»: Тез. докл. - Кишинев, 1986. - часть 2. -С. 129.

11. Гремальский А. А, Станчу И. И., Секриеру И. Г. Анализ систем- моделирования интегральпых схем И Вторая всесоюзная

' конференция «Физические основы надежности и деградации полупроводниковых приборов»: Тез. докл. - Кишинев, 1986. - пасть 2. -С. 171. •

12. Гремальский А А. Функциональный псевдослучайный контроль . цифровых устройств // Системы автоматизированного проектирования в

ыапяшо- и приборостроении: Тез. докл. научно-практической конференции. - Кишинев: АН МССР. - 1986. - С. 104-106.

13. Гремаг.ъекий А А, Андроник С Ai. Генерация тестовых программ для микропроцессоров с помощью цепей Маркова // В сб.: Исследования новых микроэлектронных приборов п устройств. - Кишинев: Штиинца. - 1987. - С. 96-98.

14. Гремальский А. А, Андроник С. И. ИИС псевдослучайного функционального контроля цифровых устройств // Всесоюзная научно-техническая конференция «Измерительные информационные

системы» (ИИС-87): Тез. докл.- Ташкент, 1987. - С. 86.

15. Клисторин И. Ф., Гремальсгий А. А. Система программно-аппаратного моделирования цифровых устройств // Всесоюзная конференция «Теория ц' практика построения интеллектуальных интегрированных систем автоматизированного проектирования РЭЛ и БИС»: Тез. докл. - Москва, 1987. - С. 35.-36.

16. Гремальский А. А., Андроник С. М. Управляемая генерация тестовых программ при контроле микропроцессоров // Известия Академии Наук Молдавской ССР. Серия фнзико-тсхиичсскнх в математических наук - 1987. - N 2. - С. 70-73.

17. Клисторин II. Ф., Гремальский А. А, Стаичу И. II. Программно-аппаратная система моделирования микропроцессорных устройств // Республ. научи.-техи. хонф. «Проблемы диагностирования микропроцессорных систем»: Тез. докл. - Киев, 1987. - вып. I. - С. 20-22.

18. Гремальский А. А., Андроник С. М. Функциональный псевдослучайный контроль микропроцессоров // Респ. шучп. техн. гонф. «Проблемы диагностирования микропроцессорных систем»: Тез. докл. -Киев, 1987. - вып. 2. - С. 12-13.

19. Гремальский А. А, Андроник С. М. /изтоштщпрованияц система псевдослучайного функционального контроля микропроцессорных устройств // Республ. шучн.-техн. коиф. «.Системы контроля параметров электронных устройств и приборов»: Тез. докл. - Киев, 1988. - Секция 1. - С. 29.

20. Гремальский А. А. Теоретические основы управляемой геиеращш псевдослучайных тест-программ // XXX Всесоюзная школа-семинар им. Ы. А. Гаарилова «Разшггке теор!ш дискретных систем и проблемы логического проектирования СБИС»: Тез. докл.- Кишинев, 1988. - С. 103-109.

21. Гремальский А. А, Андроник С. Л/. Высокочастотная система функционального контроля микропроцессоров // XI паучп.-техи. коаф. «Проблемы разработки измерительных приборов со встроенным интеллектом и перспективы их развитая»: Тез. докл. - Каунас, 1988. -С. 70-71..

22. Гремальский А А. Генерация стохастических тест-программ дав высокочастотного контроля микропроцессоров 1/ Известия Академии наук Молдавской ССР. Серия физико-технических и математических иаук. -1988. - N 2. - С. 37-41.

23. Гремальский А. А, Станчу И. П., Ревинская Н. В. Параллельное моделирование цифровых устройств // Вестник Киевского Политехнического Института. Техническая кибернетика. - 1988. - вып. 12.

- С. 79-81.

24. Гремальский А. А., Секриеру И. Г., Станчу И. И. Система функционального иногоуровнего моделирования цифровых устройств // Всесоюзная научн.-техи. конф. «Техническое и программное обеспечение комплексов полунатурного моделирования»: Тез. докл. - Москва, 1988. • часть 1. - С. 110-111.

25. Гремальский А. А Программно-аппаратная система функционального проектирования цифровых устройств Н В сб. научи, тр. МАИ: Конструирование и производство РЭА и ЭВА с применением малых и персональных ЭВМ - Москва: Издательство Московского авиационного института. - 1988. - С. 12-15.

26. Гремальский А. А, Андроник С. М. Анализ качества псевдослучайных тест-программ для контроля • микропроцессоров // В сб.: Вопросы технической диагностики. - Ростов/Д: Ростовский инжинерно-сгроительный институт. - 1987 - С, 143-146.

27. Гремальский А. А., Станчу /. И. Анализ многошинной специализированной системы моделирования // Известия Академии Наук Молдавской ССР. Серия физико-технических и математических наук. -1988. - N 3. - С. 37-43.

• 28. Гремальский А А. Система программно-аппаратного моделирования цифровых устройств // В сб.: Полупроводниковые структуры, радиоэлектронные устройства и системы контроля. - Кишинев: Штиинца. - 1989. - С. 73-81.

29. Гремальский А. А., Андроник С. М. Методы генерации и оценки качества ^псевдослучайных тест-профамм // Республ. научн.-техн. конф. «Автоматизация контроля вычислительных устройств и систем»: Тез. докл. •- Киев, 1988. - С. 55-56.

30. Клисторин И. Ф., Гремальский А. А., Станчу И. И. Анализ специализированного процессора для моделирования цифровых устройств // Электронное моделирование. - 1989. - N 3. - С. 12-17.

31. Гремальский А. А, Клисторин И. Ф., Андроник С. М. Высокочастотная генерация псевдослучайных тест-программ для псевдослучайного функционального контроля микропроцессоров // Электронное моделирование. - 1989. - N 4. - С. 60-64.

32. Гремальский А. А., Андроник С. М. Высокочастотная система функционального контроля микропроцессоров // В сб. научи, тр. МАИ: Методы конструирования и технологической подготовки производства радиоэлектронной аппаратуры средствами АРМ и персональных ЭВМ: -Москва: Издательстпо Московского авиационного института. - 1989. - С. 45-51.

33. Гремальский А. А., Андроник С. М., Настасснко Л. Я.

Эквивалентность команд микропроцессора и управляемая генерация псевдослучайных тест-программ // Известия Академии Наук Молдавской ССР. Серия физико-технических и математических наук. - 1989. - N 3.

34. Клисторич И. Ф., Гремальский А А Высокочастотная генерация псевдослучайных тест-программ в системах контроля микропроцессоров {! В сб.:. Измерительно-вычислительные системы и их элементы (теория и реализация). - Новосибирск: НЭТИ. - !989. - С. 33-40.

35. Гремальский А. А. Генератор псевдослучайных тест-программ для высокочастотного контроля микропроцессорных СБИС // Управляющие системы и машины. - 1990. - N I. - С. 41-45.

36. Клисторич И. Ф„ Гремальский А А. Функциональный контроль микропроцессорных устройств // Кишинев: Штшшца. - 1990. -91 с.

37. Гремальский А А Синтез псевдослучайных тесг-протрамм по алгоритмическому описанию дискретного устройства // Известия Академии Наук ССР Молдова. Физика и техника. - 1990. - N 2. - С. 36-44.

38. Гремальский А. А Генерация случайных марковских процессов при стохастическом контроле микропроцессорных устройств // В сб.: Вероятность и ее приложения. - Кишинев. - Штшшца. - 1990. - С. 47-50.

39. Gremalschi A Model al procesului de generare de stimuli pseudoaleaiori 11 Sinipozionul national de teoría sistemelor. Robotica, calcuiaioare çi Informática de procès. Vol. 2. Calculatoare numérico -hardware çi software. - Craiova. - 1991. - P. 5-12.

40. Гремальский A A., Рошка A. A, Бежап В. E. Генерация многосвязных . тест-программ для псевдослучайного контроля микропроцессоров // Электронное моделирование. - 1991. - N 3. - С. 63-67.

41. Гремальский /1. А Методы стохастического контроля и диагностики микропроцессорных СБИС 11 III Всесоюзная конференция «Физические основы полупроводниковых приборов»: Тез. докл. Кишинев, 1991. - часть 2, - С. 74.

42. Гремальский А. А, Бежап В. Е, Рошка А. А Теория и методы псевдослучайного. функционального контроля микропроцессорных устройств // Рсспубл. научи.-техн. конф. «Проблемы автоматизации контроля и диагностирования сложных технических систем»: Тез. докл.. -Киев,' 1991. - С. 25-26.

43. Гремальский А А, Рошка А А, Бежан В. Е. Генератор мноюевязных последовательностей для псевдослучайного тестирования микропроцессоров // Известия Академии Наук Республики Молдова.

Физика и техника. - 1991. - N 3(6). - С. 37-43.

44. Гремальский А А., Ротка Л А, Бежан В. Е. Мультимикропрограммное устройство управления для моделирования и псевдослучайного контроля // Известия Академии Наук Республики Молдова. Физика и техника, - 1991. - N 3(6). - С. 44-50.

45. Anatol Gremalschi, Pinlilie De$atu Diagnosticsrea tehnicä a echipamenteior mfcroprocesor. Manual pentru institu|iile de lrtvätäinint superior. Chisinau: Universitas. - 1992. - 265 р. (Техническая диагностика микропроцессорных устройств. Учебник для ВУЗ-ов. Кишинев.: Универсатас. - 1992. - 265 с.)

46. А. с. 1332320 СССР, МКИ С 06 F 11/00. Устройство контроля микропроцессорных блоков / А. А. Гремальский, С. М. Андроиих. - Заявлено 03.04.86. Б юл. N 31, 1987.

47. А. с. 1453403 СССР, МКИ G 06 F 7/58. Генератор случайного марковского процесса / А. / "ремальсхий, С. М. Андроник.

- Заявлено 24.06.87. Бюл. N 3, 1989.

43. А. с. 1481755 СССР, МКИ О Об F 7/58. Генератор случайного марковс?.ого процесса / А. А. Гремальский, С. М. Андроник.

- Заявлено 11.05.87. Бюл. N 16, 1989.

49. А. с. 1531093 СССР, МКИ О Об F 7/58. Генератор случайного маркопского процесса / А. А. Гремальский. - Заявлено 04.0-1.S8. Бюл. N 47, 1989.

50. А. с. 1531099 СССР, МКИ G 06 F 11/00. Устройство для контроля микропроцессорных блоков / А. А. Гремальский, С. М. Андроник. - Заявлено 11.04.88. Бюл. N 47, 1989.

51. А. с. 1552185 СССР, МКИ О 06 F 11/26. Формирователь .тестов* / А, А. Гремальский, С. М. Андроник. - Заявлено 25.11.87. Бюл. N 11, 1990.

52. Ai с. 1566348 СССР, МКИ О 06 F 7/58. Генератор равномерно распределенных случайных чисел / А. А. Гремальский. -Заявлено 28.07.88. Бюл. N 19, 1990,

53. А. с. 1580360 СССР, МКИ О 06 F 9/22. Микропрограммное устройство управления / А. А. Гремальский. - Заявлено 21.04.88. Бюл. N 27, 1990.

54. А. с. 1591032 СССР, МКИ G Об " 15/00. Система логического моделирования цифровых объектов / А. А. Гремальский, И. И. Станчу. - Заявлено 17.11.88.Бюл. N 33, 1990.

55. А. с. 1619262 СССР, МКИ G 06 F 7/58. Генератор случайного марковского процесса / А. А. Гремальский, С. М. Андроник.

- Заявлено 24.01.84. Бюл. N 1, 1991.

56. А. с. 1619263 СССР, МКИ G 06 F 7/58. Генератор

случайного марковского процесса / А. А. Гремальский, С. М. Андроник.

- Заявлено 24.01.89. Бюл. N 1, 1991.

57. А. с. 1624446 СССР, МКИ О Об Р 7/58. Генератор случайного марковского процесса / А. А. Грсмальский, С. М. Андроник.

- Заявлено 24.01.89. Бюл. N 4, 1991.

58. А. с. 1631542 СССР, МКИ О 06 Р 9/22, 9/00. Мультимикропрограммная управляющая система / А. А.- Гремальский. -Заявлено 28.02.89. Бюл. N 8, 1991.

59. А. с. 1635187 СССР, МКИ О 06 Р 11/26. Формирователь тестов / А. А. Гремальский. - Заявлено 10.10.88. Бюл. N 10, 1991.

60. А. с. 1647566 СССР, МКИ С 06 Р 9/22. Микропрограммное устройство управления / А. А. Гремальский. - Заявлено 18.04.89. Бюл. N 17, 1991.

61. А. с. 1660004 СССР, МКИ О 06 Р 11/00. Устройство для хонтроля микропроцессора / А. А. Гремальский. - Заявлено 21.12.88. Бюл. N 24, 1991.

62. А. с. 1661769 СССР, МКИ О 06 Р 11/26. Формирователь тестов / А. А. Гремальский, С. М. Андроник. - Заявлено 09.03.89. Бюл-N 25, 1991.

63. А. с. 1672454 СССР, МКИ О 06 Р 11/00. Устройство для контроля больших интегральных схем / А. А. Гремальский. - Заявлено 09.11.88. Бюл. N 31, 1991.

64. А. с. 1711155 СССР, МКИ О Об Р 7/58. Генератор случайного марковского процесса / А. А. Гремальский, С. М. Андроник.

- Заявлено 9.03.89. Бюл. N 2, 1992.

65. А. с. 1711156 СССР, МКИ С 06 Р 7/58. Генератор случайного марковского процесса / А. А. Гремальский, С. М. Андроник.

- Заявлено 9.03.89. Бюл. N 2, 1992.'