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

С'-,-, <о

/

Сх.

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

ЗАХАРОВА Ларису Евгеньевна

УДК 681.513

ИЕТОДЫ И АЛГОРИТМЫ ДЛЯ АВТОМАТИЗАЦИИ МОДЕЛИРОВАНИЯ Н ТЕСТИРОВАНИЯ ГШ1С

Специальность 05.13.12. - Системы автоматизированного

прое«тирования

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

Москва - 1395

Работа выполнена на кафедре "Вычислительные системы и сети" Московского Государственного Института электроники и Математики.

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

профессор B.C. Жданов.

*

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

профессор С.П. Плеханов! кандидат технических науК| доцент Зыков А,К.

Всздуивя организация ПИЙ Информационной такнол гии.

С

Защита диссертации состоится "^й."1995 г. в /5"час. на [заседании Специалиаированного Совета К 063,'63.01 Московского Государственного Институтка Электроники и Математики по aApecyi 109028, Москва« Б. Треневятительский пер.1 дои 3/12.

С диссертацией можно оонакомится в библиотеке Г1ГИЭМ.

Автореферат раоостлан "Ш,"1995 г.

■ - Учений секретерь Специализированного Совета кандидат техническим наук / Старых В.А.

Подписано к печати 21.11.1995 г. "Зак.Г49. Тпр.Зи Ооъем I п,

МГИЭМ, Москва, М,Пионерская ул., 12

- 3 -

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

Агасуалыюсгь работы. Цифровые устройства, разработанные на 5азе программируемых логических интегральных схем (ПЛИС), является конкурентоспособными из-за высоких экономических и технических характеристик. Для разработки цифровых устройств на баэе' ПЛИС Используются системы автоматизированного проектирования и программирования (САПР) ПЛИС, т.к. применение ШШС без средств автоматизации проектирования и отладки устройств, программирования 'ПЖС :: тестирования запрограммированных ШШС невозможно.

Лчя проектирования цифровых устройств используется различные гходные ..зкки описания ПЛИС, отличающиеся степенью' приближенности к структуре конкретной ПЛИС. Наличие нескольких входных языков позволяет пользователю выбрать наиболее подходящий для него язык описания ШИС и способствует увеличению числа возможных: пользователей САПР. Для экономии ресурсов ШИС в САПР, применяется логическая минимизация описания ПЛИС. Отладка проектов устройств перед программированием повышает эффективность САПР, уменьшая число бракованных ШТОС- при проектировании. Для отладки используется математическая модель ПЛИС. Тестирование запрограммированных ШИС проводится для проверки их исд^авности и состоит в сравнении значения последовательностей выходных векторов тестируемой ШШС и математической модели или эталонной ШШС при заданной последовательности входных векторов.

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

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

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

- исследование математических моделей цифровых устройств и разработка математической модели ШШС;

- разработка и обоснование методов и алгоритмов полного

- 4 - '

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

- анализ методов и разработка' методики минимизации описа ния ПЛИС;

- разработка и оценка эффективности методики полного авто матиэироЕанного функционального тестирования ПЛИС с использова нкем минимизации, сокращающей время тестирования, позволяют? восстанавливать ШШС и для которой не требуется математическа модель ШШС;

- разработка Форш представления данных описания ПЛИС обеспечивавшей минимальное время определения активных терме ПЛИС при математическом моделировании ПЛИС и минимальное вреь преобразования термов при минимизации описания ПЛКС различные методам!.

- разработка математического и программного обеспечен!' для проектирования, отладки, минимизации и тестирования ПЛИС.

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

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

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

- метод и алгоритм полного автоматизированного функцш нального тестирования ПЛЖ с использованием развернутого гра! состояний;

- метод и алгоритм компенсационных матриц для оптимигац полного автоматизированного функционального тестирования ПЛИ1

На эащиту также выносятся:

- методика полного автоматизированного функционально тестирования ПЛИС а использованием минимизации, сокращают время тестирования и позволявшая восстанавливать описание ПЛИ

' - форма представления данных описания ПЛКС, сокращают

ремя отклика при моделировании и минимизаций описания ШШС.

Практическая цешюсть и реализация результагоп работы

