ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

РАДІОЕЛЕКТРОНІКИ

КОВАЛЬОВ ЄВГЕН ВІКТОРОВИЧ

УДК 681.32:519.713

ПРОЕКТУВАННЯ МОДЕЛЕЙ ЦИФРОВИХ АВТОМАТІВ

ДЛЯ ГЕНЕРАЦІЇ ТЕСТІВ У СЕРЕДОВИЩІ ACTIVE-HDL

05.13.12 – системи автоматизації проектувальних робіт

АВТОРЕФЕРАТ

дисертації на здобуття вченого ступеня

кандидата технічних наук

Харків 2000

Дисертацією є рукопис.

Робота виконана в Харківському державному технічному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник доктор технічних наук, професор Хаханов Володимир Іванович,

Харківський державний технічний

університет радіоелектроніки, професор

Офіційні опоненти: доктор технічних наук, професор

Хажмурадов Манап Ахмадович,

Національний науковий центр

“Харківський фізико-технічний інститут”, начальник відділу;

кандидат технічних наук

Литвинова Євгенія Іванівна, Харківський державний технічний

університет радіоелектроніки, доцент кафедри проектування й експлуатації електронних апаратів

Провідна установа: Національний технічний університет України “КПІ”, Міністерство освіти і науки України, м. Київ

Захист відбудеться 27 березня 2001 року о 14 годиі на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському державному технічному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитися в бібліотеці Харківського державного технічного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий 26 лютого 2001 року

Вчений секретар

спеціалізованої вченої ради Безкоровайний В.В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Проектування обчислювальних пристроїв орієнтується на два основних напрямки. Перший пов’язаний з новими технологіями розробки універсальних і спеці-алізованих процесорів із щільністю до 15 млн. вентилів на кристалі для персональних і суперкомп’ютерів. Останні досягнення в даній області пов’язуються з багато-процесорними обчислювальними пристроями великої продуктивності. Вітчизняна наука практично не може впливати на розробки, щодо досягнень в області hardware універсальних комп’ютерних систем. Другий напрямок відноситься до області розробки й проектування спеціалізованих обчислювальних керуючих пристроїв на основі використання програмувальних логічних інтегральних схем (ПЛІС). Помітний прогрес у зростанні виробництва ПЛІС пов’язаний з підвищенням їхньої ролі на ринку обчислювальної техніки. Це визначається: зниженням їхньої вартості за рахунок упровадження технології Hardware-Software Cooperation, високим ступенем інтеграції (до 12 млн. вентилів на кристалі), зменшенням часу реалізації проекту (2 - 4 тижні) на основі використання Field Programable Gate Array (FPGA), Complex Programable Logic Device (CPLD), низькою вартістю проекту в порівнянні з використанням сигнальних чи універсальних процесорів, наявністю ефективних програмних засобів автоматизованого проектування цифрових обчислювальних пристроїв. Структура технологічного процесу створення програмно-апаратного пристрою керування містить:–

мови опису апаратури (VHDL, Verilog, Superlog, Abel, System C), що використовуються в системах проектування таких фірм як: Aldec, Altera, Cadence, Actel, Mentor Graphics, Xilinx, Sinopsys;–

засобу моделювання формальної і тестової верифікації проектів на пове-дінковому та вентильному рівнях;–

програмних пакетів синтезу цифрових пристроїв у вигляді комплектуючих примітивів, що маються в наявності на кристалах ПЛІС;–

системи трасування і розміщення для конкретної реалізації FPGA, CPLD.

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

Інакше кажучи, там, де існує автоматизоване чи ручне перетворення інформації, необхідно практично чи теоретично доводити тотожність вихідної моделі (сертифікація) і одержуваної (реалізації).

При існуючому різноманітті вихідних форм опису проектів можна виділити найбільш популярні у світі: аналітичні – мови опису апаратури, графічні або візуальні – ієрархічні цифрові структури і схеми, графи переходів автоматів. Як правило, кожна промислова програма прагне мати всі можливі інтерфейси для того, щоб задовольнити самого вишуканого споживача на ринку систем проектування.

Однією з розповсюджених форм вихідного опису спеціалізованого цифрового обчислювального пристрою є граф переходів автомата. Достоїнства згаданої форми полягають у наочності і технологічності зображення функцій, що просто перетворюються в табличну форму внутрішнього опису автомата у вигляді кубічних покрить. Тому такий спосіб представлення проекту мається у всіх системах провідних фірм світу.

Однак під таку реалізацію цифрового пристрою практично відсутні засобу синтезу тестів для верифікації і діагностування проекту. Аналогами тест-генераторів для граф-схем можуть служити системи: State-CAD фірми Visual Software Solutions, Escalade фірми Mentor Graphics, TetraMax фірми Synopsys. Тому проблема генерації тестів, що перевіряють, для цифрових автоматів, які описані у вигляді графів переходів і реалізовані на кристалах ПЛІС, є дуже актуальною для американського та європейського ринків.

