автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Методы и алгоритмы встроенного тестирования ОЗУ

бел(^усский государственный университет,-

Информатики и радиоэлектроники

г*5-£ ^

63^326.7

Микитюк Вячеслав Георгиевич

методы И алгоритмы встроенного тестирования озу

Специальность 05Л 3.05 Элементы и устройства вычислительной техники и систем управления

автореферат диссертации на соискание ученой степени кандидата технических наук

МИНСК, 1996

Работа выполнена в Белорусском государственном универснте информатики и радиоэлектроники

Научный руководитель

Официальные оппоненты

- доктор технических наук, профессор Ярмолик В.Н.

- доктор технических наук, профессор Урбанович П.П.

- кандидат технических наух, доцент Головко В,А.

Оппонирующая организация - КТБ "Белмикросистемы"

НПО "Интегралл"

Защита состоится "21" ноября 1996 г. в 14.00 на заседании совета п защите Диссертаций Д02.15.01 б Белорусском государственно! университете информатики и радиоэлектроники по адресу: 22002'/ г.Минск, ул. П.Бровки , 6.

С диссертацией можно ознакомиться в библиотеке Белорусской государственного университета информатики и радиоэлектроники.

Автореферат разослан че» октября 1996 г.

Ученый секретарь совета по защите диссертаций

В.А.Кешишьян

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Прогресс в микроэлектронике, а также высокая регулярность структуры памяти привели к созданию целого ряда как микросхем ОЗУ большой емкости (до 1Гбита в экспериментальных образцах), так и специализированных СБИС со встроенными ОЗУ большой емкости. Появление. подобных микросхем и широкое их применение в современных устройствах вычислительной техники привели к значительному усложнению проблемы тестирования ОЗУ как на уровне ТЭЗов, так и на уровне микросхем.

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

Одним нз наиболее перспективных подходов контролепригодного проектирования является разбиение рассматриваемого устройства на ряд структурных модулей и разработка включаемых в состав усгройства схем, обеспечивающих тестирование каждого из модулей. При этом функции тестовой проверки возлагаются на сам объект контроля, т.е. реализуется встроенное тестирование (самотестирование) устройства. Данный подход может быть осуществлен как на уровне ТЭЗа, так и на уровне кристалла микросхемы. Причем реализация встроенного тестирования на уровне кристалла значительно облегчает разработку систем самотестирования на уровне ТЭЗа.

Анализ публикаций, посвященных методам самотестирования ОЗУ, показывает, что подходы, основанные на использовании маршевых алгоритмов тестирования, являются наиболее приемлемыми и будут преобладать в будущем. При этом все более широкое распространение получают их модификации для обеспечения неразрушающего контроля (неразрушатощий контроль характеризуется сохранением содержимого тестируемых ячеек памяти). Это обусловлено высокой обнаруживающей способностью маршевых алгоритмов тестирования ОЗУ, а также малыми аппаратными затратами на реализацию генератора тестов как для традиционного тестирования, так и для неразрушающего контроля.

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

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

Анализ работ, посвященных исследованию характерных неисправностей ОЗУ, позволяет проследить отчетливо выраженную тенденцию, что с увеличением степени интеграции микросхем памяти возрастает вероятность появления многократных неисправностей. Однако данная тенденция не нашла адекватного отражения в методах встроенного тестирования ОЗУ. Известные маршевые алгоритмы тестирования ОЗУ разрабатывались для обнаружения однократных неисправностей. Анализ полноты покрытия многократных неисправностей для этих алгоритмов не проводился. Применяемые же методы проектирования сигнатурных анализаторов основаны на макетировании либо программном моделировании и их использование для ОЗУ большой емкости невозможно при рассмотрении многократных неисправностей ввиду огромных временных затрат (для ОЗУ емкостью 1Мбит число двукратных константных неисправностью превышает 1012).

Связь работы с научными программами, темами. Результаты диссертационной работы связаны с выполнением хоздоговорных НИР, проводившихся НИЛ 3.3 Белорусского государственного университета информатики и радиоэлектроники в рамках республиканской программы "Информатика" на 1991-1995 гг. и на перод до 2000 года по темам "Исследование проблем проектирования тестопригодных и самотестируемых архитектур" и "Разработать методы и средства автомахизироврчного диагностирования БИС, СБИС и устройств на их основе, в том числе СБИС, реализующих методы граничного сканирования и архитектуры сканирования пути, а также модулей персональных ЭВМ", а также в рамках гранта молодых ученых Фонда фундаментальных исследований РБ по теме "Развитие теории и методов компактного

тестирования регулярных вычислительных структур".

Целью диссертационной работы является разработка маршевых алгоритмов тестирования ОЗУ и методов проектирования анализаторов выходных реакций, обеспечивающих эффективное обнаружение многократных неисправностей при встроенном тестировании.

Для достижения поставленной цели необходимо решить следующие задачи:

- провести анализ полноты покрытия многократных неисправностей для известных маршевых алгоритмов тестирования ОЗУ;

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

- получить оценки минимальНой'разрядности анализаторов выходных реакций, обеспечивающих 100%-е обнаружение заданных многократных неисправностей ОЗУ;

- разработать аналитический метод определения порождающего полинома сигнатурного анализатора, обеспечивающего 100%-е обнаружение заданных неисправностей ОЗУ;

разработать алгоритм быстрого вычисления сигнатур неисправностей для оценки достоверности тестирования ОЗУ.

Научная новизна полученных результатов.

Впервые осуществлен анализ многократных неисправностей, наиболее характерных для динамических и статических ОЗУ, на предмет обнаруживаемое!!! их маршевыми алгоритмами тестирования ОЗУ.

Разработка новых алгоритмов тестирования для обнаружения многократных неисправностей ОЗУ, в отличии от предшествующих работ, проводилась не путем модификации алгоритмов, разработанных для однократных неисправностей, а на основе специально сформулированных требований к тестам, обеспечивающих обнаружение рассматриваемых многократных неисправностей. Это позволило достичь ! 00%-го обнаружения многократных неисправностей в ¡рамках моделей, описывающих точечные дефекты матрицы накопителя ОЗУ.

На базе оригинального метода, основанного на определении числа неисправностей, сигнатуры которых должны быть различны для удовлетворения обобщенному условию тестируемости, получены оценки минимальной разрядности сигнатурных анализаторов, обеспечивающих 100%-е обнаружение заданных многократных неисправностей ОЗУ.

Предложен аналитический метод проектирования сигнатурных анализаторов, обеспечивающих 100%-е обнаружение заданных неисправностей ОЗУ, в отличии от применяемых методов, основанных на

макетировании либо программном моделировании.

Практическая значимость полученных результатов состоит в том, что они направлены из решение актуальных задач проектирования схем, обеспечивающих эффективное встроенное тестирование современных ОЗУ высокой степени интеграции. Ряд результатов, полученных в рамках данной диссертационной работы, в частности алгоритм тестирования статических ОЗУ March MS, а также программные средства на базе алгоритма быстрого вычисления сигнатур применены при разработке программно-аппаратных средств контроля и диагностики графического процессора, внедренных в Институте технической кибернетики АН РБ.

Основные положения диссертации, выносимые на защиту, заключаются в следующем:

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

- сформулированы требования к маршевым алгоритмам тестирования ОЗУ, при удовлетворении которым обеспечивается обнаружение всех многократных неисправностей, наиболее характерных для динамических и статических ОЗУ;

- предложен новый алгоритм тестирования, условно названный March М, характеризуемый наибольшей полнотой обнаружения многократных неисправностей среди известных маршевых алгоритмов тестирования динамических ОЗУ ( обеспечивает 100%-е обнаружение многократных неисправностей в рамках моделей, описывающих точечные дефекты матрицы накопителя ОЗУ);

- предложены новые алгоритмы тестирования, являющиеся наиболее эффективными из известных маршевых алгоритмов тестирования статических ОЗУ (при равной полноте обнаружения неисправностей с наиболее универсальным из разработанных ранее алгоритмов March G, их сложность в два раза меньше);

- получены оценки минимальной разрядности сигнатурных анализаторов, обеспечивающих 100%-е обнаружение заданных многократных неисправностей ОЗУ с ограничением по кратности;

• предложен аналитический метод определения порождающего полинома сигнатурного анализатора, обеспечивающего 100%-е обнаружение заданных многократных неисправностей ОЗУ;

- предложен алгоритм быстрого вычисления сигнатур одноканальных и многоканальных сигнатурных анализаторов для оценки достоверности тестирования ОЗУ.

Апробация результатов диссертации. Результаты диссертационной работы докладывались и обсуждались на IEEE European Design & Test Conference (Париж, Франция, 1996), на ШЕЕ VLSI Test Symposium (Принстон, США, 1996), на SEMICON Conference (Сеул, Южная Корея, 1996), на международном семинаре "Entwurf Integrierter Schaltungen" (Тубилген, Германия, 1993), на международной конференции "Автоматизация проектирования дискретных систем" (Минск, 1995), на конференции "Современные проблемы радиотехники, электроники и связи" (Минск, 1995), на научной конференции посвященной 30-летию деятельности коллектива БГУИР (Минск, 1994), на международной конференции "Информатика и вычислительная техника" (Кишинев, 1993), на 48-й научной сессии Российского научно-технического общества им. А.С.Попова, посвященной дню радио (Москва, 1993).

Публикации. По теме диссертации опубликовано 18 печатных работ, из них 1 статья в научном журнале, 6 статей в сборниках трудов конференций, 7 тезисов докладов конференции и 4 отчета по НИР.

Структура и объем диссертации. Диссертация изложена на 137 страницах машинописного текста,, содержит 25 рисунков, 21 таблицу и состоит из введения, чегырех глав, выводов, списка литературы, включающего 122 названия, и двух приложений.

СОДЕРЖАНИЕ РАБОТЫ

В первой главе дан краткий обзор литературы по исследуемой теме. Рассмотрены известные функциональные модели неисправностей, описывающие точечные дефекты в ОЗУ: БДР- константные неисправности, TF- переходные неисправности, AF - адресные неисправности, CFi„ -инверсные неисправности взаимного влияния, CFid - неинверспые неисправности взаимного влияния, SOF - неисправности, характеризуемые невозможностью доступа к ячейке памяти, DRF - неисправности, характеризуемые невозможностью удержания ячейкой памяти своего логического значения более некоторого периода времени (SOF и DRF характерны только для статических ОЗУ, CFi„ - только Для динамических ОЗУ). Отмечена тенденция повышения вероятности возникновения многократных неисправностей с увеличением степени интеграции современных ОЗУ.

Исследованы существующие методы встроенного тестирования ОЗУ. Показано, что наиболее перспективными являются методы, основанные на использовании маршевых алгоритмов тестирования как для реализации традиционного, так и неразрушагощего контроля ОЗУ (неразрушающий

контроль характеризуется сохранением содержимого тестируемых ячеек памяти). Проведенный анализ данных алгоритмов показывает, что они разрабатывались для обнаружения одиночных неисправностей ОЗУ. Обеспечение же обнаружения отдельных видов многократных неисправностей достигалось за счет расширения известных алгоритмов дополнительными операциями.

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

Во второй главе исследуются многократных неисправности ОЗУ. Выделены доминирующие виды неисправностей. Проведен анализ обнаруживающей способности известных маршевых алгоритмов тестирования ОЗУ относительно доминирующих видов неисправностей, результаты которого для динамических и статических ОЗУ приведены в таблицах 1 и 2 соответственно.

Таблица 1

Обнаруживающая способность маршевых алгоритмов тестирования ___динамических ОЗУ___

Название теста Сложность теста Обнаруживаемые неисправности

AF SAF TF С Fjn CFid TF-CF CFid-CFjd CFin-CFin CFid-CFin

MATS 4n •

MATS+ 5n • •

MATS++ 6n • * •

March X 6n • » • •

March Y 8n • • • • •

Marching 1/0 14n • • • • •

March С Un • • 9 • • •

March'C- i Jn • » • • • •

March A 15n • • • • • • .

March В 17n • • • • • • •

Alporilhm В 17n • * • • • • •

Таблица 2

Обнаруживающая способность маршевых алгоритмов тестирования

статических ОЗУ ___

Название теста Сложность теста Обнаруживаемые неисправности

AF SAF TF CFid SOF DRF TF-CF CFid-CFid DRF-CF

IFA-6 6n • • • •

March С-, Del 10n+2D • • • • •

I FA-9 12n+2D • • 0 • •

IFA-13 16n+2D • * • • • • •

March G 23n+2D • • • • • • • •

Результаты анализа свидетельствуют, что остается открытой проблема обнаружения многократных связных неисправностей ОЗУ. Под связными понимаются многократные неисправности, состоящие нз одиночных, оказывающих плияинс на поведение одной и т он ;кс ячейки памяти (и табл.1, 2 ТР-СР, СРи-СРи, 0!1Р-СР и т.д. обозначают многократные синшые нпинрапнопн, состоящие из одиночных неисправностей соотетпуюшпх видов). Для решения этой проблемы проводится исследование возможностей обнаружения наиболее сложных для тестирования видов связных неисправностей СРт-СИт, СРи-СРы, СРт-СРи маршевыми алгоритмами.

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

Утверждение I. Маршевый элемент, обнаруживающий связную неисправность, не содержащую СИщ заданного вида, позволяет обнаружить и любую аналогичную связную неисправность, содержащую четное число СР|П данного вида.

Утверждение 2. Маршевый элемент, обнаруживающий связную неисправность, содержащую одну одиночную С^п заданного вида, позволяет обнаружить и любую аналогичную связную неисправность, содержащую нечетное число данного вида.

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

Утверждение 1 позволяет выявить неисправности вида CFjn-CFin, которые не могут быть обнаружены ни одним маршевым алгоритмом.

Утверждение 3. Связные неисправности CFjn-CFjn не обнаруживаются ни одним маршевым алгоритмом, если они включают в себя только четное число (либо 0) CF,n каждого да 4-х видов.

Однако данные неисправности составляют лишь небольшую часть всего множества неисправностей CF;n-CFjn. Поэтому в табл.1 и в дальнейшем под CFjn-CFin понимаются только неисправности, не удовлетворяющие утверждению 3. В свою очередь множество CFjn-CFjn, подлежащих рассмотрению, на основании утверждений 1 и 2 может быть сведено к 15-и видам, в рамках которых неисправности эквивалентны с точки зрения их обнаружнваемости. Таким образом, для доказательства обиаружнваемости всех CFjn-CFjn (с учетом введенного ограничения) оказывается достаточным доказать обнаруживаемость 15-и неисправностей.

Результатом проведенных исследований явились предложения по модификации маршевых алгоритмов March A, March В и Algorithm В, позволяющие расширить их обнаруживающую способность и на класс CFjn-CFjn без увеличения сложности.

Исследования особенностей проявления С Fa позволили выявить эффективные сочетания маршевых элементов, обеспечивающие обнаружение всех связных CFa-CFy и CF.n-CFa.

Утверждение 4. Маршевый алгоритм тестирования ОЗУ, ■ включающий в себя маршевые элементы:

1)ft(rx,vvx,...,wx,...);%y,„.);

