Довганич Егор Валерьевич

      Автореферат

Введение

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

Актуальность темы

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

Цель и задачи разработки и исследований

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

Научная новизна

Данный метод диагностики ПЛИС был предложен в 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).[5]

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

При построении ВП «*» обозначает критичность значения. Вход ЛЭ является критическим, если при изменении данного значения на противоположное, при неизменных значениях других входов элемента, значение выхода ЛЭ также меняется на противоположное. Значение без «*» обозначает то, что данное логическое значение заблокировано другой входной линией элемента, т.е. при изменении такого значения на противоположное, при неизменных значениях других входов элемента, значение выхода этого элемента не изменяется.[7]

Если ЛЭ имеет более чем два входа, то вырожденные покрытия для него будут строиться аналогично с выполнениями следующих правил:

• если ВП двухвходового ЛЭ (далее 2ЛЭ) состоит только из критических значений, то это же критическое значение будет на всех входах соответствующего многовходового ЛЭ (далее МЛЭ);
• если ВП 2ЛЭ состоит из критического и некритического значений, то у МЛЭ будет n наборов входных значений, каждый из которых состоит из критического значения на одном из его входов и некритических – на остальных, где n – количество входов ЛЭ.

Эти правила не распространяются на ЛЭ исключающее ИЛИ, т.к. такие ЛЭ используются довольно редко, а построение их ВП представляет собой нетривиальную задачу.

Итак, зная правила построения ВП ЛЭ можно переходить непосредственно к МКП. Как уже отмечалось ранее, с помощью этого метода строится тест и определяются схемные линии, значения которых влияют на значения первичных выходов. Константные неисправности на таких линиях обнаруживаются тестом на входах схемы. Обобщённый алгоритм МКП будет выглядеть следующим образом (рис. 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.