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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Харківський національний університет радіоелектроніки

УДК 681.326:519.713

АВТОРЕФЕРАТ

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

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

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

Колесніков Костянтин Васильович

Харків-2003

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

Робота виконана у Харківському національному університеті

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

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

Хаханов Володимир Іванович,

Харківський національний університет радіоелектроніки, декан факультету комп'ютерної інженерії та управління.

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

Хажмурадов М.А.,

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

Голубничий Д.Ю., канд. техн. наук,

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

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

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

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

Автореферат розісланий 23 січня 2004 року

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

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

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

дедуктивний розгалуження дефект цифровий

В даний час продукція, що постачається на ринок електронних технологій використовується у всіх областях людської діяльності. Компанії Intel, Motorola, AMD, IBM, Sun Microsystems і Hewlett-Packard витрачають мільйони доларів на розробку могутніх процесорів, що оперують уже 64- і 128-бітовими даними. Щільність розміщення транзисторів у кристалах мікросхем досягла 200 млн. на 1 см2. [Bass M.J. and Cristensen C.M. The future of the Microprocessor Business.- IEEE Spectrum, April, 2002, P. 34-39].

У мікропроцесорів, як і в інших типів мікросхем, спостерігається експоненційне зростання можливостей, відповідно до закону Мура . Мікропроцесори з такою самою періодичністю збільшують свою продуктивність на 100%. Однак ситуація в даний час змінюється у зв'язку зі зростанням продуктивності середніх і малих мікропроцесорів. Очевидна ринкова тенденція - протягом найближчих 15 років можливості, пропоновані технічним прогресом і ринком, перевищать потреби користувача. Тому корпорації, які націлені тільки на випуск могутніх універсальних процесорів , ризикують втратити свою частку прибутку на ринку мікроелектроніки. Щоб цього не сталося, вони вже зараз реорганізують частину свого виробництва на швидкий випуск замовлених (customized) мікросхем.

Ще в 1996 році компанія National Technology Roadmap for Semoconductor звернула увагу на факт, що виробництво транзисторів щорічно збільшується на 60%, при цьому їхнє використання в нових проектах зростає тільки на 20 %. З цієї причини й в області мікроелектроніки відбувається переорієнтація засобів на можливості реалізації тільки необхідних і замовлених властивостей. Розвивається модульність пристроїв, у якій зберігається стандартизація інтерфейсів між підсистемами. Такий підхід уже реалізований у нижніх рівнях проектування мікропроцесора у вигляді системи на кристалі (System-on-chip чи SoС), що складається з багаторазово використовуваних IP модулів.

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

Актуальність теми. Нові технології мікроелектроніки породили більш складні об'єкти діагностичного обслуговування у вигляді складних цифрових систем на кристалах ПЛІС. Проблема їхнього тестування (80% часу проектування) визна чається протиріччям між необхідністю синтезу тестів верифікації за прийнятний час з одного боку, а з іншого боку - можливістю обробки структурно й функціонально складних проектів, що мають сотні тисяч еквівалентних вентилів. У зв'язку з цим актуальною представляється задача розробки раціональних моделей, методів і алгоритмів генерації тестів і оцінки їхньої якості для цифрових пристроїв, створюваних на основі використання сучасної технології граничного сканування, аналізу структурних особливостей цифрового виробу на ранніх стадіях проектування.

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

Зв'язок роботи з науковими програмами, планами, темами. Розробка основних положень роботи здійснювалася відповідно до планів НДР, программ й договорів, виконуваних в Харківському національному університеті радіоелектроніки: 102 - “Розробка нових інформаційних технологій в автоматизованому проектуванні, діагностиці засобів радіоелектронної апаратури й обчислювальної техніки”, № державної реєстрації 0100U03417 ; університетська програма міжнародного співробітництва в області освіти, науки “Стратегічне партнерство” від 10.03.2000; договори про довгострокове науково-технічне співробітництво з фірмою Аldес Inc. (USA) № 01 від 06.06.1999 і № 02 від 19.11.2001 “Розробка програмних засобів автоматичної генерації тестів і моделювання несправностей для цифрових систем, реалізованих на основі програмувальних логічних інтегральних схем”. При виконанні вищезазначених договорів автор брав участь у розробці системи генерації тестів і моделювання для цифрових проектів, реалізованих у ПЛІС, як виконавець й консультант.

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