2) ff(rx,wx,...,wx,...); О (гу,...);

позволяет обнаружить всевозможные CF^-CF^ (ft, U, о - направления изменения адресации в маршевых элементах: соответственно от младших адресов к старшим, от старших адресов к младшим и безразличное направление движения; wO и wl - операции записи логических нуля и единицы в ячейку памяти; г0 и rl - операции чтения ячейки памяти с ожидаемым зна лшем нуля и единицы соответственно).

Утверждение 5: Маршевый алгоритм тестирования ОЗУ, включающий в себя маршевые элементы:

1) ft(rx,\vx ,wx); o(rx);

2) it(rx ,wx,wx);»(rx);

позволяет обнаружить всевозможные связные СР^-СРу и CF^-CF^.

На основании утверждения 5 разработан новый алгоритм тестирования, названный March М и имеющий вид:

<=> (wO); fl(rO,w!,wO); c>(rO); i!(rO,wl); ft(r!,\vQ,wi); <=>(rl); %I,wO). Данный алгоритм имеет более высокую обнаруживающую способность в сравнении с наиболее универсальными из известных маршевых алгоритмов тестирования динамических ОЗУ March В и Algorithm В (обеспечивает обнаружение всех неисправностей видов СР,П-СР[П и CFin-CFj^) при уменьшении в 1,3 раза временных затрат.

Алгоритм для обнаружения неисправностей статических ОЗУ разрабатывался на основании утверждению 4. Был?! проанализированы известные методы расширения маршевых алгоритмов для обнаружения DRF. Предложен новый, более эффективный метод расширения. Результатами исследований являются новые алгоритмы тестирования статических ОЗУ, названные March MS и March MS+, пыбор одного из которых должен осуществляться в зависимости от реализации усилителей считывания. March MS:

o(w0); ft(rO,wf,wO,wl); Del; <=>(ri); fl(rl.w0,wl,w0); Dei; c*(rO). March MS.+:

<t>(\vO); ff(rO,wi,wO,wl); Del; <=>(rl); ft(rf ,wO,rO,wt,wO); Del; <=>(r0.) Обнаруживающая способность данных алгоритмов равна обнаруживающей способности March G (наиболее универсального из известных маршевых алгоритмов тестирования статических ОЗУ), однако сложность их в 2 раза ниже.

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

Для многократных неисправностей ОЗУ справедливым является следующее утверждение.

Утверждение 6. Пусть S(<f| /2.....fr>) - сигнатура ошибки несвязной

5{г) =

многократной неисправности ОЗУ заданного вида Г^, ..., ^ и 5(<Г,>) -сигнатура соответствующей ошибки одиночной неисправности этого же вида Тогда

5(<Г|,Г2, Гг>) = Б(<Г,>) Ф 3{<Г2>) © ... ФБ(<ГГ>). (1)

Утверждение 6 и обобщенное условие тестируемости неисправностей, записанное в виде 5(<£>)*0 (где <Г>=éç - ошибка, генерируемая неисправностью) позволяют получить число различных сигнатур, генерацию которых должен обеспечивать искомый сигнатурный анализатор.

Теорема. Для обнаружения с" использованием сигнатурного анализа всех неисправностей ОЗУ в рамках выбранной модели до заданной кратности г сигнатурный анализатор должен обеспечивать возможность генерации .

г/2 • г

г=2Н={1,2,... }

1=0

(г-1 )/2

2 С'+С^2, г=2]-1,з={1,2,... }

¡=о

различных сигнатур, где п - емкость ОЗУ; С'п- число сочетаний по 1 элементов в множестве мощности п.

Результирующее выражение для определения нижней границы разрядности сигнатурного анализатора, обеспечивающего обнаружение 100% многократных неисправностей в рамках выбранной' модели до кратности г может быть записано следующим образом: г/2 .

1о§2(1С1п), г = 23,]= {1,2,... } 1=0

