Введение к работе
Актуальность работы
Сложность цифровых схем определяется не только все увеличивающимся числом логических элементов в микросхемах, но также и возрастающей плотностью интеграции микросхем. Разработка конкурентоспособных электронных схем сегодня практически невозможна без использования автоматизированных средств разработки. Такие инструменты позволяют сократить срок разработки нового изделия. В связи с этим, разработчики микросхем вынуждены применять средства высокоуровневого синтеза микросхем, эмуляторы, автоматизированные средства построения тестов для того, чтобы спроектировать схему, удовлетворяющую заданным требованиям и в заданные сроки.
Практически невозможно устранить неисправность в уже изготовленной микросхеме. После того, как спецификация схемы поступила на завод по производству микросхем, требуется еще несколько недель, чтобы начать производство. Если ошибка обнаружена уже в произведенной микросхеме, требуется повторное проектирование и подготовка к производству. Это приводит к дополнительным затратам и временным задержкам, которые неприемлемы при заданном календарном плане и бюджете. Следовательно, значительная часть ресурсов при проектировании схемы должна быть занята проверкой правильности разработанной схемы.
Цель тестирования - удостовериться, что разработанная схема функционирует правильно и отвечает требованиям, заложенным разработчиком.
Учитывая, что тестирование играет ключевую роль в процессе производства микросхем (около 70% общих затрат на производство микросхемы расходуется на тестирование), оптимальная стратегия тестирования является насущной необходимостью. Поэтому не удивительно, что тестирование является ключевым компонентом значительной важности.
В настоящее время для тестирования последовательностных схем широко используются автоматические генераторы тестов, основанные на EAN-алгоритме. Автоматическая генерация тестов для константных неисправностей в комбинационных и последовательностных схемах была исследована многими учеными, и было опубликовано впечатляющее количество алгоритмов и моделей, в частности: 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 и Aiith (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 г.).
racMAiuKHMjuiiwi 3
ммиотем |
Однако тестирование больших схем требует большего количества тестов, они достаточно сложны для эффективного тестирования. Быстродействующие микросхемы не всегда могут быть протестированы с использованием имеющихся средств.
Поскольку схемы содержат до миллионов логических элементов и линий соединения, тестирование схем в настоящее время является длительным и дорогостоящим процессом. Так как размер пространства поиска, внутри которого производится поиск тестовой последовательности векторов, растет экспоненциально от числа первичных входов и собственных состояний схемы, то проблема генерации тестов отнесена к классу NP-полных.
Поэтому разработка новых, эффективных средств и методов для тестирования цифровых схем является актуальной проблемой в области технической диагностики.
Цель работы
Целью работы является разработка и исследование эффективных методов построения тестов для синхронных последовательностных схем на основе непрерывного подхода к моделированию схемы.
На защиту выносятся:
Способ поиска тестов для синхронных последовательностных схем путем нахождения максимума непрерывной целевой функции.
Алгоритмы построения тестов, использующие методы непрерывной оптимизации.
Анализ эффективности разработанных методов и алгоритмов.
Программное обеспечение для исследований алгоритмов поиска тестов на основе непрерывного подхода.
Экспериментальные исследования различных методов поиска тестов на стандартном наборе тестовых схем формата International Symposium on Circuits and Systems (ISCAS)'89.
Методы исследования
Работа базируется на методах технической диагностики, теории построения проверяющих тестов, теории графов, теории конечных автоматов, булевой алгебры, методах прямого поиска экстремума функции.
Научная новизна
Научная новизна работы состоит в следующем:
Разработан способ построения тестов синхронных последовательностных устройств на основе непрерывной оптимизации целевой функции.
Разработаны высокоэффективные алгоритмы моделирования схемы непрерывными функциями, позволившие значительно сократить время поиска тестовых последовательностей.
Актуальность работы
Сложность цифровых схем определяется не только все увеличивающимся числом логических элементов в микросхемах, но также и возрастающей плотностью интеграции микросхем. Разработка конкурентоспособных электронных схем сегодня практически невозможна без использования автоматизированных средств разработки. Такие инструменты позволяют сократить срок разработки нового изделия. В связи с этим, разработчики микросхем вынуждены применять средства высокоуровневого синтеза микросхем, эмуляторы, автоматизированные средства построения тестов для того, чтобы спроектировать схему, удовлетворяющую заданным требованиям и в заданные сроки.
Практически невозможно устранить неисправность в уже изготовленной микросхеме. После того, как спецификация схемы поступила на завод по производству микросхем, требуется еще несколько недель, чтобы начать производство. Если ошибка обнаружена уже в произведенной микросхеме, требуется повторное проектирование и подготовка к производству. Это приводит к дополнительным затратам и временным задержкам, которые неприемлемы при заданном календарном плане и бюджете. Следовательно, значительная часть ресурсов при проектировании схемы должна быть занята проверкой правильности разработанной схемы.
Цель тестирования - удостовериться, что разработанная схема функционирует правильно и отвечает требованиям, заложенным разработчиком.
Учитывая, что тестирование играет ключевую роль в процессе производства микросхем (около 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 и Aiith (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-полных.
Поэтому разработка новых, эффективных средств и методов для тестирования цифровых схем является актуальной проблемой в области технической диагностики.
Цель работы
Целью работы является разработка и исследование эффективных методов построения тестов для синхронных последовательностных схем на основе непрерывного подхода к моделированию схемы.
На защиту выносятся:
Способ поиска тестов для синхронных последовательностных схем путем нахождения максимума непрерывной целевой функции.
Алгоритмы построения тестов, использующие методы непрерывной оптимизации.
Анализ эффективности разработанных методов и алгоритмов.
Программное обеспечение для исследований алгоритмов поиска тестов на основе непрерывного подхода.
Экспериментальные исследования различных методов поиска тестов на стандартном наборе тестовых схем формата International Symposium on Circuits and Systems (ISCAS)'89.
Методы исследования
Работа базируется на методах технической диагностики, теории построения проверяющих тестов, теории графов, теории конечных автоматов, булевой алгебры, методах прямого поиска экстремума функции.
Научная новизна
Научная новизна работы состоит в следующем:
Разработан способ построения тестов синхронных последовательностных устройств на основе непрерывной оптимизации целевой функции.
Разработаны высокоэффективные алгоритмы моделирования схемы непрерывными функциями, позволившие значительно сократить время поиска тестовых последовательностей.
Предложены быстродействующие и не требовательные к объему оперативной памяти алгоритмы обработки последовательностных схем, насчитывающих сотни входов и десятки тысяч вентилей.
Разработан подход и соответствующие алгоритмы, обеспечивающий возможность применения широкого спектра методов локальной и глобальной оптимизации к задачам поиска тестов.
Практическая ценность
На базе разработанных алгоритмов и методов, используя написанное в рамках диссертации программное обеспечение, решены следующие прикладные задачи:
Разработаны алгоритмы преобразования исходной логической последова-тельностной схемы в итеративный массив из временных кадров, включающие в себя: алгоритм представления разветвлений, алгоритм преобразования триггеров и топологическую сортировку вентилей.
Реализован алгоритм поиска тестовых последовательностей на основе повторного использования единственного временного кадра в памяти программы.
Получены численные характеристики эффективности каждого из разработанных алгоритмов.
Реализована программная платформа для исследования эффективности алгоритмов построения тестов на основе непрерывных методов оптимизации.
Построены тестовые последовательности для последовательностных схем из стандартного тестового набора схем 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 наименований.