Значний внесок у рішення проблем тестування управляючого автомата і його компонентів внесли вчені: В.М.Глушков, В.А.Якубайтис, П.П.Пархоменко, А.М. Романкевич, Д.В.Сперанський, Р.Й.Убар, Ю.В.Малишенко, Ю.А.Скобцов, С.Г.Шаршунов, А.Д.Закревський, В.Н.Ярмолик, Ю.Л. Сагалович, M.Breuer, A.Friedman, S.Thatte, J.Abraham, M.Abramovici, D.Agwaral, J.Hayes, Y.Zorian, B.Courtois, I.Pomeranz, S.M.Reddy.

Актуальність теми. Цифрові автомати, що представлені у вигляді змістовного графа, знаходять широке застосування у користувачів САПР, що проектують системи на основі FPGA, CPLD, ASIC. У процесі проектування неминуче виникають задачі верифікації і тестування, для чого необхідно проектувати тести, що перевіряють. Генерація тестових наборів вручну – процес, що займає значний час і вимагає високої кваліфікації проектувальника. Рішення задачі автоматичної генерації тестів дозволяє істотно скоротити загальний час створення проекту в системі Active-HDL.

Зв’язок дисертації з науковими програмами, планами, темами. Реалізація результатів роботи здійснювалася відповідно до планів виконання НДР і договорів:

453-1 – “Дослідження і розробка перспективних способів проектування і діагностики електронних систем із застосуванням їх у навчальному процесі по ком-п’ютерній інженерії”; № гос. реєстрації 0196U011364.

522-1 – “Розробка учбово-методичного забезпечення і програмно-апаратних засобів для нових навчальних дисциплін з комп’ютерних наук і комп’ютерної инженерії”, № гос. реєстрації 0197U012176.

102 – “Розробка основ нових інформаційних технологій в автоматизованому проектуванні, діагностиці засобів радіоелектронної апаратури й обчислювальної техніки”, № гос. реєстрації 0100U03417.

Університетська програма міжнародного співробітництва в області освіти, науки “Стратегічне партнерство” від 10.03.2000.

Договір про науково-технічне співробітництво з фірмою Аldес Inc. (Las-Vegas, Nevada, USA) від 6.06.1999 р.

При виконанні робіт із зазначених тем автор брав участь як виконавець і консультант.

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

Об’єкт дослідження – цифрові керуючі системи, що проектовані на основі використання мов опису апаратури високого рівня.

Предмет дослідження – моделі цифрових керуючих систем, що представлені у вигляді змістовних граф-схем у середовищі Active-HDL для генерації тестів цифрових пристроїв, які реалізовані на основі FPGA, CPLD.

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

Мета роботи – розробка моделей керуючих автоматів і їх компонетів на основі змістовного графа автомата у середовищі Active-HDL для зменшення часових витрат при верифікації цифрового проекту шляхом автоматичної генерації тестів.

Для досягнення поставленої мети в роботі розв,язуються задачі:–

розробка математичної моделі змістовного графа автомата, що містить управляючий автомат і компоненти операційного;–

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

розробка математичних моделей несправностей змістовного графа автомата і предикатних функцій збудження з метою генерації тестів;–

розробка детермінованого методу генерації тестів для змістовного графа автомата шляхом рішення настановної задачі на безлічі предикатних функцій збудження;–

розробка лінгвістичного, інформаційного, програмного, методичного забезпечень автоматичного генератора тестів ASFTEST, що підтримує стандарти VHDL, Verilog, і його інтегрування в систему проектування Active-HDL.

Наукову новизну, що виноситься на захист, складають:–

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

математична модель предикатної функцій збудження управляючого автомата, що підтримує 6 типів змінних стандартів VHDL і Verilog;–

математичні моделі несправностей змістовного графа автомата і предикатних функцій збудження, що відносяться до опису об’єкта на функціональному й алгоритмічному рівнях;–

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

Практичне значення отриманих результатів вирішують задачі:–

синтаксичного і семантичного контролю вихідного опису цифрового проекту, що представлений на мовах опису апаратури VHDL і Verilog з наступною трансляцією в абстрактне дерево синтаксичного аналізу;–

генерації тестів на основі застосування 4-х стратегій обходу компонентів графа з вирішенням задачі установки на основі зворотньої імплікаціїза предикатними функціями збудження;–

моделювання справної поведінки змістовного графа на алгоритмічному рівні з метою верифікації згенерованого тесту;–

форматування отриманого тесту до стандарту VHDL з метою його використання в системах автоматизованого проектування для верифікації цифрових проектів;–

розробки лінгвістичного, інформаційного, програмного, методичного забезпечень автоматичного генератора тестів ASFTEST і його інтегрування в систему проектування Active-HDL.

Результати дисертації у вигляді програмних додатків використовуються на підприємствах: Aldec Inc. (Las-Vegas, Nevada, USA); Міжнародний консорціум “Енергозбереження” і ЗАТ “Харэнергоремонт” (Харків); а також у навчальному процесі ХТУРЕ і Тернопільського технічного університету.