1°е2( I с'п+с(пг:11)/2), г = 23-и={и,... }

¡=о

где Шг - разрядность сигнатурного анализатора.

Для определения же порождающего полинома сигнатурного анализатора, обеспечивающего требуемую достоверность контроля, в работе предлагается новый метод - аналитический, в отличии от известных методов, основанных на макетировании либо программном моделировании. Метод основан на получении полиномов ошибок для рассматриваемых видов неисправностей в обобщенном виде (емкость ОЗУ и адрес ячейки памяти, в которой произошла неисправность, являются переменными параметрами) и использовании модели, описывающей процедуру сжатия информации при помощи сигнатурного анализатора как операцию деления полиномов над полем вР(2). Данная модель позволяет

п»г

применить теорию кодирования при анализе получением полиномов ошибок.

На основе предложенного метода определены порождающие полиномы сигнатурных анализаторов, обеспечивающих 100%-е обнаружение одно- и двукратных, и одно-, двух- и трехкратных константных неисправностей ОЗУ для маршевого теста March MS.

Утверждение 7. Одноканальный сигнатурный анализатор, задаваемый примитивным порождающим полиномом степени m=flog2(n+1)1+2 (где п - емкость ОЗУ) обеспечивает обнаружение всех одиночных и двукратных константных неисправностей ОЗУ при использовании алгоритма тестирования March MS.

Утверждение 8, Сигнатурный анализатор, задаваемый порождающим полиномом вида (х+1)Р (где Р - примитивный полином степени m=Tlog2(2n+l)T) обеспечивает обнаружение всех одиночных, двукратных и трехкратных константных неисправнотей ОЗУ при использовании маршевого алгоритма тестирования March MS и получении сигнатуры после маршевых элементов М2 и М4.

В диссертации рассмотрен процесс сжатия информации посредством многоканальных сигнатурных анализаторов (МСА). Показано, что в данных структурах имеется дополнительный источник снижения достоверности обнаружения ошибок, связанный с возможностью взаимокомпенсации искажений в различных каналах анализатора, ввиду чего предложенный метод не может быть для них применен. Рассмотрены многоканальные схемы сжатия данных, достоверность анализа информации посредством которых будет полностью соответствовать достоверности классических одноканальных сигнатурных анализаторов (ОСА) с внутренними сумматорами по модулю два и внешними сумматорами по модулю два. Функционирование данных схем может быть описано выражениями (3) и (4) соответственно:

Si+i=AkSi©D*, (3)

SI+i=AkSi©AkD*, (4)

где D* - матрица-столбец mxl, для которой первые к элементов равны соответствующим элементам вектора анализируемых данных, а остальные элементы равны 0; А - матрица, описывающая функцию получения очередного состояния анализатора для соответствующего ОСА; Ак -некоторая степень матрицы A; Ak=l |A|k-l| |А2И ... |А)Ч |lj| ] (А]! -первый столбец матрицы А', II - матрица-столбец mxl, первый элемент которой равен 1, а остальные равны 0). При проектировании рассмотренных схем, обеспечивающих 100%-е обнаружение неисправностей ОЗУ заданного вида с ограничением по кратности, для получения матрицы