Результаты проведенных научных исследований позволили раэ-аботать САПР ШШС , выполняющие проектирование, отладку и тес-ирование ШШС. САПР ШШС типов ГИМ, PAL, ЕР 900, 22V10 разра- . отаны на ПЭВМ IBM PC/AT.и внедрены в ЦНИИ "Циклон" в программе У электронной промышленности ГОСКОМОБОРОНПРОМА "Развитие тех-ических и организационных средств проектирования МаБИС с ис-ользованием технологии ПЛИС" ("ШШС - БЫК"), «то подтв'ерзцдает-я актом о внедрении.

Предложенные математические модели, методы и алгоритмы вотирования могут Быть применены как при моделировании и тес-ировании других типов ПЛИС, так и при моделировании и тестиро-ании автоматов, содержащих комбинационные (не имеющие памяти) : триггерные (с памятью) выходы.

Для использования в учебном процессе разработаны учебные ерсии САПР ПЛИС - автоматизированные рабочие места (АРМ) про- . ктировщика ШШС. Проекты цифровых устройств, разработанные и тлаженные на АРМ ПЛИС, далее могут Сыть использованы в САПР, .к. форматы файлов данных .совпадают. Учебные версии внедрены в чебном процессе, что подтверждается актом о внедрении*

Апробация работы.. Основные научные положения и , результаты ;иссертадиояяой работы были представлены и обсуждались ка еле-;утацих конференциях и семинарах: "Автоматизация проектирования 'ЗА и ИВА" (Пенва, 1990), "Микросистема - 93" (Москва,' 1993), :а научно-технической конференции-конкурсе студентов, аспиран-ов и молодых специалистов ШЯ (Москва, 1994 и 1995 г.г.), на Ьжгосударственной научно-практической конференции творческой юлодежи "Актуальные проблемы автоматики: математическое, программное и информационное обеспечение" (Минск, БГУ, 1994), на !еждународной научно-технической конференции "Развитие и приме-[ение открытых систем" (Казань, 1994), а также на'ааееданиях аучно-технического семинара кафедры "Вычислительные системы и :етиТ МГИЭМ.

/публикации. Основное содержание диссертации отражено в 9 гэчатных pa6oráx.

Структура \И объем работы Диссертация состоит иа введения,

- б -

• четырех глав, заключения, списка литературы» включаюшэго Ю2 наименования, приложения и содержи 111 страниц основного текста, 41 рисунок, 1 таблицу.

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

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

В первой глало проведен сравнительный анализ входных языков описания' ПЛИС и предло.чена форма представления описания ШИС в виде массива минимизации для моделирования и мингашзацга ПЛИС. Если провести аналогию между входным языка),и описаниг ПЛИС и алгоритмическими языками, то таблица истинности ПЛИС соответствует ассемблеру, являясь как бы языком нижнего уровня, : логические уравнения, схемотехническое проектирование и т. д. ■ nsuiiai.ni верхнего уровня. Таблица истинности отличается от остальных языков быстротой перевода в массив программировали ПЛИС и приближенность» к структуре ПЛИС. Схемотехнический вход ной язык обеспечивает графический ввод принципиальной злектри ческой схемы и базируется на библиотечных элементах, т. е, pas личных вентилях "ИЛИ", "И" и входах/выходах, соответствуюши ПЛИС. Логические уравнения - самый компактный и унифицирована способ описания устройств. Для схемотехнического проектирован! существует перевод в уравнения, а для уравнений - перевод таблицу истинности.

Внутри ПЛИС соединение элементов происходи! в следуют* последовательности: вход (обратим связь) - инвертор -"И" "ИЛИ" - выход. Любой из элементов этой цепочки кроме входа выхода иолег отсутствовать. Входы, соединенные коньгакцией, о разуют терм. Термы, соединенные дизъюнкцией, образуют выход.

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

женных перемычек некорректно, переменными являются входы и обратные связи. Например, типом выхода у ЕР 900 управляют 4 перемычки, но.из 16-ги вариантов корректно только 9, поэтому тип выхода ЕР 900 задается латинскими буквами от А до I, а не состояниями перемычек. Существует перевод таблицы истинности в логические уравнения.

Предложена форма представления данных описания ПЛИС в'виде массива минимизации для минимизации и моделирования 'ПЛИС. Если нет специальных требований к массиву программирования, то массив программирования совпадает с массивом минимизации. Массив минимизации (и, при необходимости, массив программирования) непосредственно получается из таблицы истинности с использование^ несложных операций.

Из входных языков верхнего уровня более подробно рассмотрим уравнения. Представление описания ПЛИС в виде уравнений соответствует представлению логических функций в нормальной дизъюнктивной форме. Левая часть уравнения сос!гоит из переменных, соединенных знаками операций - логическими умножением и сложением, правая - из выходов. Компактность описания - следствие того, что безразличные переменные в уравнения не входят, и термы, одинаковые для разных выходов, можно описать один раз. В отличие от таблицы, в языках верхнего уровня происходит диаг-. ностировани? ошибок в описании ПЛИС вместе с проверкой на превышение ресурсов ПЛИС. Для логических уравнений это ошибки типов: неверная переменная; неверный знак операции; превышено число термов в выходе; выход описан разными типами и т. д. Перевод в таблицу истинности происходит только при отсутствии ошибок в уравнениях. '

Несмотря на наличие нескольких входных языков в САПР ПЛИС, минимизация, отладка, программирование и тестирование должны выполняться для проекта устройства, разработанного в одном из входных языков. Проекты устройств, разработанные в других входных языках, для продолжения проектирования в САПР ПЛИС долины быть переведены в таблицу истинности. _ •

Сравнительный анализ входных языков описания ПЛИС показал, что таблица истинности- является наиболее подходящей для минимизации, отладки, программирования и тестирования ПЛЕС, т. к.

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

Вторая глава посвящена разработке математических модель ПЛИС. Математическое моделирование состоит в определении после довательности выходных векторов при заданной последовательное! входных векторов. Такой набор входных и выходных векторов наз! вается тестом пользователя. В САПР ПЛИС имеется возможность н; бирать и редактировать тест пользователя.

Основной частью модели является определение активных те] мов ПЛИС при воздействии входного вектора. Терм - это вход: соединенные коньюнкцней, причем некоторые"'значения входов терме могут быть безразличными, когда как во входном векто] безразличных значений входов Сыть не может. Активными при во; действии входного вектора будут те термы, значения входов у к торых или совпадут со значениями входов во входном векторе и будут безразличными. Если у терма п безразличных переменных, активным его могут сделать 2 в п -ой степени различных входн векторов.