Особистий внесок здобувача: [1] – математичні моделі змістовного графа автомата, генерації тестів для функцій збудження, зворотньої імплікації для розв,язання настановної задачі; [2] – модель предикатної функції збудження управляючого автомата, моделі несправностей змістовного графа автомата і предикатних функцій збудження, детермінований метод генерації тестів для змістовного графа автомата на основі модифікації П-алгоритма для предикатних функцій, програмна реалізація системи генерації тестів ASFTEST; [3] – моделі несправностей і виконання прямої імплікації на кубічних покриттях; [4] – адаптація автоматної моделі до опису базових осередків однорідних обчислювальних структур у табличній формі з метою спрощення задачі генерації тестів; [5-7] – моделі процесів виконання прямої і зворотньої імплікацій на кубічних покриттях цифрових автоматів; [8] – розробка алгоритму переходу від змістовного графа мікропрограми до змістовного графа автомата; [9] – алгоритмічна і програмна реалізація системи генерації тестів для цифрових автоматів.

Апробація результатів досліджень здійснювалася на: 8-й Міжнародної школі-семінарі “Перспективні системи керування на залізничному, промисловому і міському транспорті”, Алушта, 1995; 13-й Міжнародної школі-семінарі “Перспективні системи керування на залізничному, промисловому і міському транспорті”, Алушта, 2000; міждержавному науково-технічному семінарі “Надійність, відмовостійкість і продуктивність інформаційних систем”, Туапсе, 2000; науково-технічних конференціях професорсько-викладацького складу Харківського державного технічного університету радіоелектроніки (1995-2000).

Публікації. Основні результати роботи опубліковані в 9 наукових працях, серед яких 6 статей у виданнях, що затверджені ВАК України, інші 3 є тезами доповідей на конференціях.

Структура й обсяг дисертації. Дисертаційна робота містить 238 сторінки, 38 малюнків (на 26 с.), 6 таблиць(на 5 с.). Її структура включає: вступ, 4 розділи, висновок, список використаних джерел з 147 назв (на 14 с.), 3 додатки (на 35 с.).

ЗМІСТ РОБОТИЗМІСТ РОБОТИ

Вступ містить обґрунтування актуальності проблеми, що розв,язується, формулювання мети, об’єкта і задач дослідження, сукупність наукових результатів, що виносяться на захист, зведення про їхню апробацію і практичну реалізацію.

Перший розділ являє собою оглядовий і критичний аналіз розвитку основних наукових напрямків технічної діагностики, що пов’язані з існуючими моделями цифрових об,єктів; моделюванням несправностей і справної поведінки цифрових пристроїв; генерацією тестів для кінцевих автоматів. Більш 90% наведених публікацій вийшли у світло за останні три роки. Інші представлені канонічними монографіями більш ранніх років вітчизняних (країн СНД) і закордонних авторів. Що стосується моделей, то з чотирьох основних форм опису дискретних об,єктів: поведінкової (мовної), аналітичної, графічної, табличної – перевага віддається останньої, яка зручна для сприйняття інформації людиною, технологична – для машинного логічного аналізу, оскільки містить явні рішення задач прямої і зворотньої імплікації. Недолік таблиць – розмірність – не є істотним для опису автоматів керування, оскільки формальне завдання графа переходів можливо лише в доступних для огляду і для проектувальника розмірах. Вихідне завдання цифрового пристрою в основному представлено мовами опису апаратури високого рівня. Тут мова йде про структури: Abel, Verilog, VHDL, System C, що представлені у порядку зростання їхніх функціональних можливостей. Перший є найбільш простим за синтаксисом для опису функцій цифрових виробів. Verilog, виходячи з мети його розробки, орієнтований на рішення задач моделювання і генерації тестів. Мова VHDL ефективно вирішує задачі компактного опису і створення проекту багаторівневої ієрархії. Мову System C можна вважати найбільш перспективною, оскільки вона є розширенням мови С шляхом її доповнення засобами VHDL.

Виходячи зі значних потенційних розмірів об’єкта тестування, що нараховує мільйони вентилів, до засобів моделювання пред’являються суперечливі вимоги високої швидкодії й адекватності. Крім того, існують задачі моделювання об’єктів, що представлені на поведінковому рівні опису. У цьому випадку актуальним є підтримування стандартів згаданих мов високого рівня при побудові швидкодіючих компіляторів чи трансляторів. Крім того, корисно мати додаткові засоби аналізу цифрових виробів, такі як логічні аналізатори для виконання зворотної імплікації, активізації одне- чи багатомірних логічних шляхів. Природно, що найбільш істотними і потребними на ринку проектування є швидкодіючі засоби проектування тестів перевірки справного поводження і/чи несправностей заданого класу. Щодо кінцевих керуючих автоматів мова йде про стратегії такого обходу станів і переходів автомата, що забезпечують реальну верифікацію цифрового проекту, а також перевірку справності синтезованого пристрою на основі FPGA, CPLD у припустимому часовому інтервалі. При цьому інтерес становить і роз-в,язання задачі установки вхідних, внутрішніх і вихідних змінних операційного й управляючого автоматів, що забезпечують виконання переходу, який міститься в стратегії тестування управляючого автомата. Розділ закінчується формулюванням мети і задач дослідження.

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

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

