Методы синтеза тестов для цифровых синхронных схем на основе реконфигурируемых аппаратных средств

• Автор: Борисевич, Алексей Валерьевич
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Севастополь
• Количество страниц: 227 с. : ил.

СОДЕРЖАНИЕ

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИИ

ВВЕДЕНИЕ

РАЗДЕЛ 1. Обзор методов построения тестовых последовательностей для 13 цифровых синхронных схем с памятью и выбор перспективных направлений их совершенствования

1.3 Краткий обзор классических методов построения тестов для цифровых 18 схем

1.4 Вычислительная сложность алгоритмов синтеза теста

1.5 Критерии эффективности и показатели совершенствования методов синте- 24 за тестов

1.6 Методы построения тестов на основе эволюционных алгоритмов

1.7 Аппаратная реализация алгоритмов как методология ускорения вычисле- 35 ний
1.8 Проблемы и перспективы применения эволюционных методов в задачах 39 построения тестов
1.9 Цели и задачи исследования 40 РАЗДЕЛ 2. Совершенствование эволюционных методов синтеза тестов на ос- 42 нове декомпозиции и символьного анализа
2.1 Эволюционный метод синтеза тестов на основе декомпозиции и символь- 42 ного анализа
2.2 Декомпозиция тестируемой схемы и символьное представление подсхем
2.3 Алгоритм вычисления тестов для подсхем
2.4 Алгоритм построения проверяющего теста для комбинационных схем с 51 учетом декомпозиции на основе топологически-оринтированного перебора тестовых наборов
2.5 Оценка эффективности применения декомпозиции
1.1 Цифровая синхронная схема как объект диагностики
1.2 Модели неисправностей

2.6 Генетико-символьный алгоритм построения проверяющего теста с учетом 60 декомпозиции схемы
2.7 Алгоритм синтеза диагностического теста
2.8 Экспериментальное исследование генетического алгоритма
2.9 Иллюстративный пример применения генетико-символьного метода син- 75 теза теста
2.10 Выводы по разделу 79 РАЗДЕЛ 3. Эволюционный метод синтеза тестов с использованием аппарат- 82 ного ускорения
3.1 Необходимость и эффективность аппаратного ускорения
3.2 Оценивание длины тестовых последовательностей синхронных схем
3.3 Аппаратно-ориентированный метод синтеза тестов для синхронных схем
3.4 Синтез теста цифровой схемы с памятью как задача скалярной оптимиза- 103 ции
3.5 Выбор оптимизационного алгоритма
3.6 Вероятностная модель и анализ сходимости эволюционного алгоритма
3.7 Выводы по разделу 128 РАЗДЕЛ 4. Аппаратные средства ускорения вычислений при синтезе тестов 129 схем эволюционными методами
4.1 Совместная аппаратная реализация оптимизационного алгоритма и систе- 129 мы моделирования неисправности
4.2 Параллельная аппаратная реализация оптимизационного алгоритма
4.3 Оптимальная последовательно-параллельная аппаратная реализация
4.4 Аппаратная реализация алгоритма оптимизации с применением селекции
4.5 Выбор генератора псевдослучайных чисел
4.6 Экспериментальные результаты решения задачи скалярной оптимизации с 141 помощью предложенного аппаратного средства
4.7 Аппаратная реализация вычислителя целевой функции
4.8 Выводы по разделу 151 РАЗДЕЛ 5. Апробация результатов исследования на международной библио-

теке последовательностных схем ISCAS-
5.1 Программа экспериментов по апробации предложенных методов
5.2 Состав и структура экспериментальных аппаратных средств
5.3 Состав и структура программного обеспечения
5.4 Результаты и анализ применения смешанного генетико-символьного ме- 162 тода на схемах библиотеки ISCAS-
5.5 Результаты и анализ применения совместной аппаратной реализации гене- 166 тического алгоритма и подсистемы моделирования для схем библиотеки
1БСА
5.6 Сравнительный анализ применения предложенных методов
5.7 Сравнение временных преимуществ и аппаратных затрат
5.8 Выводы по разделу
ВЫВОДЫ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ А. Численные результаты по апробированию методов
А.1 Характеристики схем библиотеки І8СА8
А.2 Результаты применения смешанного генетико-символьного метода на 192 схемах библиотеки 18СА
А.З Результаты применения совместной аппаратной реализации генетическо- 194 го алгоритма и подсистемы моделирования для схем библиотеки 18СА
А.4 Сложность аппаратной системы синтеза тестов
ПРИЛОЖЕНИЕ Б. Вспомогательные алгоритмы методов синтеза теста
Б.1 Алгоритмы символьного представления булевых функций
Б.2 Транслятор с входного языка описания структуры схемы
ПРИЛОЖЕНИЕ В. Результаты логического моделирования для верификации 210 тестов схемы s344 библиотеки 1SCAS-
ПРИЛОЖЕНИЕ F. Акты внедрения

Теорема нетестируемости гласит, что если для некоторого t-расширения схемы, / е 0, / -1, не удается построить тест, считая вектор W входами схемы, то неисправность является нетестируемой. Иными словам, тест для автомата с заданной неисправностью существует только тогда, когда существует тест для комбинационной схемы
Y = S1(X) = (d(X,W0),

Y = S2(Xl,X0,W) = е>(Хьо(Хо Л)),
где вектора Х0, Хх и W, X - входы схемы; W0 - начальное состояние автомата; Y(X,W) - функция выходов автомата; W(X.V) - функция переходов.
Кроме подобного сочетания детерминированных методов и эволюционного поиска, в ряде работ было предложены другие варианты гибридизации. В частности, в работе [75] детерминированный метод ШТЕС использовался для генерации неисправности и ее транспортировки на выходы схемы, а генетический алгоритм применялся для установки схемы в заданное состояние.
1.7 Аппаратная реализация алгоритмов как методология ускорения вычислений
Кроме традиционного программного метода реализации алгоритмов, использующего микропрограммные устройства (микропроцессоры), также существует и аппаратный, основанный на аппаратной технологии, в виде либо специализированных интегральных схем (Application Specific Integrated Circuit - ASIC) [78], либо схемы из набора отдельных электронных компонентов, формирующих аппаратное средство для решения конкретной вычислительной задачи. Совершенно очевидно, что такие специализированные аппаратные средства, полностью выполняющие все алгоритмические операции процесса вычисления, позволяют добиться максимальной производительности за счет распараллеливания.