Для установления активности терма при воздействии данно входного вектора используются 2 простых операции: инверсия логическое умножение. Дал ускорения моделирования применено т называемое параллельное моделирование. Одновременно и неэавис мо выполняется логическая операция над целым словом - 2 байт Структура ПЭВМ IBM PC/AT позволяет обрабатывать S входов одне ременно.

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

Если все выходы у проекта устройства на ПЛИС триггерные, то после вычислений значений всех выходов для данного входного вектора происходит переход к следующему входному вектору., в котором эначейия обратных связей берутся из значений выходов на предыдущем входном векторе. Для первого входного вектора значения обратных связей берутся из значений выходов ПЛИС при еклю-. чении питания.

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

Но такйк шагов 'может быть не более п, и если к п-му иагу процесс не установился, моделирование прекращается. Это значит, что или последовательность входных векторов иди проект устройства были составлены некорректно. п=2*т«п, где т.- число комбинационных выходов устройства на ШШС.

Ери моделировании всегда существует определенный порядок вычислений значений выходов, например 1, 2, ... , в. Для определения числа п рассматривается устройство, когда все комбинационные выходы соединены в "кольцо" в порядке, обратном порядку вычислений, например 1, т, .. ,2, 1. Таким образом, значение к-ого выхода зависит от значения (к+1)-го выхода для к<п. Но (к+1)-ый выход вычисляется после к-ого. Значит за каждый "обратный" проход кольца, равный п катов, вычисляется только один выход, а для т выходов надо сделать ш проходов, или го«« шагов.

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

Если устройство имеет и триггерные и комбинационные выходы, то моделирование происходит по трехэтапной волнлвоь шп по трехэтапной ранжированной модели. Моделирование каждогс входного' вектора делится на 3 этапа. 1-ый и 3-ий этапы - эт< водноЕое или ранжированное моделирование работы комбинационны: выходов, 2-ой этап - моделирование рабо.j триггерных выходов, На первом этапе волновым или ранжированным обраэсм определяете: промежуточные зна^ния комбинационных выходов с использование во входном векторе значений триггерных выходов, полученных пр моделировании предыдущего входного вектора. На втором этапе оп редедяюгея окончательные г ач^кия триггерных-выходов с исподь эованием во входном векторе значений триггерных выходов, полу чекных для предыдущего гходного вектора, и промелуточ:ь значений комбпационных выходов, полученных на первом этапе. I третьем этапе волновым или ранжированным образом определяете окончательные значения комбинационных выходов с ислальзованиг во входном векторе окончательных значений триггерных выхода! полученных на предьиущэг этапе. И, естественно, если на перве или третьем этапах волнового моделирования га п шагов значен! входных и выходных векторов не установятся, -с модели.;ован: прекращается. Блок-схема математического моделирования Ш~ изображена на рис. 1.

