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

Сисенко Ірина Юріївна

УДК 681.32:519.713

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

05.13.13 – обчислювальні машини, системи та мережі

АВТОРЕФЕРАТ

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

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

Харків 2002

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

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

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

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

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

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

Офіційні опоненти: –

доктор технічних наук, професор, заслужений винахідник України

Харченко Вячеслав Сергійович, Національний аерокосмічний університет

ім. Жуковського М.Є. “Харківський авіаційний інститут”, завідуючий кафедрою комп'ютерних систем і мереж –

кандидат технічних наук Гусятін Володимир Михайлович, Харківський нацiональний університет радіоелектроніки, доцент кафедри електронних обчислювальних машин

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

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

Захист відбудеться 30 жовтня 2002 року о 14 годині на засіданні

спеціалізованої вченої ради Д 64.052.01 у Харківському національному

університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

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

Автореферат розісланий 27 вересня 2002 року

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

спеціалізованої вченої ради Саєнко В.І.

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

Актуальність теми. Комп'ютерні системи, що реконфігуруються, є новим перспективним напрямком підвищення ефективності використання обчислювальної техніки в Україні і в цілому світі для вирішення NP-складних задач. Реалізація таких систем припускає використання як універсального процесора з метою керування обчисленнями, так і програмованої логіки, орієнтованої на паралельну обробку структур даних великого розміру. Поряд з низькою вартістю кристалів програмованих логічних інтегральних схем (ПЛІС) – Field Programable Gate Array (FPGA), Complex Programable Logic Device (CPLD) і незначним часом синтезу структурно і функціонально складних обчислювальних пристроїв на їхній основі існує проблема тестування останніх. Вона визначається великою розмірністю реалізації цифрової системи, що нараховує до 10 мільйонів еквівалентних вентилів на одному кристалі і недостатньою швидкодією існуючих методів моделювання несправностей з метою верифікації і тестування цифрових систем. Комплексне рішення згаданої проблеми можливо шляхом розробки нових швидкодіючих методів і алгоритмів аналізу дефектів з метою їхнього використання при побудові тестів верифікації й оцінки їхньої якості. Це дозволить обробляти на сучасних робочих станціях обчислювальні системи на кристалах, що нараховують порядку 100 000 еквівалентних вентилів. Процес обробки включає: синтез тестів, моделювання несправностей для визначення повноти перевірки фізичних та модельних дефектів. З метою рішення задач тестування кристалів, що нараховують мільйони вентилів, необхідно використовувати ще і технології граничного сканування – Boundary Scan, що вже приведені до стандарту проектування IEEE. Дана технологія дозволяє декомпозувати як завгодно складну систему на підсхеми, що є доступними для методів синтезу тестів і моделювання, які розроблюються або існують.

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

Вагомий внесок у розвиток напрямку технічної діагностики обчислювальних систем, зв'язаного з моделюванням несправностей для синтезу тестів, внесли вчені: I.Pomeranz, 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) № 01 від 06.06.1999 і № 02 від 19.11.2001 “Розробка програмних засобів автоматичної генерації тестів і моделювання несправностей для цифрових систем, реалізованих на основі програмованих логічних інтегральних схем”.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результати дисертації у вигляді програмних додатків використовуються на підприємствах: ЗАТ “НДІРВ” (довідка про упровадження від 18.02.2002), ЗАТ “Енергозбереження”, Харків (довідка про упровадження від 10.03.2002); а також у навчальному процесі Харківського національного університету радіоелектроніки (акт про упровадження від 23.04.2002) і Національного технічного університету “Харківський політехнічний інститут” (довідка про упровадження від 15.05.2002).