Концептуальна модель об’єкта, що оперує дискретною інформацією, зображена тріадою компонентів: F = <f, t, h>, де f, t, h – дискретні параметри опису функцій, часу, структури. Проблема верифікації реалізації проекту з метою аналізу тотожності функцій, структури часових співвідношень для конкретної специфікації розглядається в рамках самої повної f-t-h-cтруктури, у той час як генерація тестів, що перевіряють, цілком може обходитися f-h-моделлю об’єкта.

Одне з можливих взаємодій простору функцій і структури в часі (модельному) подано універсальною концепцією автомата першого роду, що диференціюється на керуючу й операційну частини: SM={CM, OM}. У процесі проектування кінцевого автомата розроблювач не піклується про строгий поділ на керуючу й операційну частини. Його метою є зменшення часу проектування й апаратурних витрат автомата в цілому. Для цього використовуються додаткові змінні пам’яті у вигляді сповіщальних сигналів. При цьому автоматна модель послідовнісного примітива зображується у вигляді M=<X, Y, Z, f, g>, де X=(X1,X2,...,Xi,...,Xm), Y=(Y1,Y2,...,Yi,...,Xh), Z=(Z1,Z2,...,Zi,...,Zk) – безлічі вхідні, внутрішні і вихідні автоматні змінні, відносини між якими описуються узагальненими рівняннями кінцевого автомата:

Y(t)=f[X(t-1), X(t), Y(t-1), Z(t-1)];

Z(t)=g[X(t-1), X(t), Y(t-1), Y(t), Z(t-1)].

Змінні Z(t) відрізняються від Y(t) тим, що перші можуть спостерігатися за вихідними лініями, а Y(t) у цьому сенсі є внутрішні.

Кінцевий автомат довільної складності може бути представлений таблицею істинності чи кубічним покриттям, як однією з найбільш простих і технологічних для комп’ютерного аналізу форм опису. У цьому випадку мається на увазі, що функціональний послідовнісний примітив задається компонентами: F2 =<(t-1,t), (X,Z,Y),{A2}>, де (t-1,t) – два автоматних сусідніх такти в описі функції; {A2} – двотактний алфавіт опису станів (переходів) автоматних змінних:

A2={Q=00,E=01,H=10,J=11,O={Q,H},I={E,J},A={Q,E}, B={H,J}, S={Q,J}, P={E,H}, C={E,H,J}, F={Q,H,J},L={Q,E,J}, V={Q,E,H},Y={Q,E,H,J}, A1={0,1,X={0,1}}, (U)}. Кубічне покриття є система відносин векторів вхідних, внутрішніх і вихідних змінних, що задані у багатозначному теоретико-множинному алфавіті опису автоматних змінних: C = (C1, C2, ..., Ci, ..., Cn), де Ci = (Ci1, Ci2, ..., Cij, ..., Ciq) – куб, що включає вхідні, внутрішні, вихідні координати Ci = (Ci, Ci, Ci), q=m+h+k. Для комбінаційного автомата формат опису кубічного покриття F1 = <(t),(X,Z),{A1}> визначається відносинами на (q=m+k)-мірному векторі змінних Ci = (Ci, Ci). Формат задає багатовихідний комбінаційний примітивний елемент із m входами і k виходами. Для послідовнісного автомата загальним випадком є формат опису примітива: F2 = <(t-1,t),(X,Z,Y),{A2}>.

В основу методів аналізу цифрових пристроїв покладені процедури прямої і зворотньої імплікації кубічного покриття C, що задає відносини між вхідними, внутрішніми і вихідними змінними за допомогою символів A-алфавіту.

Для вирішення задачі прямої імплікації F(X,Z)фX*=1 (Х* – вхідна умова) в одному часовому фреймі виконується процедура об’єднання перетинань

.

Одержання результату Х**№Х* чи Y**=Ж є свідченням неповноти покриття. При трійковому алфавіті завдання вхідного слова Х* стану виходів визначені символами {0,1,X,Ж}. Використання символу порожньої безлічі Z (Z З U =U, Z И U =Z) на додаток до алфавіту {0,1,X} для визначення координат покриття не суперечить процедурі об’єднання перетинань.

З метою максимальної адаптації моделі (рис.1) до змістовного графа автомата, що описаний у середовищі Active-HDL, уводиться залежність управляючого автомата від станів сповіщальних сигналів Z = (Z1, ..., Zj, ..., Zk) операційного автомата (див. рис.1).

Рис. 1. Модель автомата для середовища проектування Active-HDL

Функції операційного пристрою W-автомата W=<X, Y, Z, f, g, h>, визначаються характеристичними рівняннями:

Yt = f(Xt, Yt-1, Zt-1);

Zt = g(Xt, Yt-1, Zt-1);

Xt = h(Wt, Yt-1, Zt-1).

