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

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

Мд. МЕХЕДІ МАСУДМд. МЕХЕДІ МАСУД

УДК 658.512.011:681.326:519.713

МОДЕЛІ ТА АЛГОРИТМИ ГЕНЕРАЦІЇ ТЕСТІВ ДЛЯ ЦИФРОВИХ СИСТЕМ, ЩО ПРОЕКТУЮТЬСЯ У СЕРЕДОВИЩІ VHDLМОДЕЛІ ТА АЛГОРИТМИ ГЕНЕРАЦІЇ ТЕСТІВ ДЛЯ ЦИФРОВИХ СИСТЕМ, ЩО ПРОЕКТУЮТЬСЯ У СЕРЕДОВИЩІ VHDL

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

АВТОРЕФЕРАТ

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

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

Харків 2001

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

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

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

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

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

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

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

Дербунович Леонід Вікторович,

Національний технічний університет “Харківський політехнічний інститут”, професор кафедри автоматики і управління в технічних системах.

кандидат технічних наук Литвинова Євгенія Іванівна,

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

радіоелектроніки, доцент кафедри технології і автоматизації

виробництва радіоелектронних засобів та

електронно-обчислювальних засобів

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

Міністерство освіти і науки України, м. Київ

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

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

Автореферат розісланий 11 грудня 2001 року

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

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

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

Автоматизоване проектування цифрових систем в останні роки має тенденцію до використання мов опису апаратури високого рівня. При цьому існує певний прогрес у переході від традиційних представлень (VHDl, Verilog, Abel, EDIF, TDF, XNF) до нових інтегрованих мов, типу System C, що об,єднає переваги паралелізму VHDL із семантичними можливостями мови програмування С++. Прогрес у засобах опису цифрових систем пов’язаний зі зростанням ринкового попиту на могутні компілятори і симулятори, що здатні вирішувати задачі введення і верифікації проектів, які містять сотні і тисячі рядків вихідних описів. До того ж поява нових субмікронних мікроелектронних технологій привела до створення могутньої елементної бази у вигляді програмувальних логічних інтегральних схем (ПЛІС): Field Programable Gate Array (FPGA), Complex Programable Logic Device (CPLD), на яких реалізуються System on Chip (SoС). Тому в даний час користувач має високий технічний потенціал для проектування будь-яких цифрових систем: кристали ПЛІС зі ступенем інтеграції до 12 млн. вентилів; швидкодія 500 Мгц; вартість чипа від декількох доларів; могутні компілятори для всіх мов опису апаратури високого рівня (фірм Aldec, Cadence, Altera, Xilinx, Synopsys ), достатня кількість синтезаторів (MAX+PLUS II – Altera; Foundation 2.1 – Xilinx; FPGA Express Synthesis – Synopsys; ActelDeskTop – Actel, VeriBest, Synplicity; Synplify – Synplicity) для перетворення опису цифрової системи в конструкції ПЛІС.

Структурна складність об’єктів тестування, що обумовлена мільйонами вентилів, накладає певні вимоги на швидкодію і функції створюваної системи генерації тестів. При цьому основним постулатом процесу проектування є твердження: неможливо створити універсальну систему, що обробляє об’єкти довільної розмірності і функціональної складності за прийнятний час. Тому раціональним алгоритмом проектування системи генерації тестів є: 1. Створення ядра у вигляді засобів моделювання дефектів і реалізації алгоритмів детермінованої і псевдовипадкової генерації тестів. 2. Визначення представницької вибірки тест-прикладів цифрових схем з каталогів провідних фірм для визначення валідності програмного забезпечення системи. 3. Тестування версії на множині прикладів з метою пошуку цифрових структур, для яких параметри якості тесту або час його побудови не задовольняють користувача. 4. Пошук раціональних алгоритмів генерації тестів для необроблюваних типів схем. 5. Включення програмних реалізацій знайдених алгоритмів до складу системи разом із критеріями ідентифікації цифрових структур.

