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

Одесский национальный политехнический университет

Борисевич Алексей Валерьевич

УДК 681.518.54

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

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

Специальность 05.13.05 – Компьютерные системы и компоненты

Автореферат

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

кандидата технических наук

Одесса – 2008

Диссертация является рукописью.

Работа выполнена в Севастопольском национальном техническом университете 
Министерства образования и науки Украины, г. Севастополь.

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

Официальные оппоненты:
доктор технических наук, профессор,
Дрозд Александр Валентинович

доктор технических наук, профессор,
Мусиенко Максим Павлович

Защита состоится в «22» января 2009 года в 13:30 на заседании специализи
рованного ученого совета Д 41.052.01 при Одесском национальном политехническом университете по адресу: 65044, г. Одесса, пр. Шевченко 1, ауд. 400-А.

С диссертацией можно ознакомиться в библиотеке Одесского национального 

политехнического университета по адресу: 65044, г. Одесса, пр. Шевченко 1,

Автореферат разослан «19» декабря  2008 года.

Ученый секретарь специализированного 
диссертационного совета                          
Ю.С. Ямпольский

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Современные системы автоматизированного управле
ния, связи, обработки сигналов, представляют собой электронные схемы сверхбольшой сложности, тестирование и верификация которых является важнейшей 
задачей, решаемой на этапе выпуска готовой продукции и при ее эксплуатации, 
неотъемлемой частью которой является синтез проверяющих и диагностических 
тестов.

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

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

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

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

Связь работы с научными программами, планами, темами. Диссертаци
онная работа выполнена на кафедре «Кибернетики и вычислительной техники» в 
соответствии с планом научно-исследовательских работ Севастопольского национального технического университета в период 2004-2007 гг. в рамках темы «Моделирование и диагностика цифровых, аналого-цифровых и микропроцессорных 

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

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

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

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

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

2. Применить к существующим эволюционным и комбинаторным методам 

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

3. Провести анализ эффективности аппаратного ускорения алгоритмических 

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

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

5. Получить и проанализировать целевую функцию, выражающую разность 

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

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

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

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

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

Объект исследования – цифровые синхронные схемы с памятью.
Предмет исследования – методы и средства синтеза структурных тестов для 

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

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

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

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

2. Впервые разработан аппаратно-ориентированный метод решения задачи 

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

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

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

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

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

Предложенные в работе методы и аппаратные структуры являются основой

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

Результаты исследования внедрены в предприятиях:

- ЗАО «НТП ЮБК-Спектр» в программно-аппаратном комплексе АСК для 

ремонта и диагностики специализированной электронной техники (акт внедрения 
от 3.06.2008),

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

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

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

подтверждается:

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

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

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

апробацией разработанных методов на библиотеке схем ISCAS-89, предложенной 
на международном симпозиуме по тестированию дискретных схем (ISCAS). 

Личный вклад соискателя заключается в совершенствовании и разработке 

новых методов и средств, которые позволили решить сформулированные задачи 
исследования. Все основные результаты получены автором лично. В работах, 
опубликованных в соавторстве, соискателю принадлежит: обобщение метода 
PODEM для функциональных элементов схем произвольного базиса и усовершенствование генетического алгоритма для построения установочных последовательностей [1]; генетический алгоритма для построения тестов синхронных схем с 
множеством тактовых входов [2]; функциональная модель и экспериментальная 
реализация системы [3]; целевые функции для оценивания тестовых последовательностей [7]; условия транспортировки и генерации неисправностей, выраженные через тестовые ситуации [8]; оценка эффективности средства по сравнению с 
программной реализацией [9]; обобщение метода, основанного на модели сокращения-исчезновения термов булевой функции, для многоуровневых вентильных 
схем [11]; целевая функция и алгоритм оптимизации для поиска установочной последовательности автомата [13]; декомпозиционный алгоритм синтеза теста [14].