Тут h являє собою предикатну функцію збудження чи ініціалізації переходів у кінцевому автоматі, де Xt = {0,1} – вихідна функція для активізації переходу (якщо Xt = 1); W – керуючі впливи в стандартах мови WHDL: W = {WBО, WBI, WBIV, WSTDL, WSTDLV, WI}, де WBО = {false, true} – змінні типу boolean; WBI = {0,1} – змінні типу bit; WBIV = (WBI...WBI) – змінні типу bit_vector; WSTDL = {X – Forcing Unknown, 0 – Forcing 0, 1– Forcing 1, Z – High Impedance, W – Weak Unknown, L – Weak 0, H – Weak 1, “–” – Don’t care} – змінні типу std_logic; WSTDLV = (WSTDL...WSTDL) – змінні типу std_logic_vector; WI = [-2147483647 – 2147483647] – змінні типу integer.

Стратегія тестування управляючого автомата визначається W-процедурою генерації тестів, що містить виконання трьох кроків.

1. Побудова тесту обходу всіх дуг графа за таблицею переходів.

2. Розв,язання задачі зворотньої імплікації за функцією X=h(W) для обчислення вхідних послідовностей у термінах стандарту VHDL.

3. Розв,язання задачі установки в часі й у просторі, якщо для активізації переходів використовуються сигнали з безлічі Z.

4. Модифікація шляху рішення настановної задачі у випадку відсутності рішення для обраних сигналів з безлічі Z.

Функціональних властивостей класичних автоматів Мура чи Милі часто не вистачає для оптимальної реалізації керуючих впливів – функцій виходів автомата. Тому в системі проектування Active-HDL передбачений наступний формат опису таблиці переходів графа автомата:

,

де – чотири операції, що можуть виконуватися для кожної пари <X, Y,>. Акція відповідає вихідному стану переходу автомата (вершині-джерелу для розглянутого переходу); – акція, що ототожнюється з виходом з вихідного стану переходу; – акція, що ототожнюється із самим переходом; – акція, що ототожнюється з входом у кінцевий стан переходу. Для переходу-скидання (Reset) існують тільки два типи операцій (,).

Проблема одержання тесту обходу всіх вершин і дуг графа переходів пов’язана з розв,язанням задачі установки умов переходу: . Формально вона зводиться до зворотньої імплікації на функції збудження для розглянутого переходу . Якщо значення , то перехід виконується, у протилежному випадку () – ні. У загальному випадку вхідна змінна визначається типами:

{WBО, WBI, WBIV, WSTDL, WSTDLV, WI}.

Предикатним називається примітив (W-елемент), що має в якості вхідних змінні типи з безлічі W, а значення виходу визначене на безлічі сигналів {false, true} чи {0, 1}. Схемна структура, що складена з предикатних елементів, визначає предикатну функцію збудження чи h-функцію. Зовнішні вхідні змінні такої структури визначені на безлічі W. Значення внутрішніх і вихідних ліній предикатної функції дорівнюють {0, 1}. Змінні типу {WBIV, WSTDL, WSTDLV, WI} можуть бути тільки зовнішніми входами. Аналітичний запис предикатної функції містить дужки, знаки ко-н,юнкції, диз’юнкції, заперечення, інші логічні й арифметичні операції, що підтримуються в стандарті VHDL. Будь-якому предикату, що представлений в аналітичній формі, можна поставити у відповідність таблицю істинності чи кубічне покриття. Функція збудження є взаємозалежна структура типів функцій, кожна з яких на виході має двійкове значення. Це означає, що до такої схеми можна застосувати модифікований П-алгоритм [2], який за одиничним станом функції збудження визначить рішення у вигляді вхідних сигналів, що забезпечують необхідний перехід .

Основою модифікованого П-алгоритма є ітеративна процедура

,

що виконується на безлічі вхідних, внутрішніх і вихідних змінних <X,Z,Y>, де p – число примітивів у схемній структурі; – оператор мінімізації, який призначений для склеювання кубів (векторів), що відрізняються за однією змінною; – оператор поглинання, який призначений для зменшення числа кубів за рахунок виключення надлишкових; – таблиці розв,язків, що одержані після обробки кожного кубічного покриття (КП) за правилами; – КП i-го примітива схемної структури.

Модифікація алгоритму стосовно канонічного полягає у використанні оператора перетинання замість підстановки, а також у виконанні операцій мінімізації і поглинання після обробки кожного КП. Така модифікація приводить до зменшення часу одержання КП у 2-10 разів.

Модель проектування кубічного покриття примітива предикатної функції визначається доповненням одиничних кубів нульовими, які виходять шляхом векторного вирахування одиничних кубів з їхніх доповнень з наступною мінімізацією. Тут операція векторного вирахування між Ci і Cj визначається як:

доповнення до координати Cij куба визначено виразом

а доповнення до куба Ci задається формулою

.

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

Наведено опис моделей несправностей цифрового автомата як об’єднання самотніх несправностей переходів і константних дефектів, що є теоретичною основою для перевірки функціонування й оцінки якості тестової послідовності цифрового автомата.