Для досягнення поставленої мети необхідно:

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

- розробити графо-теоретичні моделі структурного аналізу розгалужень, що сходяться (РС), і виділити деревоподібні сегменти для роздільного моделювання несправностей;

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

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

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

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

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

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

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

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

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

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

- удосконалено моделі процесу дедуктивного й паралельного моделювання несправностей на основі технології граничного сканування з метою істотного (у

кілька разів) підвищення швидкодії програмної реалізації розроблювальних методів аналізу надскладних проектів;

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

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

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

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

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

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

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

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

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

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

Результати дисертації у вигляді програмних додатків використовуються на підприємствах: ЗАТ “НДІРІ” , Харків (довідка про упровадження від 17.06.2003),

ЗАТ “Енергозбереження”, Харків (довідка про упровадження від 19.05.2003); а також у навчальному процесі Харківського національного університету радіоелектроніки (акт про упровадження від 23.06.2003) і Черкаського державного технологічного університету (довідка про упровадження від 24.05.2003).

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

Апробація результатів дисертації представлена конференціями, що мають пряме відношення до теми дисертаційної роботи: 1) 10-th International Conference “Mixed Design of Integrated Circuits and Systems”, Poland, Lodz, 2003; 2) VII-th Conference CADSM “The Experience of Designing and Application of CAD System in Microelectroncs”, Lviv, Slavsko, 2003; 3) 8-ма Міжнародна конференція “Теорія і техніка передачі, прийому й обробки інформації”, Туапсе, 2002; 4) 15-та Міжнародна школа-семінар “Інформаційно-керуючі системи на залізничному транспорті”, Алушта, 2002; 5) 1-й Молодіжний науково-практичний форум “Інформаційні технології в 21 сторіччі”.- Дніпропетровськ, 2003; 6) 2-га Міжнародна науково-технічна конференція “Проблеми інформатики й моделювання.- Харків, 2002; дипломом переможця в конкурсі дослідницьких проектів, проведеного фірмою Intel, 2003, http://www.intel.com/ru/Pressroom/2003/061001.htm.

Публікації. Результати наукових досліджень відображені в 11 друкованих працях. У їхнє число входять 6 статей, опублікованих у наукових виданнях, що включені в Переліки ВАК України, а також 5 матеріалів конференцій. Структура й обсяг дисертації. Дисертаційна робота містить 171 сторінку, 50 рисунків (на 27 с.), 1 таблицю. Її структура включає: вступ, 5 розділiв, 35 пiдрозділiв, висновок, список використаних джерел з 159 найменувань (на 15с.), 2 додатки (на 20 с.).

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

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

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

Розділ 2. Запропоновано методи структурного аналізу цифрових систем, що використовуються на стадії попередньої обробки схем для пошуку розгалужень, що сходяться, і визначення деревоподібних підграфів із метою підвищення швидкодії методів моделювання несправностей за стратегією зворотного простежування дефектів. Представлені чотири наступних методи: 1) Одиночне структурне моделювання РС. Структура представлена в списочному вигляді. Найбільш простий у реалізації, але вимагає квадратичних витрат від кількості еквіпотенційних ліній. Рекомендується для аналізу схем із великим числом розгалужень (>20%). 2) Ітеративний аналіз матриці суміжностей. Орієнтований на обробку цифрових структур, представлених у матричному вигляді. Обчислювальна складність аналогічна першому методу. 3) Дедуктивний структурний аналіз РС. Схема пристрою представляється у вигляді множини списків функціонально зв'язаних ліній. Обчислювальна складність визначається квадратичною залежністю від числа РС. 4) Дедуктивно-паралельний аналіз РС. Метод ізоморфний останньому, але орієнтований на паралельні обчислення над матрицею суміжностей цифрової схеми. Два останніх методи засновані на дедуктивному підході до структурного моделювання графа, що дозволяє визначати всі розгалуження, що сходяться, у цифрових схемах за один прохід.