Изложенная выше ; ^тематическая модель применялась при со дании САПР ПЛИС типа ЛЛЫ* PAL, ЕР 9СО и проверена при много ратном тестировании устройств яа баге ПЛИС этих типов. Изложе пые в литературе математические модели цифровых устройств пр менимы кли для комбинационных, или для последовательных ус ройств на баз* ПЛИС. Модели устройств с ¿заимгосвяэаннь комбинационными и тритгернымл выходами, довольно часто разраС тываечых на базе ПЛИС, в лн-ературе отсутствует. Предложат трехэтапная ранжирт?анно-волновая математическая модель иш научную новизну, т. к. позволяет моделирсаать цифровые устрой! 'ва с взаимосвязанными трит рными и ко. Зинационными выхода!

В третьей глава диссертации списываются разработка и ;

-и-

номер итерации=х -1—:-

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

-г

Начало моделирования

Вычислении значений к комбинационных выходов, где к - число комбинационных чых.

-1-

V

Л ' \ /эна-\ да /чения \

-(ком. вь_с>

пре-/

\дыд./ \? /

\/

| гет

V /\

/ \ / \ да / \ —<и>г*к*к?> ч / \ / \ / \/

| нет

-V-

N=N+1

V

/ч / \ /КОМ-Ч

/бика- \ <ционные >■ \выходи/

Честь/ \? /

ч/ I да

V Л

/ Ч /МО Ч нет /дель ч

-<ранжиру->

\ется? / ч / Ч / ч/ I да

-V-

нег

Ранжирование модели

Определение входного вектора по значениям входов и обртньх связей

Вычисление значений комбинационных выходов в порядке ранжирования

Вывод на дисплей сообщения о некорректности данных 1ли проекта устройства

/ч

/ ч / ч /триг- Ч нет

-хгерные >-

Чииоды/ Честь/ \? / Ч/ да |

Г

I Определение входного -> вектора по значениям входов и обратных

СВЯР^Й

I

V /\ / \ / ч

/ григ-Ч да

< герныэ >->

Чвыходы/ Честь/ ч? / ч/

| нет

-г-V-) ,

Конец моделирования <-

Вычисление значений тригге: !ЫХ выходов. Приравнивание нулю числа тр!..\ выходов.

Вычисление числа триггерных выходов

Вычисление значений триггерных выходов

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

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

Вычисление значении триггерных выходов

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

Рис. 1. Блок-схема математического моделирования ПЛИС.

N

<

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

Для геста пользователя сравнение выходов ПЛИС с математической моделью проводится для каждого входного вектора. При несравнении значения входов и выходов выдаются на дисплей.

.Остальные методы тестирования явлкггся автоматизированными, т. о. последовательность входных векторов вырабатывается ПЭВМ.

Полное автоматизированное тестировали» ПЛИС, не имеющих обратных связей, достигается перебором всех возможных входных векторов-. Для устройств, имеющих обратные связи, этого недостаточно, тут надо перебрать все возможные комбинации входов и обратных сЕязей. Второй метод тестирования основан на построений развернутого графа состояния устройства. Развернутый граф состояний представлен в виде двумерного массива, где колотествс строк равно количеству входных векторов, а кол-во столбцов ■ кол-ву состояний устройства, или числу всех возможных ссстояши обратных связей. Входные вектора и состояния пронумерованы. Каждый элемент массива, соответствующий состоянию ПЛКС и входному вектору, равен номеру того состояния, в которое ПЛКС пере ходит из этого состояния при воздействии этого входного векто ра. Массив заполняется до тех пор, пока в нем не.останется не полностью заполненных колонок. Наличие пустых колонок при ос тальных полностью заполненных означает, что устройство в ка кие-то состояния не переходит совсем.

Если на.ШИС реализовано устройство, в котором используют ся не все входы, то количество входных векторов соответствен« уменьшается. Если у угтройства на ПЛИС использованы не все вь ходы, то сравнение с математической моделью ШМС производите только по использованным выходам.

. Порядок перебора входных векторов значения не имеет, гла! ное чтобы все цектора были перебраны. Способ определения по ш

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

