Довганич Єгор Валерійович

      Автореферат

Вступ

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

Актуальність теми

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

Мета і завдання розробки і досліджень

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

Наукова новизна

Даний метод діагностики ПЛІС був запропонований в 1990 році Майком Абрамовичем, проте цей метод давав невисокий відсоток покриття КН при його практичному застосуванні.[1] Після того, як метод був модифікований цей відсоток можна було вважати задовільним, оскільки він генерував тестовий вектор, здатний покрити більше, ніж 80% КН, які можливо виявити.

Практична новизна

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

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

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

Апробація робіт

З доповіддю з даної тематики виступав на четвертій міжнародній науково-технічній конференції студентів, аспірантів і молодих учених в секції "Проектування ЕОМ і цифрових пристроїв".

Огляд досліджень і розробок за темою

Регіональний:
На регіональному рівні, одним з небагатьох, даною проблемою займався магістр ДонНТУ Бобровський К.В. У своїй роботі він детально вивчив питання зондовой діагностики ТЕЗ за допомогою щупа. Ця робота найбільш близька за своєю тематикою до моєї магістерської роботи.
1. Магістр ДонНТУ Бобровський Костянтин Вікторович
Тема магістерської роботи: "Розробка структури поста контролю зондової діагностики ТЕЗ на базі HDL- і FPGA-технологій", 2001р.
http://www.masters.donntu.ru/2006/fvti/bobrovskyy/diss/index.htm

Національний:
При розгляді національного рівня досліджень була виявлена книга Бутакова Е.А., в якій розглядаються питання діагностики програмованих логічних матриць, що по суті є основною складовою ПЛІС. Ця книга була видана в Москві, але віднесена до національного рівня за мовним критерієм.
2. Бутаков Е.А. Диагностика программируемых логических матриц / Е.А. Бутаков, М.Б. Волынский, В.Г. Новоселов – М.: Радио и связь, 1991 – 160 с.

Глобальний:
У світі даною проблемою займаються набагато інтенсивніше. Одного з перших, хто почав займатися дослідженням методів діагностики логічних схем, можна назвати Майка Абрамовича. Йому належить значна кількість статей та досліджень у цій області.
На сайті IEEE Xplore міститься велика кількість наукових статей, в тому числі і з даної тематики. Однак у вільному доступі представлені лише короткі огляди і висновки статей, а основний зміст доступний тільки зареєстрованим користувачам.
3. Abramovici, M. Strond, C. Hamilton, C. Wijesuriya, S. Verma, V. Murray Hill, NJ
Using roving STARs for on-line testing and diagnosis of FPGAs infault-tolerant applications Test Conference, 1999.
http://ieeexplore.ieee.org/iel5/6540/17459/00805830.pdf?arnumber=805830

4. Stroud, C. Lashinsky, M. Nall, J. Emmert, J. Abramovici, M.
On-line BIST and diagnosis of FPGA interconnect using roving STARs, On-Line Testing Workshop, 2001.
http://ieeexplore.ieee.org/iel5/7458/20291/00937813.pdf?arnumber=937813

5. Stroud, C. Lee, E. Abramovici, M.
BIST-based diagnostics of FPGA logic blocks, Test Conference, 1997.
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=639662

6. Jack Smith, Tian Xia, Charles Stroud
An Automated BIST Architecture for Testing and Diagnosing FPGA Interconnect Faults, Journal of Electronic Testing, Theory and Applications 2006.
http://www.springerlink.com/index/FR805MQQ78876118.pdf

Основний зміст роботи

Даним методом трасування критичних шляхів є метод дослідження комбінаційних схем, за допомогою якого можна побудувати тестовий вектор для даної схеми. Тестовий вектор включає набір тестів, тобто набір початкових значень первинних входів схеми, які дають можливість знайти максимальну кількість константних несправностей, що виявляються (далі КН). Таким чином даний метод – це метод аналізу комбінаційних схем на предмет наявності в схемі КН, що виявляються. Метод аналізує і дає результат по кожній з точок схеми (з урахуванням еквівалентності несправностей).[2,9]

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

Також, МКШ дає можливість оцінки повноти тесту (вектора), тобто можна оцінити, яку кількість КН покриває даний тест. Отже, даний метод не вимагає використання додаткових алгоритмів оцінки повноти тестів.

Перші дослідження в цій області були зроблені Майком Абрамовічи у 1983 році, результатом яких стала стаття «Abramovici 1983 Critical path tracing - an alternative to fault simulation». Також певних успіхів у дослідженні даної проблеми досяг іранський університет, які послужили основою статті «Using VHDL Critical Path Tracing Models for Pseudo Random Test Generation». Саме ці статті стали основою глибшого дослідження МКШ, а також його програмної реалізації.

Ще однією корисною властивістю МКШ є побудова списку КН, що виявляються, а також визначення КН, що не виявляються, з метою подальшої генерації тестів іншими методами.