А может быть применен предложенный аналитический метод. Получены матрицы, описывающие многоканальные схемы сжатия, для обеспечения 100%-го обнаружения одно- и двухкратных, и одно-, двух- и трехкратных константных неисправностей ОЗУ для маршевого теста March MS.

В четвертой главе предложен ЭВМ-ориентированный алгоритм быстрого вычисления сигнатур для определения достоверности тестирования ОЗУ с использованием сигнатурного анализа.

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

Наличие полученной таблицы позволяет свести задачу вычисления сигнатур неисправностей к нахождению суммы соответствующих значений из таблицы. Для получения оценки эффективности данного алгоритма по сравнению с программным моделированием предположим, что сложение по модулю два двух значений сигнатур из таблицы по трудоемкости равно получению значения сигнатурного анализатора при сжатии одного бита выходной последовательности (хотя реально второе требует больших временных затрат). Тогда коэффициент' эффективности алгоритма при вычислении сигнатур однократных неисправностей определяется

отношением F -m , где п - емкость ОЗУ, г - число операций чтения в [г/2]

маршевых элементах теста. Для ОЗУ емкостью 1Кбит это даст увеличение быстродействия в 2000 раз.

Разработаны модификации алгоритма быстрого вычисления сигнатур для многоканальных сигнатурных анализаторов. Для этого получены выражения вычисления сигнатур МСА на основе сигнатур ОСА, структуры обратных связей которых идентичны:

SMCA= IS>(Xj) = L('l«jVi*J"IS1(Xi)) (5)

¡=1 i=l j=0

s' MCA= IS,(Xi) = ¿(V'-'SjCXO) (6)

i=l i=l

где Smca - сигнатура MCA с внешними сумматорами по модулю два; S*mca - сигнатура МСА с внутренними сумматорами по модулю два; к - число выходов ОЗУ; Xj - последовательность, подаваемая на i-й вход МСА; Sj(X) -сигнатура последовательности X, подаваемой на i-й вход сигнатурного анализатора.

Оценки эффективности алгоритма по сравнению с программным

моделированием для случая вычисления сигнатур - однократных

гп

неисправностей определяются отношениями =-=--- и

[г/2]+ 2ik- 1)

f— - (г - число анализируемых выходов ОЗУ) для МСА с

I г / 2| + к - 1

внешними и внутренними сумматорами по модулю два соответственно.

На основе данного алгоритма разработаны программные средства определения достоверности сигнатурного анализа для заданной системы компактного тестирования на базе маршевых тестов. Результатами работы программы могут являться достоверность анализа, значение эталонной сигнатуры и сигнатур заданных неисправностей, а также список необнаруживаемых неисправностей. В качестве неисправностей рассматриваются константные неисправности ОЗУ, а алгоритм тестирования может быть выбран из следующего списка: MATS+, MATS++, March С-, March A, March В, March М, March MS.

