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

Нижегородский государственный технический университет

Разработка и исследование методов и алгоритмов построения тестов последовательностью схем на основе непрерывного подхода

Специальность 05.13.01 - «Системный анализ, управление и обработка информации»

АВТОРЕФЕРАТ

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

На правах рукописи

ДАНИЛОВ Сергей Олегович

Нижний Новгород 2004

Работа выполнена на кафедре «Информатика и системы управления» Нижегородского государственного технического университета (НГТУ)

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

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

кандидат технических наук, доцент Н. И. Кащеев

доктор технических наук, профессор К. Г. Кирьянов

кандидат технических наук, доцент С. Г. Мосин

Ведущая организация: Научно-исследовательский Центр

контроля и диагностики, Н. Новгород

Защита состоится «_»_2004 г. в_часов

на заседании диссертационного совета № Д.212.165.05

при Нижегородском государственном техническом университете по адресу: 603600, г. Нижний Новгород, ГСП-41, ул. Минина, 24, НГТУ.

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

Автореферат разослан «_»_2004 г.

Ученый секретарь

диссертационного совета .

кандидат технических наук А. П. Иванов

Актуальность работы

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

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

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

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

В настоящее время для тестирования последовательностных схем широко используются автоматические генераторы тестов, основанные на FAN-алгоритме. Автоматическая генерация тестов для константных неисправностей в комбинационных и последовательностных схемах была исследована многими учеными, и было опубликовано впечатляющее количество алгоритмов и моделей, в частности: Seshu и Freeman (1962 г.); Kubo (1968 г.); Putzolu и Roth (1971 г.); Пархоменко (1971 г.); Гольдман и Чипулис (1976 г.); Muth (1976 г.); Матросова (1977 г.); Marlett (1978 г.); Биргер (1978 г.); Goel (1981 г.); Гуляев и др. (1981 г.); Fujiwara и Shimono (1983 г.); Тоценко (1985 г.); Горяшко (1987 г.); Kirkland и Mercer (1987 г.); Cheng (1988 г.); Убар (1988 г.); Schulz и Auth (1989 г.); Cheng и Davidson (1989 г.); Матросова (1990 г.); Niermann и Patel (1991 г.); Larrabee (1992 г.); Lee и На (1993 г.); Kelsey и Saluja (1993 г.); Teramoto (1993 г.); Silva и Sakallah (1994 г.); Ривин И., Chakradhar S.T. (1994 г.); Евтушенко, Лебедев и Петренко (1994 г.); Glaser и Vierhaus (1995 г.), Гессель и Согомонян (1996 г.); Куфарева и др. (1998 г.); Куфарева (2000 г.).

РОС НАЦИОНАЛЬНА», МММТШ I

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

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

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

Цель работы

Целью работы является разработка и исследование эффективных методов построения тестов для синхронных последовательностных схем на основе непрерывного подхода к моделированию схемы.

На защиту выносятся:

1. Способ поиска тестов для синхронных последовательностных схем путем нахождения максимума непрерывной целевой функции.

2. Алгоритмы построения тестов, использующие методы непрерывной оптимизации.

3. Анализ эффективности разработанных методов и алгоритмов.

4. Программное обеспечение для исследований алгоритмов поиска тестов на основе непрерывного подхода.

5. Экспериментальные исследования различных методов поиска тестов на стандартном наборе тестовых схем формата International Symposium on Circuits and Systems (ISCAS)'89.

Методы исследования

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

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

Научная новизна работы состоит в следующем:

1. Разработан способ построения тестов синхронных последовательностных устройств на основе непрерывной оптимизации целевой функции.

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

Актуальность работы

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

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

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

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

В настоящее время для тестирования последовательностных схем широко используются автоматические генераторы тестов, основанные на FAN-алгоритме. Автоматическая генерация тестов для константных неисправностей в комбинационных и последовательностных схемах была исследована многими учеными, и было опубликовано впечатляющее количество алгоритмов и моделей, в частности: Seshu и Freeman (1962 г.); Kubo (1968 г.); Putzolu и Roth (1971 г.); Пархоменко (1971 г.); Гольдман и Чипулис (1976 г.); Muth (1976 г.); Матросова (1977 г.); Marlett (1978 г.); Биргер (1978 г.); Goel (1981 г.); Гуляев и др. (1981 г.); Fujiwara и Shimono (1983 г.); Тоценко (1985 г.); Горяшко (1987 г.); Kirkland и Mercer (1987 г.); Cheng (1988 г.); Убар (1988 г.); Schulz и Auth (1989 г.); Cheng и Davidson (1989 г.); Матросова (1990 г.); Niermann и Patel (1991 г.); Larrabee (1992 г.); Lee и На (1993 г.); Kelsey и Saluja (1993 г.); Teramoto (1993 г.); Silva и Sakallah (1994 г.); Ривин И., Chakradhar S.T. (1994 г.); Евтушенко, Лебедев и Петренко (1994 г.); Glaser и Vierhaus (1995 г.); Гессель и Согомонян (1996 г.); Куфарева и др. (1998 г.); Куфарева (2000 г.).

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

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

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

Цель работы

Целью работы является разработка и исследование эффективных методов построения тестов для синхронных последовательностных схем на основе непрерывного подхода к моделированию схемы.

На защиту выносятся:

1. Способ поиска тестов для синхронных последовательностных схем путем нахождения максимума непрерывной целевой функции.

2. Алгоритмы построения тестов, использующие методы непрерывной оптимизации.

3. Анализ эффективности разработанных методов и алгоритмов.

4. Программное обеспечение для исследований алгоритмов поиска тестов на основе непрерывного подхода.

5. Экспериментальные исследования различных методов поиска тестов на стандартном наборе тестовых схем формата International Symposium on Circuits and Systems (ISCAS)'89.

Методы исследования

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

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

Научная новизна работы состоит в следующем:

1. Разработан способ построения тестов синхронных последовательностных устройств на основе непрерывной оптимизации целевой функции.

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

3. Предложены быстродействующие и не требовательные к объему оперативной памяти алгоритмы обработки последовательностей схем, насчитывающих сотни входов и десятки тысяч вентилей.

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

Практическая ценность

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

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

2. Реализован алгоритм поиска тестовых последовательностей на основе повторного использования единственного временного кадра в памяти программы.

3. Получены численные характеристики эффективности каждого из разработанных алгоритмов.

4. Реализована программная платформа для исследования эффективности алгоритмов построения тестов на основе непрерывных методов оптимизации.

5. Построены тестовые последовательности для последовательностных схем из стандартного тестового набора схем ISCAS'89.

Апробация работы

Основные положения работы доложены и апробированы на 7 научных конференциях:

- на конференции «Информационные системы и технологии (ИСТ)-2002» (г. Нижний Новгород, НГТУ, Апрель 2002);

- на конференции «Информационные системы и технологии (ИСТ)-2003» (г. Нижний Новгород, НГТУ, Апрель 2003);

- на региональном молодежном научно-техническом форуме «Будущее технической науки нижегородского региона» (г. Нижний Новгород, 2002);

- на девятой нижегородской сессии молодых ученых (технические науки) (г. Нижний Новгород, 2004);

- на международной конференции «Informatics, Mathematical Modelling and Design in the Technics, Controlling and Education», (IMMD)'2004, (Vladimir city, May 2004);

- на конференции «Мехатроника, автоматизация, управление» (МАУ), (г. Владимир, Июнь 2004);

- на конференции East-West Design & Test Workshop (EDTW)'04, (Ялта, Алушта - Крым, Украина, Сентябрь 2004).

Публикации

По материалам диссертации опубликовано 10 научных работ, в том числе 4 статьи.

Структура и объем работы