Уведено поняття внутрішнього зображення моделі змістовного графа автомата як структур даних, що є технологічними для генерації тестів і логічного аналізу. Вона являє собою декомпозицію змістовного графа автомата, що крім канонічного зображення автомата у вигляді функцій збудження і виходів має: перетворювач сигналів зі стандартних типів мов VHDL і Verilog у внутрішнє представлення; функції аналізу цілочислових операндів і бітових операндів. Така декомпозиція дозволяє розподілити процес генерації тестів на дві стадії: тестування автомата, рішенням якої є послідовність символів його вхідного алфавіту, й активізацію отриманих символів на вході автомата, для якої необхідний аналіз додаткових внутрішніх станів і рішення задачі зворотньої імплікації.

Однією з основних відмінностей розробленого методу генерації тестів від існуючих є послідовність виконання основних кроків: спочатку виконується процедура перебування мінімального шляху обходу, а потім здійснюється активізація знайденого шляху. Такий підхід дозволяє одержати 100% якість тесту стосовно впровадженого типу несправностей для структур, що не тестувалися цілком продуктом-аналогом фірми Visual Software Solutions Inc. StateCAD.

Перебування мінімального шляху обходу станів для різних стратегій приводить до можливості застосування відомих методів теорії графів і комбінаторики. Рішення задачі однократного обходу станів приводить до задачі комівояжера, що ефективно розв’язується за допомогою методу гілок і границь. Задача виконання всіх переходів вирішується шляхом визначення квазіейлерова шляху. Задача переходу зі стану Si у стан Sj вирішується побудовою матриці довжин. Оскільки в багатьох випадках необхідне вирішення всіх трьох, то для розв,язку задачі комівояжера і для визначення квазіейлерова шляху використовується побудована матриця довжин, що для змістовного графа автомата має істотні відмінності, які пов’язані з переходами за сигналом скидання, для яких вихідний стан не визначений.

Увага приділена питанню досяжності станів. Проблема полягає в тому, що через наявність додаткових внутрішніх змінних у функції збудження отриманий шлях може не існувати для змістовного графа. У цьому випадку необхідна модифікація шляху, що в загальному випадку приводить до NP-повної задачі. Тут процедура пошуку рішення істотно поліпшена шляхом використання евристичного алгоритму модифікації шляху, що розроблений на основі аналізу конструкцій змістовного графа автомата (операції инкремента, декремента, що накопичують підсумовувачі), що найбільше часто зустрічається.

Для рішення задачі забезпечення активізації отриманого шляху запропонована модель внутрішнього зображення змінних у вигляді інтервалів цілих чисел і інтервалів бітових значень. Інтервал задається у вигляді двох чисел, мінімального і максимального. Необхідно помітити, що при описі автомата для кожної цілочислової змінної задається область визначення. Бітові вектори представлені у вигляді цілих чисел.

Подібне зображення даних ефективно у випадку використання операцій з цілими числами. Розроблено процедури прямої і зворотньої імплікації, що дозволяють перейти від аналізу змінних на всій області визначення до аналізу на більш вузькій області можливих розв,язків. Дані процедури не забезпечують точного рішення, а тільки відтинають ті області, де рішення гарантовано відсутнє. Однак у для простих функцій збудження перебір практично відразу дає відповідь.

Оброблювана підмножина операцій містить і такі, які орієнтовані на цеілочислове зображення змінної (додавання, вирахування, унарний мінус, множення, розподіл, порівняння) і логічне (заперечення, поразрядна кон,юнкція, диз’юнкція, штрих Шеффера, стрілка Пірса, сума за модулем 2 і рівнозначність). Процедури реалізовані за допомогою набору простих операцій, що є присутнім у кожній мові програмування. Процедура узгодження бітових і цілочислових значень сигналу дозволяє застосовувати арифметичні і логічні операції для тих самих змінних, що дуже важливо для мов VHDL і Verilog.

Розроблено алгоритм побудови КП за скобковою формою предикатного рівняння. Будь-який умовний оператор мови VHDL може бути представлений предикатним рівнянням у вигляді скобкової форми (СФ). Рішення такого рівняння складається в перетворенні його до ДНФ, що представляється у вигляді кубічного покриття в предикатному алфавіті. Правила побудови КП включають кроки: 1.Опис СФ у вигляді дерева синтаксичного розбору за операціями OR, AND, NOT. 2. Для кожної змінної нижнього ярусу записується куб рангу (k-1) c прямим предикатним значенням на координаті куба, що відповідає даній змінній, k-мірність куба покриття. 3. У вершині (NOT) виконується операція інвертування КП: куб рангу r заміняється n кубами рангу (k-1), де k – мірність, n=(k-r) – кількість координат куба, не рівних X, а далі в кубах рангу (k-1) значущі координати заміняються їхнім доповненням в алфавіті кубічного числення. 4. У вершині (AND) виконується визначення безлічі непорожніх результатів попарного перетинання отриманих кубів з наступним виконанням операції поглинання. 5. У вершині (OR) виконується об’єднання в одне покриття вихідних кубів.