Цікавим рішенням в дедуктивний аналіз РС. Розглядається деяка поточна вершина в орієнтованому графі G ліній схеми. Стосовно суміжних вершин-попередників, що є прообразами згадана вершина є образом(рис.1), де - оператор взяття прообразу.

Для ілюстрації можливості застосування дедуктивного методу до структурного аналізу виконаємо перетворення графа в OR-модель за правилами: 1) вершини, що містять тільки вихідні дуги, стають зовнішніми входами схеми; 2) інші вершини представлені OR-елементами, а точніше, їх виходами; 3) дуги графа відповідають функціональним зв'язкам між суміжними вершинами. У такий спосіб вершина графа перетвориться в еквипотенційну лінію OR-структури, де число входів у кожного елемента дорівнює кількості суміжних вершин-попередників. Наприклад, граф, що має дев'ять вершин перетвориться в схему з 6 елементів із трьома зовнішніми входами

1. Усі вершини, що входять у контур, мають однакові екстраобрази. Це є наслідком існування таких фактів: 1) усі лінії контуру однаково досяжні стосовно одна до іншої; 2) кожна лінія,що входить до контура має у якості попередника будь-яку вершину, від якої існує шлях до однієї з контурних ліній. Звідси виходить, що усі вершини , що належать до контуру, мають однакові екстраобрази. Розгалуженню, що сходиться, можуть передувати вершини (лінії), що не є такими, але виявляються на вершині-сходженні як РС. Прикладом таких ліній є вершини, що складають шлях без розгалужень, що закінчується на лінії РС.

2. Для того, щоб усунути всіх попередників РС, що входять у множину Vj кандидатів в РС для вершини Vj, але не є РС, необхідно і достатньо відняти з множини Vj об'єднання перетинань усіх пар сполучень C²nj екстраобразів f*(f-1(Vj)) для безпосередніх попередників вершини Vj , де nj - число попередників.Процедура дедуктивного аналізу. Якщо граф - орієнтований, без контурів глобальних зворотних зв'язків, то стратегія пошуку РС зводиться до одноразового проходу всіх його вершин на основі процедури дедуктивної обробки , яка включає операції:

де -екстраобрази прообразів , число яких для вершини Vj дорівнює nj. Перше рівняння призначено для визначення РС шляхом виконання операції об'єднання перетинань усіх пар екстраобразів для прообразів аналізованої вершини, число яких дорівнює кількості сполучень - C²; друге - для виключення зі списку РС вершин, що не є такими у відповідності з твердженням 2.Тут f* - екстраобраз вершини, що взята у список кандидатів в РС при аналізі , число яких дорівнює mj. Множина РС, яка визначена в процесі обробки (третье рівняння), накопичується у складі окремої підмножини VRC та видаляється зі списків при обробці кожної вершини. Четверте рівняння призначено для формувания екстраобразу оброблювальної вершини .

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

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

(1), де

-

сукупність функцій справної поведінки пристрою; m - число його входів; - -входовий i-й елемент схеми, який реалізує Fi для визначення стану лінії (виходу)Yi на тест-векторіTt ; деXij j-й вхід i-го елементу; тест - упорядкована сукупність двійкових векторів, яка довизначена у процесі справного моделювання на множині вхідних, внутрішних й вихідних ліній, яка поєднана в матрицю