Апробация результатов диссертации. Основные научные положения и ре
зультаты, полученные автором при выполнении диссертационной работы, рассматривались на следующих научно-технических конференциях и семинарах: III 
международная научная конференция «Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий ISDMIT’2007» (г. Евпатория, май 2007 г.); IX международная научно-технической конференция «Системный анализ и информационные технологии» (15-19 мая 2007 г., г. Киев); «Современные проблемы радиотехники и телекоммуникаций РТ-2007», (г. Севастополь, 16-21 апреля 2007 г; международная научно-практическая конференция 

«Информационные технологии и информационная безопасность в науке, технике и 
образовании ИНФОТЕХ-2007» (10-16 сентября 2007 г. Севастополь); Всеукраинская научно-технической конференции «Системы автоматики и автоматическое 
управление» (г. Севастополь, 16-18 мая 2006 г.);  

Публикации. Основные результаты диссертации опубликованы в 16 печат
ных работах, среди которых 5 статей в сборниках научных работ, которые включены в список специальных изданий ВАК, а также 11 тезисов докладов в сборниках 
материалов научных конференций. 

Структура и объем диссертации. Диссертация состоит из введения, пяти 

разделов, выводов и приложений. Полный объем диссертации составляет 189 
страниц, 153 страницы машинописного текста. Работа содержит 56 рисунков, 21 
таблицу, 4 приложения на 40 страницах, 129 наименования литературных источников на 16 страницах.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность диссертационной работы, фор
мулируются цель и задачи исследования, и приводится краткое содержание работы 
по главам.

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

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

Объектом тестирования является комбинационная часть цифровой синхрон
ной схемы с памятью (с единственным тактовым входом). Схема S , представляемая мультиграфом 
( ,
)
S
E Н , где 
{
}
i
E
E
– множество логических элементов 

схемы, 
{ }
l
H
– множество соединений, декомпозируется на множество фраг
ментов (подсхем) 
{
}
j
S
, 
j
h
. В работе применен алгоритм декомпо
зиции схемы на подсхемы без разветвлений, что позволило использовать теорему о 
доминировании и эквивалентности неисправностей. Разбиение схемы может быть 
заданным изначально, если цифровое устройство синтезировано на функциональных элементах известного базиса (мультиплексоры, сумматоры и т.д.), в таком 
случае достигается сокращение времени синтеза теста за счет повторного исполь

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

Для решения задачи синтеза теста на основе декомпозиционного представ
ления схемы разработано обобщение метода PODEM, предложенного П. Гоэлем, 
для функциональных элементов произвольной структуры, описанных системой 
булевых функций. На основе обобщенного метода разработан алгоритм
1, кото
рый осуществляет синтез проверяющего теста, используя следующие символьные
описания каждой подсхемы 
j
S : 

- системы булевых функций исчерпывающих тестовых проверок 
(
)
j

j
k
, 

- системы булевых функций прозрачности входов 
(
)
xi
j
Tr
, 

- выходной булевой функций 
(
)
j
j , 

где 
{ }
j
i
– множество сигналов, от которых зависит выходное значение 

подсхемы 
j , и все булевы функций F заданы в виде множества конъюнкций 

{ }
v
F
k
.

Предложенному алгоритму
1 присущи основные достоинства программных 

реализаций исходного метода PODEM:

1. Перебор только по входным наборам (не по элементам схемы, как в клас
сическом D-алгоритме).

2. Максимальное использование средств моделирования схем.
3. Отсутствие стадии обратного продвижения – вычисление тестового набора 

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

Первым этапом алгоритма является поочередное доопределение входов из 

X
(множества входов, устанавливающих значение на проверяемой подсхеме 
)

до тех пор, пока не возникнет активизация неисправности:
(
) = 1
k
X
. Если все 

q
x
X
уже определены, то начинается перебор наборов значений входов X
. На 

следующем этапе алгоритма осуществляется доопределение 
ix
X , с целью 

транспортировки сигнала неисправности. Последовательно рассматриваются элементы 
j на пути от выхода тестируемого элемента до выхода схемы, и осущест
вляется воздействие на входы схемы X с попыткой выполнить условие транспортировки 
(
)
1
j
h
Tr
X
по соответствующему входу.

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

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

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

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

время построения теста и улучшает его качество;

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

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

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

пространстве последовательностей входных наборов 
={
}
k
X
схемы, решаемая с 

помощью генетического алгоритма.

Функция 
задается с помощью числовых оценок
( ,
( ))
s
F
, вычисляемых 

от всех булевых функций 
( )
s
F
, задающих условия генерации и транспортировки

неисправности, конъюнкция которых является необходимым и достаточным условием построения теста:

=
max
A
T
F
F
,                                            (1)

=
(
)
A

A
i

A
F
A
i

F
F
, 
=
max

(
)

T
k

k
Y

F
f

Out S

,

1

1

1
( ,
)
1
min
2
(
' )

2

n
j
i

i
i
n
j
k
F
i

F
k
,

где:
A – множество булевых функций, выполнение которых необходимо для активизации неисправности,

=|
|
n
X
– число переменных, от которых зависит булева функция F ,

(
)
Y
Out S
– множество подсхем, выходы которых являются выходами схемы,

'
( ,
)
k
K k X
– точка пространства двоичных наборов 
|
|
{0,1} X
k
такая, что 

'
,
(
, ')
min
k
k d X k
, где ( , )
d x y – расстояние между векторами по Хэммингу.

Коэффициенты 0
1
jf
в (1) вычисляются следующим образом:

1. 
,
=
(
)
j
k
f
, для подсхемы 
, содержащей тестируемую неисправность, 

где 
,
j
k
– логическое условие генерации неисправности.

2. 
= 0
if
, если через 
i не транспортируется сигнал неисправности.

2. 
=
{ (
) }
max
X

j

j
i
i
i
j
f
Tr
f , где X j – множество входных сигналов подсхемы 

j , 
j
i
Tr
– условие транспортировки сигнала со входа 
i на выход 
j , 
if – значе
ние коэффициента для подсхемы, подключенной ко входу i .

Для целевой функции (1) показано, что 
( ) принимает максимальное зна
чение 
max тогда и только тогда, когда последовательность 
является тестовой 

для заданной неисправности.

Как показывают результаты экспериментальной апробации предложенных 

алгоритмов
2, сочетание символьного анализа схемы и генетического поиска 

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

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

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

Представлен анализ эффективности аппаратного ускорения эволюционного 

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

= A
B
C

qN
q
N ,

0
(
1)
exp(
)
( , ) =
, ( , ) =
, ( , ) =

exp(
)
exp(
)
exp(
)

H
H
H
H

C
C
F

S
S
S
S
S
S

F
F
F

T
l
nl
A n l
B n l
C n l

l
nl
l
nl
nl

,

где: 
– оценка отношения среднего времени решения задачи синтеза теста с 

применением программной реализации эволюционного поиска ко времени решения с применением аппаратно-ориентированного метода, 
0
H
C
T
– минимальное вре
мя подготовки аппаратных средств к работе, n – число входов в тестируемой схеме, l – средняя длина тестовой последовательности,  N – число логических элементов в схеме, q – количество тестируемых константных неисправностей, 
S
F –

удельная производительность системы моделирования неисправностей (среднее 
время моделирования одного логического элемента), 
H
F – время такта работы тес
тируемой синхронной схемы, 
H
C – удельная производительность системы логиче
ского синтеза  (среднее время синтеза в ПЛИС одного логического элемента), 

,
H
S – коэффициенты, характеризующие размер пространства поиска от битовой 

длины тестовой последовательности.

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

0
0

1
1

=

S
E

S
E ,

,
,
S
E
S
E

i
i
i
i ,

где компоненты 
,
S
E

i
i
описывают потенциальную возможность установки 

соответствующих логических значений: сигнал a может принять значение логической 1 на тактах с 
1
=
S
t
по 
1
=
E
t
, и логического 0 во временном интервале с 

1
=
S
t
по 
1
=
E
t
. 

Представлена псевдобулева алгебра над множеством матриц 
{ }, в кото
рой определены операции: 
=
, =
,
=
, являющиеся аналогами дизъ
юнкции, конъюнкции и инверсии логических значений в схеме, соответственно, а