У розділі 4 представлено опис програмного пакета генерації тестів ASFTEST, що розглядається як частина системи Active-HDL, яка призначена для проектування складних цифрових пристроїв і дозволяє виконувати їхній опис на мовах VHDL і Verilog, а також за допомогою програм-надбудов у графічному форматі змістовного графа автомата чи в графічному форматі опису структури пристрою. До складу системи входять програми: керування проектом, уведення проекту на мовах опису апаратури VHDL і Verilog HDL, уведення графічного ієрархічного опису схеми, уведення змістовного графа автомата, компілятори, логічного моделювання, перегляду часових діаграм, формування тестових впливів оператором, перегляду списків, інтегрований відладчик, що припускає покрокове виконання програми, генератори шаблонів і різні сервісні програми. Структура системи генерації тестів зображена на рис. 2.

У якості вхідних дані програми лексичного і семантичного аналізу служить ASF-файл. Дані також можуть надходити у форматі DIA (формат графічного представлення автомата системи StateCAD). Для контролю правильності перекладу у внутрішнє зображення даних може генеруватися VHDL-код автомата. За матрицею мінімальних шляхів перевіряється связність отриманого графа. У випадку, якщо граф не є зв’язковим, побудова тесту, що перевіряє всі стани, неможливо. Далі виконується побудова тесту за одним з алгоритмів.

При використанні стратегії обходу всіх станів за методом гілок і границь будується послідовність обходу всіх станів. Для стратегії обходу всіх переходів будується шлях, що проходить через усі дуги отриманого графа, результат записується у вигляді послідовності станів. Для стратегії скидання в стан і видаються 2n пар елементів матриці шляхів мінімальної довжини, де n – число станів автомата.

Отримана послідовність станів повинна бути активізована за допомогою подачі на вхідні лінії значень, що обчислюються за допомогою процедури зворотньої імплікації. Однак одержання таких значень не завжди можливо внаслідок наявності внутрішніх змінних. У випадку, якщо активізація заданої послідовності станів неможлива, послідовність модифікується шляхом уведення додаткового циклу, у результаті проходження по який інтервал можливих значень необхідної внутрішньої змінної міняється. Після побудови тесту виконується його трансляція на необхідну мову опису апаратури (VHDL чи Verilog HDL, у залежності від того, яка мова обрана автором моделі).

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

Характеристика програмного продукту ASFTEST: Операційна система– Windows 95, 98, NT4.0. Інтегроване середовище проектування – Active-HDL 3.5, 3.6, 4.1, 4.2. Обсяг пам’яті для EXE-модуля – 300 Кбайт. Обсяг вихідного тексту мовою З – більш 500 Кбайт. Використовувані компілятори LCC-Win32 3.1, GCC 2.91.1, компілятор компіляторів PCCTS 1.13MR22. Число програмних модулів – 21. Середній час генерації тестів для реальних об,єктов – 20 с. У загальному випадку час обробки об’єкта пропорційно другого ступеня числа станів графа. Максимальна кількість станів автомата – 200.

ВИСНОВКИВИСНОВКИ

У результаті виконання дисертаційної роботи для досягнення мети – зменшення часових витрат верифікації цифрового проекту шляхом автоматичної генерації тестів на основі модифікації моделей управляючого автомата і його компонентів, що представлені у середовищі Active-HDL, – отримані наступні найбільш суттєві теоретичні і практичні результати:

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

2. Математична модель предикатних функцій збудження управляючого автомата, що підтримує стандарти VHDL і Verilog, яка необхідна для виконання прямої і зворотньої імплікацій у просторі шости типів предикатних змінних;

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

4. Детермінований метод генерації тестів для змістовного графа автомата, що поєднує три стратегії обходу графа і вирішує настановні задачі на безлічі предикатних функцій збудження, дозволяє одержати кращу якість тесту.

5. Лінгвістичне, інформаційне, програмне, методичне забезпечення системи моделювання й автоматичної генерації тестів ASFTEST, що не має аналогів для середовища проектування Active-HDL;

6. Засоби конвертування отриманого тесту до стандартів мов VHDL і Verilog з метою його використання в системах автоматизованого проектування для верифікації цифрових проектів, що необхідні для практичного використання розробленої програми;

7. Тестування програмного продукту ASFTEST на 75 реальних об,єктах і його впровадження в середовище Active-HDL, а також у технологічний процес трьох підприємств і в навчальний процес двох університетів.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇСПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Кривуля Г.Ф., Хаханов В.И., Ковалев Е.В. Проектирование тестов для цифровых устройств на основе FPGA, CPLD// Информационно-управляющие системы на железно-дорожном транспорте.– 2000.– № 4.– С. 120-121.

2. Хаханов В.И., Ковалев Е.В., Ханько В.В., Масуд М.Д. Мехеди. Система генерации тестов для проектирования цифровых автоматов в среде
ACTIVE-HDL//АСУ и приборы автоматики.-– Харьков.– 2000. – Вып.111.– С. 15-22.