Особистий внесок здобувача. Всі основні результати отримані здобувачем особисто. У роботах, опублікованих спільно, автору належать: [2] – розробка об'єднаного алгоритму зворотнього простежування для комбінаційних схем; [3] – структури даних (формат SCH), що орієнтовані на побудову кубічних покрить для послідовносних схем; [4] – процедури аналізу тестів для структурно-функціональних моделей цифрових схем; [5] – алгоритм кубічного моделювання несправностей цифрових схем; [6] – модель асинхронних структур примітивних автоматів; [7] – реалізація алгоритму кубічного моделювання несправностей цифрових схем; [8] – дедуктивно-паралельний метод моделювання цифрових пристроїв, моделі цифрових систем, що реконфігуруються; [9] – алгоритм аналізу розгалужень, що сходяться, для підвищення точності зворотнього моделювання несправностей; [10] – аналіз перехідних процесів у методах моделювання цифрових структур; [11] – розробка процедур керування моделюванням; [12] - дедуктивна процедура кубічного моделювання несправностей цифрових схем; [13] - процедура моделювання доповнень до тест-вектору для цифрових пристроїв на основі програмованої логіки; [14, 15, 17] – алгоритм дедуктивного кубічного моделювання несправностей комбінаційних і послідовносних цифрових схем; [16] – досвід застосування програм і методів моделювання у дистанційне навчання; [18,19] – реализація методів моделювання як ядра автоматичної системи генерації тестів; [20] – трійкове моделювання справного поводження цифрових систем; [21] – алгоритми моделювання несправностей цифрових пристроїв для генетичних алгоритмів синтезу тестів; [22] – швидкодіючий алгоритм дедуктивно-паралельного моделювання несправностей для системи генерації тестів; [23-25] – реалізація зворотнього моделювання несправностей для методу генетичних алгоритмів.

Апробація результатів дисертації здійснювалася на конференціях різного рівня, що мають безпосереднє відношення до теми дисертаційної роботи: 1) 8-th International Conference “Mixed Design of Integrated Circuits and Systems”, Poland, Zakopane, 2001; 2) VI-th Conference CADSM “The Experience of Designing and Application of CAD System in Microelectroncs”, Lviv, Slavsko, 2001; 3) VII-th Conference CADSM ”Modern Problems of Radio Engeneering, Telecommunication and Computer Science”, Lviv, Slavsko, 2002; 4) IFA Conference “Programmable Devices and Systems”, Poland, Gliwice, 2001; 5) V-th International conference “The experience of designing and application of CAD systems in microelectronics“, Ukraine, Slavsko, 2000; 6) III Krajovej konferencji naukowej “Reprogramowalne uklady cyfrowe”, Poland, Szczecin, 2000; 7) 9-th International Conference. Mixed Design of Integrated Circuits and Systems, Poland, Wroclaw, 2002; 8) 13th International Conference on Modelling and Simulation, USA, California, Marina del Ray; 9) Третя Міжнародна науково-практична конференція “Сучасні інформаційні й електронні технології СІЕТ-2002”, Україна, Одеса, 2002; 10) Міжнародна конференція “Комп'ютерні науки й інформаційні технології”. – Саратов. – 2002; 11) I Міжнародна конференція по індуктивному моделюванню МКІМ'2002. – Львів; 12) Сьома Міжнародна науково-технічна конференція “Інформаційні технології: техніка, технологія, освіта, здоров'я” MicroCAD-99, ХГПУ, Харків, 1999; 13) 5-а Міжнародна конференція “Техніка передачі, прийому й обробки інформації”, Туапсе, 1999; 14) 4-а Міжнародна конференція “Інформаційно-керуючі системи на залізничному транспорті”, Алушта, 2000; 15) 6-а Міжнародна конференція “Техніка передачі, прийому й обробки інформації”, Туапсе, 2000; 16) 4-а Міжнародна конференція Української асоціації дистанційного освіта "Освіта і віртуальність-2000", Севастополь, 2000.

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

Структура й обсяг дисертації. Дисертаційна робота містить 148 сторінок, 38 рисунків (на 33 с.),7 таблиць (на 7 с.). Її структура включає: вступ, 4 розділи, висновок, список використаних джерел з 133 назв. (на 11 с.), 3 додатки (на 13 с.).

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

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

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

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

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

Вектор несправностей, що перевіряються на тесті, являє собою одномірний масив, координати якого визначають перевірку (1) чи неперевірку (0) несправності на даному тест-векторі.

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

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

Тому представляється доцільним об'єднання методів кубічного дедуктивного і паралельного моделювання з метою підвищення швидкодії аналізу дефектів і визначення якості тесту. Запропонований алгоритм орієнтований як на табличний опис примітивів довільної складності RTL рівня, так і на вентильне представлення цифрових систем. Швидкодія алгоритму залежить від представлення моделей цифрових пристроїв, що можуть бути реалізовані як у компілятивному, так і интерпретативному виконанні. Переваги дедуктивно-паралельного методу моделювання несправностей: уникнення операцій над списками, характерних для дедуктивного методу, що мають обчислювальну складність n2, і перехід до реалізації паралельних операцій на процесорі PRUS, акселераторі HEFS, використання компілятора Active-HDL для одержання тест-векторів справної поведінки, довизначених по невхідних координатах; інтерактивна подійна модифікація дедуктивної интерпретативної моделі паралельного моделювання несправностей на кожному вхідному наборі без інверторів на виходах логічних елементів; можливість використання універсального елемента моделювання несправностей для синтезу схеми аналізу дефектів цифрової системи для побудови компілятивної моделі паралельно-дедуктивного моделювання несправностей.