Актуальність теми. Цифровий виріб практично на всіх стадіях його життєвого циклу (у тому числі і на етапі проектування) має потребу в тестуванні. Більшість раніше згаданих систем моделювання і синтезу не має автоматичних генераторів тестових впливів. Аналоги, до яких належить, наприклад, Nemesis (University of California), мають вузькоспеціалізовану орієнтацію на платформи DEC Alpha, DEC station, HP UX, Sun-4. Тому необхідність розробки автоматичних генераторів тестів для перевірки відповідності виробу його вихідної специфікації обумовлена факторами: 1) дефіцитом програмних засобів генерації тестів на ринку САПР; 2) неможливістю верифікації без тестів об’єктів, що перевіряють, діагностування великої розмірності, вентильного, функціонального алгоритмічного рівнів опису, заданих у вигляді булевих рівнянь; 3) необхідністю забезпечення високої якості і надійності функціонування проектованої цифрової системи; 4) доцільністю зменшення часу створення виробу шляхом автоматизації процесу верифікації проекту; 5) необхідністю підтримки стандарту VHDL для опису поводження і тесту цифрової системи; 6) доцільністю інтегрування засобів генерації тестів з існуючими САПР провідних фірм світу.

В області автоматизованого проектування і тестування цифрових пристроїв і систем великий внесок внесли вчені: Y. Zorian, I. Pomeranz, J.P.Hayes, S.M.Reddy, D.B.Armstrong, А.Г.Биргер, Y.H.Levendel, M.A.Breuer, M.Abramovici, П.П.Пархоменко, А.М.Романкевич, Д.В.Сперанський, Р.Й.Убар, Ю.А.Скобцов, Л.В.Дербунович, Ю.В.Малишенко, А.Э.Таргамадзе, В.Н.Ярмолик, В.П.Чипулис, В.А.Твердохлебов, О.Ф.Немолочнов.

Зв’язок роботи з науковими програмами, планами, темами. Розробка основних положень роботи здійснювалася відповідно до планів НДР і договорів, що виконуються у Харківському національному університеті радіоелектроніки: 522-1-2 – “Розробка інформаційного забезпечення і програмно-апаратних комплексів для курсів з комп’ютерних наук та інженерії”, № держ. реєстрації 0199U012176; 102 – “Розробка інформаційних технологій в автоматизованому проектуванні, діагностиці радіоелектронної апаратури й обчислювальної тех-ніки”, № держ. реєстрації 0100U03417; Університетська програма міжнародного співробітництва в області освіти, науки “Стратегічне партнерство” від 10.03.2000; Договір про довгострокове науково-технічне співробітництво з фірмою Аldec Inc. (USA) від 6.06.1999 “Розробка програмних засобів автоматичної генерації тестів для цифрових систем, що реалізовані на основі програмувальних логічних інтегральних схем”. При виконанні названих тем і договорів автор брав участь як консультант і виконавець – розробив структури даних для опису цифрових систем та веріфікував 60 моделей тестових прикладів.

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

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

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

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

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

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

Об’єкт дослідження – спеціалізовані цифрові системи, описані у формі булевих рівнянь мовою опису апаратури VHDL, орієнтовані на їхню реалізацію в кристалах FPGA, CPLD як SoС.

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

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

Наукова новизна отриманих результатів:–

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

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

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

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

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

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

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

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

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

Результати дисертації у вигляді програми використовуються на: ЗАТ “Енергозбереження”, Харків (довідка про впровадження від 11.07.2001); а також у навчальному процесі Харківського національного університету радіоелектроніки (акт про впровадження від 15.09.2001) і Національного технічного університету “Харківський політехнічний інститут” (довідка про впровадження від 09.09.2001).

Особистий внесок здобувача. Всі основні результати отримані здобувачем особисто. У роботах, що опубліковані спільно, автору належать: [2] – структурно-функціональні моделі цифрових примітивів і модель процесу генерації тестів на основі кубічного покриття; [3] – алгоритми генерації тестів для комбінаційних схем великої розмірності і їхня програмна реалізація; [4] – стратегії генерації тестів і математичні моделі функціональних елементів і тригерних структур, заданих кубічними покриттями; [5] – псевдокомбінаційні моделі примітивних елементів для генерації тестів активізації; [6] – програмна реалізація моделей і алгоритмів генерації тестів для схем великої розмірності; [7-12] – моделі й алгоритми побудови тестів для комбінаційних і послідовностних цифрових схем, що задані булевими рівняннями, у системі генерації тестів для САПР Active-HDL.