Ряд полученных в рамках данной диссертационной работы результатов был использован на практике при разработке программно-аппаратного комплекса контроля и диагностики графического процессора. Разработанный комплекс предназначен для проверки работоспособности ТЭЗов графического процессора и локализации неисправностей с точностью до отказавшего элемента без участия специалистов (под управлением специализированного программного обеспечения).

ТЭЗы графического процессора содержат большое число микросхем статических ОЗУ, для проверки работоспособности которых использован алгоритм тестирования March MS. Для сокращения же числа точек снятия сигнатур при локализации неисправности были использованы программные средства на основе алгоритма быстрого вычисления сигнатур. С помощью данных средств вычисляются сигнатуры неисправностей в анализируемой точке схемы. Совпадение получаемой в точке сигнатуры с одной из сигнатур неисправностей приводит к быстрой дальнейшей локализации неисправности.

В состав разработанного комплекса входят управляющая ПЭВМ, графический процессор, диагностический контроллер с зондом сигнатурного анализатора и специализированное программное обеспечение. Контроллер диагностики функционально представляет собой программно-управляемый ОСА. Специализированное программное обеспечение выполняет пять основных функций:

- управление графическим процессором в режиме тестирования;

- управление работой контроллера диагностики;

- управление снятием эталонных сигнатур;

- управление действиями оператора в процессе выполнения процедуры диагностики и принятие решений по результатам проверки;

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

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

В приложении 1 приведены коды команд диагностики ГП и определяемые ими действия.

В приложении 2 приведены сведения о внедрении результатов работы на предприятиях.

ВЫВОДЫ

Основные результаты диссертационной работы можно сформулировать следующим образом:

1. Получены оценки обнаруживающей способности известных маршевых алгоритмов тестирования относительно многократных неисправностей, наиболее характерных для динамических и статических ОЗУ.

2. Сформулированы требования к маршевым алгоритмам тестирования ОЗУ, обеспечивающие обнаружение всех многократных неисправностей в рамках моделей, наиболее характерных для динамических ОЗУ. Предложен эффективный метод расширения маршевых алгоритмов для обнаружения неисправностей статических ОЗУ.