Третий метод тестирования ПЛИС является решением одной из задач дискретного программирования - пройти все ребра ориентированного графа так, что оСезя сумма ребер Судет минимальной.

Представим граф состояний ПЛИС в виде квадратной матрицы А размеркссти п, где п - число состояний ПЛИС. Каждый элемент матрицы a(isj) равен числу переходов из i-oro состояния в д-оэ. Для i-ого состояния £ а( i, j)-числу выходов из него, a ¿a(j,i)» числу входов а него. Обозначим сумму элементов по i-ому столбцу как a(j,i), a no i-ой строке как Z i» fa(i,j). Для графа

состояний ПЛИС на рис. 2 вид матрицы А изображен на рис. 3.

УТНЕРЯДОВЯ; 1: Скомпенсированная матрица переходов между состояниями является матричным изображением оптимального пути тестирования ПЛИС.

1 1 1 2 3 4

! 1 1 2 1 1 0

2 1 0 ,1 2 1

3 1 О О 3 1

4 1 2 О • 0 2

Рис. 2. Граф состояний Гис. 3. Вид матрицы А.

Скомпенсированной называется квадратная матрица

размерности п, у которой |£1= XI V 1.

Состоянию, " в котором находится ПЛИС при включении питания, присвоим номер 1. Считаем, что тестирование ПЛИС начинается и кончается в 1-ом состоянии, т.к. после тестирования питание выключается. Если тестирование проходит все ребра между состояниями, то число выходов из ¡.-ого состояния равно числу входов в него, причем 1-1, ... , п.

Для полностью'заполненной матрицы А ¥ состояния 3 переход в любое другое состояние. Если матрица ещэ не скомпенсирована, тоЗ 1. такое что | гы г 1.

УТВдаданИЕ 2: ЕслиЗ состояние i, для которого |xí>(<)5:i,

■toi ■

то 3 по крайней мерэ одно состояние ш, для которого | гпк(>)?ш.

Это следует из того, что V матрицы к г |£i-¿r fi- £ ia(i,j).