Апробація результатів дисертації здійснювалася на конференціях: VI-th Conference CADSM “The Experience of Designing and Application of CAD System in Microelectronіcs”, Lviv – Slavsko, 2001; IV міська науково-технічна конференція “Актуальні проблеми сучасної науки в дослідженнях молодих учених Харківщини”, Харків, 2001; International Workshop of Discrete Event System Design DESDes’01, Zielona Gora, Poland, 2001; 14-я Міжнародна школа-семінар “Перспективні системи управлніння на залізничному, промисловому і міському транспорті", Алушта – Харків, 2001; 7 міжнародна конференція “Теорія і техніка передачі, прийому й обробки інформації”, Туапсе, 2001; 8-th International Conference Mixed Design of Integrated Circuits and Systems MIXDES2001, Zakopane, Poland, 2001.

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

Структура й обсяг дисертації. Дисертаційна робота містить 181 сторінку, 39 рисунків (на 24 с.). Її структура включає: вступ, 4 розділи, висновок, список використаних джерел з 132 назв. (на 12с.), 2 додатки (на 31 с.).

ОСНОВНИЙ ЗМІСТ РОБОТИОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

Як висновок по огляду публікацій формулюється актуальність створення моделей і алгоритмів системи генерації тестів і її місце в процесі проектування цифрових систем на основі програмувальної логіки (рис. 1).

Розділ 2 присвячений побудові автоматних моделей різних типів тригерних структур на основі аналізу проектів, що реалізуються у середовищі Active-HDL. Вихідний опис цифрової системи зображено підмножиною мови VHDL, яка найбільш зручної для задання булевих рівнянь.

Рис.1. Стадії проектування ПЛІС

Приклади опису двох примітивних автоматів мають такий вигляд:

latch (R,S, CE, c_high,D);

C=CLK*CE; S1=S+(D*C); R1=R+(C*!D); Q(t)=S1+(!R1*Q(t-1));

flip-flop(C_low,D);

S=!C*Q1(t-1); R=!C*!Q1(t-1); Q(t)=S+(!R*Q(t-1)); S1=D*C; R1=C*!D;

Q1(t)=S1+(!R1*Q1(t-1)).

При аналізі двох сотень проектів було ідентифіковано 34 типи тригерів, реалізованих у програмувальній логіці. Логічне дослідження тригерних структур дозволило виконати їхню класифікацію і побудувати два типи моделей у вигляді одне- і двоступінчастих примітивних автоматів. Перший орієнтований на синтез тестів шляхом виконання процедур одномірної активізації і забезпечення, реалізованих в одному автоматному такті. Другий, більш адекватний, призначений для логічного аналізу з метою оцінки якості синтезованих тестів перевірки константних несправностей. Подальше узагальнення описів тригерних структур дозволило одержати концептуальну модель (рис.2) примітивних кінцевих автоматів як окремий випадок автомата Мура:

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)].

Рис.2. Концептуальні моделі примітивних автоматів

Функціональний послідовносний примітив задається у табличному вигляді такими компонентами:

F2 = <(t-1,t),(X,Y,Z),{A2}>,

де (t-1,t) – два автоматні сусідні такти в описанні функції; (X,Y,Z) – вектори вхідних, внутрішніх та вихідних змінних; 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)} – двотактний алфавіт опису станів (переходів) автоматних змінних, що містить однотактний A1.

Як основна форма опису примітивного елемента (ПЕ) виступає кубічне покриття у загальному випадку трійкових векторів:

C = (C1, C2, ..., Ci, ..., Cn),

де Ci = (Ci1, Ci2, ..., Cij, ..., Ciq) – куб покриття примітивного елемента, що містить вхідні, внутрішні, вихідні координати Ci = (CiX, CiY, CiZ), q=m+h+k.

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