З огляду на те, що паралельні процеси є домінуючими і найбільше часозатратними в пропонованому методі моделювання, пропонується апаратурна реал ізація метода, зображена на рис.1. Алгоритм роботи пристрою моделювання складається з реалізації процедур справного моделювання й аналізу дефектів. Спочатку заноситься інформація – схемний опис у блок 6, формується одинична матриця в блоці 1, ініціалізуються регістри блоків 2-5. Інформація з блоку 6 – тип елемента (AND, OR) надходить на блок 9 з метою вибору операцій для формування векторів дефектів, що перевіряються, разом з тестовими сигналами, що надходять на входи a, b блоків 8, 9 із блоку 5, що формують сигнали на виході блоку 8, що надходять далі в блок 5, визначаючи невхідні координати. Після обраного дешифратором одного з чотирьох елементів на його входи подається вміст реєстрових змінних А и В, що надходить за два часових такти в блок 7. Результат векторної логічної операції з виходу Mi у третьому такті надходить у блок пам'яті 1, де формуються вектори дефектів, що перевіряються, для всіх ліній схеми. Після обробки всіх елементів, що знаходяться в блоці 6 виконується формування осередків блоку 2 і повторення процедури з метою установлення факту збіжності моделювання справного поводження і несправностей. Після цього виконується формування вмісту осередків блоку 3 і 4. По закінченні моделювання всіх наборів тесту в блоці 4 формується вектор перевірених дефектів, на підставі аналізу якого формується якість тесту у відсотках.

У третьому розділі пропонується метод зворотнього моделювання несправностей, який може бути використаний для швидкого аналізу надскладних цифрових систем на основі ПЛІС, що містять мільйони вентилів, оскільки він має високу швидкодію обробки комбінаційних, так і послідовностних схем. Граф-схема алгоритму зворотнього моделювання представлена на рис.2.

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

З метою обґрунтування оцінювання якості тестів для цифрових систем на моделях, що реконфігуруються, доведено:

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

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

З обліком викладеного вище стратегія застосування методу зворотнього моделювання несправностей, що перевіряються тестом, виглядає в такий спосіб: –

аналіз схемної структури для визначення розгалужень, що сходяться;–

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

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

Приклад 1. Виконати моделювання несправностей синхронного двоступінчатого Т-триггера (рис.3), синхронізованого зsаднім фронтом, на вхідному тест-векторі 1101. Результати справного моделювання схеми визначаються вектором Т=110111101101.

З обліком наявних у схемі розгалужень на лініях 1,2,3,4,7 і 8 вихідний список несправностей представлений вектором множин:

Ітеративне виконання дедуктивно-паралельного аналізу дефектів зі списку S на моделі, що реконфігуруються (рис. 4) дає формування наступних підмножин перевірки , та неперевірки Лінії 1 і 4 з'являються виходами, що спостерігаються, після чого виконується моделювання послідовностної схеми методом зворотнього моделювання:

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

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

де r – потужність множини розгалужень, що сходяться; G – число вентилей, b – кількість несправностей, W – довжина машинного слова. Для списочного представлення дефектів, що моделюються, остання формула модифікується до виду

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

У четвертому розділі пропонуються програмні засоби оцінювання якості тестів та моделювання несправностей, що є інтегрованими в систему автоматичної генерації тестів для цифрових систем, що проектуються з використанням середовища Active-HDL і орієнтованi на їхню реалізацію в кристалах FPGA, CPLD. Система дозволяє зменшити час (на 50–60%) верифікації цифрових проектів завдяки реалізації розроблених швидкодіючих методів дедуктивно-паралельного та зворотнього моделювання зворотнього моделювання на порядок зменшує час аналізу схеми в порівнянні з дедуктивно-паралельним; залежність часу обробки схеми від числа вентилів носить лінійний характер.

Додатки містять коди апаратної та программної реалізації запропонованих методів та моделей. Система моделювання несправностей, інтегрована в автоматичну систему генерації тестів, впроваджена в ЗАТ “НДІРВ”, ЗАТ “Енергозбереження” для тестування проектів цифрових пристроїв, що є орієнтованими на релізацію в ПЛІС, а також у навчальному процесі Харківського національного університету радіоелектроніки і Національного технічного університету “Харківський політехнічний інститут”.

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