Текст диссертации состоит из введения, четырех глав, заключения, библиографического списка и приложения, содержит 158 стр. машинописного текста, 50 рисунков, 5 таблиц, библиографию из 132 наименований.

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

Во введении рассматривается актуальность, цель и задачи исследований, научная новизна и практическая ценность результатов диссертационной работы, публикации, объем и структура диссертации.

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

Во второй главе рассматривается непрерывная модель для задач поиска тестовых последовательностей векторов.

Практически все современные методы генерации тестов основаны на дискретном подходе при обработке схемы. При этом уровни сигнала в схеме моделируются несколькими значениями. В простейшем случае это осуществляется с использованием трехзначной логики, в которой определены значения «0» для логического нуля, «1» для логической единицы и х для неопределенного или несущественного значения на линии. Такая логика имеет ряд недостатков. Дальнейшее развитие алгоритмов генерации тестов привело к возникновению 5-ти, 6-ти и 9-значной логики. При этом значения на каждой линии кодируются одним из нескольких значений. Существующие работы в этой области, использующие дискретный подход к задачам поиска тестов для логических схем, сводятся к разработке узкоспециализированных алгоритмов для построения тестов, основанные на эвристиках, свойствах логической импликации.

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

Раздел 2.1 приводит обобщенную структуру взаимодействия разработанных в рамках диссертации алгоритмов (см. рис. 1).

Рис. 1. Обобщенная структура взаимодействия разработанных алгоритмов

На рис. 1 темные прямоугольники содержат общеизвестные методы прямого поиска, а также файлы описания схем и неисправностей в формате ISCAS'89, которые были начальными данными для написания диссертации. Белыми блоками помечены алгоритмы, разработанные в диссертации.

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

Раздел 2.3 посвящен разработке алгоритмов первого, самого нижнего уровня в приведенной на рис. 1 иерархии алгоритмов. Такими алгоритмами являются алгоритмы представления разветвлений и преобразования триггеров задержки. Доказывается теорема об эквивалентном преобразовании исходной схемы во временной кадр.

В элементную базу описания схемы наряду со стандартными элементами «И», «НЕ», «ИЛИ» был добавлен фиктивный элемент «FAN», который служит для представления разветвлений в схеме. Значение с единственного входа данного элемента копируется на все его выходы.

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

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

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

Раздел 2.4 определяет используемую в работе модель неисправностей и дает определение тестовой последовательности векторов. Работа использует модель одиночных константных неисправностей.

В разделе 2.5 разрабатывается подход к поиску тестовых последовательностей путем поиска максимума построенной непрерывной целевой функции.

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

На рис. 2 изображена классическая структура сравнения эквивалентности двух схем - митер, здесь вверху - исправная копия тестируемой схемы, внизу -неисправная копия той же схемы. Значение неисправности подается на линию / схемы по дополнительному входу, имеющему константное значение

Рис. 2. Схема для организации поиска теста для неисправности 1/а

На рис. 2 каждая схема моделируется к= 3 временными кадрами. Выход й принимает значение, равное 1, тогда и только тогда, когда схемы имеют различные значения выходных линий при подаче определенной комбинации сигналов на входы

Для поиска тестов на основе непрерывного подхода необходимо:

- сформировать модель схемы на основе итеративного массива из заданного числа кадров;

- создать непрерывную модель, соответствующую построенному итеративному массиву;

- построить целевую функцию в соответствии с рис. 2;

- решить задачу максимизации целевой функции.

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

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

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

Непрерывным продолжением последовательностной схемы назовем итеративный массив из непрерывных продолжений временных кадров.

Возьмем за основу конъюнктивный базис Буля. В работе исследованы непрерывные продолжения функций алгебры логики, основанные на двух вариантах продолжений для отрицания: (1-х)/(1+х) и (1-х). Как было показано в работе, оба варианта дают неплохие результаты, позволившие алгоритму генератора тестов Алг.З (см. стр. 12) достичь 100% покрытия неисправностей.

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

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

Целевая функция для задачи поиска тестовых последовательностей векторов имеет вид:

—>тах.

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

Здесь п означает количество временных кадров, на пространстве которых ищется активизирующая последовательность для неисправности,

п1 и п2 — количество временных кадров, которые алгоритму необходимо добавить в начало и конец активизирующей последовательности соответственно, чтобы распространить эффект неисправности на первичные выходы схемы,

- количество первичных входов схемы,

- количество первичных выходов,

- число псевдопервичных входов схемы (равное числу псевдопервичных выходов схемы),

- значение на линии образованное во временном кадре после подачи

на первичные входы схемы векторов (разделенных синхросигналами),

— вектор значений псевдопервичных входов (вектор текущего состояния последовательностной схемы),

Д - значение неопределенного (неизвестного) сигнала на линии. Подразумевается, что временной кадр имеет р + к входов и 5 + /г выходов, первые р (й) из которых - первичные, последние тс - псевдопервичные.

Значения вектора в текущем временном кадре зависят от

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

схемы. Специальное условие, а именно, соу =Де(0,1),V/ = 1,ят, при / = 1, говорит о том, что в самом первом временном кадре значения на линиях псевдопервичных входов принадлежат отрезку (0,1), но они не известны (т.е. не известно

*/=1Ы1> к = 1>р>

со}= , ./ = 1, п,

А е (0,1), V; = 1 ,к, при г = 1,

= пРи ' > 1»

е {0,1} Хп1+и =Ху,

/' <п.

начальное состояние последовательностной схемы). При этом в разработанной программе для моделирования неизвестного значения Д было выбрано значение 'Л для большинства схем, поскольку именно это значение позволило получить лучшие результаты. Однако, как показали эксперименты, для некоторых схем значение х/г не позволяет достичь 100% покрытия неисправностей.

За активизацию неисправности отвечает первый множитель целевой функции, за распространение — второй множитель.

Теорема. Целевая функция О принимает свое максимальное значение, равное 1, тогда и только тогда, когда X является тестовой последовательностью векторов для тестирования неисправности

На рис. 3 приведены результаты прогонов разработанной программы. В качестве исходных данных для работы программного обеспечения использовались последовательностные схемы с числом элементов до тысячи, взятые из тестового набора схем ISCAS'89. Можно отметить, что при ограничении длины тестовой последовательности до 4 векторов покрытие неисправностей не превысит 60% для схемы s349, тогда как для последовательности длиной не больше 9 покрытие неисправностей составит все 100%.

! 100%

' 90%

! 60%

' 70%

! £ 60% Ь