Для визначення КН, які можна виявити, виконується моделювання справної схеми, в ході якого розраховуються значення сигналів для критичних шляхів. Цей розрахунок виконується від первинних виходів до первинних входів. Побудова критичних шляхів базується на теорії кубів логічних елементів (ЛЕ). Всю теорію кубів ЛЕ можна звести до аналізу вироджених покриттів (ВП) різних ЛЕ. Для даного аналізу необхідно скласти нульові і одиничні вироджені покриття вищеперелічених логічних елементів (табл. 1).

Таблиця 1. Вирождені покриття логічних елементів.

При побудові ВП «*» позначає критичність значення. Вхід ЛЕ є критичним, якщо при зміні даного значення на протилежне, при незмінних значеннях інших входів елементу, значення виходу ЛЕ також міняється на протилежне. Значення без «*» позначає те, що дане логічне значення заблоковане іншою вхідною лінією елементу, тобто при зміні такого значення на протилежне, при незмінних значеннях інших входів елементу, значення виходу цього елементу не змінюється.[7]

Якщо ЛЕ має більш ніж два входи, то вироджені покриття для нього будуватимуться аналогічно з виконаннями наступних правил:

• якщо ВП двухвходового ЛЕ (далі 2ЛЕ) складається лише з критичних значень, то це ж критичне значення буде на всіх входах відповідного многовходового ЛЕ (далі МЛЕ);
• якщо ВП 2ЛЕ складається з критичного і некритичного значень, то в МЛЕ буде n наборів вхідних значень, кожен з яких складається з критичного значення на одному з його входів і некритичних – на інших, де n – кількість входів ЛЕ.

Ці правила не поширюються на ЛЕ "сума за модулем 2", оскільки такі ЛЕ використовуються досить рідко, а побудова їх ВП є доволі складним завдання.

Отже, знаючи правила побудови ВП ЛЕ можна переходити безпосередньо до МКШ. Як вже наголошувалося раніше, за допомогою цього методу будується тест і визначаються схемні лінії, значення яких впливають на значення первинних виходів. Константні несправності на таких лініях виявляються тестом на входах схеми. Узагальнений алгоритм МКП виглядатиме таким чином (рис. 1):[4]

1. знаходяться первинні виходи схеми;
2. для всіх первинних виходів складаються набори всіх можливих критичних значень, тобто для схеми з двома первинними виходами це буде набір – 0*0*, 0*1*, 1*0* і 1*1*; з одним – 0* і 1*;
3. знаходиться ЛЕ, значення виходу якого було визначено на попередньому кроці, і відповідно до його вихідного значення визначається ВП даного ЛЕ;
4. якщо значення цього ВП не конфліктують із значенями, отриманими на попередніх кроках, то входам ЛЕ привласнюються відповідні до ВП логічні значення. В разі визначення значень всіх первинних входів, ці значення будуть тестом, який розміщується у векторі. Після цього, або якщо стався конфлікт значень, вибирається наступний набір вхідних значень останнього обробленого ЛЕ. Після обробки останнього набору поточного ЛЕ виконується перехід до попереднього ЛЕ, тобто на один рівень назад і т.д.;
5. після перебору всіх можливих наборів критичних значень первинних виходів, отримуємо тестовий вектор для КН, які виявляються, і його повноти.

Рисунок 1. Практичне застосування МКШ на КЛС (анімація, 16 кадрів, 5 циклів, 88.4 Кбайта).

Таким чином, ми отримуємо набір тестів, який утворює тестовий вектор. Цей вектор покриває певну частину КН схеми. Тестовий вектор вважається задовільним, якщо його покриття складає 80% і більш від загального числа КН. Це називається оцінкою повноти тесту. Тому необхідно при побудові чергового тесту (безконфліктного повного проходу від первинних виходів до первинних входів), відразу додавати в список виявлені даним тестом несправності. КН х (stuck-at-x) вважається виявленою, якщо в одному з критичних шляхів міститься критична лінія із значенням ‘X (НЕ x).

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

Вище викладені основні положення і принципи методу трасування критичних шляхів. При практичному вживанні МКП можуть виникати окремі випадки окремих ділянок схем, такі як: трасування конусів, петель, трасування розгалуження, що сходиться, самомаскування і так далі. Ці випадки є досить вузькоспеціалізованими моментами в області діагностики ІС, тому розглядатися в межах даного реферату не будуть. Замість цього, далі наведений приклад практичної реалізації МКП (рис. 2).

Рисунок 2. МКШ для комбінаційної схеми без розгалуження.

На рисунку 2а зображена комбінаційна логічна схема без розгалужень з 8 вентилями (ЛЕ). На входи схеми поданий певний набір вхідних значень, який дозволить розглянути контрольні моменти методу. Відповідно до вхідних значень розраховані решта значень вентилів. Такий розрахунок з певним тестом на вході називається справним моделюванням схеми.[10]

Крапка на вході вентиля позначає критичність даного входу по відношенню до інших входів вентиля. Вхід без крапки вказує на те, що даний вхід заблокований іншим критичним входом вентиля. Бувають випадки, коли всі входи вентиля критичні або заблоковані.[3]

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