3. Хаханов В.И., Ковалев Е.В., Масуд М.Д. Мехеди, Хак Х.М. Джахирул. Кубическое моделирование неисправностей цифрових систем на основе FPGA,CPLD// Радиоэлектроника и информатика.– 1999.-– № 4.– С. 64-71.

4. Таранов В.Б., Кулак Э.Н., Ковалев Е.В. Обеспечение тестопригодности ортогонально связанных матричных структур // Радиоэлектроника и информатика.–1998.– №1.– С.91-94.

5. Хаханов В.И., Монжаренко И.В., Ковалев Е.В. Система компьютерного моделирования цифровых и МП-структур. Материалы 8-й Международной школы семинара "Перспективные системы управления на железнодорожном, промышленном и городском транспорте".– Алушта.– 1995.– Харьков: ХарГАЖТ.–С. 26.

6. Ковалев Е.В., Скворцова О.Б., Побеженко В.В. Метод генерации тестов для константных неисправностей в цифровых схемах. Материалы 13-й Международной школы-семинара "Перспективные системы управления на железнодорожном, промышленном и городском транспорте".–Алушта.–2000.–Харьков:
ХарГАЖТ.– С. 16.

7. Ковалев Е.В., Сысенко И.Ю., Дробязко О.А. Алгоритм кубического моделирования неисправностей цифровых схем. Тезисы докладов шестой международной конференции "Теория и техника передачи, приема и обработки информации".– Туапсе.– 2000.– Харьков:ХТУРЭ.– С. 67-69.

8. Хаханов В.И., Шкиль А.С., Ковалев Е.В. Модель процесса перехода от содер-жательного графа микропрограммы к содержательному графу автомата// АСУ и приборы автоматики.-– Харьков.– 2000. – Вып.112.– С. 112-120.

9. Хаханов В.И., Рустинов В.А., Горбунов Д.М., Ковалев Е.В., Масуд М.Д. Мехеди, Хак Х.М. Джахирул. Система генерации тестов цифровых проектов с среде ACTIVE-HDL//Радиоэлектроника и информатика.– Харьков.-– 2000.-– № 3.– С. 92-101.

АНОТАЦІЯАНОТАЦІЯ

Ковальов Є.В. Проектування моделей цифрових автоматів для генерациії тестів у середовищі Active-HDL.– Рукопис.

Диссертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.12 – системи автоматизації проектувальних робіт.– Харківський державний технічний університет радіоелектроніки, Харків, 2000.

Диссертація присвячена питанням проектувания моделей цифрових керуючих автоматів, поведінка яких представлена на мові VHDL. З метою дотримання стандарту VHDL розроблені моделі змістовних графів переходів цифрових автоматів, які орієнтовані на технологічне рішення задач генерації тестів, перевірки справної поведінки та веріфікаційного моделювання. Запропоновані: стратегія тестувания управляючого автомату, яка містить в собі чотири алгоритми обходу верхівок та дуг графу; модифікованний П-алгоритм для знахождения рішень у вигляді вхідних наборів, які устанавлюють автомат у необхідний стан. Моделі опису, генерації тестів реализовані у вигляді програмного продукта ASFTEST, який сумісний з системою Active-HDL та підтримує стандарти мов VHDL, Verilog.

Ключові слова: автоматизоване проектування, цифровий управляючий автомат, логиічне моделювання, генерація тестів.

АННОТАЦИЯАННОТАЦИЯ

Ковалев Е.В. Проектирование моделей цифровых автоматов для генерации тестов в среде Active-HDL.– Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 – системы автоматизации проектных работ.– Харьковский государственный технический университет радиоэлектроники, Харьков, 2000.

Диссертация посвящена вопросам проектирования моделей цифровых управляющих автоматов, поведение которых представлено на языке VHDL. В целях поддержания стандарта VHDL разработаны модели содержательных графов переходов цифровых автоматов, ориентированные на технологичное решение задач генерации тестов, проверки исправного поведения и верификационного моделирования. Предложены: стратегия тестирования управляющего автомата, включающая 4 алгоритма обхода вершин и дуг графа; модифицированный П-алгоритм для нахождения решений в виде входных воздействий, устанавливающих автомат в требуемое состояние. Модели описания, генерации тестов реализованы в виде программного продукта ASFTEST, который совместим с системой проектирования Active-HDL и поддерживает стандарты языков VHDL, Verilog.

Основные результаты работы для достижения цели – уменьшения временных затрат верификации цифрового проекта путем автоматической генерации тестов на основе модификации моделей управляющего автомата и его компонентов, представленных в среде Active-HDL, – выносимые на защиту:–

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

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

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

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

– лингвистическое, информационное, программное, методическое обеспечения системы моделирования и автоматической генерации тестов ASFTEST, интегрированной в среду проектирования Active-HDL;

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

– тестирование программного продукта ASFTEST более, чем на 100 реальных обьектах и его внедрение в среду Active-HDL, а также в технологический процесс трех предприятий и в учебный процесс двух университетов.

Практическое значение полученных результатов состоит в:–

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

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

моделировании исправного поведения содержательного графа на алгоритмическом уровне в целях верификации сгенерированного теста;–

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

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