[а, 50%

I I 40%

30% 20% | 10% 0%

Рис.3. Покрытие неисправностей при различных значениях максимальной длины тестовой последовательности

Данные на рис. 3 основаны на работе алгоритмов, подразумевающих, что значением неопределенного сигнала на линии является величина !4. Исключением является результат для схемы б713, для которой это значение неопределенного сигнала на линии не позволяет обнаружить 100% неисправностей, тогда как значение от 0,01 до 0,07 позволило достичь 100% результата в покрытии неисправностей.

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

Длина тестовой последовательности 1-Ф-827 -И-81238 -»-51196 -о-§349 -*-э344 -»-¡713 |

кадр, полученный из исходной схемы, будет иметь несколько сотен входов. Целевая функция, построенная из двух копий схемы (моделируемых к временными кадрами каждая) согласно рис. 2, будет содержать в 2*&раз больше элементов, чем в одном временном кадре. Целевая функция будет непрерывной функцией нескольких сотен переменных. На практике часто требуется построить от А=5 и более временных кадров для обеспечения того, чтобы неисправность могла быть активизирована и выведена на первичные выходы схемы. Это приводит к образованию целевой функции от нескольких тысяч переменных.

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

На основе алгоритма Алг. 1 разработан алгоритм Алг. 2 для поиска максимума целевой функции О на заданном числе временных кадров N = п1+п+п2. Если алгоритму Апг.2 не удается найти тестовую последовательность при моделировании 1 < к < N временных кадров, то алгоритм пытается продолжить поиск на множестве из А+1 кадров. Оценена трудоемкость выполнения алгоритма Алг.2: оценено общее количество временных кадров, которое будет обработано алгоритмом для худшего случая, когда не удалось найти тестовую последовательность векторов для тестирования неисправности 1/а.

Быстродействие алгоритма Алг.2 можно улучшить, сократив количество обрабатываемых временных кадров. В работе предложен алгоритм вычисления необходимого для построения теста числа временных кадров Кп> 1, позволяющий вести поиск тестовой последовательности в диапазоне значений К„<к<N. В работе оценена трудоемкость вычисления К„.

Поиск максимума целевой функции (поиск теста) в алгоритме Алг.2 ведется с использованием методов локальной оптимизации (см. главу 3) внутри и на границах единичного гиперкуба области определения.

Алгоритм генератора тестов Алг.З состоит в последовательном поиске теста алгоритмом Алг.2 для каждой неисправности из списка неисправностей, и включает в себя указанные исследователем алгоритмы, описанные в главе 4.

В третьей главе проводится анализ эффективности различных методов локальной оптимизации для задач поиска максимума целевой функции, осуществляемых алгоритмом Алг.2. Если алгоритмы локальной оптимизации находят локальный экстремум, то поиск продолжается с целью достичь глобального максимума. Поиска локальных экстремумов проводится с использованием методов Нелдера-Мида, Хука-Дживса, Розенброка, а также с помощью метода покоординатного подъема.

В качестве инструмента исследования используется программное обеспечение 8ЕСО]МТ, разработанное в рамках научного исследования по тематике диссертации, которое содержит около 8500 строк кода на языке С++.

Настройка алгоритмов осуществляется с помощью параметра который имеет следующий смысл: 12

- Для метода покоординатного подъема: размер шага алгоритма. При этом из текущей точки алгоритм будет делать пробные ходы в точки, полученные добавлением величины delta к каждой из координат поочередно.

- Для метода Нелдера-Мида: размер грани начального симплекса.

- Для метода Хука-Дживса: величина шага для исследующего поиска.

- Для метода Розенброка: начальный шаг алгоритма.

Алгоритмы начинают поиск из точки единичного £*р-мерного гиперкуба области определения целевой функции G с координатами, равными неопределенному сигналу на линии Д, где к - начальное число временных кадров, указанное алгоритмом Алг.2, р - количество первичных входов схемы.

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

Алгоритмы покоординатного подъема и Хука-Дживса, по сумме показателей, продемонстрированных на рассмотренных схемах из набора схем ISCAS'89, являются самыми эффективными алгоритмами поиска максимума непрерывной целевой функции из всех рассмотренных. Алгоритм Розенброка имеет несколько худшую эффективность, и заключает список алгоритм Нелде-ра-Мида, с помощью которого удалось найти тесты только для 70% неисправностей для протестированных схем.

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

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

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

ных неисправностей к общему числу тестируемых неисправностей) и, в целом, к более быстрой работе алгоритма.

Экспериментальные результаты показали, что алгоритм сортировки неисправностей для схемы sl 196 приводит к уменьшению количества вычислений целевой функции на 12,09 процента, при этом время работы алгоритма сокращается на 10%. Для схемы s349 количество вычислений целевой функции, напротив, возрастает на 3,45 - 15,26% и, как следствие, возрастает время работы алгоритма на 4,5 — 13%.

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

Раздел 4.3 исследует алгоритм «заморозки» схемы применительно к по-следовательностным схемам. Алгоритм хорошо исследован для комбинационных схем и дает при этом неплохие результаты, заключающиеся в значительном ускорении процесса поиска тестов.

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

На рис. 4 приведены экспериментальные испытания алгоритма заморозки на примере схемы sl196. Испытания проводились для различных значений начального шага алгоритма покоординатного подъема delta.

Схема 1196

' в 0.6 -1,11

| о 0,5 -0,5

0,4 -о,!

0,3 -1,0

0,2 -0,9

0,1 -1,0

0.9 -1,19 0,8 -1,21 0,7 -1,0!

4, 35

4 76

5, 23

5,63

>, 88

6,16

-2 -1 01234 567

... ............измен %

¡И изменение числа операций, % ■ изменение времени, % '

Рис. 4. Результаты работы алгоритма «заморозки» для схемы si 196

В результате экспериментальных испытаний количество элементов, не обрабатываемых алгоритмом, составило 0,98 - 1,21%, тогда как накладные расходы для вычисления таких элементов сказались на общем времени работы генератора тестов, увеличив его на 4,35 - 6,16%.

Раздел 4.4 представляет алгоритм анализа нетестируемых неисправностей. В последовательностной схеме могут присутствовать неисправности, которые не влияют на работу схемы, за счет избыточности схемы. Такие нетестируемые неисправности включены в общий список неисправностей для тестирования для каждой конкретной схемы формата КСЛ8'89. Заранее неизвестно, какие из неисправностей не являются тестируемыми. На протяжении 30 лет остро стоит проблема идентификации нетестируемых неисправностей. Алгоритмы генерации тестов наибольшее количество времени тратят на безуспешный поиск тестовой последовательности для нетестируемых неисправностей.

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

Для больших схем формата КСЛ8'89, таких, как схема 85378, имеющая 4111 элементов, включая 179 триггеров, и 4603 неисправности, предложенный алгоритм позволил сократить время работы генератора тестов в 1,682 раза. Ниже приведена сводная таблица тестовых экспериментов с использованием целого ряда схем. На рис. 5 видно, что применение предложенного алгоритма позволяет значительно сократить время работы генератора тестов, уменьшив количество вычислений целевой функции на величину порядка 10-50%.

»1196 >349 $1236 >208 1 >298 >510 >526