Из утверждения 2 следует, что если матрица не скомпенсирована, то всегда 3 элемент матрицы a(i,j), находящийся на пересечении меньших (из пар столбец-строка) строки и столбца. a(l.d) увеличиваем на min ((Iii-Ii) чем достигается

компенсация по меньшей мере одного Ио состояний 1 или j.

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

- Также компенсируется неполностью заполненная матрица, но не имеющая ва пересечении меньших столбцов и строк нулей. Для компенсации неполностью заполненной матрицы переходов А, имеющей на пересечении некоторых меньших столбцов и строк нули, в одномерном массиве В размерности п будем хранить значения чисел, на которые надо увеличить при компенсации матрицы А меньшие m столбцов, а в одномерном массиве С размерности п будем хранить значения чисел, на которые надо увеличить меньше к строк. Составим вспомогательную квадратную матрицу Al размерности п. Элементы ее определим так: al(i,j)-min(c(¿),b(j), a(i, J».

Если V i<«n £ al( i, j)<=cC i) aV j<«n £ al(i, J)<=b(j), то прибавим к матрице А матрицу Al. Если суммы матрицы Al по строкам и столбцам р-?:зны соответствующим элементам массивов. Б и С, то матрица А скомпенсируется полностью. В противном случае матрица А будет неполностью скомпенсированной, а на пересечении всех меньших строк и столбцов будут стоять нули.

V а(i,j)=0 на пересечении меньших строки и столбца определим минимальный путь из i-oro состояния в j-oe состояние. Воспользуемся для этого двумя двумерными массивами размерности п -S и SI. S - массив длин минимальных путей. s(í,j)=l и sl(iij)ei. если a(i,j)?0. Это те состояния, длина пути в которые равна 1. Определим теперь состояния, длина пути в которые равна 2. V j, если s(í,j)-l и V m, такого что a(j,mVO, и если

з(1,ш) было равно нули, 3(1, т) присваиваем значение 2, а р1(1,ш) - значение Таким образом, в э1(1,к) будет хранится номер того состояния, из которого попадаем ь данное 'состояние к. При заполнении массивов 5 и 51 ранее заполненные элементы ь. меняшся, поэтому это массивы именно минимальных путей. Для матрицы А на рис. 3. составим массивы 5 и Б1:

г , 51

0 1 1 2 Массив О 1 1 3 Массив

2 0 1 1 длин 4 0 2 2 шши.'4альных

'с в 0 1 минимальных 4 1 О 3 путей

1 'о 2 0 ■ пут ЭЙ 4 1 1 0

! Минимальный путь длиной 3 иа 3-его состояния во 2-ое определим по массиву путей S1: это 1 сое. из 4 сос. из 3 сос.

Компенсация по крайней мере одного из двух состояний 1 или j может быт> достигнута увеличением всех элементов минимального пути на ;nin((|zi-Si),(fj-|s:j)).

Для графа состояний, отражающего устройство, разработанное на базе ПЛИС, ЕсегдаЗ минимальный путь из одного состояния в другое. Если через граф состояний пути из i-oro состояния в j-oe нет, то всегда3 путь через 1 состояние, в которое попадает ГЛИС пги В!мючении-включении питания.

Если в матрице А1 сущэствуит такие строки и столбцы, что сумма элементог по ни* больпе соответствующих элементов массивов С иди В, то попробуем сделать юс равными уменьшением элементов на иг пересечении.

Окончателы.ая компенсация матрйцы А проходит одновременно через матрицы А1 и S. Сначала определим матрицу Alt al( 1, j)«mn (c(i),b(j)). Оп;эделяем s(i,j)>-max(S). И если cyj&ia по i-ой строке матрины А1 болыш о(1), сумма по J-ому столбцу матрицы А1 больше b(j), ю уменьшаем al(i, j) до тех пор пока или суша по строке 1 илл сумма по стс тбцу j катрицы А1 то станут равным-1 of 1) или b(j) или al(i,j) обрагится в нуда. Затем в любом случае обнуляем s(i,j). Такую операцию выполняем дм всех элементов матрицы А1, так как все элементы массива S станут по очереди максимальными.

- 16 -

Далее компенсируем матрицу А. Если а( 1,з)/0, то прибавляем к нему а1( 1, з), после чего а1( 1,3) обнуляем. Если а( 1,3)-0, а а1( 1,3)5*0, то компенсация будет проходить через минимальный путь. Затем а1(1,з) также обнуляем. После обнуления матрицы А1 матрица А окажется полностью скомпенсированной. Способ компенсации матрицы А через матрицы А1 и 5 является универсальным.

Для построения оптимального пути тестирования используем одномерный массив Из матричного изображения оптимального пути тестирования получим в массиве Ь оптимальный путь тестирования ПЛИС в виде последовательности состояний.

УТВЕРЖДЕНИЕ 3: Любой непересекающейся по ребрам скомпенсированного конечного графд состояний, но, возможно, пересекаю-щйся по состояниям путь может кончиться только в том состоянии, в котором начался.

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

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

При построении последовательности состояний в матрице А при переходе из 1-ого состояния в 3-ое а(1,з) будет уменьшаться на единицу, в то время как элемент массива Ь будет приравнивайся к

Ц1Ы; Находим а(1,1)зЮ, КЕМ, а(1,0=а(1,1)-1. V 3, такого что 1(з)=КиО, 1С3+1) =0, находим т, такое что а(к,т)*0,. и тогда 1(з+1)=т, а(к,п1)=а(к,га)-1. Если неразного нули а(к,и) в к-ой строке нет, то первая последовательность состояний получена. Если при этом весь массив последовательности состояний Ь заполнен, а матрица А обнулилась, то оптимальный путь тестирования построен.

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

Находим такое состояние ] (1С к) , и по оставшимся ненулевым элементам матрицы А построим из него путь. Сдвигаем элементы массива (., начиная с 1(к+1), в конец массива. Построим вторую последовательность состояний, начиная с 1(к)=*;). Если в массиве Ь не останется нулевых элементов, а массив А обнулится, процесс закончен. Если нет, то в конец второго пути придвинем из конца массива Ь вторую часть первого пути и опять найдем не-дотестированное состояние.

Процесс конечен, т. к. на каждом шаге хотя бы одно состояние полностью включается вместе со всеми своими ребрами в последовательность состояний. Теперь в том же массиве из последовательности состояний получим последовательность входных векторов. Заменим в массиве !_ номера состояний номерами входных векторов. Воспользуемся для этого развернутым графом состояний, как во втором методе тестирования. Построенный массив Ь входных векторов является векторнь-л выражением оптимального пути тестирования и может непосредственно использоваться для тестирования ПЛИС.

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

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

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

Предложенные методы полного автоматизированного тестирования ограничены только возможностями ПЭШ, или, точнее, размерами используемых при тестировании массивов. Для полного тестирования последовательного устройства на баае 8-ми входовой PAL типа 1б55хр8 с 8-и триггерными выходами нужен массив тестирования размером 2Т8*2?8=2|1б=ББ53б, что возможно реализовать на 1ВШ. Для большего числа состояний (у EP-S00 24 выхода) размеров памяти ПЭШ может не хватить. Если на ПЛИС разработано несколько устройств, то их можно тестировать отдельно. ПЛИС типов PAL, ЕР-300, ЕР-600, 22VI0 можно тестировать целиком, памяти ПЭВМ для этого хватит.

Время исчерпывающего тестирования зависит от используемого тестера и, в меньшей степени, от тестируемого устройства. Время полного тестирования последовательного устройства средней сложности с 8 входами и 8 выходами на базе PAL 1556хрЗ на тестере, подключенном к IBM XI/AT, не превышает 2-х часов.

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

. Четвертая гласа посвящена анализу методов и разработке методик минимизации описания IWíC и использованию минимизации при тестировании.

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

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

Для склеивания склеивающиеся термы должны совпадать во всех переменных кроме одной, но в этой переменной иметь полярные значения, один "О" - другой "1". После склеивания один терм обнуляется, а в другом (любом из двух) на месте несовпадающей переменной стоит "X".

Обобщенное склеивание состоит в расщеплении одного из термов на ДЕа по какой-либо безразличной переменной, после чего оба расщепленных терма погдошдютсл двумя другими гермами описания ПЛИС. Подвергщийся расщеплению терм обнуляется.

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

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

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

один терм, или когда пройдены все ненулевые термы выхода, и число ненулевых термов не сократилось. И так все выходы ПЛИС.

Объем программы простой минимизации ПЛИС из 48 входных переменных и 1000 термов равен 4D кб. Бремя минимизации 470 произвольно набранные термов равно 38 сек, а 360-ти - 23 сек на IEM ХГ/АТ. Число термов после минимизации уменьшалось в обоих случаях на 10%. Данная методика минимизации быстродействующая и не требует больших объемов памяти ПЭВМ, хотя и не всегда результат минимизации будет оптимальным.

Табличный метод Квайна-Маккласки дает оптимальный результат минимизации и требует 2-х больших массивов и больших временных затрат. Сначала термы .выхода ПЛИС разлагаются на термы, не содержащие безразличных переменных. Далее термы разбиваются на группы по числу едийиц в терме. Между соседними группами проводится склеивание для все возможных пар термов. Результаты склеивания - термы, имеющие одну безразличную переменную, помещаются во второй массив. Несклеивающиеся термы помешаются в окончательное описание выхода ПЛИС. Первый массив обнуляется. Во втором массиве проводится поглощение, а затем группировка по числу единиц. Далее опять проводится склеивание между соседними группами, результат склеивания с 2-мя безразличными переменными помещается в первый массив, а несклеивающиеся термы с одной безразличной переменной помешдются в описание выхода. Затем обнуляется второй массив и т.д., пока результат склеивания даст , не более одного терма.

Оценим объем памяти ПЭВМ, необходимый для хранения данных при простой минимизации и минимизации методом Квайна-Маккласки. Для п переменных максимальное число термов равно 2 в n-ой степени. Будем считать, что минимизуруется половина максимально аозможгаго числа термов - 2Т(п-1) степени. Число слов к на терм из п переменных равно к=[(п-1)/8]+1, где [ 1 обозначает целую часть от деления на S. Общэе число слов для хранения данных при минимизации методом Квайна-Иакяласки оценивается величиной к*2Т (п-1). Число термов t при простой минимизации совпадает с числом термов выхода и не более 8-ми для ПЛИС типов PAL и серии ЕР, не более 16-ти для 22V10, не более 48-ми для ПЛМ и не зависит от числе переменных п. Число слов для хранения данных при

простой минимизации равно к*г и существенно меньше к*2Т( п-1).

Оценим быстродействие в операциях минимизации за один проход при простой минимизации и минимизации методом Квай-на-Маккласки. Для метода Квайна-Ыаккласки число операций оценивается той же величиной к*2Т(п-1), чтобы не превысить отведенный для минимизации объем памяти. Для метода простой минимизации для склеивания I термов надо выполнить Ь*(1-1)*к/2 операций, для поглощения и неполного склеивания - (;*(С-1)*к. Число операций для одного прохода методом простой минимизации оценивается величиной 1*(1.-1)*к*1. 5 и существенно меньше к*2"Т(п -1).

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

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

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

ЗАКЛКШНИК

По результатам диссертационной работы можно сделат^ следующие выводы:

1. Разработана и проверена при функциональном тестировании

В САПР ПЛИС трехэтапная ранжированно-волновая математическая модель ПЛИС. Эта модель позволяет исследовать как ПЛИС, так и автоматы, содержащие комбинационные и триггерные еыходы. Для волновой модели получена оценка максимального числа шагов п для стабилизации волнового процесса моделирования в виде: n=2*m*m, где ш - число комбинационных выходов.

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

3. Разработаны метод и алгоритм компенсационных матриц для решения одной из задач дискретного программирования - пройти все ребра ориентированного графа состояний так, что суша пройденных ребер будет минимальной. Доказано, что в применении к оптимизации тестирования ПЛИС эта задача всегда имеет решение. Получены условия, при которых эта задача имеет решение для произвольного графа состояний.

4. Предложено представление данных в виде массива минимизации, поэволяющзе сократить время отклика при моделировании и минимизации описания ШШС, пропорциональное числу входных переменных и числу термов, до 10 сек. на 100 тактов (входных векторов) при моделировании 1ШС типа PAL с 16-ю входными переменными и 64-мя термами и до 1 - 2 сек. при минимизации ПЛИС типа PAL на IBM ХТ/АТ-286. Предложенная форма представления данных использовалась при создании САПР ПЛИС.

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

Разработанные математическая модель ПЛИС, методы и алгоритмы полного тестирования ПЛИС и методики минимизации и восстановления ПЛИС реализованы на ШВЫ IBM РС/АТ-286 в составе САПР ЛЛЖ, с использованием которых был разработан, отлажен и

- 23 -

[ротестировак ряд высокоэффективных цифровых устройств.

Основные положения диссертационной работы отражены в сле-1У*зщих публикациях:

1. Чурков ЕМ., Захарова Л. Е. Подсистема проектирования [а ШШ // Микропроцессорные средства и системы (ИПСиС). - и. : псковский эксперименталвный вычислительный центр "Элекс". -' 1989. - N7. 2. - С. 41 - 42.

2. Чурков Е М., Котрелев С. А,, Захарова Л Программное збеспечение САПР цифровых устройств для программируемой матричной логики серии КР1Й56 // ШСиС - 1939. - 2. - с. 35 - 40.

3. Гарбуэов Н. И., Чурков В. И. , Захарова Л Е., Абашкин А. Л., Маркин В. А. САПР ПЛИС на основе ЗУ с произвольной вь'бор-' кой. // Тез. докл. на конференции "Ангомагнзация проектирования РЗА и ИВА", Пенза - 15-16 окт. 1990.-- 3 с;

4. . Гарбуэов Н. И , Чурков В. 11, Захарова Л. Е., Абашкин А. Л., Маркин В. А. САПР ПЛИС // Тез. докл. на конференции "Автоматизация проектирования РЭА и ИВА", Пенза - 15-16 окт. 19Э0. -2 с.

5. Чурков В. И., ЗДанов Е С., Захарога Л. Е. Методы и примеры построен^" цифровых устройств на базе' ПЛИС // Тез. докл. на конференции в ЫГКЗМ "Микросисте(,'1-93", Шсква - 8-Ю дет 1993. - 3 с.

6. Жданов Е С., Захарова Л Е. Штод полного автоматизированного тестирования ПЛИС // Гез. докл. на конференции в ■ .15ГИЭМ "Микросистема-93", Москва- Ь-10 дек. 1993. - 3 с.

7. Захарова ЛЕ. Матричные методы автоматизации годного • тестирования ПЛИС // Тез. докл. на научно-технической конференции-конкурсе студентов, аспирантов и молодых специалистов МГИЭМ, Москва - 27- 29 апр. 1994. - 1 с.

8. Жданов В.'С., Чурков В. Л , Захарова Л Е. Ьйтоды математического моделирования работы ПЛИС // Тез. Докл.- на Межгосударственной научно-практической конференции творческой молодежи "Актуальные проблемы рэтоматики: математическое, программ?-е- и информационное обеспечение", Минск, БГУ - 16-20 мая 1994. - 2 с.

9. Захарова Л Е. Восстановление описания по результатам тестирования ПЛИС // Тез. докл. на научно-технической конференции студентов, аспирантов и молодых, специалистов ' МГИЭМ, Косква - 17-24 апр. 1995. - 1

■ ; . к'