ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
РАДІОЕЛЕКТРОНІКИ
СКВОРЦОВА ОЛЬГА БОРИСIВНАМд. МЕХЕДІ МАСУД
УДК 681.32:519.713
ПРОЕКТУВАННЯ ТЕСТIВ ДЛЯ ПОСЛIДОВНОСНИХ ФУНКЦIОНАЛЬНИХ СХЕМ, ЩО РЕАЛIЗОВАНI У ПРОГРАМОВАНIЙ ЛОГIЦIПРОЕКТУВАННЯ ТЕСТIВ ДЛЯ ПОСЛIДОВНОСНИХ ФУНКЦIОНАЛЬНИХ СХЕМ, ЩО РЕАЛIЗОВАНI У ПРОГРАМОВАНIЙ ЛОГIЦIМОДЕЛІ ТА АЛГОРИТМИ ГЕНЕРАЦІЇ ТЕСТІВ ДЛЯ ЦИФРОВИХ СИСТЕМ, ЩО ПРОЕКТУЮТЬСЯ У СЕРЕДОВИЩІ VHDL
05.13.12 – системи автоматизації проектувальних робіт
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Харків 2002
Дисертацією є рукопис.
Робота виконана в Харківському нацiональному університеті радіоелектроніки, Міністерство освіти і науки України.
Науковий керівник доктор технічних наук, професор Хаханов Володимир Іванович,
Харківський державний технічний університет
радіоелектроніки, професор кафедри
автоматизації проектування обчислювальної техніки
Офіційні опоненти: доктор технічних наук, професор
Дербунович Леонід Вікторович,
Національний технічний університет “Харківський політехнічний інститут”, професор кафедри автоматики і управління в технічних системах.
кандидат технічних наук Литвинова Євгенія Іванівна,
Харківський державний технічний університет
радіоелектроніки, доцент кафедри технології і автоматизації
виробництва радіоелектронних засобів та
електронно-обчислювальних засобів
Провідна установа: Національний технічний університет України “КПІ”,
Міністерство освіти і науки України, м. Київ
Захист відбудеться 23 квітня 2002 року о 14 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському нацiональному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
З дисертацією можна ознайомитися в бібліотеці Харківського державного технічного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
Автореферат розісланий 20 березня 2002 року
Вчений секретар
спеціалізованої вченої ради Безкоровайний В.В.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Рівень розвитку мікроелектроніки є визначальним для побудови причинно-наслідкової ієрархії створення нових систем: мікроелектронні субмікронні технології – схемотехнічні стандарти – системно-технічні рішення. На середньому рівні цифрової техніки найбільш популярні три базові компоненти: мікропроцесорні БІС (CPU); замовлені БІС (ASIC); програмовані логічні інтегральні схеми – ПЛIС (CPLD, FPGA).
Постійно конкуруючи один з одним, вони складають базу імплементації синтезованих цифрових систем на основі використання універсального дорогого процесора або шляхом створення спеціалізованого обчислювача. В останньому випадку конкурентна боротьба виграється більш дешевими і менш трудомісткими при проектуванні ПЛIС. Але дійсну революцію в області високих технологій проектування зробило об’єднання переваг універсального процесора зі швидкодією і можливостями реконфігурації ПЛIС. Така інтеграція породила нову ефективну концепцію створення цифрової обчислювальної системи – Hardware - Software Cooperation Design. При цьому ПЛIС виграли тверду конкуренцію на ринку мікроелектроніки, вступивши у вигідний союз з CPU. Останні придбали нові якості: висока швидкість паралельної обробки даних і можливість перенастроювання обчислювальної системи для ефективного вирішення конкретного класу задач. Поява нових виробів мікроелектроніки і схемотехнічних рішень породило новий об’єкт діагностичного обслуговування у виді структурно і функціонально складної реалізації цифрової системи на кристалі ПЛIС. Проблема тестування такого об’єкта визначається протиріччям між необхідністю проектування тестів для верифікації цифрових систем за прийнятний час у межах декількох годин, з одного боку, а з іншого боку – можливістю обробки проектів на основі ПЛIС, що складають сотні тисяч еквівалентних вентилів.
Відмовляючись від розробки дорогих і універсальних алгоритмів генерації тестів для різних типів об’єктів діагностування, у якості основної застосовується стратегія послідовного нарощування функцій системи генерації тестів завдяки створенню алгоритмів, що орієнтованi на обробку окремих типів цифрових структур. Це дозволяє створювати працююче ядро системи генерації тестів, яке вже в процесі експлуатації поповнюється новими модулями, що реалізують функціональні можливості, які раніше були відсутні у системі. Така стратегія створення САПР використовується практично усіма ведучими фірмами світу, що працюють в області нових технологій створення програмного й апаратного забезпечення цифрових систем.
В областi автоматизованого проектування і тестування цифрових пристроїв і систем великий внесок додали вчені: J.P.Roth, D.B.Armstrong, О.Ф.Немолочнов, А.Г.Биргер, Y.H.Levendel, M.A.Breuer, M. Abramovici, Д.В.Сперанский, П.П.Пархоменко, Р.Й.Убар, В.П.Чипулис, .Ю.А.Скобцов, Л.В.Дербунович, Ю.В.Малишенко, В.Н.Ярмолик, В.А.Твердохлебов.
Актуальність теми. Поява нових об’єктів діагностичного обслуговування у виглядi структурно і функціонально складної реалізації цифрової системи чи її частини на кристалах ПЛIС породило проблему тестування таких об’єктів. Вона визначається необхідністю проектування тестів для верифікації цифрових систем і можливістю обробки реалізацій проектів на основі ПЛIС. З огляду на те, що гранична складність вирішення задачі генерації тестів детермiнованим способом є NP повною, доцільно використовувати стратегію пошуку раціональних рішень поліноміальної складності для окремих класів об’єктів діагностування. У зв’язку з цим актуальною виявляється задача розробки раціональних алгоритмів генерації тестів для функціональних структур реалізацій цифрових пристроїв, до яких належать тригернi і сильнопослiдовносні схеми. Ці структури, будучи атрибутом реалізації об’єкта на ПЛIС, складають компоненти, найбільш складні з погляду проблеми їхньої верифікації. Для її вирішення необхідно синтезувати тести перевірки справної поведiнки або несправностей заданого класу.
Зв’язок роботи з науковими програмами, планами, темами. Реалізація результатів роботи здійснювалася відповідно до планів виконання НДР і договорів:
522-1 – “Розробка навчально-методичного забезпечення і програмно-апаратних засобів для нових навчальних дисциплін з комп’ютерних наук і комп’ютерної инженерії”, № держ. реєстрації 0197U012176.
102 – “Розробка основ нових інформаційних технологій в автоматизованому проектуванні, діагностиці засобів радіоелектронної апаратури й обчислювальної техніки”, № держ. реєстрації 0100U03417.
Університетська програма міжнародного співробітництва в області освіти, науки “Стратегічне партнерство” від 10.03.2000.
Договір про науково-технічне співробітництво з фірмою Аldес Inc. (Las-Vegas, Nevada, USA) від 6.06.1999 р.
При виконанні робіт із зазначених тем автор брав участь як виконавець і консультант, був одним з розроблювачів програмних засобів автоматичної генерації тестів.
Мета дослідження – розробка моделей і алгоритмів детермiнованої генерації тестів для тригерних і сильнопослiдовносних структур цифрових систем, якi проектуються, що дозволяють зменшити час їхньої верифікації.
Для досягнення поставленої мети формулюються наступнi задачі:–
удосконалення концептуальної і структурної моделей примітивного автомата для опису тригерних структур з метою моделювання їхньої справної поведiнки і генерації тестів;–
удосконалення моделі для реалізації структурно-функціонального - алгоритма побудови кубічних покрить для тригерних структур, що описанi у виглядi булевих рівнянь, з метою зменшення часу їхнього аналізу і детермiнованої генерації тестів;–
модифікація моделі процесу генерації тестів для верифікації цифрових систем на основі методу генетичних алгоритмів, що орієнтована на обробку цифрових схем великої розмірності з метою зменшення часу синтезу теста заданої повноти;–
модернізація метода детермiнованої генерації тестів, що гарантовано перевiряє несправності істотних змінних сильнопослiдовносних і тригерних структур на основі використання багатозначного двотактного алфавіту;–
розробка програмного комплексу детермiнованої генерації тестів для одиничних константних несправностей цифрових систем, що проектуються у середовищі Active HDL.
Об’єкт дослідження – цифрові системи, що проектуються в середовищі Active HDL, якi орієнтовані на їхню реалізацію в кристалах FPGA, CPLD.
Предмет дослідження – структурно-функціональні моделі цифрових пристроїв, що описані за допомогою кубічного зчислення для вирішення задачі детермiнованої генерації тестів.
Методи дослідження представлені апаратами: булевої алгебри, теорії множин, кубічного зчислення – для опису функцій примітивних елементів; теорії автоматів і графів – для реалізації структурно-функціональних моделей цифрових систем; теорії тестування цифрових систем, методів генерації тестів – для розробки алгоритмів побудови перевiряючих послідовностей.
Наукова новизна отриманих результатів:–
удосконалення концептуальної і структурної моделей примітивного автомата, що дає можливість описувати тригернi схеми в однотактному автоматному форматі змінних для моделювання їхньої справної поведiнки і наступної генерації тестів;–
удосконалення моделі послiдовносного пристрою для реалізації структурно-функціонального -алгоритму, що дозволяє виконувати адекватнi кубічнi покриття для тригерних структур, що описанi у виглядi булевих рівнянь, і дає можливість зменшити час їхнього аналізу і детермiнованої генерації тестів;–
модифікація моделі синтезу тестів для верифікації цифрових систем на основі генетичних алгоритмів, що дозволяє обробляти цифрові схеми великої розмірності й зменшити час синтезу теста заданої повноти;–
модернізація метода детермiнованої генерації тестів, що враховує структурно-функціональні особливості ПЛIС і дозволяє з гарантованою повнотою будувати тести в одній копії ітеративної моделі на основі стандартних процедур прямого просування і довизначення алгоритму активізації сильнопослiдовносних і тригерних структур.
Практичне значення отриманих результатів визначається:–
створенням програми автоматизованої побудови кубічних покрить для тригерних структур, якi заданi у виглядi булевих рівнянь, що дозволяє зменшити обсяги пам’яті, необхідні для збереження внутрішньої моделі цифрового пристрою, і час його обробки;–
реалізацією програми автоматизованої генерації тестів для тригерних і сильнопослiдовносних структур, якi заданi у виглядi булевих рівнянь, що дозволяє зменшити час верифікації цифрового проекту;–
програмною реалізацією моделей і алгоритмів процесу побудови тестів перевірки несправностей цифрових схем великої розмірності методом генетичних алгоритмів, що дозволяє значно зменшити час синтезу тестів заданої повноти;–
впровадженням практичних результатів у технологічний і навчальний процеси у виглядi програми детермiнованої генерації тестів, що дозволяє в автоматичному режимі будувати тести перевірки одиничних константних несправностей для цифрових проектів у середовищі Active HDL.
Достовiрнiсть теоретичних результатів підтверджується коректністю введених моделей, доведенням ряду теорем, інтеграцією прототипу програмного забезпечення із системою проектування Active-HDL, впровадженням і експлуатацією засобів генерації тестів, реалізацією натурних тестових експериментів над реальними цифровими проектами.
Результати дисертації у виглядi програмних додатків використовуються на підприємстві ЗАТ “Енергозбереження” (довідка про впровадження від 10.09.2001) м. Харків; у науково – дослідницькій і виробничій діяльності НДПI “Асутрансгаз” (довідка про впровадження від 10.2001) м. Харків; а також у навчальному процесі Харківського національного університету радіоелектроніки (акт про впровадження від 15.09.2001) і Національного технічного університету “Харківський політехнічний інститут” (довідка про впровадження від 09.09.2001).
Особистий внесок здобувача. Всі основні результати отримані здобувачем особисто. У роботах, що опублікованi спільно, автору належать: [2] – внутрішні структури даних, що орієнтовані на побудову кубічних покрить для послiдовносних схем; [3] – метод побудови тестів для послiдовносних цифрових схем без глобальних зворотних зв’язків, що містять синхронні тригери, що з’єднані в асинхронну структуру; процедура активізації лічильних моделей; метод побудови тестів для послiдовносних схем на основі стандартних процедур прямого просування і довизначення; [4] – класифікація методів і засобів генерації тестів; [5] – -алгоритм для послiдовносних схем, що мають тригернi структури; метод генетичних алгоритмів для синтезу тестів верифікації цифрових схем; [6] – модель тестопригодного проекту цифрового модуля; [7] – процедура аналізу кубічних покрить примітивних автоматів; [8] – структурний метод оптимізації тестування послiдовносних схем; [9] – алгоритм побудови тестів для багаторангових схем з розгалуженнями, що сходяться; [10] – алгоритм тестування макродефектів у логічних схемах; [11] – алгоритм генерації тестів, що заснований на активізації одномірного логічного шляху; [12] – метод обробки послiдовносних примітивів цифрових автоматів, що описанi кубічними покриттями; [13] – схема аналізу покриття примітива і формування вихідних значень елемента в буферному векторі моделювання; [14] – метод генерації тестів для константних несправностей, що використовує кубічні покриття; [15] – алгоритм визначення станів невхідних координат вектора моделювання; [16] – структури даних для автоматизованого проектування тестових послідовностей; [17] – система генерації тестів для верифікації цифрових проектів; [18] – процедура визначення дефектiв, що виникають на стадії проектування цифрового пристрою.
Апробація результатів дисертації здійснювалася на конференціях: 8-th International Conference “Mixed Design of Integrated Circuits and Systems”, Poland, Zakopane, 2001; VI-th Conference CADSM “The Experience of Designing and Application of CAD System in Microelectroncs”, Lviv-Slavsko, 2001; 7 Міжнародна науково-технічна конференція “Інформаційні технології: техніка, технологія, освіта, здоров’я” MicroCAD-99, ХДПУ, Харків, 1999; 5 Міжнародна конференція “Техніка передачі, прийому й обробки інформації”, Туапсе, 1999; 4 Міжнародна конференція “Інформаційно-керуючі системи на залізничному транспорті”, Алушта, 2000; 6 Міжнародна конференція “Техніка передачі, прийому й обробки інформації”, Туапсе, 2000; IV міська науково-технічна конференція “Актуальні проблеми сучасної науки в дослідженнях молодих учених Харківщини”, ХДУ, 2001; 5 Міжнародний молодіжний форум “Радіоелектроніка і молодь у XXI столітті”, ХНУРЕ, 2001; 7 Міжнародна конференція “Теорія і техніка передачі, прийому й обробки інформації”, Туапсе, 2001; 4 Міжнародна конференція “Теорія і техніка передачі, прийому й обробки інформації”, Туапсе, 1998.
Публікації. Основні результати роботи вiдбитi в 18 друкованих працях, серед яких 7 статей у виданнях, що затверджені ВАК України, інші 11 є тезами доповідей на конференціях.
Структура й обсяг дисертації. Дисертаційна робота містить 185 сторінок, 56 рисунків (на 25 с.),13 таблиць (на 6 с.). Її структура включає: вступ, 4 розділи, висновок, список використаних джерел з 163 назв. (на 14 с.), 3 додатки (на 20 с.).
ОСНОВНИЙ ЗМІСТ РОБОТИОСНОВНИЙ ЗМІСТ РОБОТИ
Вступ містить обґрунтування актуальності проблеми, що розв,язується, формулювання мети, об’єкта і задач дослідження, сукупність наукових результатів, що виносяться на захист, відомості про їхню апробацію і практичну реалізацію.
Розділ 1 присвячений аналізу опублікованих робіт в області генерації тестів для цифрових пристроїв. Було встановлено, що на сьогодні ПЛIС надають розроблювачам нові можливості для проектування швидкодіючих спеціалізованих цифрових систем. Відзначено, що сучасні функціональні схеми мають десятки тисяч ліній і містять важкотестовані послiдовносні фрагменти, а існуючі методи генерації тестів для таких схем мають недоліки: неприйнятний час синтезу детермiнованих тестів, недостатня повнота і велика розмірність тестів. Тому удосконалення існуючих методів генерації тестів, що орієнтованi на обробку лічильних і регiстрових структур з метою подолання перерахованих недоліків є актуальною задачею.
В розділі 2 пропонується метод побудови кубічних покрить (КП) для структурно-функціональних моделей цифрових пристроїв, що містять послiдовносні елементи. Розглянуто моделі і методи побудови тестів для верифікації цифрових систем на основі генетичних алгоритмів.
Модифікований -алгоритм відрізняється від відомого можливістю його застосування до тригерних багатоступінчастих структур. Визначено модель об’єкта тестування як цифрової системи на основі ПЛIС. Математичний апарат для опису моделі об’єкта дослідження – кубічне зчислення. Запропонована процедура побудови КП, що призначені для синтезу перевiряючих тестів послiдовносних схем, якi представлені у виглядi системи булевих рівнянь (рис.1).
Рис. 1. Структура алгоритма
Аналіз схемної структури проводиться з метою декомпозиції на комбінаційні і послiдовносні пiдсхеми, де останні представлені у виглядi структури примітивних автоматів (ПА), а комбінаційні інтерпретуються як сукупність логічних елементів. При наявності глобальних зворотних зв’язків (ГЗС) у схемі виконується їх псевдорозрив з додаванням у модель псевдовходiв. Для пiдсхем будуються власні КП, по яких виконується побудова загального покриття за модифікованим -алгоритмом. Отримане покриття мінімізується до тупікового КП. Для верифікації покрить використовується середовище моделювання Active-HDL, де схема представляється у виглядi системи логічних рівнянь.
Побудова КП пiдсхем використовується в алгоритмах генерації перевiряючих тестів для послiдовносних схем, що показано в розд. 3, а макромодель ЦУ дозволяє зменшити тимчасові витрати на вирішення задач синтезу тестів завдяки компактному представленню моделі дискретного об’єкта.
Запропоновано модернізований метод генетичних алгоритмів побудови тестів, що відрізняється від існуючих квазiдетермiнізмом і можливістю його застосування до послiдовносних пристроїв. Метод дозволяє досягти порівнянних з детермiнованим методом результатів по структурній простоті реалізації, ідентичних псевдовипадковому тестуванню. Розроблено програмні засоби, що орієнтовані на обробку цифрових схем великої розмірності, якi дозволяють істотно підвищити швидкодію системи генерації тестів.
Введено основні поняття і визначення, що адаптовані до вирішення задачі побудови тестів для цифрових систем: ген – один елемент {0,1,Х} у тест-векторі, хромосома – тест-вектор, представник популяції – тест, популяція – сукупнicть тестів. Введено визначення теста, що побудований за rt ітерацій, як сукупності кінцевої множини популяцій хромосом у k-мірному просторі і при наявності n входів у схемі:
(1)
якiй відповідає кількісний показник, визначений як відношення перевірених несправностей до повної множини існуючих:
Введено оціночну функцію для гена як якісний показник, якому відповідає кількісний, обумовлений як число несправностей, що перевіряються:
, де
Визначено формулу обчислення оціночної функції для хромосоми (-– координата тест-вектора ), що є кількісним показником у виглядi вектора дефектів, що перевіряються:
Оціночна функція для представника і популяції задається аналогічним образом.
Оціночна функція для тесту Т, що визначений як вектор перевірених несправностей є якісний показник усіх популяцій, що обчислюється за (1).
Введено модернізовані процедури методу генетичних алгоритмів із заміною випадкових компонентів на детермiнованi для пошуку раціонального вирішення у виглядi вхідних тестових послідовностей – хромосом: , (kx – кількість вхідних ліній цифрової схеми). Процедури: задання початкової популяції; схрещування хромосом популяції виконанням операції кросiнговера (crossover); мутація хромосом на заданих умовах; природний добір найбільш перспективних хромосом:
1. Задання випадкової початкової популяції замінюється алгоритмічними тестами: – 0,що біжить; 1, що біжить; шаховий код; галоп 0; галоп 1; код Грея; логаріфмічний.
2. Вибір оптимальної довжини n представників в популяції здійснюється з урахуванням якості векторів, що утворені кожним з обраних генераторів:
де ks – коефіцієнт структурної глибини схеми, що залежить від кількості вхідних kx, внутрішніх ky і вихідних kz ліній схеми.
3. Модернізація процедури одержання популяції. Фiтнес для кожної ітерації складається з оцінки попередньої популяції за умови q(Qr) = 100%. У цьому випадку ітеративний процес пошуку теста вважається завершеним.
Аналіз фiтнес-функцiй для попередньої і поточної популяцій – ітерацій служить умовою їхнього продовження або закінчення й обчислюється за формулою:
4. Модернізація процедури природнього добору представників у кожній популяції ґрунтується на вирішенні задачі покриття.
5. Модернізація операції кросiнговера дозволяє виконувати модифікацію тільки тих генів, що в обох представниках складали мінімальне значення фiтнес-функцiї.
6. Модифікація процедури мутації хромосом і генів. Для виключення випадкового характеру введені дискретні умови, що складають мінімальні значення фiтнеса генів.
Запропонований метод дозволяє одержувати тести прийнятної повноти (>94%). При цьому виграш у часі в порівнянні з псевдовипадковими процедурами генерації тестів методу генетичних алгоритмів для послiдовносних схем складає 49%.
У роздiлi 3 запропонований метод кратних символів для активізації шляхів послiдовносного з’єднання автоматів, що заданi кубічними покриттями в алфавіті А2. Введено поняття кратності k символа алфавіту A2, що визначає кількість двiйкових наборів (тактів), що необхідні для його реалізації. Перехід від кратних символів до двiйкових послідовностей виконується за допомогою рекурентних формул зниження кратності для всіх елементів, що наведені в табл. 1.
Таблиця 1
Формули зниження кратностей елементів алфавіту A2
Тут лінійна кратність задає (m-1) повторень відповідного символа в m тактах, а логарифмічна характеризує однократну появу підходящого символа, що зрушений у часі на (m-1) тактів. Логарифмічна кратність зазначена в дужках праворуч від символа алфавіту, а лінійна – ліворуч. Використання рекурентних формул зниження кратності ілюструється при одержанні універсальних покрить і активізації для JK-, D- і T- тригерів, що побудованi на основі таблиць переходів:
; ; .
З метою обґрунтування синтезу тестів для послiдовносних синхронних (асинхронних) структур доведено: 1. Кожен куб покриття активізації є повним перевiряючим тестом для одиничних константних несправностей тригера. 2. Для активiзацiї всіх шляхів одновихiдного підграфа асинхронної структури досить виконати активізацію, починаючи з будь-якого зовнішнього входу до його виходу. 3. Для активізації всіх шляхів одновихiдного подграфа синхронної структури досить виконати активізацію, починаючи з зовнішніх входів першого каскаду до його виходу. 4. Активізація шляху від будь-якого зовнішнього входу до виходу в сильнопослiдовносних схемах дозволяє побудувати тест, що виявляє всі істотні несправності.
Розглянуто приклади синтезу тестів за допомогою побудови одномірних шляхів, що активізованi кратними символами транспортування і забезпечення.
Приклад 1. Для асинхронної структури примітивних автоматів, яка представлена на рис. 2, побудувати тест методом кратних символів. Покриття активізації D-тригера представлено вище.
Рис. 2. Асинхронна структура примітивних автоматів
Результати запропонованої процедури побудови тестів для асинхронних послiдовносних структур представлені перетинанням покрить активізації першого і другого примітивів (див. рис. 2) при прямому просуванні, на координаті зв’язку Q1 (лінія 6) виконується перетинання зі зрівнюванням кратності по координаті зв’язку:
.
Виключивши приведені у роботі обчислення, далі представлений тест перевірки несправностей, що записаний у скороченій формі:
(I E 2E 3E 4E 3E2 2E3 E4 E4),
який перетвориться в 16 двійкових векторів: (00000,00001,00010,00011, 00100, 00101, 00110, 00111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111).
Обчислювальна складність (Z1) методу кратних символів для активізації шляху в одній копії залежить від кількості ліній схеми n: Z1 = (n+3*m) / n = 1 + 3*m/n; при цьому витрати на активізацію цифрової схеми (Z2) у всіх копіях залежать від кількості розрядів сильнопослiдовносної схеми m і від числа оброблюваних копій ітеративної моделі l: Z2 = (l+2*m) / l = 1 + 3*m/l. Витрати пам’яті (Z3) для вирішення процедури активізації залежать від кількості збережених результатів перетинань р: Z3 = (p*2m) / p = 2m.
Приклад 2. Для синхронної структури трирозрядного регістра зі зрушенням вправо, що представлена на рис. 3, побудувати тест методом кратних символів.
Рис. 3. Синхронна структура регістра
Для синхронних структур при зрівнюванні кратностей символів використовується процедура сегментування тесту, при виконанні якої будуються покриття активізації і КП. Результати застосування згаданої процедури побудови тесту для синхронної структури регістра (див. рис. 3) представлені в табл.2.
Остаточний результат роботи методу кратних символів представлений у виглядi тесту перевірки несправностей, що записаний в нижній правій частині табл. 2, у рядках з нульовою кратністю (k=0).
Таблиця 2
Тест перевірки несправностей
; .
Оцінка витрат на реалізацію процедури побудови тесту в зрушеній синхронній структурі за аналогією з (Z1-Z3) визначається формулами:
Z1* = (n+3*m) / n = 1 + 3*m/n;
Z2 *= (l+m) / l = 1 + m/l;
Z3 *= 2*n / n–1 = 2m.
Для активізації шляхів у лічильних структурах запропоновані спеціальні процедури, що призначені для формалізації процесів установки виходів у наперед задані стани або для здійснення конкретного переходу:
; .
Результатом виконання процедур є тест активізації синхронного двійкового лічильника, що здійснює переходи: 1H000 - 1H100 - 1H 010 - 1H110 - 1H 001, де Н – символ заднього фронту на вході синхронізації.
Оцінка витрат на процедуру побудови тесту для лічильної синхронної структури: Z1 = (n+4*m) / n = 1 + 4*m/n. Вхідні набори, що генеруються забезпечують обхід усіх станів графа переходів лічильника, при цьому кількість збережених векторів зменшується в 2 рази, завдяки використанню двотактного алфавіту A2.
Розроблені процедури активізації шляхів на основі методу кратних символів у структурах примітивних автоматів дозволяють зменшити обчислювальну складність вирішення задачі в порівнянні з методом активізації несправностей при використанні псевдокомбiнацiйних копій цифрових автоматів, що спричиняє зменшення часу обробки послiдовносних структур на 40%.
У розділі 4 пропонуються програмні засоби генерації тестів для цифрових систем, що проектуються з використанням середовища Active-HDL і орієнтованi на їхню реалізацію в кристалах FPGA, CPLD. Система дозволяє зменшити час (на 20–50%) верифікації цифрових проектів на стадіях: введення, синтезу й імплементації, завдяки автоматизації процесу побудови тестів. Об’єкт тестування – цифрові пристрої, що реалізовані в програмованій логіці. Структура програмної реалізації системи представлена на рис. 4.
Рис. 4. Структура системи синтеза тестів
Основні програмні модулі системи синтезу тестів і їхнi функції:
1. Введення. Призначений для конвертування вихідного файлу, що представлений мовою опису апаратури VHDL (Verilog) у формат BNF (булевих рівнянь) і для перетворення BNF-формату у внутрішні структури даних (SCH).
2. Генератор тестів. Здійснює: синтез тестів методом генетичних алгоритмів для послiдовносних схем; генерацію детермiнованих тестів методом кратних символів для сильнопослiдовносних структур; синтез тестів методом активізації одномірних логічних шляхів і засобами алгоритмічної і псевдовипадкової генерації вхідних послідовностей.
3. Моделювання несправностей. Призначено для аналізу якості тестів перевірки одиничних константних несправностей (iнтерпретативний і компілятивний алгоритми), побудови таблиці несправностей і мінімізації тестів.
4. Вивід. Призначений для конвертування синтезованого тесту, що задовольняє умовам повноти, у формат мови VHDL (TestBench), з метою його використання в середовищі Active-HDL для верифікації цифрових проектів.
Перша група експериментів відноситься до синтезу цифрових систем за допомогою засобів проектування Active-HDL, Synplify. Показано, що при компіляції VHDL-кодів цифрових пристроїв засобами синтезу виходять RTL-схеми, що містять 10-25% таких пристроїв, як: регістри, лічильники, що накопичують, суматори, що підтверджує актуальність розробки засобів генерації тестів для послiдовносних структур.
Iнша група експериментів відноситься до тестування програмних засобів синтезу тестів для послiдовносних структур, що взятi з бібліотек ISCAS (10), проекту PRUS (50) і ITC (30). Отримані результати показали:
1) Розробленими засобами синтезу тестів методом кратних символів були отримані тести для структурно складних схем з бібліотеки ISCAS, тоді як системою Nemesis тести аналогічної повноти для окремих пристроїв отримані не були. Для послiдовносних схем з бібліотеки Aldec (рис.5) повнота згенерованих тестів на 45% вище в порівнянні з результатом, що отриманий системою Nemesis.
2) Розроблені програмні засоби синтезу тестів на основі модернізованого методу генетичних алгоритмів мають переваги перед системою Nemesis: –
за часом; застосування генетичних алгоритмів дає виграш у середньому на 49% (рис. 6) для схем, що містять більш 1000 вентилів;–
за якістю тесту; виграш складає 0,06%;–
за довжиною синтезованого тесту переваг немає.
Рис. 5. Порівняльний аналіз повноти тестів систем генерації
Рис.6. Порівняльний часовий аналіз систем генерації тестів
ВИСНОВКИВИСНОВКИ
У процесі досліджень, що проведенi у рамках виконання дисертаційної роботи, яка спрямована на розробку моделей і алгоритмів детермiнованої генерації тестів для тригерних і сильнопослiдовносних структур у цифрових системах, що проектуються, що дозволяють зменшити час їхньої верифікації, отримані наступні основні результати, що виносяться на захист:–
удосконалені концептуальна і структурна моделі примітивного автомата, що описують тригернi схеми і дозволяють моделювати їхню справну поведiнку і генерувати перевiряючi тести;–
удосконалена модель послiдовносного пристрою, що реалізує структурно-функціональний -алгоритм побудови адекватних кубічних покрить для тригерних структур, якi описанi у виглядi булевих рівнянь, що дозволяє зменшити час їхнього аналізу і детермiнованої генерації тестів завдяки компактному представленню моделі дискретного об’єкта і відрізняється від відомої можливістю її застосування до тригерних багатоступінчастих структур; –
модифікована модель процесу генерації тестів для верифікації цифрових систем на основі методу генетичних алгоритмів, що дозволяє обробляти цифрові схеми великої розмірності i зменшити час синтезу тестів заданої повноти, а також дозволяє досягти порівнянних з детермiнованим методом результатів по структурній простоті реалізації, що ідентичні псевдовипадковому тестуванню, при цьому виграш у часі для послiдовносних схем складає 49%;–
модернізований метод детермiнованої генерації тестів, що дозволяє з гарантованою повнотою будувати перевiряючi тести в одній копії ітеративної моделі для послiдовносних і тригерних структур на основі застосування багатозначного двотактного алфавіту і дозволяє зменшити обчислювальну складність вирішення задачі в порівнянні з методом активізації несправностей при використанні псевдокомбiнацiйних копій цифрових автоматів, що спричиняє зменшення часу обробки послiдовносних структур на 40%;–
реалізована програма автоматизованої побудови кубічних покрить для тригерних структур, які задані у виглядi булевих рівнянь, що дозволяє зменшити обсяги пам’яті для збереження внутрішньої моделі і час її обробки;–
реалізована програма детермiнованої генерації тестів, яка в автоматичному режимі будує тести перевірки одиничних константних несправностей для цифрових проектів у середовищі Active HDL і дозволяє зменшити час (на 20–50%) верифікації цифрових проектів на стадіях введення, синтезу й імплементації;–
виконані експерименти на моделях реальних проектів цифрових пристроїв і тестових схем з каталогів ведучих фірм в області проектування, а також з матеріалів конференцій IEEE;–
впроваджені теоретичні результати моделей, алгоритмів і програмних засобів у навчальний і технологічний процеси з метою автоматизації проектування і верифікації цифрових систем, що реалізованi на основі FPGA, CPLD;–
впроваджені практичні результати у виглядi програмних засобів у навчальний і технологічний процеси з метою зменшення часу проектування шляхом автоматизації процесу верифікації цифрових систем, що реалізованi на основі ПЛIС.
Практичні та теоретичні результати у вигляді програмних засобів генерації тестів можна викристовувати у проектних установах та університетах, що займаються разробкою дискретних систем на кристалах програмованої логіки.
СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇСПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1. Скворцова О.Б. Генерация тестов для синхронных структур примитивных автоматов // Радиоэлектроника и информатика. – 2001. – № 3. – С.56-61.
2. Хаханов В.И., Скворцова О.Б., Пудов В.А. Масуд М.Д. Мехеди, Чамян А. Генерация тестов для последовательностных схем, имеющих триггерные структуры // Радиоэлектроника и информатика. – 2001. – №1. – С.96-99.
3. Шкиль А.С., Скворцова О.Б., Сысенко И.Ю., Чамян А. Генерация тестов для асинхронных структур примитивных автоматов // Радиоэлектроника и информатика. – 2001. – № 2. – C.97-103.
4. Хаханов В.И., Скворцова О.Б., Бабич А.В. Алгоритм построения кубических покрытий для схем с триггерными структурами (модифицированный П-алгоритм). Метод генетических алгоритмов для синтеза тестов верификации цифровых систем // АСУ и приборы автоматики. – 2001. – № 115. – C. 105-111.
5. Хаханов В.И., Скворцова О.Б., Бабич А.В. Генерация тестов для цифровых устройств // АСУ и приборы автоматики. – 2001. – № 116. – C.88-94.
6. Хаханов В.И., Скворцова О.Б., Монжаренко И.В. Алгоритм диагностирования тестопригодных цифровых структур // Радиоэлектроника и информатика. – 1998. – №2. – C. 127-130.
7. Хаханов В.И., Скворцова О.Б., Ханько В.В., Бедратый Р.В. Методы моделирования цифровых структур. Трехтактный автомат // Радиоэлектроника и информатика, 1998, №4. – С. 82-89.
8. Hahanov V.I., Skvortsova O.B., Mehedy M.M.D. Structural Method of Optimized Fault Location Using a Guide Probe // 8-th International Conference. Mixed Design of Integrated Circuits and Systems. – Poland. – Zakopane. -– 2001. – P. 465-468.
9. Хаханов В.И., Скворцова О.Б., Бабич А.В. Метод псевдослучайной генерации тестов для цифровых схем // 7-я Международная конференция “Техника передачи, приема и обработки информации” (Телекоммуникации. Радиотехника. Электроника). – Харьков: ХТУРЭ – 2001. С.305-306.
10. Скворцова О.Б., Бедратый Р.В., Абу Занумех Халиль И.М. Алгоритмы диагностирования макродефектов в логических схемах // 7-я Международная научно-техническая конференция “Информационные технологии: техника, технология, образование, здоровье” MicroCAD-99. – Харьков: ХГПУ – 1999. – С. 190-192.
11. Shkil A.S., Skvortsova O.B., Masud MD. Mehedy. Test generation for digital device based on FPDA, CPLD // // Sixth International conference “The experience of designing and application of CAD systems in microelectronics”. – Slavsko: “Lvivska Politechnica” – 2000. – P. 83-84.
12. Хаханов В.И., Скворцова О.Б., Побеженко В.В. Генерация тестов для цифровых схем // 6-я Международная конференция “Техника передачи, приема и обработки информации” (Телекоммуникации. Радиотехника. Электроника). – Харьков: ХТУРЭ – 2000. С.133-135.
13. Скворцова О.Б., Побеженко В.В., Алаиддин Одех С.А., Абу Занунех Халиль Х.И. Методы моделирования цифровых устройств // 7-я Международная конференция “Техника передачи, приема и обработки информации” (Телекоммуникации. Радиотехника. Электроника). – Харьков: ХТУРЭ. – 1999. C. – 389-391.
14. Скворцова О.Б., Бабич А.В., Хаханова И.В. Кубические модели цифровых схем для анализа качества тестов // 4-ая Международная конференция “Информационно-управляющие системы на железнодорожном транспорте”. – Харьков: IКСЗТ – 2001. – C. 146.
15. Ковалев Е.В., Скворцова О.Б., Побеженко В.В. Метод генерации тестов для константных неисправностей в цифровых схемах // 4-я Международная конференция “Информационно-управляющие системы на железнодорожном транспорте”. – Харьков: IКСЗТ – 2000. – C. 195.
16. Скворцова О.Б., Пудов В.А., Хак Х.М. Джахирул, Масуд МД. Мехеди. Генерация тестов для последовательностных схем, имеющих триггерные структуры // IV городская научно-техническая конференция “Актуальные проблемы современной науки в исследованиях молодых ученых Харьковщины”. -– Харьков: ХГУ. – 2001. – С. 86-89.
17. Скворцова О.Б., Бабич А.В. Система генерации тестов цифровых проектов в среде Active-HDL // 5-й Международный молодежный форум “Радиоэлектроника и молодежь в XXI веке”. – Харьков: ХТУРЭ. – 2001. – С. 305-306.
18. Хаханов В.И., Скворцова О.Б., Ханько В.В. Проблемы диагностирования неисправностей и сертификации программного продукта // 4-я Международная конференция "Теория и техника передачи, приема и обработки информации". – Туапсе. – 1998. – Харьков: ХТУРЭ. – 1998. – С. 467-468.
АНОТАЦІЯАНОТАЦІЯ
Скворцова О.Б. Проектування тестів для послiдовносних функціональних схем, що реалізованi у програмованiй логіці.– Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за
спеціальністю 05.13.12 – системи автоматизації проектувальних робіт.– Харківський нацiональний університет радіоелектроніки, Харків, 2002.
Робота присвячена розробці структурно-функціональних моделей послiдовносних схем і удосконаленню методів генерації тестів для зменшення часу верифікації цифрових систем на стадіях їхнього автоматизованого проектування й імплементації в кристалах ПЛIС.
У процесі виконання дослiджень отриманi результати, що виносяться на захист: удосконаленна концептуальна і структурна моделi примітивного автомата, що дає можливість описувати тригернi схеми в однотактному автоматному форматі змінних для моделювання їхньї справної поведiнки і наступної генерації тестів; удосконаленi моделі послiдовносного пристрою для реалізації структурно-функціонального -алгоритму, що дозволяє виконувати адекватнi кубічнi покриття для тригерних структур, якi описанi у виглядi булевих рівнянь, і дає можливість зменшити час їхнього аналізу і детермiнованої генерації тестів; модифікованi моделі генерації тестів для верифікації цифрових систем на основі генетичних алгоритмів, що дозволяють обробляти цифрові схеми великої розмірності й зменьшити час синтезу теста заданої повноти; модернізацiя метода детермiнованої генерації тестів, що враховує структурно-функціональні особливості ПЛIС і дозволяє з гарантованою повнотою будувати тести в одній копії ітеративної моделі на основі стандартних процедур прямого просування і довизначення алгоритму активізації сильнопослiдовносних і тригерних структур.
Ключові слова: генерація тестів, цифрова система, кубічне покриття, програмована логіка.
АННОТАЦИЯАННОТАЦИЯ
Скворцова О.Б. Проектирование тестов для последовательностных функциональных схем, реализуемых в программируемой логике.– Рукопис.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 –системы автоматизации проектных работ – Харьковский национальный университет радиоэлектроники, Харьков, 2002.
Работа посвящена разработке структурно-функциональных моделей последовательностных схем и усовершенствованию методов генерации тестов для уменьшения времени верификации цифровых систем на стадиях их автоматизированного проектирования и имплементации в кристаллах ПЛIС.
Объект исследования – цифровые системы, проектируемые в среде Active HDL, ориентированные на их реализацию в кристаллах FPGA, CPLD.
Предмет исследования – структурно-функциональные модели цифровых устройств, описанные с помощью кубического исчисления для решения задачи детерминированной генерации тестов.
В процессе выполнения исследований получены результаты, выносимые на защиту: усовершенствованая концептуальная и структурная модели примитивного автомата, дающая возможность описывать триггерные структуры в однотактном автоматном формате переменных для моделирования их исправного поведения и последующей генерации тестов; усовершенствованная модель для реализации структурно-функционального -алгоритма, позволяющего производить построение адекватных кубических покрытий для триггерных структур, описанных в виде булевых уравнений, и дающего возможность уменьшить время их анализа и детерминированной генерации тестов; модифицированная модель синтеза генерации тестов для верификации цифровых систем на основе генетических алгоритмов, позволяющая обрабатывать цифровые схемы большой размерности и уменьшающая время синтеза теста заданной полноты; модернизированный метод детерминированной генерации тестов, учитывающий структурно-функциональные особенности ПЛИС, и позволяющий с гарантированной полнотой строить тесты в одной копии итеративной модели на основе стандартных процедур прямого продвижения и доопределения алгоритма активизации сильнопоследовательностных и триггерных структур.
Практическое значение полученных результатов определяется: созданием программы автоматизированного построения кубических покрытий для триггерных структур, заданных в виде булевых уравнений, позволяющей сократить объемы памяти, необходимые для хранения внутренней модели цифрового устройства, являющегося объектом верификации; реализацией программы автоматизированной генерации тестов для триггерных и сильнопоследовательностных структур, заданных в виде булевых уравнений, позволяющей уменьшить время верификации цифрового проекта; программной реализацией моделей и алгоритмов процесса построения тестов проверки неисправностей цифровых схем большой размерности методом генетических алгоритмов, позволяющей значительно сократить время синтеза теста заданной полноты; внедрением практических результатов в технологический и учебный процессы в виде программы детерминированной генерации тестов, позволяющей в автоматическом режиме строить тесты проверки одиничных константных неисправностей для цифровых проектов в среде Active HDL.
Результаты диссертации в виде программных приложений используются на предприятии ЗАО "Энергосбережение"г. Харьков; в научно – исследовательской и производственной деятельности НИПИ "АСУтрансгаз"г. Харьков; а также в учебном процессе Харьковского национального университета радиоэлектроники и Национального технического университета "Харьковский политехнический институт".
Cистема автоматизированной генерации тестов протестирована на 90 примерах комбинационных и последовательностных схем из списков ISCAS (10), проекта PRUS (50) и ITC (30), что подтвердило состоятельность предложенных моделей и методов детерминированной генерации тестов, а также метода генетических алгоритмов и показало приемлемое быстродействие.
Ключевые слова: генерация тестов, цифровая система, кубическое покрытие, программируемая логика.
ABSTRACTABSTRACT
Skvortsova Olga B. Test Generation for sequential functional circuits, that realized in programmable logic. – Manuscript.
Thesis for a candidate degree of technical sciences on speciality 05.13.12 – computer-aided design systems.– Kharkov national university of radio electronics, Kharkov, 2002.
The thesis is devoted to the development structural-functional models of sequential circuits and modernization of test generation methods for decreasing of digital systems verification time during all stages of CAD and implementation to FPGA, CPLD chip.
During the period of research following problems were solved: modernization of conceptually and structurally complicated model of primitive automata for trigger structures description in one-frame automata format for modeling their fault-free behavior and following test generation; modification of sequential device model for realization structural-functional -algorithm