де p – загальне число примитивів у схемі; q – кількість типів ПЕ; Ki (Kj), Nj – число змінних та кубів у елементі.

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

Застосування двотактного алфавіту кубічного зчислення дозволило значно зменшити розмірність покрить активізації функціональних елементів, пропорційно збільшивши швидкодію алгоритмів прямої імплікації. У порівнянні з аналогічними покриттями Рота зменшення числа кубів активізації оцінюється виразом 2n-1/n. Однак це не єдина перевага надлишкового алфавіту. Наявність символів Х на лініях зменшує кількість суперечливих рішень у процесі виконання зворотної імплікації у середньому на 50-70 %. Це дає можливість підвищити швидкодію генерації тестів у порівнянні з алгоритмом Рота і його аналогами в 3-4 рази. Практична реалізація алгоритму одномірної активізації на численних прикладах (160) підтвердила приведені оцінки. Основні кроки алгоритму:

1. Вибір чергової лінії j для активізації й ініціалізація координати вектора активізації символами активності:

2. Визначення чергового примітиву Pt для здійснення прямої імплікації символа активізації за правилом:

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

3. Зворотна фаза. Обробка кожного примітива схеми, на виході якого після прямої фази існують відмінні від (XХ) символи за винятком елементів, що стали активними при виконанні прямої фази. Перетинання кожного куба Cl покриття забезпечення з поточним вектором активності Di. При непорожньому перетинанні Di з n кубами виконується розмноження рядка Di на n векторів (j=1,n), що є наслідком багатоваріантності рішення задачі:

4. Об’єднання поточних векторів активізації з метою мінімізації кількості проміжних рішень. Виконується у випадку розходження пари рядків тільки за однією координатою, або при поглинанні одного з векторів:

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

.

Розділ 3. Відмінними рисами удосконалення алгоритму активізації для обробки послідовносних схем є: 1) Використання псевдокомбінаційних автоматних моделей тригерних структур, заданих покриттями у трійковому алфавіті, що спрощує програмну реалізацію процедури зворотної імплікації і не вимагає ітерацій при побудові тестів і моделюванні; 2) Визначення фази забезпечення для перебування настановних послідовностей не тільки в просторі, але і в часі при побудові тестів для послідовносних схем. 3) Сполучення процедур активізації і забезпечення шляхом зворотного простежування сигналів дає можливість виключити проміжні обчислення справних станів і за рахунок цього підвищити швидкодію імплікації на 20-30 %.

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

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

1. Виділення входів синхронізації. Шляхом аналізу кубічних покрить або кодів мови VHDL визначається напрямок синхронізації.

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

Це дає можливість розбити схему на n+1 частин (n=0,1,2,3,...), де n – число незалежних зовнішніх синхровходів Взаємодія підсхем визначається такими відношеннями:

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

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

4. Підсхема розбивається на фрагменти, кількість яких дорівнює кількості виходів в ній з урахуванням виконання такого критерію для входів:

5. Композиція отриманих розбивок шляхом об’єднання підсхем, що відрізняються не більш, ніж q змінними

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

,

якщо всі підсхеми відповідають умові. Довжина теста визначається формулою

У альтернативному випадку, коли має місце умова перетинання

,

виконується мінімізація теста за правилом адитивного об,єднання

Довжина теста для всієї схеми буде дорівнювати .

У загальному випадку, коли виконуються умови

тест формується на основі аналізу чергової пари підсхем:

де * – операція конкатенації тестів для підсхем; – матрична операція перетинання тестів, яка визначається у такому вигляді:

де np, nq – довжина тестів Tp і Tq, m – загальна кількість ліній у цифровій схемі.

Таким чином, загальна довжина теста після об,єднання часткових тестів для підсхем визначається інтервалом