Отже, даний тест дозволяє виявити 5 КН: КН1 на первинному вході схеми і 4 КН0 – на 3 лініях вентиля А і первинному виході схеми. Окремо розглядаються випадки з розгалуженням схемних ліній, використовуються правила трасування, так званих, ствола і гілок.

Проте, вживання вище описаного, так званого, класичного МКП на практиці не дає належного результату. Це відбувається через те, що, враховуючи правила побудови кубів ЛЕ, не завжди пошук оптимального набору вхідних значень вентиля дає можливість перебору всіх існуючих варіантів значень. Іншими словами, за наявності критичного значення на виході вентиля відбувається перебір його вхідних значень з відповідного ВП. Але ВП не містить повного набору можливих значень, а лише групи значень, що відповідають умовам критичності. Отже, при трасуванні схеми необхідно після аналізу групи значень для входів вентиля з відповідного ВП, аналізувати і варіанти, які залишилися, не присутні у ВП. Проте, вибірку здійснювати спочатку потрібно все ж з ВП ЛЕ.

Наприклад, для елементу 3І при значенні виходу 0* маємо наступні набори вхідних значень вентиля: 0*11, 10*1 і 110*. При виборі одного з цих наборів, отримуємо в результаті тест з максимально високим відсотком покриття КН. Але, інколи виникає ситуація, коли на входи цього ЛЕ можливо подати лише набір значень 000, що не суперечить логіці побудови комбінаційних схем. Проте, такого набору немає у ВП даного ЛЕ, слідуючи правилам класичного МКП. Якщо не враховувати таку ситуацію, то можна втратити тест для певної схеми, тоді як, розгляд даного набору призводить лише до зниження потенційно можливого відсотка покриття КН. Але у результаті, сумарний відсоток покриття всього вектора буде значно вищий.

До цих виводів я прийшов, застосовуючи класичний МКП для схеми одного розряду суматора з черезрозрядной інверсієй перенесення. Результатом класичного методу буде вектор, що складається з одного тесту, – 1*1*1*. Цей вектор з 24 КН (з врахуванням еквівалентності) виявляє лише 5, що складає 21%. Для того, щоб вектор можна було вважати задовільним, він повинен як мінімум покривати 80% всіх КН. Очевидно, що даний вектор таким назвати не можна. Вживання вдосконаленого МКП збільшує відсоток покриття до 100%.[8]

Отже, при розгляді вхідних значень не лише з ВП ЛЕ, а застосовуючи після аналізу ВП ще і повний перебір значень, можна досягти 100% покриття КН для даної комбінаційної схеми. Використання даного прийому я назвав універсальним МКШ.

Додам, що даний метод діагностики ІС здатний значною мірою скоротити час моделювання і діагностики ПЛІС, а також при спільному використанні з іншими методами (як, в іншому, і при одиночному використанні) дає високі показники повноти покриття КН і не вимагає великих апаратних витрат при його практичній реалізації.

На даний момент робота над магістерською дисертацією не завершена.

Висновки

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

Список використаної літератури

1. M. Abramovici, P.R. Menon and D.T. Miller. Critical path tracing - an alternative to fault simulation. - IEEE Design and test, Feb. 1984 - pp. 83-92.
2. M. Shadfar, A. Paymandoust, Z. Navabi. Using VHDL Critical Path Tracing Models for Pseudo Random Test Generation. - Electrical and Computer Engineering Department - pp. 8.
3. Барашко А.С., Скобцов Ю.А., Сперанский Д.В. Моделирование и тестирование дискретных устройств. – К., Наукова думка, 1992 - c. 28-32.
4. Бутаков Е.А. Диагностика программируемых логических матриц / Е.А. Бутаков, М.Б. Волын-ский, В.Г. Новоселов – М.: Радио и связь, 1991 – 160 с.
5. Новоселов В.Г. Синтез полных проверяющих тестов И–НЕ схем произвольной структуры на базе модели расширения и исчезновения интервалов / В.Г. Новоселов // Труды четвертой междунар. конф. «CADD’2001» сент. 2001, г. Минск — Минск: Ин-т техн. кибернетики НАН Беларуси, 2001 - c. 143-155.
6. Новоселов В.Г. Построение проверяющего теста для современных ПЛМ (CPLD) / В.Г. Новоселов, А.В. Борисевич // Вестник СевНТУ, вып. 74 — Севастополь: изд-во СевНТУ, 2006 — с. 47-57.
7. Беннетс Р. Проектирование тестопригодных логических схем. - Пер. с английского. - М.: Радио и связь, 1990 - 176 с.
8. Тарасенко А.Н. Методы оценки и показатели тестируемости дискретных устройств (обзор) //Зарубежная радиоэлектроника, 1989, выпуск 7 - с. 24-29.
9. Зинченко Ю.Е. T-модель дискретного устройства и решение диагностических задач на ее основе. - Электронная библиотека магистра Маркитанова В.Р. http://www.masters.donntu.ru/2001/fvti/markitantov/diss/library/zinchenko1/index.html, Портал магистров, 2001.
10. Уильямс Т.У., Паркер К.И. Проектирование контролепригодных устройств //ТИИЭР, 1983 - с. 122-139.