невхідна координата якої визначається моделюванням функції на тест-векторіTt; ; - множина дедуктивних схем або моделей, які визначені виразом (1), де ; - дедуктивна функція (ДФ) паралельного моделювання несправностей на тест-векторі , що відповідає справному элементу Fi, що дає можливість обчислювати список вхідних несправностей, які транспортуються на вихід елементу . Поняття синхронності введенної моделі (1) визначається за умови: , коли інтервал часу між зміною вхідних наборів , які подаються на схему, набагато більше максимальної затримки схеми t і елемента ti . Це дозволяє виключити час як несуттєвий параметр, що застосовується в технологіях моделювання й синтезу тестів.

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



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

З урахуванням розбиття тесту на вектори рівняння (1) одержання ДФ для приймає вигляд: Якщо функціональний опис пристрою представлено компонентами (примітивами), які формують стани усіх ліній схеми, то в якості формули перетворення справної моделі примітиву на тест-векторі в дедуктивну функцію постає вираз

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

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

Мова йде про визначення стану координати тест-вектору : : , яка відповідає виходу Yi логічного елементу його двійковий код або ідентифікатор) по його вхідним значенням, що представлені вектором , за умови, що FT є таблиця істиности сукупності булєвих функцій для опису елементів схеми, вхідний набор для якого формується конкатенаціею слів . З урахуванням даного факту вираз для обчислення трансформується до виду . Інакше, щоб визначити стан коордінати , необхідно сформувати двійковий вектор значень вхідних змінних елементу Fi, з використанням іх адресу для вилучення станів з вектору Tt Потім слід виконати конкатенацію отриманого вектору Xi з двійковим кодом типу функції з метою одержання вхідного слова для узагальненої таблиці істиности FТ, де в стовпці Yi, який відповідає значенню функції Fi, знаходиться стан координати . Модель дедуктивно-паралельного анализу неисправностей, окрім структури, задіяної в справному моделюванні, містить два додаткових модуля M и L.

Аналітичний вираз для обчислення векторів несправностей, які перевіряються та сполучені у матрицю М за допомогою набору дедуктивних функцій L, отриманих з F по (4), має вигляд: .

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

Таким чином, для визначення стану вихідного вектору несправностей Mi необхідно знайти адресу дедуктивной функції Li, з використанням отриманої для справного моделювання конкатенації двійкових cлів . Вхідні змінні для елементу Li є регістровими, теоретична розмірність яких дорівнює числу ліній в цифровому пристрої. Далі відбувається послідовне виконання (n-1) регістрових операцій над вхідними векторами . Результат у вигляді рядка Mi заносять в матрицу М. Вхідна змінна може мати знак інверсії. Тоді перед виконанням бінарної операції відбуваеться інверсія вмісту регістрової змінної: .

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

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

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

Алгоритм синтезу тесту перевірки одиночних константних несправностей одновихідного примітиву, що задаються регулярним діагональним -покриттям списку дефектів усіх змінних функціонального елементу (одиниця на вхідній і вихідній координаті кожного куба позначає активізацію виходу Z при наявності несправності будь-якого знаку на вході) містить наступні пункти: 1) Формування кандидатів у тест шляхом виконання операцій над векторами з : . 2) Одержання тесту Т () із кандидатів на основі аналізу 3) Мінімізація множини тест-векторів T шляхом застосування операції поглинання: . 4) Для одержання ще більш мінімального тесту необхідно виконати процедуру моделювання дефектів на функціональній чи структурній моделі пристрою й на отриманій багатозначній таблиці несправностей вирішити задачу одержання мінімального покриття несправностей побудованим тестом. Наступний приклад ілюструє основні кроки описаного алгоритму.

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

Дана операція приводить до одержання трьох підмножин кубів, що є кандидатами в тест:

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

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