[□исходное количество вычислений и используя алгоритм [

Рис. 5. Влияние алгоритма анализа нетестируемых неисправностей на производительность генератора тестов

Полученные результаты позволяют говорить о высокой эффективности предложенного алгоритма.

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

Этот алгоритм моделирования неисправностей позволяет ускорить работу генератора тестов на 20 - 36% для разных схем. Эффективность алгоритма зависит от числа тестируемых неисправностей в схеме: чем их больше, тем больше времени экономится в результате процесса моделирования неисправностей.

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

Экспериментальные исследования показывают, что полное моделирование позволяет смоделировать в 1,17-1,42 раза больше неисправностей, по отношению к моделированию неисправностей на основе анализа очувствленного пути (см. рис. 6).

Моделирование: процент смоделированных неисправностей

90% 80% 70% 60% 50% 40% 30% 20% 10% 0%

827 $349 8713 81196 81238 I

¡■Моделирование ■ Полное моделирование □ Полное доопределяющее ! '

Рис. 6. Процент смоделированных неисправностей

Разработанный алгоритм моделирования с доопределением значений вводит две эвристики, связанные с процессом моделирования неисправностей.

Эвристика 1. В найденной тестовой последовательности векторов доопределить все несущественные значения значениями «0» и провести полное моделирование схемы на основе полученной последовательности векторов.

Эвристика 2. В найденной тестовой последовательности векторов доопределить все несущественные значения значениями «1» и провести полное моделирование схемы на основе полученной последовательности векторов.

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

На рис. 6 приведены результаты экспериментальных испытаний всех трех алгоритмов моделирования.

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

На втором этапе формируется минимальный список установочных последовательностей для последовательностной машины путем сокращения последовательностей, переводящих схему в одинаковые состояния.

На третьем этапе для каждой неисправности, для которой не получилось найти тест ранее, производится повторный поиск тестовой последовательности, причем схема предварительно переводится в известное состояние путем приложения установочной последовательности.

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

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

Раздел 4.8 Фантомные (мнимые) первичные входы. В процессе поиска тестовой последовательности векторов генератору приходится работать на переменном числе временных кадров. Дополнительные временные кадры для дальнейшего поиска решения могут потребоваться как в начале, так и в конце итеративного массива. При этом возникает проблема оптимальной реализации алгоритмов, реализующих адекватное изменение множества первичных входов. Чтобы минимизировать накладные расходы, связанные с изменением количест-

ва первичных входов в итеративном массиве, был предложен подход, названный алгоритмом «фантомных первичных входов».

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

Раздел 4.9 приводит исследование эффективности поиска тестов в двух случаях - при наличии и отсутствии полностью неопределенных значений в первом временном кадре.

В разделе 4.10 представлены результаты экспериментальных исследований влияния значения неопределенного сигнала на линии А на эффективность генератора тестов. Наиболее хорошие результаты по покрытию неисправностей, при прочих равных условиях, достигаются для значений из интервала 0,47 - 0,73 в качестве значения неопределенного сигнала на линии, поэтому выбор значения 0,5 можно считать правильным. Исключением является схема 8713. Максимальное покрытие для данной схемы алгоритм показывает для значений неопределенного сигнала на линии, равных 0,01 - 0,07.

В разделе 4.11 приведено сравнение алгоритма 8ЕСО№Г с существующими алгоритмами. В табл. 1 приведены результаты, которые получены разработанными в рамках диссертации непрерывными методами по сравнению с существующими дискретными методами.

Жирным шрифтом выделены результаты, соответствующие 100%-ной эффективности конкретного генератора тестов.

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

Как можно видеть, разработанный в рамках диссертации генератор тестов на основе непрерывного подхода, 8ЕСО№Г, сравним по эффективности с лучшими генераторами тестов, основанными на дискретном подходе.

В приложении приводятся грамматики для файлов описания схем и неисправностей в формате КСЛ8'89, а также приводится логическая схема одной из самых простых схем в формате КСЛ8'89. Приводится пример одиночной константной неисправности в этой схеме и указывается последовательность векторов для тестирования этой неисправности.

Эвристика 2. В найденной тестовой последовательности векторов доопределить все несущественные значения значениями «1» и провести полное моделирование схемы на основе полученной последовательности векторов.

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

На рис. 6 приведены результаты экспериментальных испытаний всех трех алгоритмов моделирования.

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

На втором этапе формируется минимальный список установочных последовательностей для последовательностной машины путем сокращения последовательностей, переводящих схему в одинаковые состояния.

На третьем этапе для каждой неисправности, для которой не получилось найти тест ранее, производится повторный поиск тестовой последовательности, причем схема предварительно переводится в известное состояние путем приложения установочной последовательности.

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

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

Раздел 4.8 Фантомные (мнимые) первичные входы. В процессе поиска тестовой последовательности векторов генератору приходится работать на переменном числе временных кадров. Дополнительные временные кадры для дальнейшего поиска решения могут потребоваться как в начале, так и в конце итеративного массива. При этом возникает проблема оптимальной реализации алгоритмов, реализующих адекватное изменение множества первичных входов. Чтобы минимизировать накладные расходы, связанные с изменением количест-

ва первичных входов в итеративном массиве, был предложен подход, названный алгоритмом «фантомных первичных входов».

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

Раздел 4.9 приводит исследование эффективности поиска тестов в двух случаях — при наличии и отсутствии полностью неопределенных значений в первом временном кадре.

В разделе 4.10 представлены результаты экспериментальных исследований влияния значения неопределенного сигнала на линии А на эффективность генератора тестов. Наиболее хорошие результаты по покрытию неисправностей, при прочих равных условиях, достигаются для значений из интервала 0,47 - 0,73 в качестве значения неопределенного сигнала на линии, поэтому выбор значения 0,5 можно считать правильным. Исключением является схема s713. Максимальное покрытие для данной схемы алгоритм показывает для значений неопределенного сигнала на линии, равных 0,01 - 0,07.

В разделе 4.11 приведено сравнение алгоритма SECONT с существующими алгоритмами. В табл. 1 приведены результаты, которые получены разработанными в рамках диссертации непрерывными методами по сравнению с существующими дискретными методами.

Жирным шрифтом выделены результаты, соответствующие 100%-ной эффективности конкретного генератора тестов.

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

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

В приложении приводятся грамматики для файлов описания схем и неисправностей в формате ISCAS'89, а также приводится логическая схема одной из самых простых схем в формате ISCAS'89. Приводится пример одиночной константной неисправности в этой схеме и указывается последовательность векторов для тестирования этой неисправности.

Таблица 1

Сравнение метода К1Х'(Ж1 с разными генераторами тестов

Схема

Неисправностей'

всего

в т.ч. тестируемы)«^

Метод SECONT

ТО(1)

TG(2)

ATOMS

GENT, EST }

H1TEC

SEMI LBT

s27

s208 1

s298

s344

s349

s420 1

s510

s713

s838 1

s953

si 196

S1238

s 1423

S9234

32

217

308

342

350

455

564

581

931

1079

1242

1355

1515

6927

32_

J8_

265 329 335

28_

0_

476

48_

89_

1239 1283 1498 18

32

18_

256 329 335

28_

0 -476 48«

89_

1239 1283 849 18_

32_

18_

265 329 335

28_

0_

476

48_

89_

1239 1283 474 18

262 314 310

476

87_

1239 1283 609 18

265 329 335

476

89_

1239 1283 1095

264 329 335

473

1239 1283

265 324 332

476

1239 1283

264 329 335

476

1239 1283

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

2. Предложены эффективные алгоритмы обработки модели схемы, алгоритмы моделирования неисправностей алгоритмы поиска тестов.

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

4. Разработанные алгоритмы и методы экспериментально апробированы на широко известном тестовом наборе схем КСА8'89. Эксперименты показали высокую эффективность предложенного подхода, сравнимую с лучшими классическими методами поиска тестов, основанными на дискретном подходе.

5. На ряде схем тестового набора КСА8'89 достигнуто 100%-ное покрытие множества тестируемых неисправностей, что говорит о практической ценности и применимости представленных в диссертации алгоритмов.

»25614

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Данилов СО. "Алгоритм генерации тестов последовательностей схем на основе непрерывной модели". // Тез. докл. научно-техн. форума «Будущее технической науки Нижегородского региона». — Н. Новгород, 2002. стр. 118-119.

2. Данилов СО. "Построение тестов последовательностей схем на основе непрерывного подхода". // Тез. докл. девятой нижегородской сессии молодых ученых. — Н. Новгород, 2004. стр. 10-11.

3. Данилов СО. "Транслятор для системы автономного тестирования". // Тез. докл. Всероссийской научно-техн. конф. «Информационные системы и технологии». — Н. Новгород, 2001. стр. 130-131.

4. Кащеев Н.И., Данилов СО. "Алгоритм поиска тестовых последовательностей для тестирования последовательностей схем". // Межвуз. сб. науч. тр. «Труды НГТУ: Системы обработки информации и управления». Том 35, выпуск 9. — Н. Новгород, 2002. стр. 79-81.

5. Кащеев Н.И., Данилов СО. "Использование методов непрерывной оптимизации для задач построения тестов последовательностных схем". -// Тез. докл. Всероссийской научно-техн. конф. «Информационные системы и технологии». — Н. Новгород, 2002. стр. 186-187.

