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

СЕВАСТОПОЛЬСКИМ НАЦИОНАЛЬНЫМ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

62 11/7

На правах рукописи БОРИСЕВИЧ АЛЕКСЕЙ ВАЛЕРЬЕВИЧ

УДК 681.518.54

МЕТОДЫ СИНТЕЗА ТЕСТОВ ДЛЯ ЦИФРОВЫХ СИНХРОННЫХ СХЕМ НА ОСНОВЕ РЕКОНФИГУРИРУЕМЫХ АППАРАТНЫХ СРЕДСТВ

)Л\

ТУ

05.13.05 - Компьютерные системы и компоненты

ДИССЕРТАЦИЯ на соискание научной степени кандидата технических наук

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

М'/уу'гщ I Скатков Александр Владимирович,

доктор технических наук, профессор

СЕВАСТОПОЛЬ - 2008

СОДЕРЖАНИЕ

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

7

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

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

1.1 Цифровая синхронная схема как объект диагностики

1.2 Модели неисправностей

13

15

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 Результаты и анализ применения смешанного генетико-символьного ме- 162 тода на схемах библиотеки ISCAS-89

5.5 Результаты и анализ применения совместной аппаратной реализации гене- 166 тического алгоритма и подсистемы моделирования для схем библиотеки

ISCAS-89

5.6 Сравнительный анализ применения предложенных методов 168

5.7 Сравнение временных преимуществ и аппаратных затрат 171

5.8 Выводы по разделу 173 ВЫВОДЫ 175 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 178 ПРИЛОЖЕНИЕ А. Численные результаты по апробированию методов 191 А. 1 Характеристики схем библиотеки ISCAS 191

А.2 Результаты применения смешанного генетико-символьного метода на 192 схемах библиотеки 18СА8-89

А.З Результаты применения совместной аппаратной реализации генетическо- 194 го алгоритма и подсистемы моделирования для схем библиотеки 18СА8-89

А.4 Сложность аппаратной системы синтеза тестов 196

ПРИЛОЖЕНИЕ Б. Вспомогательные алгоритмы методов синтеза теста 198

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

Б.2 Транслятор с входного языка описания структуры схемы 205 ПРИЛОЖЕНИЕ В. Результаты логического моделирования для верификации 210 тестов схемы s344 библиотеки ISCAS-89

ПРИЛОЖЕНИЕ Г. Акты внедрения 225

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

S - тестируемая схема как множество элементов,

0 - вектор-функция переходов автомата, со - вектор-функция выходов автомата, X - множество входных сигналов схемы, Y - множество выходных сигналов схемы, W(t) - множество сигналов состояния схемы,

W(t +1) - множество входных сигналов регистра состояния схемы, п - число входов схемы, п-\Х\, т - число выходов схемы, m=\Y\,

q — число сигналов состояния (элементов памяти) схемы, q=\W\, El - логический элемент схемы,

S® - итеративный массив комбинационных схем тестируемой схемы, Aj - фрагмент тестируемой схемы (подсхема)

X - множество входов подсхемы,

Ъ,к е X - вход подсхемы как управляемый сигнал схемы,

Н - тестовая последовательность,

1 - длина тестовой последовательности,

К - множество тестовых последовательностей, Т - множество неисправностей схемы, К - число неисправностей в схеме, К =| Т |, 1к е Т - неисправность в схеме,

Q(X) - булева функция, задающая состояние выхода подсхемы, &fo(X) - булева функция, являющаяся условием активизации k-ой неисправности типа константная- а в подсхеме,

Щ(Х) - булева функция, являющаяся условием транспортировки сигнала со

входа ^еХ,

N - число логических элементов в схеме, N =| S |, V - число логических элементов в подсхеме, Vi =| Лг-1,

S(n) - зависимость сложности вычислительного узла от параметра п, выраженная в логических элементах,

ПЛИС, FPGA - программируемая логическая интегральная схема, ПЭВМ - персональная электронная вычислительная машина, ОЗУ, RAM - оперативное запоминающее устройство, ГА - генетический алгоритм.

ВВЕДЕНИЕ

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

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

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

Агравела, М. Бушнела, Т. Лараби, X. Шнурмана, П. Тафертсгофера, С. Акерса, Д. Армстронга, В.-Т. Ченга, П. Гоэля, В.И. Хахано-ва, Ю.А. Скобцова.

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

Связь работы с научными программами, планами, темами. Диссертационная работа выполнена на кафедре «Кибернетики и вычислительной техники» в соответствии с планом научно-исследовательских работ Севастопольского национального технического университета в период 2004-2007 гг. в рамках темы «Моделирование и диагностика цифровых, аналого-цифровых и микропроцессорных РЭА» №Е503-42/2003 (ДР №10411003502). Кроме того, отдельные результаты диссертационных исследований были использованы в научно-исследовательской работе по теме «Разработка систем автоматизированного проектирования устройств на СБИС» шифр «Парус», № 286-Н, 2005 г.

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

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

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

1. Провести анализ имеющихся средств и методов построения тестов для цифровых комбинационных схем и синхронных автоматов с памятью. Выбрать Крите-

рии эффективности оценки методов генерации тестовых последовательностей. Выделить основные подходы к повышению эффективности существующих методов.

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

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

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

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

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

7. Провести экспериментальное исследование эффективности и быстродействия предложенных методов и аппаратных средств. Для этого разработать соответствующие языковые описания для логических структур, синтезируемых в ПЛИС; программное обеспечение для подготовки данных и управления процессами программ-

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

Объект исследования - процесс контроля и структурной диагностики электронных цифровых синхронных схем с памятью.

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

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

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

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

2. Впервые получено доказательство сходимости компактного генетического алгоритма (compact genetic algorithm - Compact-GA) с моделированием элитизма к глобальному оптимуму инъективной целевой функции.

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

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

5. Получил дальнейшее развистие метод топологически-ориентированного принятия решений (Path Oriented DEcision Making - PODEM) для построения тестов комбинационных схем, который осован на применении структурной декомпозиции схемы функциональные элементы, описываемые системой булевых функций.

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

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

Результаты исследования внедрены в предприятиях: ЗАО «НТП ЮБК-Спектр» в программно-аппаратном комплексе АСК для ремонта и диагностики специализированной электронной техники (акт внедрения от 12.10.2007), ДП АО «Завод «Терминал» НПК «Приборостроительный завод», г. Винница, в диагностической программно-аппаратной системе ПАРМ (акт внедрения от 4.03.2008).

Научные положения, выводы и рекомендации, предложенные в работе, используются в ряде дисциплин, читаемых в СевНТУ на факультете «Автоматика и вычислительная техника» и при подготовке бакалавров по направлениям «Компьютерная инженерия».

Достоверность научных положений и выводов диссертационной работы подтверждается:

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

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

- результатами экспериментальных исследований основных алгоритмов и апробацией разработанных методов на библиотеке схем ISCAS-89, предложенной на междун