Розділ 5. Система моделювання несправностей і синтезу тестів ориєнтована на обробку складних цифрових проектів на основі ПЛІС, які містять сотні тисяч вентилів. Тестові експеріменти програмної реалізації метода на сотнях цифрових комбинаційних і послідовнісних схемах дали гарні результати за швидкодією у порівнянні з традиційними алгоритмами паралельного и дедуктивного моделювання. Окремі приклади аналізу швидкодії розробленого методу (обробка тест-прикладів на 1000 вхідних послідовностей, IBM PC 500 MГц, 256 Mбайт) та існуючих базових показані на рис. 5. Прискорення моделювання складає не менш десятка разів. На рис. 6 представлені результати аналізу швидкодії трьох реалізованих методів моделювання цифрових схем на однім і тим самим комп'ютері при обробці 1000 векторів. Показано переваги ЗДП- і ТЗДП-методів перед дедуктивно-паралельним і стратегія іх використання для обробки РС та деревоподібних структур (рис.7). Виграш у швидкодії більщ значущий для схем великої розмірності. Число РС в тест-схемах в середньому складає 20% від загальної кількості ліній. Реалізація SIGETEST: компілятор

Microsoft VisualC++; операційна система - Windows; середовище проектування - Active-HDL; - обсяг пам'яті для EXE-модуля - 1 Mбайт; - обсяг вихідних текстів - 700 Кбайт; число програмних модулів - 17; середній час генерації тестів, алгоритмічних (детермінованих), 2000 ліній - 10 (30) хвилин, при якості більш 90 %; зменшення часу побудови тестів після декомпозиції - 10 %; тест-приклади: ISCAS'85 (37 схем); проект PRUS (116 схем); ITC'99 (32 схеми); стан системи: працездатний - Prototype.

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

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

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

1. Хаханов В.И., Сысенко И.Ю., Колесников К.В. Дедуктивно-параллельый метод моделирования неисправностей на реконфигурируемых моделях цифровых систем // Радиоэлектроника и информатика. 2002.- №1.- С. 98-105.

2. Хаханов В.И., Колесников К.В., Хаханова А.В. BDP-метод моделирования неисправностей для синтеза тестов цифровых проектов // Радиоэлектроника и информатика.- 2002.- №2.- С. 60-66.

3. Хаханов В.И., Кривуля Г.Ф., Колесников К.В. Моделирование неисправностей для цифровых проектов на основе программируемой логики // Информационно-управляющие системы на железно-дорожном транспорте.- 2002.- № 4-5.- С. 51-59.

4. Хаханов В.И., Чумаченко С.В., Колесников К.В., Хаханова А.В. Анализ графовых структур для моделирования цифровых систем // Радиоэлектроника и информатика.- 2002.- №4.- С. 92-98.

5. Хаханов В.И., Колесников К.В., Парфентий А.Н., Хаханова И.В., Обризан В.И., Мельникова О.В. Технология моделирования и синтеза тестов для сложных цифровых систем // Радиоэлектроника и информатика.- 2003.- №1.- С. 72-80.

6. Хаханов В.И., Колесников К.В., Парфентий А.Н., Хаханова И.В. Моделирование и синтез тестов для цифровых схем с граничным сканированием // Радиоэлектроника и информатика.- 2003.- №2.- С. 79-86.

7. Ковалев Е.В., Хаханова А.В., Колесников К.В. Система верификации цифровых устройств, представленных в виде содержательного графа цифрового автомата.- Мат. 8-й междунар. конф. "Теория и техника передачи, приема и обработки информации".- Туапсе.- 2002.- Харьков: ХТУРЭ.- 2002.- С. 212-213.

8. Колесников К.В., Хаханова А.В., Побеженко И.А. Дедуктивный метод обратного моделирования неисправностей цифровых проектов.- Материалы 2-й Междунар. науч.-тех. конф. "Проблемы информатики и моделирования.- Харьков.- 2002.- Харьков: НТУ"ХПИ".- 2002.- С. 44.

9. Хаханов В.И., Колесников К.В., Хаханова И.В. Технологии проектирования и тестирования цифровых устройств и систем.- Сб. докл. и тез. 1-го Молодежного научно-практического форума "Информационные технологии в 21 веке".- Днепропетровск.-23-24 апреля 2003.- С. 32-36.