6. Кащеев Н.И., Данилов СО. "Выбор оптимального числа временных кадров для поиска тестовой последовательности". // Межвуз. сб. науч. тр. «Труды НГ ТУ: Системы обработки информации и управления». -Том 37, выпуск 10, - Н. Новгород, 2003. стр. 103 - 105.

7. Кащеев Н.И., Данилов СО. "Модифицированный метод градиентного подъема". // Тез. докл. Всероссийской научно-техн. конф. «Информационные системы и технологии». — Н. Новгород, 2003. стр. 127-128.

8. Danilov S., Kasheev N. "Automatic test pattern generation using continuous approach" . // Proceedings of Internetional Scientific conf. «Informatics, Mathematical Modelling & Design in the technics, controlling & education (IMMD) '2004». — Vladimir city, VGU, 2004. pp. 187-192.

9. Данилов СО. "Непрерывный подход к построению тестов последовательностных схем" // Труды I Всеросс. научн.-техн. конф:. «Мехатроника, автоматизация, управление». — Москва, 2004. стр. 352355.

10.Kascheev N., Ryabkov Y., Danilov S. «Test generation for synchronous digital circuits based on continuous approach to circuit modeling» // Proceedings of conference "East-West Design & Test Workshop (EDTW04)". -Ялта, Алушта. Crimea, Ukraine, September 23 - 26,2004. стр. 161-165.

Подписано в печать 22.10.04. Формат 60 х 84 1/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Зак. 657.

Нижегородский государственный технический университет. Типография НГТУ. 603600, Нижний Новгород, ул. Минина, 24.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМЫ ГЕНЕРАЦИИ ТЕСТОВ ДЛЯ СИНХРОННЫХ ПОСЛЕДОВ ATE ЛЬНОСТНЫХ СХЕМ.

1.1. Виды неисправностей логических схем.

1.2. Существующие методы и алгоритмы тестирования последовательностных схем.

1.2.1. Функциональные подходы.

1.2.2. Эвристические методы.

1.2.3. Подходы, подразумевающие известное начальное состояние схемы.

1.2.4. Контролепригодный сканируемый дизайн схемы.

1.2.5. Методы высших уровней абстракции.

1.3. Сложность проблемы генерации тестов.

Выводы и постановка задачи.

ГЛАВА 2. РАЗРАБОТКА НЕПРЕРЫВНОГО ПОДХОДА К ТЕСТИРОВАНИЮ СИНХРОННЫХ ПОСЛЕДОВАТЕЛЬНОСТНЫХ СХЕМ.

2.1. Общая структура взаимодействия разработанных алгоритмов.

2.2. Необходимые определения.

2.3. Алгоритмы преобразования последовательностной схемы в итеративный логический массив.

2.4. Используемая в работе модель неисправностей.

2.5. Подход к поиску тестовых последовательностей путем поиска максимума построенной непрерывной целевой функции.

2.6. Непрерывная целевая функция для задачи поиска тестовой последовательности.

2.7. Сложность целевой функции.

Выводы.

ГЛАВА 3. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДОВ ЛОКАЛЬНОЙ ОПТИМИЗАЦИИ ПРИМЕНИТЕЛЬНО К ЗАДАЧАМ ПОИСКА ТЕСТОВ.

3.1. Объект и методы исследования.

3.2. Исследование алгоритмов на примере схемы s27.

3.3. Исследование алгоритмов на примере схемы s344.

3.4. Исследование алгоритмов на примере схемы si 196.

Выводы.

ГЛАВА 4. МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПОИСКА ТЕСТОВ.

4.1. Вычисление количества предваряющих и замыкающих временных кадров.

4.2. Сортировка неисправностей в списке.

4.3. «Заморозка» схемы.

4.4. Анализ нетестируемых неисправностей.

4.5. Алгоритмы моделирования неисправностей.

4.5.1. Моделирование неисправностей на очувствленном пути.

4.5.2. Полное моделирование неисправностей.

4.5.3. Моделирование с доопределением значений.

4.5.4. Адаптивное моделирование неисправностей.

4.6. Пакетное тестирование.

4.7. Адаптивное изменение величины начального шага.

4.8. Фантомные (мнимые) первичные входы.

4.9. Контроль первого вектора.

4.10. Исследование зависимости покрытия и быстродействия алгоритма от значения неопределенного сигнала на линии.

4.11. Сравнение алгоритма SECONT с существующими алгоритмами. 136 Выводы.

Актуальность работы

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

Практически невозможно устранить неисправность в уже изготовленной микросхеме. После того, как спецификация схемы поступила на завод по производству микросхем, требуется еще несколько недель [130], чтобы начать производство. Если ошибка обнаружена уже в произведенной микросхеме, требуется повторное проектирование и подготовка к производству. Это приводит к дополнительным затратам и временным задержкам, которые неприемлемы при заданном календарном плане и бюджете. Следовательно, значительная часть ресурсов при проектировании схемы должна быть занята проверкой правильности разработанной схемы.

Цель тестирования — удостовериться, что разработанная схема функционирует правильно и отвечает требованиям, заложенным разработчиком.

Учитывая, что тестирование играет ключевую роль в процессе производства микросхем (согласно [40], до 70% общих затрат на производство микросхемы расходуется на тестирование), оптимальная стратегия тестирования является насущной необходимостью. Поэтому не удивительно, что тестирование является ключевым компонентом значительной важности [85].

В настоящее время для тестирования последовательностных схем широко используются автоматические генераторы тестов, основанные на FAN-алгоритме [67][121]. Автоматическая генерация тестов для константных неисправностей в комбинационных и последовательностных схемах была исследована многими учеными, и было опубликовано впечатляющее количество алгоритмов и моделей, в частности: Seshu и Freeman (1962 г.) [124]; Kubo (1968 г.) [87]; Putzolu и Roth (1971 г.) [111]; Пархоменко (1971 г.) [31]; Гольдман и Чипулис (1976 г.) [20]; Muth (1976 г.) [99]; Матросова (1977 г.) [28]; Marlett (1978 г.) [95]; Биргер (1978 г.) [18]; Goel (1981 г.) [64]; Гуляев и др. (1981 г.) [23]; Fujiwara и Shimono (1983 г.) [60]; Тоценко (1985 г.) [33]; Горяшко (1987 г.) [21]; Kirkland и Mercer (1987 г.) [83]; Cheng (1988 г.) [51]; Убар (1988 г.) [34]; Schulz и Auth (1989 г.) [121]; Cheng и Davidson (1989 г.) [53]; Матросова (1990 г.) [29]; Niermann и Patel (1991 г.) [101]; Larrabee (1992 г.) [88]; Lee и На (1993 г.) [90]; Kelsey и Saluja (1993 г.) [82]; Teramoto (1993 г.) [131]; Silva и Sakallah (1994 г.) [125]; Ривин И., Chakradhar S.T. (1994 г.) [14]; Евтушенко, Лебедев и Петренко (1994 г.) [24]; Glaser и Vierhaus (1995 г.) [63]; Гессель и Согомонян (1996 г.) [18]; Куфарева и др. (1998 г.) [26]; Куфарева (2000 г.) [27].

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

Поскольку схемы содержат до миллионов логических элементов и линий соединения, тестирование схем в настоящее время является длительным и дорогостоящим процессом. Так как размер пространства поиска, внутри которого производится поиск тестовой последовательности векторов, растет экспоненциально от числа первичных входов и собственных состояний схемы, то проблема генерации тестов отнесена к классу NP-полных [79].

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

Цель работы

Целью работы является разработка и исследование эффективных методов построения тестов для синхронных последователыюстных схем на основе непрерывного подхода к моделированию схемы.