Представлено три стратегії побудови тестів, що включають використання детермінованих і алгоритмічних генераторів на основі декомпозиції схеми і розбивки множини використовуваних генераторів тестів: 1) Детермінований. Модифікація К-алгоритму активізації одномірних шляхів на парі вхідних наборів для комбінаційних схем і на упорядкованому сегменті вхідних векторів кінцевої довжини – для послідовносних. Переваги: цілеспрямована побудова тестів для замовлених несправностей; алгоритмічна збіжність при вирішенні задачі побудови тесту для конкретної несправності, якщо така існує, що підтверджується доказом двох теорем. Недоліки: неможливість за прийнятний час одержати повний тест для схем, що містять мільйони вентилів. 2) Алгоритмічний. Генерація регулярних вхідних наборів: 0 і 1, що біжать; галоп 0 і 1; шаховий код; логарифмічний; генератори псевдовипадкових послідовностей. Переваги: висока швидкодія і повна перевірка несправностей для регулярних схем: суматори, лічильники, регістри. Відомий контрприклад Шнейдера цілком перевіряється кодом “1, що біжить”. Недоліки: низька якість тесту для послідовносних та нерегулярних структур.

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

Об’єкт тестування. Цифрові системи, що представлені у формі булевих рівнянь мовою опису апаратури VHDL, орієнтовані на їхню імплементацію в кристали FPGA, CPLD. Елементна база: логічні елементи, функціональні елементи (мультиплексори, перетворювачі кодів), тригерні схеми (34 типу). Типи змінних:

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.

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

Усі моделі й алгоритми протягом року проходили апробацію на представницькій вибірці тест-прикладів цифрових схем з каталогів провідних фірм для визначення коректності програмного забезпечення системи. Крім того, програмне забезпечення системи генерації тестів порівнювалося за основними параметрами з аналогом (Nemesis, Sun-station).

Результати обробки 60 прикладів. При грубому настроюванні програми генерації тестів система Nemesis у 20% прикладів давала кращий час обробки схем, при однаковій якості тестів. При точних параметрах настроювання з урахуванням структурних особливостей цифрових пристроїв часові параметри системи Tesbuilder (Pentium II) виявилися не гірше, при цьому 15% схем узагалі не оброблялися аналогом, для яких Tesbuilder побудував тести з не менш, ніж 97% якістю.

Реалізація системи генерації тестів: компілятор Microsoft Visual C++; операційна система – Windows; середовище проектування – Active-HDL; – обсяг пам’яті для EXE-модуля – 630 Кбайт; – обсяг вихідних текстів – 300 Кбайт; число програмних модулів – 14; середній час генерації тестів, алгоритмічних (детермінованих), 2000 ліній – 14 (46) хвилин, при якості більш 90 %; зменшення часу побудови тестів після декомпозиції – 10 %; тест-приклади: ISCAS’85 (14 схем); проект PRUS (116 схем); ITC’99 (30 схем); стан системи: працездатне – Prototype 2.

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

Рис. 4. Порівняльний аналіз детермінованої генерації тестів

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

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

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

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

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

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

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

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

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

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

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

1. Mд. Мехеди Масуд. Стратегии построения тестов для цифровых систем // Радиоэлектроника и информатика.– 2001.– № 3.– С. 50-55.

2. Хаханов В.И., Хак Х.М. Джахирул, Mд. Мехеди Масуд. Модели анализа неисправностей цифровых систем на основе FPGA, CPLD // Технология и конструирование в электронной аппаратуре.–2001.– № 2.– С. 3-11.

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

4. Хаханов В.И., Скворцова О.Б., Пудов В.А., Масуд М.Д. Мехеди. Генерация тестов для последовательностных схем, имеющих триггерные структуры // Радиоэлектроника и информатика.– 2001.– № 1.– С. 96-98.

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

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

7. Shkil Alexander, Skvortsova Olga, Md Masud Mehedy, Haque H.M. Jahirul. – Test Generation for Digital Device on FPGA, CPLD // The Experience of Designing and Application of CAD System in Microelectroncs.– Proceeding of the VI-th Conference CADSM 2001.– Lviv – Slavsko.– P. 83-84.

8. Скворцова О.Б., Пудов В.А., Хак Х.М. Джахирул, Mд. Мехеди Масуд. Генерация тестов для последовательностных схем, имеющих триггерные структуры // IV городская научно-техническая конференция “Актуальные проблемы современной науки в исследованиях молодых ученых Харьковщины”. – Харьков: ХНУ.– 2001.– С. 87-88.