10. Vladimir Hahanov, Iryna Sysenko, Konstantin Kolesnikov. Backtraced Deductive-Parallel Fault Simulation for Digital Circuits.- Proceedings of the 7-th Internat. Conf. "The Experience of designing and Application of CAD Systems in Microelectronics".- Lviv - Slavske, 18-22 February 2003.- P.382-387.

11. Hahanov V.I., Skvortsova O.B., Kolesnikov K.V., Parfenty A.N. The Digital Cirtiut Models and Data Structure for High Performance Fault Simulation.- 10-th Internat. Conf. Mixed Design of Integrated Circuits and Systems.- Poland.- Lodz.-- 2003.- P. 334-339.

АНОТАЦІЯ

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

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

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

АННОТАЦИЯ

Колесников К. В. Дедуктивный метод моделирования неисправностей для синтеза тестов цифровых систем, реализуемых в программируемой логике.- Рукопись.- Диссертационная работа на соискание ученой степени кандидата технических наук по специальности 05.13.12 - системы автоматизации проектных работ.- Харьковский национальный университет радиоэлектроники, Харков, 2003.

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

Практическое значение полученных результатов определяется: реализацией комплекса SIGETEST моделирования неисправностей и синтеза тестов, позволяющего в несколько раз уменьшить время разработки и оценки качества тестов проектируемых цифровых устройств большой размерности; валидным тестированием программных средств моделирования неисправностей и синтеза тестов путем их сравнения с существующими мировыми аналогами и проверки с помощью тестовых примеров из библиотек ISCAS и сайтов ведущих фирм в области проектирования цифровых систем; внедрением практических результатов в технологический и учебный процессы в виде программы SIGETEST, позволяющей в автоматическом режиме строить тесты проверки одиночных константных неисправностей и синтеза тестов для цифровых проектов в среде Active HDLсложных цифровых проектов на основе ПЛИС, содержащих сотни тысяч вентилей. Тестовые эксперименты программной реализации метода на сотнях цифровых комбинационных и последовательностных схем дали хорошие результаты по быстродействию по сравнению с традиционными алгоритмами параллельного и дедуктивного моделирования. Ускорение моделирования составляет не менее десяти раз. Показано преимущество ОДП- и ТОДП-методов перед дедуктивно-параллельным. Выигрыш в быстродействии более существенен для схем большой размерности. Число сходящихся разветвлений в тест-схемах в среднем составляет 20% от общего количества линий.

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

ABSTRACT

Kolesnikov K.V. Deductive method of fault simulation for test generation of digital systems implemented in program logic device.- Manuscript.- Thesis for a candidate degree of technical sciences on speciality 05.13.12 - Design Automation Systems.- Kharkov National University of Radio Electronics, Kharkov, 2003.

The thesis is devoted to the development of deterministic test generation and deductive-parallel fault simulation of digital system for decreasing of their verification time for computer aided design using Active-HDL.

The offered fault simulation and test generation methods is oriented on processing of complex digital devices implemented into PLD containing millions of gates. The program realization of the method was tested on several hundreds of combinational and sequential benchmarks and gave good speed-up results in comparison with classic parallel and deductive fault simulation algorithms. The simulation speed-up was increased no less than 10 times. The speed advantage of BDP-method is more efficient for the VLSI circuits. The number of RFO in samples is about 20% from the number of lines. The absolute advantage of back-traced quasi exact method is connected with decreasing adequate of RFO fault simulation. The main results of given work is improving of deductive-parallel method that consists in: 1) Creation of general deductive-parallel model of digital circuit analysis based on back-traced superposition procedure which requires the computation complexity linear depending on number of equipotent lines; 2) Algorithms development of structural and functional analysis of digital circuits with purpose of the RFO set definition and circuit structure reconfiguration for superposition procedure realization; 3) Creation of internal interpretative-compiled model of digital device 4) Development of high performance test generation tools for tree-like structure circuits.

Key words: deterministic test generation, stuck-at-fault, digital device, deductive fault simulation, single path activization.

Размещено на Allbest.ru