3. Разработаны новые маршевые алгоритмы тестирования ОЗУ. Алгоритм, названный March М, характеризуется наибольшей полнотой обнаружения многократных неисправностей среди известных маршевых алгоритмов тестирования динамических ОЗУ (обеспечивает 100%-е обнаружение многократных неисправностей в рамках моделей,' описывающих точечные дефекты матрицы накопителя ОЗУ). Алгоритмы, названные March MS и March MS+, являются наиболее эффективными из известных маршевых алгоритмов тестирования статических ОЗУ (при равной полноте обнаружения неисправностей с наиболее универсальным из разработанных ранее алгоритмов March G, их сложность в два раза ниже).

4. Получены оценки минимальной разрядности сигнатурных анализаторов, обеспечивающих 100%-е обнаружение заданных многократных неисправностей ОЗУ.

5. Предложен метод аналитического определения порождающего полинома сигнатурного анализаторов, обеспечивающего 100%-е обнаружение заданных многократных неисправностей ОЗУ. Определена конфигурация системы встроенного тестирования, обеспечивающая эффективное обнаружение многократных константных неисправностей ОЗУ.

6. , Разработан алгоритм быстрого вычисления сигнатур одноканальных и многоканальных сигнатурных анализаторов. Разработаны программные средства определения достоверности тестирования ОЗУ на базе данного алгоритма.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ярмолик В.Н., Микитюк В.Г. Новый эффективный алгоритм тестирования ОЗУ // Автоматика и вычислительная техника - 1996 - N1 -с.61-72.

2. Mikitjuk V.G., Yarmolik V.N., van de Goor A.J. RAM Testing Algorithms for Detection Multiple Linked Faults // Proc. IEEE European Design & Test Conf., March 1996, Paris, France, pp.435-440.

3. Van de Goor A.J., Gaydadjiev G.N., Yarmolik V.N., Mikitjuk V.O. March E: A More Efficient RAM Test with Higher Fault Coverage II Proc. IEEE VLSI Test Symposium - April 1996 - Princeton, New Jersey, USA, pp.272-230.

4. Van de Goor A.J., Gaydadjiev G.N., Yarmolik V.N., Mikitjuk V.G. Memory Tests and their Fault Coverage into a New Perspective, Resulting into a New Test // Proc. Semocon Conf. - January 1996 - Seul, Korea - pp.67-76.

5. Mikitjuk V.G., Yarmolik V.N. RAM Testing Algorithm for Detection Linked Coupling Faults // Computer-Aided Design of Discrete Devices - MinskSzczecin- 1995 - pp. 145-150.

6. Yarmolik V.N., Mikitjuk V.G. Aliasing Free Compactors for RAM BIST U Computer-Aided Design of Discrete Devices - Minsk-Szczecin - 1995 -pp.151-156.

• 7. Kachan I.V., Mikitjuk V.G., Strole A, Yarmolik V.N. Berechnung der Exakten Fehlererfassunng Beim Test Mit Signature analyse II Entwurf Integrierter Schaltungen - E.I.S.-Workshop, - November 25-26, 1993 -Universität Tubingen - pp.269-275.

8. Ярмолик B.H., Микитюк В.Г. Проектирование самотестируемых структур со 100% вероятностью обнаружения неисправностей различной кратности // Информатика и вычислительная техника: Тез. докл. конф. -Кишинев, 1993, с.117-120.

9. Микитюк В.Г. Автоматизация анализа сигнатурной тестируемости

регулярных структур // 48-я научная сессия РНТО им. А.С.Попова, посвященная дню радио: Тез. докл. конф. - Москва, 1993, с.139.

10. Микитюк В.Г., Ярмолик В.Н. Эффективный тест для обнаружения связных неисправностей ОЗУ // Автоматизация проектирования дискретных систем: Тез. докл. конф. - Минск 1995 - с.87.

11. Ярмолик В.Н., Микитюк В.Г. Схемы сжатия для самотестирумых ОЗУ со 100% обнаружением неисправностей // Автоматизация проектирования дискретных систем: Тез. докл. конф. - Минск 1995 - с.72.

12. Микитюк В.Г. Новый алгоритм тестирования ОЗУ II Современные проблемы радиотехники, электроники и связи: Тез. докл. конф. - Минск, 1995, с.318-319.

13. Быков Ю.В., Микитюк В.Г. Использование схем контроля четности для обнаружения неисправностей ОЗУ в процессе тестирования // Современные проблемы радиотехники, электроники и связи: Тез. докл. конф. - Минск, 1995, с.306.

14. Микитюк В.Г. Параметры сигнатурного анализатора для обеспечения 100% вероятности тестирования неисправностей // Научная конференция посвященная 30-летшо деятельности коллектива БГУИР: Тез. докл. - Минск, 1994, с.268.

15. Исследование проблем проектирования тестопригодных и самотестируемых архитектур: Отчет о НИР 93-8018 /Ярмолик В.Н., Меметов Г.Р., Микитюк В.Г. - N ГР 1994466. - Минск, 1993.

16. разработать методы и средства автоматизированного диагностирования БИС, СБИС и устройств на их основе, в том числе СБИС, реализующих методы граничного скашфования и архитектуры сканирования пути, а также модулей персональных ЭВМ: Отчет о НИР 938017 / Ярмолик В.Н., Быков Ю.В., Калоша Е.П., Микитюк В.Г. - N ГР 1993317.-Минск, 1993,

17. Исследование проблем проектирования тестопригодных и самотестируемых архитектур: Отчет о НИР 94-8018 /Ярмолик В.Н., Микитюк В.Г., Быков Ю.В., Мурашко И.А. - N ГР 19942791. - Минск, 1994.

18. Разработать методы и средства автоматизированного' диагностирования БИС, СБИС и устройств на их основе, в том числе СБИС, реализующих методы граничного сканирования и архитектуры сканирования пути, а также модулей персональных ЭВМ: Отчет о НИР 948017 / Ярмолик В.Н., Быков Ю.В., Микитюк В.Г., Мурашко И.А. - N ГР 19942790. - Минск, 1994.

РЭЗЮМЕ

Мшцюк Вячаслау Георпев1ч Метады i алгарытмы убудаванага тесщравання АЗП.

Юночавыя словы: саматэсщравання, маршавьщ алгарытмы тэсщравання АЗП, неразбураючы кантроль памящ, функщянальныя мадэл! няспраунасцей АЗП, мнагакратныя звязиые няспраунасщ, сннатурны анализ.

У дысертацыйнай рабоце даследуюцца метады убудаваиай праверм працаздольнасщ АЗП на аснове маршавых алгарытмау тэсщравання i агнатурнага анал1зу. Мэтай работы з'яуляецца распрацоука алгарытмау тэсщравання i метадау праектавання ашшзатарау выходных рэакцый, забяспечваючых эфектыунае выяуленне мнагакратных няспраунасцей АЗП.

Зроблен аналгз выяуляючай здольнасщ вядомых маршавых алгарытмау тэсщравання АЗП. Распрацованы новы алгарытм, названы March М, характарызуемы наибольшей паунатой выяулення мнагакратных няспраунасцей сярод вядомых маршавых алгарытмау тэицравання дьшамншых АЗП (забяспечвае 100% выяуленне мнагакратных няспраунасцей у рамках маделяу, ашсваючых кропкавыя дэфекты матрацы накапляльника). Прапанаваны алгарытмы, названыя March MS i March MS+, як1я з'яуляюцца найболей эфектыуным1 з вядомых маршавых алгарытмау тэсщравання статычных АЗП (пры аднолькавай паунаце выяулення няспраунасцей з найболей ушверсальным сярод распрацаваных раней алгарытмау March G ix складанасць у два раза шжэйшая). Атраманы ацени мйпмальнай разраднасщ i аналпычны мэтад вызначення параджаючых палшомау агнатурных анал1затарау, забяспечваючых 100% выяуленне зададзеных мнагакратных няспраунасцей АЗП. Распрацаваны алгарытм хуткага вьипчэпня сигнатур для auemci дакладнасщ тэсщравання АЗП.

Атрыманыя вышет могуць быць скарыстаны пры распрацоуцы схем, забяспечваючых эфектыунае убудаванае тэсщраванне сучасных АЗП.

РЕЗЮМЕ

Микитюк Вячеслав Георгиевич Методы и алгоритмы встроенного тестирования ОЗУ

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

В диссертационной работе исследуются методы встроенной проверки работоспособности ОЗУ на основе маршевых алгоритмов тестирования и сигнатурного анализа. Целью работы является разработка алгоритмов тестирования и методов проектирования анализаторов выходных реакций, обеспечивающих эффективное обнаружение многократных неисправностей ОЗУ.

Проведен анализ обнаруживающей способности известных маршевых алгоритмов тестирования ОЗУ. Разработан новый алгоритм, названный * March M, характеризуемый наибольшей полнотой обнаружения многократных неисправностей среди известных маршевых алгоритмов тестирования дииамических ОЗУ (обеспечивает 100%-е обнаружение многократных неисправностей в рамках моделей, описывающих точечные дефекты матрицы накопителя). Предложены алгоритмы, названные March MS и March MS+, являющиеся наиболее эффективными из известных маршевых алгоритмов тестирования статических ОЗУ (при равной полноте обнаружения неисправностей с наиболее универсальным из разработанных ранее алгоритмов March G их сложность в два раза ниже). Получены оценки минимальной разрядности и аналитический метод определения порождающих полиномов сигнатурных анализаторов, обеспечивающих 100%-е обнаружение заданных многократных неисправностей ОЗУ. Разработан алгоритм быстрого вычисления сигнатур для оценки достоверности тестирования ОЗУ.

Полученные результаты могут быть применены при разработке схем, обеспечивающих эффективное встроенное тестирование современных ОЗУ.

SUMMARY

Mikitjuk Vjacheslav Georgievich Methods and algorithms for RAM built-in self-testing.

Key words: self-testing, march algorithms for RAM testing, transparent memory testing, functional fault models, multiple Jinked faults, signature analysis.

In this dissertation we investigate the methods for RAM built-in self-testing on the base of march algorithms and signature analysis. The purpose of the work is to develop the algorithms of testing and the methods of output response compactors designing which allow to detect multiple RAM faults with high efficiency.

The analysis of the familiar march algorithms fault coverage is carried out. New algorithm March M which has the most coverage of RAM multiple faults among the existing march algorithms for DRAM is developed (it allows to detect 100% of faults within the scope of models which describe the spot defects of memory cell array). New algorithms March MS and March MS+ which are the most effective algorithms among the existing march algorithms for SRAM testing are proposed. They have the equal fault coverage with the most universal algorithm March G, but their complexity is twice as small. The estimations of minimal length and the analytical method to find the characteristic polynomials of signature analysers which allow to detect 100% of the given multiple RAM faults are proposed. It is developed the fast algorithm of signatures computation to estimate the aliasing probability for RAM testing.

Our results can be used to design the circuits which ensure effective built-in self-testing of modern RAMs.

микитюк

Вячеслав Георгиевич

МЕТОДЫ И АЛГОРИТМЫ ВСТРОЕННОГО ТЕСТИРОВАНИЯ ОЗУ

Специальность 05.13.05 Элементы и устройства вычислительной техники и систем управления

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 07. Юж_1996 г. Формат бумага 60x84 1/16. Усл. печ. л.1,2 8. Уч»-изд. л. 1,0, Заказ.499, Тираж 90 экз.

Отпечатано на ротапринте Белорусского государственного университета информатики и радиоэлектроники; 220027, Минск, ул. П.Бровки 6.