9. Впроваджені практичні результати у виглядi програмних засобів у навчальний і технологічний процеси з метою зменшення часу проектування шляхом автоматизації процесу верифікації цифрових систем, що реалізованi на основі ПЛIС, наприклад в ЗАТ "НДІРВ" та ЗАТ "Енергозбереження". Практичні та теоретичні результати можна використовувати у проектних установах та університетах, що займаються розробкою дискретних систем на кристалах програмованої логіки.

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

1.Сысенко И.Ю. Метод обратного моделирования неисправностей для последовательностных схем // АСУ и приборы автоматики. – 2002. – № 119. – С. 41-50.

2.Хаханов В.И., Сысенко И.Ю., Побеженко В.В., Монжаренко И.В. Алгоритмы условного диагностирования вычислительных устройств // Радиоэлектроника и информатика. - 1998. - №3. - С. 87-91.

3.Хаханов В.И., Сысенко И.Ю., Чамян А.Л. Генерация тестов для конечных автоматов, заданных граф-схемами алгоритмов // Радиоэлектроника и информатика. - 1999. - №2. - С. 87-91.

4.Хаханов В.И., Сысенко И.Ю., Абу Занунех Халиль И.М. Проектированиетестов для структурно-функциональных моделей цифровых схем // Радиоэлектроника и информатика. - 1999. - №3. - С. 51-59.

5.Хаханов В.И., Шкиль А.С., Ханько В.В., Сысенко И.Ю. Кубическое моделирование неисправностей цифровых систем // Радиоэлектроника и информатика. - 2000. - №1. - С. 83-89.

6.Шкиль А.С., Скворцова О.Б., Сысенко И.Ю., Чамян А. Генерация тестов для асинхронных структур примитивных автоматов // Радиоэлектроника и информатика. – 2001. – № 2. – C. 97-103.

7.Хаханов В.И., Сысенко И.Ю., Хак Х.М. Джахирул, Масуд М.Д. Мехеди. Кубическое моделирование неисправностей цифровых проектов на основе FPGA,CPLD // Радиоэлектроника. Информатика. Управление. – 2001. – №1 . – C. 123-129.

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

9.Хаханов В.И. Сысенко И.Ю. Метод обратного моделирования неисправностей для сверхбольших цифровых проектов // АСУ и приборы автоматики. – 2002. – № 118. – С. 126-138.

10.Хаханов В.И., Бедратый Р.В., Сысенко И.Ю., Ханько В.В. Методы моделирования цифровых структур. Анализ переходных процессов // 5-я Международная конференция "Техника передачи, приема и обработки информации". – Туапсе. - 1999. – С. 389-391.

11.Ельчанинов Д.Б., Побеженко В.В., Сысенко И.Ю. Алгоритмы управления на базе сетей Петри с аналитическими дугами // 7-ая международная научно-техническая конференция “Информационные технологии: техника, технология, образование, здоровье” MicroCAD-99. – Харьков, ХПИ. – 1999. – С. 75-76.

12.Сысенко И.Ю., Масуд МД. Мехеди, Хак Х.М. Джахирул, Чамян А.Л. Дедуктивный метод кубического моделирования неисправностей цифровых схем // 4-ая Международная конференция "Информационно-управляющие системы на железнодорожном транспорте". – Алушта. – 2000. – С. 95.

13.Sysenko I.Y., Haque H.M. Jahirul. The deductive method of cubic simulation of complements to the test-vector of digital devices // Fifth International conference "The experience of designing and application of CAD systems in microelectronics". – Slavsko. – 2000. – C. 123-128.

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

15.Hahanov V.I., Rustinov V.A., Sysenko I.Y. Deductive method of digital devices fault cubic simulation // III Krajovej konferencji naukowej “Reprogramowalne uklady cyfrowe”. – Szczecin. – 2000. – P. 199-202.

16.Хаханов В.И., Шкиль А.С., Сысенко И.Ю., Хак Х.М. Джахирул. Дистанционное проектирование цифровых систем по технологии hardware-software cooperation // 4-я Международная конференция Украинской ассоциации дистанционного образования "Образование и виртуальность-2000". – Севастополь. – 2000. – С. 169-172.

17.Hahanov V.I., Krivoulya G.F., Rustinov V.A., Sysenko I.Y., Yegorov A.A. Fault Cubic Simulation of Digital Devices // Sixth International conference “The experience of designing and application of CAD systems in microelectronics”. – Slavsko: “Lvivska Politechnica” – 2001. – P. 112-115.