9. Hahanov V.I., Babich А.V., Md Masud Mehedy. Sistem of Digital Device Test Generation for Active-HDL // Proceedings of the Int. Workshop of Discrete Event System Design DESDes'01.– Zielona Gora, Poland.– June, 27-29, 2001.– P. 153-156.

10. Хаханов В.И., Кривуля Г.Ф., Mд. Мехеди Масуд. Генерация тестов для цифровых систем, описанных на языке VHDL // Информационно-управляющие системы на железно-дорожном транспорте.– 2001.– № 3 // Материалы 14 Межд. школы-семинара "Перспективные системы управления на железнодорожном, промышленном и городском транспорте. Алушта. Харьков: ХарГАЖТ. С. 77.

11. Хаханов В.И., Mд. Мехеди Масуд., Горбунов Д.В. Материалы седьмой международной конференции "Теория и техника передачи, приема и обработки информации".– Туапсе.– 2001.– Харьков: ХТУРЭ.– 2001.– С. 67-68.

12. Hahanov V.I., Skvortsova O.B., Md Masud Mehedy. Structural Method of Optimized Fault Location using a Guide Probe.– Proceedings of the 8-th International Conference Mixed Design of Integrated Circuits and Systems MIXDES2001.– Zakopane, Poland.– June, 23-24, 2001.– P. 465-468.

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

Mд. Мехеді Масуд. Моделі та алгоритми генерації тестів для цифрових систем, що проектуються у середовищі VHDL.– Рукопис.

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

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

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

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

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

Mд. Мехеди Масуд. Модели и алгоритмы генерации тестов для цифровых систем, проектируемых в среде VHDL.– Рукопись.

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

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

Объект исследования – специализированные цифровые системы, описанные в форме булевых уравнений на языке описания аппаратуры VHDL, ориентированные на их реализацию в кристаллах FPGA, CPLD как SoC.

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

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

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

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

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

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

Результаты диссертации в виде программы используются на: ЗАО "Энергосбережение", Харьков (справка о внедрении от 11.07.2001); а также в учебном процессе Харьковского национального университета радиоэлектроники (акт о внедрении от 15.09.2001) и Национального технического университета "Харьковский политехнический институт" (справка о внедрении от 09.09.2001).

Реализация системы генерации тестов: компилятор Microsoft Visual C++; операционная система – Windows; среда проектирования – Active-HDL; – объем памяти для EXE-модуля – 630 Кбайт; – объем исходных текстов – 300 Кбайт; число программных модулей – 14; среднее время генерации тестов, алгоритмических (детерминированных), 2000 линий – 14 (46) минут, при качестве более 90%; уменьшение времени построения тестов после декомпозиции – 10 %; тест-примеры: ISCAS’85 (14 схем); проект PRUS (116 схем); ITC’99 (30 схем); состояние системы: работоспособное – Prototype 2.

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

ABSTRACTABSTRACT

Md Mehedi Masud. Models and Algorithms for Test Generation of Digital System for its Designing in Active-HDL. – 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, 2001.

The thesis is devoted to the development of structural-functional and pseudo-combinational models and algorithms of deterministic test generation of digital system for decreasing of their verification time for computer aided design using Active-HDL.

The general scientific results are: modification of synchronous digital primitive model for flip-flop circuits description by cubic coverage using one-frame alphabet, which gives opportunities for deterministic test creation; improvement of models and algorithms of fault detection and test generation by using of single path activization approach for combinational and sequentional circuits, which are described by boolean equations and use forward propagation and backward implication; linear model of fault detection and test generating for all essential variables based on cubic coverage of functional description circuit; applications strategy of deterministic and algorithmic test generators for large dimension digital system using decomposition for decreasing test generation time with complete fault coverage; test generation program creation, which allows to build stuck-at-fault detection test for boolean equation description of digital devices and to simulate all faults for finding fault coverage percentage.

Key words: test generation, stuck-at-faults, digital devices, cubic coverage, single path activization algorithm.