На защиту выносятся:

1. Способ поиска тестов для синхронных последовательностных схем путем нахождения максимума непрерывной целевой функции.

2. Алгоритмы построения тестов, использующие методы непрерывной оптимизации.

3. Анализ эффективности разработанных методов и алгоритмов.

4. Программное обеспечение для исследований алгоритмов поиска тестов на основе непрерывного подхода.

5. Экспериментальные исследования различных методов поиска тестов на стандартном наборе тестовых схем формата ISCAS'89 [47].

Методы исследования

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

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

Научная новизна работы состоит в следующем:

1. Разработан способ построения тестов синхронных последовательностных устройств на основе непрерывной оптимизации целевой функции.

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

3. Предложены быстродействующие и не требовательные к объему оперативной памяти алгоритмы обработки последовательностных схем, насчитывающих сотни входов и десятки тысяч вентилей.

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

Практическая ценность

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

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

2. Реализован алгоритм поиска тестовых последовательностей на основе повторного использования единственного временного кадра в памяти программы.

3. Получены численные характеристики эффективности каждого из разработанных алгоритмов.

4. Реализована программная платформа для исследования эффективности алгоритмов построения тестов на основе непрерывных методов оптимизации.

5. Построены тестовые последовательности для последовательностных схем из стандартного тестового набора схем ISCAS'89.

Апробация работы

Основные положения работы доложены и апробированы на 7 научных конференциях:

- На конференции «Информационные системы и технологии ИСТ-2002» (г. Нижний Новгород, НГТУ, Апрель 2002);

- На конференции «Информационные системы и технологии ИСТ-2003» (г. Нижний Новгород, НГТУ, Апрель 2003);

- На региональном молодежном научно-техническом форуме «Будущее технической науки нижегородского региона» (г. Нижний Новгород, 2002);

- На девятой нижегородской сессии молодых ученых (технические науки) (г. Нижний Новгород, 2004);

