Методы синтеза тестов для цифровых синхронных схем на основе реконфигурируемых аппаратных средств
Покупка
Основная коллекция
Тематика:
Аппаратное обеспечение
Издательство:
НИЦ ИНФРА-М
Автор:
Борисевич Алексей Валерьевич
Год издания: 2008
Кол-во страниц: 210
Дополнительно
Вид издания:
Диссертации и авторефераты
Уровень образования:
ВО - Магистратура
Артикул: 620024.01.99
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Магистратура
- 09.04.01: Информатика и вычислительная техника
- 09.04.02: Информационные системы и технологии
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
СЕВАСТОПОЛЬСКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ На правах рукописи БОРИСЕВИЧ АЛЕКСЕЙ ВАЛЕРЬЕВИЧ УДК 681.518.54 МЕТОДЫ СИНТЕЗА ТЕСТОВ ДЛЯ ЦИФРОВЫХ СИНХРОННЫХ СХЕМ НА ОСНОВЕ РЕКОНФИГУРИРУЕМЫХ АППАРАТНЫХ СРЕДСТВ 05.13.05 – Компьютерные системы и компоненты ДИССЕРТАЦИЯ на соискание научной степени кандидата технических наук Научный руководитель Скатков Александр Владимирович, доктор технических наук, профессор СЕВАСТОПОЛЬ – 2008
СОДЕРЖАНИЕ ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ 5 ВВЕДЕНИЕ 7 РАЗДЕЛ 1. Обзор методов построения тестовых последовательностей для цифровых синхронных схем с памятью и выбор перспективных направлений их совершенствования 13 1.1 Цифровая синхронная схема как объект диагностики 13 1.2 Модели неисправностей 15 1.3 Краткий обзор классических методов построения тестов для цифровых схем 18 1.4 Вычислительная сложность алгоритмов синтеза теста 24 1.5 Критерии эффективности и показатели совершенствования методов синте за тестов 24 1.6 Методы построения тестов на основе эволюционных алгоритмов 26 1.7 Аппаратная реализация алгоритмов как методология ускорения вычисле ний 35 1.8 Проблемы и перспективы применения эволюционных методов в задачах построения тестов 39 1.9 Цели и задачи исследования 40 РАЗДЕЛ 2. Совершенствование эволюционных методов синтеза тестов на ос нове декомпозиции и символьного анализа 42 2.1 Эволюционный метод синтеза тестов на основе декомпозиции и символь ного анализа 42 2.2 Декомпозиция тестируемой схемы и символьное представление подсхем 44 2.3 Алгоритм вычисления тестов для подсхем 48 2.4 Алгоритм построения проверяющего теста для комбинационных схем с учетом декомпозиции на основе топологически-оринтированного перебора тестовых наборов 51 2.5 Оценка эффективности применения декомпозиции 57
2.6 Генетико-символьный алгоритм построения проверяющего теста с учетом декомпозиции схемы 60 2.7 Алгоритм синтеза диагностического теста 68 2.8 Экспериментальное исследование генетического алгоритма 70 2.9 Иллюстративный пример применения генетико-символьного метода син теза теста 75 2.10 Выводы по разделу 79 РАЗДЕЛ 3. Эволюционный метод синтеза тестов с использованием аппарат ного ускорения 82 3.1 Необходимость и эффективность аппаратного ускорения 82 3.2 Оценивание длины тестовых последовательностей синхронных схем 87 3.3 Аппаратно-ориентированный метод синтеза тестов для синхронных схем 100 3.4 Синтез теста цифровой схемы с памятью как задача скалярной оптимиза ции 103 3.5 Выбор оптимизационного алгоритма 114 3.6 Вероятностная модель и анализ сходимости эволюционного алгоритма 116 3.7 Выводы по разделу 128 РАЗДЕЛ 4. Аппаратные средства ускорения вычислений при синтезе тестов схем эволюционными методами 129 4.1 Совместная аппаратная реализация оптимизационного алгоритма и систе мы моделирования неисправности 129 4.2 Параллельная аппаратная реализация оптимизационного алгоритма 130 4.3 Оптимальная последовательно-параллельная аппаратная реализация 131 4.4 Аппаратная реализация алгоритма оптимизации с применением селекции 136 4.5 Выбор генератора псевдослучайных чисел 138 4.6 Экспериментальные результаты решения задачи скалярной оптимизации с помощью предложенного аппаратного средства 141 4.7 Аппаратная реализация вычислителя целевой функции 142 4.8 Выводы по разделу 151 РАЗДЕЛ 5. Апробация результатов исследования на международной библио- 153
теке последовательностных схем ISCAS-89 5.1 Программа экспериментов по апробации предложенных методов 153 5.2 Состав и структура экспериментальных аппаратных средств 155 5.3 Состав и структура программного обеспечения 159 5.4 Результаты и анализ применения смешанного генетико-символьного ме тода на схемах библиотеки ISCAS-89 162 5.5 Результаты и анализ применения совместной аппаратной реализации гене тического алгоритма и подсистемы моделирования для схем библиотеки ISCAS-89 166 5.6 Сравнительный анализ применения предложенных методов 168 5.7 Сравнение временных преимуществ и аппаратных затрат 171 5.8 Выводы по разделу 173 ВЫВОДЫ 175 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 178 ПРИЛОЖЕНИЕ А. Численные результаты по апробированию методов 191 A.1 Характеристики схем библиотеки ISCAS 191 A.2 Результаты применения смешанного генетико-символьного метода на схемах библиотеки ISCAS-89 192 A.3 Результаты применения совместной аппаратной реализации генетическо го алгоритма и подсистемы моделирования для схем библиотеки ISCAS-89 194 A.4 Сложность аппаратной системы синтеза тестов 196 ПРИЛОЖЕНИЕ Б. Вспомогательные алгоритмы методов синтеза теста 198 Б.1 Алгоритмы символьного представления булевых функций 198 Б.2 Транслятор с входного языка описания структуры схемы 205 ПРИЛОЖЕНИЕ В. Результаты логического моделирования для верификации тестов схемы s344 библиотеки ISCAS-89 210 ПРИЛОЖЕНИЕ Г. Акты внедрения 225
ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ S – тестируемая схема как множество элементов, – вектор-функция переходов автомата, – вектор-функция выходов автомата, X – множество входных сигналов схемы, Y – множество выходных сигналов схемы, ( ) W t – множество сигналов состояния схемы, ( 1) W t – множество входных сигналов регистра состояния схемы, n – число входов схемы, | | n X , m – число выходов схемы, | | m Y , q – число сигналов состояния (элементов памяти) схемы, | |, q W i E – логический элемент схемы, @ S – итеративный массив комбинационных схем тестируемой схемы, j – фрагмент тестируемой схемы (подсхема) – множество входов подсхемы, k – вход подсхемы как управляемый сигнал схемы, – тестовая последовательность, l – длина тестовой последовательности, – множество тестовых последовательностей, – множество неисправностей схемы, K – число неисправностей в схеме, | | K , k – неисправность в схеме, ( ) – булева функция, задающая состояние выхода подсхемы, ( ) k – булева функция, являющаяся условием активизации k-ой неисправно сти типа константная- в подсхеме, ( ) i Tr – булева функция, являющаяся условием транспортировки сигнала со входа i ,
N – число логических элементов в схеме, | | N S , V – число логических элементов в подсхеме, | | i i V , ( ) S n – зависимость сложности вычислительного узла от параметра n, выражен ная в логических элементах, ПЛИС, FPGA – программируемая логическая интегральная схема, ПЭВМ – персональная электронная вычислительная машина, ОЗУ, RAM – оперативное запоминающее устройство, ГА – генетический алгоритм.
ВВЕДЕНИЕ Актуальность темы исследования. Современные системы автоматизирован ного управления, связи, обработки сигналов, представляют собой электронные схе мы сверхбольшой сложности, тестирование и верификация которых является важ нейшей задачей, решаемой на этапе выпуска готовой продукции и при ее эксплуата ции, неотъемлемой частью которой является синтез проверяющих и диагностиче ских тестов. Распространенный подход, основанный на внутрисхемном тестировании, по зволяет значительно сократить время контроля качества интегральной схемы как продукта производства (и для сверхсложных интегральных схем делает вообще воз можным адекватный процесс тестирования). Однако, аппаратные средства, реали зующие внутрисхемное тестирование, занимают до 20% площади кристалла инте гральных схем и ухудшают временные и мощностные параметры системы в целом. Таким образом, в настоящее время существует объективное противоречие между необходимостью выделения дополнительных аппаратных ресурсов в составе цифро вых устройств для реализации средств внутрисхемного тестирования и существен ными временными затратами на построение проверяющих тестов при внешней ди агностике (без возможности контроля внутренних сигналов и загрузки произвольно го состояния автомата). В этой связи, интерес к методам синтеза тестов для внешней диагностики вызван не только наличием электронных схем, тестируемых только внешне, но и вследствие того, что применение данных методов позволяет оптимизи ровать аппаратные затраты на средства внутрисхемного тестирования комбинирова нием внутренней и внешней диагностики. Поскольку размер пространства, внутри которого производится поиск тестовых последовательностей, растет экспоненциально от числа первичных входов и собст венных состояний схемы, то проблема генерации тестов отнесена к классу NP полных. Вопросы развития и исследования методов синтеза тестов для цифровых схем в течение последних десятилетий рассматривались в работах В.П. Чипулиса, В.
Агравела, М. Бушнела, Т. Лараби, Х. Шнурмана, П. Тафертсгофера, С. Акерса, Д. Армстронга, В.-Т. Ченга, П. Гоэля, В.И. Хахано-ва, Ю.А. Скобцова. Вычислительная сложность процедур синтеза тестов, в особенности для схем с памятью, делает актуальным разработку и исследование подходов, методов и средств, которые способны сократить время решения данной задачи. Перспектив ными являются исследования, направленные на интенсивное использование эволю ционных методов оптимизации, параллельных вычислений и средств аппаратного ускорения. С помощью комплексного применения перечисленных подходов в смеж ных областях получено значительное сокращение времени решения задач большой размерности. Связь работы с научными программами, планами, темами. Диссертацион ная работа выполнена на кафедре «Кибернетики и вычислительной техники» в соот ветствии с планом научно-исследовательских работ Севастопольского национально го технического университета в период 2004-2007 гг. в рамках темы «Моделирова ние и диагностика цифровых, аналого-цифровых и микропроцессорных РЭА» №Е503-42/2003 (ДР №104U003502). Кроме того, отдельные результаты диссертаци онных исследований были использованы в научно-исследовательской работе по те ме «Разработка систем автоматизированного проектирования устройств на СБИС» шифр «Парус», № 286-Н, 2005 г. Роль автора в указанных научно-исследовательских темах и проектах, заключа ется в разработке и реализации методов синтеза тестов цифровых синхронных схем с памятью с применением декомпозиции, символьного представления схем и ис пользования средств аппаратного ускорения. Цель и задачи исследования. Целью диссертационной работы является со кращение производственного цикла диагностики электронных схем путем вершен ствования методов генерации тестов для цифровых синхронных схем с памятью за счет применения декомпозиции и средств аппаратного ускорения. Для достижения указанной цели в работе решаются следующие задачи: 1. Провести анализ имеющихся средств и методов построения тестов для циф ровых комбинационных схем и синхронных автоматов с памятью. Выбрать крите
рии эффективности оценки методов генерации тестовых последовательностей. Выделить основные подходы к повышению эффективности существующих методов. 2. Применить к существующим эволюционным и комбинаторным методам син теза тестов цифровых схем декомпозиционный подход и символьное описание фрагментов разбиения тестируемой схемы с целью минимизации времени генериро вания тестовых воздействий. 3. Провести анализ эффективности аппаратного ускорения алгоритмических процессов синтеза тестов эволюционными методами и установить условия, обеспе чивающие сокращение времени решения по сравнению с программной реализацией алгоритмов. 4. Построить и проанализировать математическую модель алгоритма для опти мизации целевой функции. Выяснить условия сходимости алгоритма к оптимуму целевой функции. Исследовать возможность аппаратной реализации алгоритма в большой программируемой логической интегральной схеме (ПЛИС), оптимально использующей ее аппаратные ресурсы. 5. Получить и проанализировать целевую функцию, выражающую разность со стояния исправной и неисправной схемы, к оптимизации которой сводится направ ленный поиск тестовых последовательностей. Исследовать эффективность аппарат ной реализации модуля вычисления целевой функции в большой программируемой логической интегральной схеме (ПЛИС), оптимально использующей ее аппаратные ресурсы. 6. Разработать архитектуру аппаратной системы, осуществляющей полный вы числительный процесс синтеза проверяющих и диагностических тестов для цифро вых синхронных схем с памятью. Разработать методику, а также алгоритмические средства построения аппаратного функционально-ориентированного модуля с при менением ПЛИС для моделирования неисправностей в цифровой схеме. 7. Провести экспериментальное исследование эффективности и быстродействия предложенных методов и аппаратных средств. Для этого разработать соответст вующие языковые описания для логических структур, синтезируемых в ПЛИС; про граммное обеспечение для подготовки данных и управления процессами программ
но-аппаратного решения задач синтеза тестов; а также аппаратное обеспече ние, необходимое для реализации соответствующих реконфигурируемых логиче ских структур. Объект исследования – процесс контроля и структурной диагностики элек тронных цифровых синхронных схем с памятью. Предмет исследования – методы и средства синтеза структурных тестов для тестирования и диагностики неисправностей в цифровых синхронных схемах с па мятью. Методы исследования. В работе использовались методы теории цифровых ав томатов, теории вероятности, теории тестирования и диагностики дискретных схем, теории эволюционных вычислений, методы аппаратной реализации алгоритмов и вычислений, теории конструирования ЭВМ, методы моделирования и проектирова ния электронной техники. Научная новизна полученных результатов заключается в усовершенствовании существующих и разработке новых методов генерации тестов для неразрушающей диагностики цифровых синхронных схем с памятью за счет применения декомпози ции и средств аппаратного ускорения. 1. Впервые разработан аппаратно-ориентированный метод решения задачи син теза тестов, который сочетает применение аппаратных средств для ускорения ком бинаторного перебора, декомпозицию схемы и использование эволюционных алго ритмов. 2. Впервые получено доказательство сходимости компактного генетического алгоритма (compact genetic algorithm – Compact-GA) с моделированием элитизма к глобальному оптимуму инъективной целевой функции. 3. Впервые разработана метрика наблюдаемости-управляемости сигналов циф ровой синхронной схемы с представлением значений сигналов в виде временных интервалов, на основе чего разработан алгоритм оценки длины тестовых последова тельностей автомата и предложены соотношения для выбора между программной и аппаратной системами синтеза тестов.