18.Hahanov V.I., Sysenko I.U., Babich A.V. System for Digital Device Test Generation in Active-HDL // 8-th International Conference. Mixed Design of Integrated Circuits and Systems. – Poland. – Zakopane: DMCSTUL – 2001. – P. 235-238.

19.Hahanov V.I., Sysenko I.Y., Pudov V.A. ATPG system and Fault Simulation Methods for Digital Devices // The 5th IFAC Workshop on programmable devices and systems. – Poland. – Gliwice: Silesian University of Technology – 2001. – P. 274-278.

20.Shkil A.S., Sysenko I.Y., Pobezhenko V.V. Ternary Simulation of Digital System in CAD Programmable Logic // Seventh Conference CADSM “Modern Problems of Radio Engeneering, Telecommunication and Computer Science” – Slavsko: “Lvivska Politechnica” – 2002. – P. 68-71.

21.Hahanov V.I., Sysenko I.Y., Skvortsova O.B. Test Generator Used Genetic Algorithms and Reconfigurable Deductive-Parallel Fault Simulation Method for Digital Devices // 9-th International Conference. Mixed Design of Integrated Circuits and Systems. – Poland. – Wroclaw – 2002. – P. 549-554.

22.Hahanov V.I., Sysenko I.Y., Skvortsova O.B. ATPG System, Fault Simulation and Test Generation Methods for Digital Devices // 13th International Conference on Modelling and Simulation MS 2002– 2002. – P. 230-235.

23.Хаханов В.И., Соколов А.В., Сысенко И.Ю., Скворцова О.Б. Детерминированный метод генетических алгоритмов для синтеза тестов верификации цифровых систем // 3-я Международная нучно-практическая конференция “Современные информационные и электронные технологии СИЭТ-2002”. – Одесса. – 2002. – С. 96.

24.Хаханов В.И., Сысенко И.Ю., Скворцова О.Б., Соколов А.В. Методы генетических алгоритмов для синтеза тестов верификации цифровых систем // Международная конференция "Компьютерные науки и информационные технологии". – Саратов. – 2002. – C. 76-77.

25.Хаханов В.И., Соколов А.В., Сысенко И.Ю., Скворцова О.Б. Детерминированный метод генетических алгоритмов для синтеза тестов верификации цифровых систем // I Международная конференция по индуктивному моделированию МКИМ'2002. – Львов. – 2002. – C. 112-118.

АНОТАЦІЯ

Сисенко І.Ю. Дедуктивно-паралельне моделювання несправностей на моделях цифрових систем, що реконфігуруються.– Рукопис.

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

спеціальністю 05.13.13 – Обчислювальні машини, системи та мережі.– Харківський нацiональний університет радіоелектроніки, Харків, 2002.

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

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

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

АННОТАЦИЯ

Сысенко И.Ю. Дедуктивно-параллельное моделирование неисправностей на реконфирурируемых моделях цифровых систем.– Рукопись.

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

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

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

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

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

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

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

Cистема оценки качества тестов и моделирования неисправностей, интегрированная в автоматизированную систему генерации тестов, протестирована на 90 примерах комбинационных и последовательностных схем из списков ISCAS (10), проекта PRUS (50) и ITC (30), что подтвердило состоятельность предложенных моделей и методов дедуктивно-параллельного и обратного моделирования неисправностей, а также построение реконфигурируемых моделей, и показало существенное увеличение быстродействия.

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

ABSTRACT

Sysenko Iryna Yu. Deductive-Parallel Fault Simulation Method on Reconfigurable Models of Digital Systems. – Manuscript.

Thesis for a candidate degree of technical sciences on speciality 05.13.13 – computing machines, systems and networks.– Kharkov National University of Radio Electronics, Kharkov, 2002.

The thesis is devoted to the development of the fast stuck-at-fault simulation methods on the reconfigurable models of digital systems, oriented on its implementation in programmable logic with purpose of synthesized test quality evaluation during verification.

During the period of research following problems were solved: improved model of deductive-parallel fault analysis, combines deductive fault simulation processibility and processing speed of parallel vector operations with purpose of significant speed-up of VLSI (Very Large Scale Integration) circuit verification; proposed deductive model of data structure reconfiguration, which allows processing of the set of faults in one iteration with purpose of applied input sequences evaluation speed-up; deductive-parallel fault simulation method of digital devices, presented on gate level and register transfer level in form of Boolean equations, which allows to combine the advantages both deductive fault analysis and parallel fault processing for handling of digital systems