- На международной конференции «Informatics, Mathematical Modelling and Design in the Technics, Controlling and Education», (IMMD'2004, Vladimir city, May 2004);

- На конференции «Мехатроника, автоматизация, управление» (МАУ, г. Владимир, Июнь 2004);

- На конференции East-West Design & Test Workshop - EDTW'04, (Ялта, Алушта - Крым, Украина, Сентябрь 2004).

Публикации

Основное содержание работы отражено в 10 печатных работах [1] —

Структура и объем работы

Текст диссертации состоит из введения, четырех глав, заключения, библиографического списка и приложения, содержит 158 стр. машинописного текста, 50 рисунков, 5 таблиц, библиографию из 132 наименований.

Выводы

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

2. Предложен алгоритм сортировки неисправностей в схеме, эффективный для больших схем.

3. Экспериментально показано, что алгоритм «заморозки» схемы, эффективный для комбинационных схем, не эффективен для последовательностных схем.

4. Разработан эффективный эвристический алгоритм анализа нетестируемых неисправностей.

5. Представлены три алгоритма моделирования неисправностей, их экспериментальное сравнение на схемах тестового набора ISCAS'89, и показана их высокая эффективность.

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

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

8. Исследована зависимость эффективности генератора тестов от величины неопределенного значения на линии. Экспериментально показано, что значение 0.5 не всегда приводит к оптимальным результатам.

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

ЗАКЛЮЧЕНИЕ

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

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

2. Предложены эффективные алгоритмы обработки модели схемы, алгоритмы моделирования неисправностей алгоритмы поиска тестов.

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

4. Разработанные алгоритмы и методы экспериментально апробированы на широко известном тестовом наборе схем ISCAS'89. Эксперименты показали высокую эффективность предложенного подхода, сравнимую с лучшими классическими методами поиска тестов, основанными на дискретном подходе.

5. На ряде схем тестового набора ISCAS'89 достигнуто 100%-ное покрытие множества тестируемых неисправностей, что говорит о практической ценности и применимости представленных в диссертации алгоритмов.

1. ДАНИЛОВ С. О. "Алгоритм генерации тестов последовательностных схем на основе непрерывной модели". // Тез. докл. научно — техн. форума "Будущее технической науки Нижегородского региона". Н. Новгород, 2002. стр. 118-119.

2. ДАНИЛОВ С.О. "Построение тестов последовательностных схем на основе непрерывного подхода". // Тез. докл. девятой нижегородской сессии молодых ученых. Н. Новгород, 2004. стр. 10 - 11.

3. ДАНИЛОВ С.О. "Транслятор для системы автономного тестирования". // Тез. докл. Всероссийской научно — техн. конф. "Информационные системы и технологии". Н. Новгород, 2001. стр. 130-131.

4. ДАНИЛОВ С.О., КАЩЕЕВ Н.И. "Алгоритм поиска тестовых последовательностей для тестирования последовательностных схем". // Межвуз. сб. науч. тр. "Труды НГТУ: Системы обработки информации и управления". Том 35, выпуск 9. Н. Новгород, 2002. стр. 79-81.

5. ДАНИЛОВ С.О., КАЩЕЕВ Н.И. "Использование методов непрерывной оптимизации для задач построения тестов последовательностных схем". // Тез. докл. Всероссийской научно - техн. конф. "Информационные системы и технологии". — Н. Новгород, 2002. стр. 186 - 187.

6. ДАНИЛОВ С.О., КАЩЕЕВ Н.И. "Выбор оптимального числа временных кадров для поиска тестовой последовательности". // Межвуз. сб. науч. тр. "Труды НГТУ: Системы обработки информации и управления". — Том 37, выпуск 10, — Н. Новгород, 2003. стр. 103 105.

7. ДАНИЛОВ С.О., КАЩЕЕВ Н.И. "Модифицированный метод градиентного подъема". // Тез. докл. Всероссийской научно — техн. конф. "Информационные системы и технологии". Н. Новгород, 2003. стр. 127-128.

8. ДАНИЛОВ C.O. "Непрерывный подход к построению тестов последовательностных схем" // Труды I Всеросс. научн. — техн. конф. "Мехатроника, автоматизация, управление". — Москва, 2004. стр. 352-355.

9. МИНДРОВ A.E., КАЩЕЕВ Н.И., "Использование непрерывной модели схемы для генерации тестов", Simulation and CAD systems, pp. 47-50, 1989.

10. Техническая диагностика электронных схем". Сборник научных трудов, Киев, "Наукова думка", 1982.

11. БИРГЕР А.И. "Техническая диагностика". М.: Машиностроение, 1978.-238 с.

12. ГЕССЕЛЬ М., СОГОМОНЯН Е.С. "Построение кодоразделительных самопаритетных комбинационных схем для самотестирования и функционального диагностирования" // Автоматика и телемеханика, 1996 —№11.

13. ГОЛЬДМАН Р. С., ЧИПУЛИС В. П. "Техническая диагностика цифровых устройств", М., Энергия, 1976.

14. КНУТ Д. "Искусство программирования", Т. 1, "Основные алгоритмы", М., 2001.

15. КУФАРЕВА И.Б., ЕВТУШЕНКО Н.В., ПЕТРЕНКО А.Ф. "Синтез проверяющих тестов для недетерминированного автомата относительно редукции" // Автоматика и вычислительная техника. — 1998. -№ 3.

16. ПАРХОМЕНКО П. П. "Методы построения надежных систем из недостаточно надежных элементов", Семинар, Общество "Знание", Киев, 1969.

17. SAR reference manual", version 6, Trademark of Teradyne, Inc., Boston, MA, 1987.

18. ABRAMOVICI M., BREUER M. A., FRIEDMAN A. D., "Digital systems testing and testable design", Computer Science Press, 1990.

19. AGARWAL V. D., MERCER M. R., "Testability Measures what do they tell us?" Digest of papers 1982 International Test conference, pp. 391 -396, November 1982.

20. AGRAWAL V. D., CHENG К. Т., AGRAWAL P. "CONTEST: A Concurrent Test Generator for Sequential Circuits", Proc. 25th Design Automation Conf., pp. 84 89, 1988.

21. BARDELL P. H., MCANNEY W. H., SAVIR J. "Built in Pseudorandom Testing of Digital Circuits", John Wiley, 1987. BENNETTS R„ "Design of Testable Logic Circuits", Addison Wesley, 1984.

22. BHATTACHARYYA A. "On a novel approach of fault detection in an easily testable sequential machine with extra inputs and extra outputs", IEEE Trans, on Computers, Vol. С 32, No. 3, pp. 323 - 325, Mar. 1983.

23. BILLINGTON D. P. "Engineering in the Modern World: A Freshman Course in Engineering", Princeton University, IEEE Frontiers in Education Conference, 1993.

24. CARTER W. С., MONTGOMERY H. C., PREISS R. J., REINHEIMER H J. "Design of serviceability features of the IBM system/360", IBM Journal of R&D. 1964.

25. CHENG К. Т., AGRAWAL V. D. "A partial scan method for sequential circuits with feedback". IEEE Trans. Comput. 39, 4, 544 548. April 1990.

26. CHENG К. Т., AGRAWAL V. D. "Unified Methods for VLSI Simulation and Test Generation". Kluwer Academic, Norwell, MA. 1989.

27. CHENG W. T. "The BACK Algorithm for Sequential Test Generation", Prec. Int. Conf. Computer Design (ICCD 88), Rye Brook, NY, pp. 66 -69, October 1988.

28. CHENG W. T. "Split Circuit Model For Test Generation", AT&T

29. Engineering Research Center Princeton, NJ 08540, 1988

30. CHENG W. Т., DAVIDSON S. "Sequential circuit test generator (STG)benchmark results", ISCAS'89: IEEE International Symposium on

31. Circuits And Systems, Portland, OR (USA), pp. 1939- 1941, May 1989.

32. CHO H., JEONG S., SOMENZI F., PIXLEY C. "Synchronizingsequences and symbolic traversal techniques in test generation". J.

33. Electron. Testing, Theor. Appl. 4, 1, 19 -31. 1993.

34. DORF Richard C., "The Electrical Engineering Handbook", Boca Raton:1. CRC Press LLC, 2000.

35. FLETCHER R., POWELL M. J. D., "A rapidly convergent descent method for minimization", The Computer Journal, 6, pp. 163 168. 1963.

36. FRIEDMAN A. D., MENON P. "Restricted Checking Sequences for Sequential Machines", IEEE Trans, on Computers, Vol. С — 22, No. 4, pp. 397-399, Apr. 1973.

37. FUJIWARA H., KINOSHITA К. "Design of Diagnosable Sequential Machines Utilizing Extra Outputs", IEEE Trans, on Computers, Vol. С — 23, No. 2, pp. 138 145, Feb. 1974.

38. FUJIWARA H., NAGAO Y., SASAO Т., KINOSHITA K. "Easily Testable Sequential Machines with Extra inputs", IEEE Trans, on Comput., vol. С 24, pp. 821 - 826, Aug. 1975.

39. FUJIWARA H., SHIMONO T. "On the Acceleration of Test Generation Algorithms", Proc. 13th International Symposium on Fault — Tolerant Computing (FTCS 13), Milan, Italy, IEEE CS Press, pp. 98 - 105, June 28-30, 1983.

40. GLAESER U., VIERHAUS H. T. "FOGBUSTER: An efficient algorithm for sequential test generation". In Proceedings of the European Design Automation Conference (EURODAC' 95), IEEE Computer Society Press, 230-235. Sept. 1995.

41. GOEL P. "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits", IEEE Transactions on Computers, Vol. С 30, No. 3„ pp. 215 - 222, March 1981.

42. HAMZAOGLU I. "Test Pattern Generation And Test Application Time Reduction Algorithms For Vlsi Circuits", 1999.

43. HAMZAOGLU I., PATEL J. H. "Deterministic Test Pattern Generation Techniques for Sequential Circuits", University of Illinois, Urbana, IL, November 2000.

44. HSIAO M. S. "A Fast, Accurate, and Non statistical Method for Fault Coverage Estimation", Department of Electrical and Computer Engineering, Rutgers University, Piscataway, NJ. Inernational Conf. on Computer-Aided Design, pp. 155- 161. 1998.

45. ARRA О. H., SAHNI S. К. "Polynomially Complete Fault Detection Problems", IEEE Trans, on Computers, vol. С 24, pp. 242 - 249, March 1975.

46. KEIM M., BECKER В., STENNER B. "On the (non-)resettability of synchronous sequential circuits". In Proceedings of the IEEE VLSI Test Symposium, 240 245. April 1996.

47. KIRKLAND Т., MERCER M. R. "A topological search algorithm for ATPG". In Proceedings of the 24th ACM/IEEE Design Automation Conference, 502 508. June 1987.

48. KOHAVI I., LAVELLEE P. "Design of sequential machines with fault -tolerant capabilities", IEEE Trans, on Computers, Vol. EC 16, pp. 473 -484, Aug. 1967.

49. KUBO H. "A procedure for generating test sequences to detect sequential circuit failures", NEC Research 85 Development, No. 12, pp. 69-78, Oct. 1968.

50. RRABEE, T. "Test pattern generation using Boolean satisfability". IEEE Trans, on Сотр. Aided Design 11, pp. 4—15, January 1992.

51. LEE D. H., REDDY S. M. "A new test generation method for sequential circuits". In Proceedings of the IEEE International Conference on Computer Aided Design (ICCAD - 91), 446 - 449, Nov. 1991.

52. LEE H. К., HA D. S. "On the generation of test patterns for combinational circuits". Technical Report #12 — 93, Department of Electrical Engineering, Virginia Polytechnic Institute and State University. 1993.

53. LEE J., PATEL J. H. "A signal driven discrete relaxation technique for architectural level test generation". In Proceedings of the IEEE International Conference on Computer — Aided Design, 458 — 461. Nov. 1991.

54. LEE J., PATEL J. H. "Architectural level test generation for microprocessors". IEEE Trans. CAD, 13, 10, 1288 1300. Oct. 1994.

55. LOT H. Y., SU С. C. "A Distributive D Algorithm for Generating the Test Pattern for Faulty Combinational Circuit", Int. J. Electronics, vol. 66, no. l,pp. 35-42, 1989.

56. MARCHOK Т. E., EL MALEH A., MALY W., RAJSKI J. "Complexity of sequential ATPG". In Proceedings of the European Design and Test Conference, IEEE Computer Society Press, 252 — 261. March 1995.

57. MARLETT R. A. "EBT, a comprehensive test generation technique for highly sequential circuits", 15th Design Automation Conference, Las Vegas, USA, pp. 332 339, June 1978.

58. MARTIN R. L. "The design of diagnosable sequential machines", Proc. Hawaii Int'l Conf. Syst. Sci., 1968.

59. MICZO A. "Digital Logic Testing and Simulation", Harper and Row, New York. 1986.

60. MOORE E. F. "Gedanken — experiments on sequential machines", Automota Studies, Princeton University Press, pp. 129 153, Princeton, NJ 1965.г

61. MUTH P. "A nine valued circuits model for test generation", IEEE Transactions on Computers, Vol. С - 25, n. 6, pp. 630 - 636, June 1976.

62. NELDER J. A., MEAD R. "A simplex method for function minimization", The Computer Journal, 7, pp. 308 313. 1965.

63. NIERMANN Т., PATEL J. H. "HITEC: A Test Generation Package for Sequential Circuits", European Design Autom. Conf., pp. 214 218, 1991.

64. NIERMANN Т., PATEL J. H. "HITEC: A test generation package for sequential circuits". In Proceedings of the European Design Automation Conference, 214-218. Feb. 1991.

65. PATIL S., "Parallel algorithms for test generation and fault simulation", University of Illinois at Urbana Champaign, 1991.

66. PIXLEY C. "A computational theory and implementation of sequential hardware equivalence". In DIMACS Tech. Rep. 90-31. In Workshop on Computer Aided Verification, vol. 2. AMS, Providence, R. I. 293 — 320. 1990.

67. PIXLEY C., BEIHL G. "Calculating resettability and reset sequences". In Proceedings of the IEEE International Conference on Aided Design, 376-379. Nov. 1991.

68. POAGE J. F. MCCLUSKEY E. J. "Derivation of optimum Kst sequences for sequential machines", Proc. 5th Symp. on Switching Theory and Logical Design, 1964.

69. POMERANZ I., REDDY S. M., "Classification of Faults in Synchronous Sequential Circuits", IEEE Trans, on Computers, vol. 42, pp. 1066-1077, Sept. 1993.

70. PRADHAN D. K. "Sequential Network Design using Extra Inputs for Fault Detection", IEEE Trans, on Computers, Vol. С 32, No. 3, pp. 319 -323, March 1983.

71. PRATT V., "Anatomy of the Pentium Bug", Dept. of Computer Science, Stanford University, Stanford, CA, June 11, 1995.

72. PRINETTO P., REBAUDENGO M., REORDA M. S. "An automatic test pattern generator for large sequential circuits based on genetic algorithm". In Proceedings of the IEEE International Test Conference, 240-249. Oct. 1994.

73. PUTZOLU G. R., ROTH J. P. "A heuristic algorithm for the testing of asynchronous circuits", IEEE Transactions on Computers, vol С — 20, n. 6, pp. 639-647, June 1971.

74. PUTZOLU G. R., ROTH J. P. "A heuristic algorithm for the testing of asynchronous circuits". IEEE Trans. Comput. С — 20, 639 647, June 1971.

75. RHO J., SOMENZI F., PIXLEY C. "Minimum length synchronizing sequences of finite state machines". In Proceedings of the ACM/IEEE Design Automation Conference, 463 468. June 1993.

76. ROSENBROCK H. H. "An automatic method for finding the greatest or least value of a function", The Computer Journal, 3, pp. 175 — 184. 1960.

77. ROTH J. P. "Diagnosis of automata failures: A calculus and a method". IBM Journal, Res. Dev. 10, 278 291. July 1966.

78. RUDNICK E. M., HOLM J. G., SAAB D. G., PATEL J. H. "Application of simple genetic algorithms to sequential circuit test generation". In Proceedings of the European Design and Test Conference, 40 — 45. March 1994.

79. SAAB D. G., SAAB Y. G., ABRAHAM J. A. "CRIS: A test cultivation program for sequential VLSI circuits". In Proceedings of the IEEE International Conference on Computer Aided Design, 216 — 219. Nov. 1992.

80. SABNANI K., DAHBURA A. "A protocol test generation procedure". Comput. Netw. 15, 285 297. April 1988.

81. SALUJA К. K., DANDAPANI R. "Testable design for single output sequential machines using checking experiments", IEEE Trans, on Сотр. Vol. С - 35, No. 7, pp. 658 - 662, July 1986.

82. SANGIOVANNI VINCENTELLI A., MA H. К. Т., DEVADAS S., NEWTON A. R., "Test generation for sequential circuit". IEEE Trans. Comput. Aided Des., 1081 - 1093. Oct. 1988.

83. SCHULZ M. H., AUTH E. "ESSENTIAL: An efficient self learning test pattern generation algorithm for sequential circuits". In Proceedings of the International Test Conference, 28 - 37. Aug. 1989.

84. SCHULZ M. H., TRISCHLER E., SARFERT Т. M. "SOCRATES: A highly efficient automatic test pattern generation system". IEEE Trans. CAD, 126-137. Jan. 1988.

85. SESHU S. "On an improved diagnosis program". IEEE Trans. Electron. Comput. EC 14, 2, 76 - 79. Feb. 1965.

86. SESHU S., FREEMAN D. N. "The diagnosis of asynchronous sequential switching systems", IRE Trans. Electron. Comput, vol. EC —11, pp. 459 — 465, Aug. 1962.

87. SILVA J. P. M., SAKALLAH K. A. "Dynamic search space pruning techniques in path sensitization". In Proc. of Design Automation Conf. pp. 705-711. 1994.

88. SNETHEN T. J. "Simulator oriented fault test generator". In Proceedings of the 14th ACM/IEEE Design Automation Conference, 88 -93. June 1977.

89. SO B. "Time Efficient Automatic Test Pattern Generation Systems", Ph. D. thesis, University Of Wisconsin — Madison, 1994.

90. SPENDLEY W., HEXT G. R., HIMSWORTH F. R. "Sequential application of simplex designs in optimisation and evolutionary operation", Technometrics, 4, pp. 441 461. 1962.

91. SRIVAS M. K., STEVEN P. M., "Applying Formal Verification to a Commercial Microprocessor", Computer Science Laboratory SRI International, Menlo Park, CA 94025 USA, 1994.

92. STOFFEL D., "Formal Verification of Sequential Circuits Using Reasoning Techniques", University'at Frankfurt at Main, 1999.

93. TERAMOTO M. "A method for reducing the search space in test pattern generation". In Proc. of Int. Test Conf. 429 435. 1993.

94. VENKARTRAMAN C. S., SALUJA К. K. "Transition count testing of sequential machines", Dig. 10th Symp. Fault Tolerant Comput., pp. 167 172, Kyoto, Japan, Oct. 1980.9V 9-valued, 9-ти-значная логика.

95. DAC Design and Automation Conference, Конференция поразработке и автоматизации.

96. DFF D flip-flop, D-триггер.

97. ЕВТ Extended Back Trace, алгоритм расширенной трассировки вобратном направлении.

98. FAN Fanout-Oriented Test Generation, алгоритм генерации тестов,ориентированный на обработку разветвлений.1С Integrated circuit, интегральная схема.

99. CAS International Symposium on Circuits and Systems,международный симпозиум по схемам и системам.

100. C International Test Conference, международная конференцияпо тестированию.

101. NP Nondeterministic polynomial time, недетерминированный вполиномиальное время.

102. PI Primary input, первичный вход.

103. РО Primary output, первичный выход.

104. PODEM Path oriented decision making, алгоритм принятия решений на основе анализа путей.

105. PPI Pseudo primary input, псевдопервичный вход.

106. РРО Pseudo primary output, псевдопервичный выход.

107. RTP Reverse time processing, обработка времени в обратномпорядке следования времени.

108. SCOAP Sandia controllability/observability analysis program, программа анализа контролируемости и наблюдаемости, разработанная в институте Sandia.

109. SECONT Sequential Test Generator based on Continuous approach, последовательностный генератор тестов, основанный на непрерывном подходе.

110. SOCRATES Structure-Oriented, Cost-Reducing Automatic test pattern generation system, структурированная, оптимизирующая система автоматической генерации тестов.

111. SOFTG Simulator-Oriented Fault Test Generator, генератор тестов для неисправностей, основанный на моделировании.

112. НГТУ Нижегородский Государственный Технический1. Университет.

113. ОКН Модель одиночных константных неисправностей.