Методы синтеза тестов для цифровых синхронных схем на основе реконфигурируемых аппаратных средств тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Борисевич, Алексей Валерьевич

• Борисевич, Алексей Валерьевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Борисевич, Алексей Валерьевич

СОДЕРЖАНИЕ

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

7

РАЯ ДЕЛ 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 Модели неисправностей

13

15

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-89

5.1 Программа экспериментов по апробации предложенных методов

5.2 Состав и структура экспериментальных аппаратных средств

5.3 Состав и структура программного обеспечения

5.4 Результаты и анализ применения смешанного генетико-символьного ме- 162 тода на схемах библиотеки ISCAS-89

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

ISCAS-89

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

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

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

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

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

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

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

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

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

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

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

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, предложенной на международном симпозиуме по тестированию дискретных схем (ISCAS).

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

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

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

Список литературы диссертационного исследования кандидат технических наук Борисевич, Алексей Валерьевич, 2008 год

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Соловьев В.В. Проектирование цифровых систем на основе программируемых логических интегральных схем / В.В. Соловьев.—М. 2001.—636 с.

2. Соловьев В.В. Структурные модели конечных автоматов при их реализации на ПЛИС /В.В. Соловьев // Chip News. —№ 9.—М. 2002.—С. 4-14.

3. Василевский М. П. О распознавании неисправности автоматов / М. П. Василевский // Кибернетика—Вып. 4.—М: Наука, 1973 —С. 98-108.

4. Galey J. М. Techniques for the Diagnosis of Switching Circuit Failures / J. M. Galey, R. E. Norby, J. P Roth // Proc. of the Second Annual Symp. On Switching Circuit Theory and Logical Design.—Detroit, Oct. 1961.— P. 152-160.

5. Bushnell M. L. Essentials of electronic testing for digital, memory and mixed-signal VLSI circuits / M. L. Bushnell, V.D. Agrawal.—New York, 2002.—713 c.

6. Bossen D. C. Cause-Effect Analysis for Multiple Fault Detection in Combinational Networks / D. C. Bossen, S. J. Hong // IEEE Trans, on Computers.—Vol. C-20.—Nov. 1971 :—P. 1252-1257.

7. Agrawal V. D. An Automatic Test Generation System for Illiac IV Logic Boards / V. D. Agrawal, P. Agrawal // IEEE Trans, on Computers.—C-21—Sept. 1972.—P. 1015-1017.

8. Eichelberger E. B. Structured Logic Testing / E. B. Eichelberger, E. Lindbloom, J. A. Waicukauski, T. W. Williams.—New Jersey , 1991.—208 p.

9. Waicukauski J. A. Fault Detection Effectiveness of Weighted Random Patterns / J. A. Waicukauski, E. Lindbloom // Proc. of the International Test Conf. Sept. 1988.—P. 245-255

10.Wunderlich H.J. On Computing Optimized Input Probabilities for Random Tests / H.J. Wunderlich // Proc. of the 24th Design Automation Conf. June-July 1987.—P. 392398.

11.Sellers F. F. Analyzing Errors with the Boolean Difference / F. F. Sellers, M. Y. Hsiao, L. W. Bearnson // IEEE Trans, on Computers.—Vol. C-17.—July 1968.—P. 676683.

12.Бутаков Е.А. Диагностика программируемых логических матриц /

Е.А. Бутаков, М.Б. Волынский, В.Г. Новоселов.—М.: Радио и связь, 1991.—160 с.

13.Новоселов В. Г. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах / В.Г. Новоселов, А. В. Скатков // Учебное пособие.—К. УМК ВО, 1992 ^-200 с.

14.Roth J. P. Diagnosis of Automata Failures: A Calculus and a Method / J. P. Roth // IBM Journal of Research and Development.—Vol. 10.— July 1966 —P. 278-291.

15.de Micheli G. Synthesis and Optimization of Digital Circuits / G. de Micheli.— New York, 1994.—576 p.

16.Chakradhar S. T. Neural Net and Boolean Satisfiability Models of Logic Circuits / S. T. Chakradhar, V. D. Agrawal, M. L. Bushnell // IEEE Design Test of Computers .—7

Oct. 1990 ^-P. 54-57

17.Larrabee T.. Efficient Generation of Test Patterns Using Boolean Difference / T. Larrabee // Proc. of the International Test Conf.—Aug. 1989 —P. 795-801

18.Chakradhar S. T. Automatic Test Pattern Generation Using Quadratic 0-1 Programming / S. T. Chakradhar, V. D. Agrawal, M. L. Bushnell // Proc. of the 27th Design Automation Conf. June 1990 :—P. 654-659

19.Hopfield J. J. Artificial Neural Networks / J. J. Hopfield // IEEE Circuits and Devices Magazine — Vol. 4 r— Sept. 1988 .—P. 3-10

20.Chakradhar S. T. Neural Models and Algorithms for Digital Testing / S. T. Chakradhar, V. D. Agrawal, M. L. Bushnell.—Boston ,1991 ^208 p.

21.Chakradhar S. T. A Transitive Closure Based Algorithm for Test Generation / S. T. Chakradhar, V. D. Agrawal // Proc. of the 28th Design Automation Conf :— June 1991 ^P. 353-358

22.1barra О. H. Polynomially Complete Fault Detection Problems / О. H. Ibarra, S. K. Sahni // IEEE Trans, on Computers Vol. C-24 Mar. 1975 —P. 242-249

23.Harel D. Is There Hope for Linear Time Fault Simulation? / D. Harel, B. Krish-namurthy // Proc. of the 17th International Fault-Tolerant Computing Symp :— 1987 :— P. 28-33

24.Хайнеман Р. Моделирование работы электронных схем (с CD-ROM) / Р. Хайнеман ^СПб.: Питер, 2002 .—336 с.

25.Гладков JI.A. Генетические алгоритмы / JI.A. Гладков, В.М. Курейчик, В.В. Курейчик;—М., 2006 ^320 с.

26.Емельянов В.В. Теория и практика эволюционного моделирования / В.В. Емельянов, В.М. Курейчик, В.В. Курейчик:—М., 2003 :—432 с.

27.Baeck Т.. Evolutionary computation / Т. Baeck, D. Fogel, Z. Michalewicz ;— Berlin Heidelberg , 2000 ^-377 p.

28.Beyer H.G. How to analyse evolutionary algorithms / H.G. Beyer, H.P. Schwefel, I. Wegener // Theoretical Computer Science — Vol. 287 —Essex, UK , 2002 —P. 101130

29.Turing A.M. Computing machinery and intelligence / A.M. Turing // Mind ;— Vol. 236 1950 ¡—P. 433-460

30.Arnold D.V. Performance analysis of evolution strategies with multirecombination in high-dimensional RN-search spaces disturbed by noise / D.V. Arnold, H.G. Beyer // Theoretical Computer Science — Vol. 289 ^-Essex, UK, 2000 :—P. 629-647

31.Beyer H.G. An alternative explanation for the manner in which genetic algorithms operate / H.G. Beyer // BioSystems — Vol. 41 1997 —P. 1-15

32.Holland J.H. Adaptation in natural and artificial systems / J.H. Holland :—Michigan , 1975 т—228 p.

33.De Jong K.A. Generation gaps revisited / K.A. De Jong, J. Sarma // Foundations of Genetic Algotihms — 1993 ^P. 19-28

34.Goldberg D. E. Genetic algorithms and the variance of fitness / D. E. Goldberg, M. Rundnick// Complex Syst. Vol. 5 .— 1991 ^-P. 265-278

35. Goldberg D. E. Genetic algorithms, noise, and the sizing of populations / D. E. Goldberg, K. Deb, J. H. Clark // Complex Syst. ^Vol. 6^- 1992 ^P. 333-362

36.Harik G. The Gambler's ruin problem, genetic algorithms, and the sizing of populations / G. Harik, E. Cantu-Paz, D. E. Goldberg, B. L. Miller // Evol. Comput. ^Vol. 7 r- 1999 :—P. 231-253

37.Harik G. The compact genetic algorithm / G. Harik, F. G. Lobo, D. E. Goldberg // IEEE Trans. Evol. Comput. Vol. 3 — Nov. 1999 :—P. 287-297

38.Harik G. Linkage learning via probabilistic modeling in the ECGA / G. Harik // IlliGAL Rep. 99 010 ^-Urbana , 1999 ^ 101 p.

39.Dasgupta D. deceptive problems using a different genetic search / D. Dasgupta // Proceedings of the First IEEE Conference on Evolutionary Computation :— 1994 ;— 807-811

40.Shakya S. K. Probabilistic model building Genetic Algorithm (PMBGA): A survey / S. K. Shakya // Technical Report. Computational Intelligence Group =—Aberdeen , August 2003 ;— http://www.comp.rgu.ac.uk/staff7ss/techReport/Basicsurvey.pdf

41.Baraglia R. A hybrid heuristic for the traveling salesman problem / R. Baraglia, J. I. Hidalgo, R. Perego // IEEE Trans. Evol. Compute Vol. 5 Dec. 2001 ^P. 613-622

42.Hidalgo J. I. A hybrid evolutionary algorithm for multi-FPGA systems design / J. I. Hidalgo, J. Lanchars, A. Ibarra, R. Hermida // Proc. Euromicro Symp. Digital System Design (DSD).—2002 ^-P. 60-67

43.Ahn C. W. Elitism-based compact genetic algorithms / C. W. Ahn, R. S. Rama-krishna // IEEE Transactions on Evolutionary Computation ;—Vol. 7 ;— 2003 :—P. 367385

44.William E. Recent Advances in Memetic Algorithms / E.William, N. Krasnogor, J.E. Smith // Studies in Fuzziness and Soft Computing :—Vol. 166:— 2005 ;—408 p.

45.Aruldoss A.V. A modified hybrid EP-SQP approach for dynamic dispatch with valve-point effect, International Journal of Electrical Power and Energy Systems / A.V.T. Aruldoss, J.A Ebenezer // IEEE Transaction on Power Systems .—Vol. 27(8) ;— 2005 ;— P. 594-601

46.Attaviriyanupap K.H. A hybrid EP and SQP for dynamic economic dispatch with nonsmooth incremental fuel cost function / K.H. Attaviriyanupap, E. Tanaka, J. Hasegawa // IEEE Transaction on Power Systems ^Vol. 17(2) 2002 .—P. 411-416

47.Burke E.K. Hybrid evolutionary techniques for the maintenance scheduling problem / E.K. Burke, A.J. Smith // IEEE Transactions on Power Systems :—Vol. 1(1);— 2000 ^P. 122-128

48.Myung H. Hybrid evolutionary programming for heavily constrained problems / H. Myung, J.H. Kim // Biosystems — Vol. 38(1) ^— 1996 —P. 29-43

49.Somasundaram P. Hybrid algorithm based on EP and LP for security constrained economic dispatch problem / P. Somasundaram, R. Lakshmiramanan, K. Kuppusamy // Electric Power Systems Research — Vol. 76(1-3) — 2005 —P. 77-85

50.Wang L. An effective hybrid genetic algorithm for flow shop scheduling with limited buffers / L. Wang, L. Zhang, D.Z. Zheng // Computers and Operations Research;— Vol. 33(10) r— 2006 ^P. 2960-2971

5 l.Schlottmann F. A hybrid heuristic approach to discrete multi-objective optimization of credit portfolios / F. Schlottmann, D. Seese // Computational Statistics and Data Analysis :—Vol. 47(2) — 2004 P. 373-399

52.Menon P.P. Hybrid evolutionary optimisation methods for the clearance of nonlinear flight control laws / P.P. Menon, D.G. Bates, I. Postlethwaite // Proceedings of the 44th IEEE Conference on Decision and Control ^Seville, Spain , 2005 —P. 4053-4058

53.Estudillo A.C. Hybridization of evolutionary algorithms and local search by means of a clustering method / A.C.M. Estudillo, C.H. Martinez, F.J.M. Estudillo, G.C. Pedrajas // IEEE Transactions on Systems, Man and Cybernetics, Part B .—Vol. 36(3) :— 2006 :— P. 534-545

54.Koenig S. Incremental heuristic search in AI / S. Koenig, M. Likhachev, Y. Liu, D. Furcy // AI Magazine ^Vol. 25 2004 ^P. 99-112

55.Niermann T. HITEC: A Test Generator Package for Sequential Circuits / T. Niermann, J.H. Patel // Proc. European Design Automation Conference :— 1991 :—P. 214218

56.Agrawal V.D. CONTEST: A Concurrent Test Generator for Sequential Circuits / V.D. Agrawal, K.T. Cheng, P. Agrawal // Proc. 25th Design Automation Conference :— 1988 ^P. 84-89

57.Saab D. G. Automatic Test Vector Cultivation for Sequential VLSI Circuits Using Genetic Algorithms / D. G. Saab, Y. G. Saab, J. A. Abraham // IEEE Trans, on Computer-Aided Design:—Vol. 15 r- Oct. 1996 r-P. 1278-1285

58.Srinivas M. A Simulation-Based Test Generation Scheme Using Genetic Algorithms / M. Srinivas, L. M. Patnaik // Proc. of the 6th International Conf. on VLSI Design — Jan. 1993 —P. 132-135

59.Rudnick E.M. Application of Simple Genetic Algorithm to Sequential Circuit Test Generation / E.M. Rudnick, J.G. Holm, D.G. Saab, J.H. Patel // Proc. European Design & Test Conf. r- 1994 :—P. 40-45

60.Rudnick E. M. Sequential circiuit test pattern generation in a genetic algorithm framework / E. M. Rudnick, J. H. Patel, G. S. Greenstein, T.M. Niermann // Proc. Design Automation Conf. .— 1994 ^P. 698-704

61.Saab D.G. Iterative [simalation-based genetic+determenistic techniques] = complete ATPG / D.G. Saab, Y.G.Saab, J.A.Abraham // In Int'l Conf. on CAD 1994 ^-P. 40-43

62.Prinetto P. An Automatic Test Pattern Generator for Large Sequential Circuits based on Genetic Algorithms / P. Prinetto, M. Rebaudengo, M. Sonza Reorda // Proc. Int. Test Conf. — 1994 =—P. 178-186

63.Corno F. Comparing topological, symbolic and GA-based ATPGs: an experimental approach / F. Corno, P. Prinetto, M. Rebaudengo, M. Sonza Reorda // IEEE International Test Confernce ^Washington (USA) , 1996 r-P. 187-196

64.Hsiao M.S. Alternation strategies for sequentioa circuit ATPG / M.S. Hsiao, E.M. Rudnik, J.H. Patel // In European Design & Test Conf — 1996 ^P. 368-374

65.Gockel N. A genetic algorithm for sequemtial circuit test generaion based on symbolic fault simulation / N. Gockel, G. Pudelko, R. Drechsler, B. Becker // In European Test Workshop r- 1997 ^P. 198-202

66.Corno F. A Genetic Algorithm for Automatic Test Pattern Generation for Large Synchronous Sequential Circuits / F. Corno, P. Prinetto, M. Rebaudengo, M. S. Reorda // IEEE Trans, on Computer-Aided Design .—Vol. 15 — Aug. 1996 —P. 991-1000

67.Hsiao M. S. Sequential Circuit Test Generation using Dynamic State Traversal / M. S. Hsiao, E. M. Rudnick, J. H. Patel // Proc. of the European Design and Test Conf. :— 1997 ^P. 22-28

68.Hsiao M. S. Dynamic State Traversal for Sequential Circuit Test Generation / M. S. Hsiao, E. M. Rudnick, J. H. Patel // ACM Trans, on Design Automation of Electronic Systems (TODAES) ^Vol. 5 .— July 2000 ^P. 548-565

69.Bencivenga R. The Architecture of the Gentest Sequential Test Generator / R. Bencivenga, T. J. Chakraborty, S. Davidson // Proc. of the Custom Integrated Circuits Conf. r- May 1991 r-P. 17.1.1-17.1.4

70.Cheng W.T. Gentest: An Automatic Test Generation System for Sequential Circuits / W.T. Cheng, T. J. Chakraborty // ^-Vol. 22 Apr. 1989 P. 43-49

71.Иванов Д.Е. Параллельное моделирование неисправностей для последова-тельностных схем / Д.Е. Иванов, Ю.А. Скобцов // Искусственный интеллект .—Вып. 1;— 1999 :—С. 44-50

72.3акусило С.А. Генетический подход к генерации проверяющих тестов в системе АСМИД-Е / С.А.Закусило, Д.Е.Иванов, В.Ю.Скобцов, Ю.А.Скобцов. // Труды конференций "Искусственные интеллектуальные системы" и "Интеллектуальные САПР" =—М., 2002 ;— С. 49-55

73.Skobtsov A. Evolutionary approach to the test pattern generation for the sequential circuits / A..Skobtsov, D.E.Ivanov // Радиоэлектроника и информатика :—Вып. 3 .— 2003 :—46-51

74. Данилов С. О. Разработка и исследование методов и алгоритмов построения тестов последовательностных схем на основе непрерывного подхода : Дис. канд. техн. наук : 05.13.01 / С. О. Данилов.—Н.Новгород , 2004 .—158 с.

75.Rudnick Е. М. Combining deterministic and genetic approaches for sequential circuit test generation / E. M. Rudnick, J. H. Patel // Proceedings of the 32nd ACM/IEEE conference on Design automation :—San Francisco, United States , June 12-16, 1995 =— P. 183-188

76.Chatchawit A. A Hardware Implementation of the Compact Genetic Algorithm / A. Chatchawit, C. Prabhas // Proceedings of the 2001 IEEE Congress on Evolutionary Computation, Seoul, Korea, May 27-30, 2001 ^ Seoul, 2001 ^P. 624-629

77.Гудилов В.В. Методы повышения эффективности вероятностных алгоритмов, адаптированные к возможности динамических изменений параметров функ-

ционирования на примере аппаратной реализации генетического алгоритма UMDA / В.В. Гудилов, В.М. Курейчик // Перспективные информационные технологии и интеллектуальные системы;—Вып. 1 (21) :—Таганрог , 2005 ;—С. 42-54.

78.Рабаи Ж.М. Цифровые интегральные схемы: Методология проектирования (пер. с англ., под ред. Назаренко А.В.) / Ж.М. Рабаи, А. Чандракасан, Б.Николич г-М. ,2007^917

79.Compton К. Configurable Computing: A Survey of Systems and Software / K. Compton, S. Hauck // ACM Computing Surveys :—Vol. 34 — June 2002 —P. 171-210

80.Estrin G. Parallel processing in a restructurable computer system / G. Estrin, B. Bussel, R. Turn, J. Bibb // IEEE Trans. Elect. Comput r- 1963 —P. 747-755

81.Стешенко В. Б. ПЛИС фирмы ALTERA: проектирование устройств обработки сигналов ALTERA: проектирование устройств обработки сигналов / В. Б. Сте-шенко ^М., 2000 —128

82.Todman T.J. Reconfigurable computing: architectures and design methods / T.J. Todman, G.A. Constantinides, S.J.E. Wilton, O. Mencer, W. Luk, P.Y.K. Cheung // IEEE Proc.-Comput. Digit. Tech. —Vol. 152 r- March 2005 —P. 193-207

83.Henz M. One flip per clock cycle / M. Henz, E. Tan, R. Yap // Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming (CP2001) r-Cyprus , 2001 ^P. 509-523

84.Elbirt A. J. An FPGA implementation and performance evaluation of the serpent block cipher / A. J. Elbirt, C. Paar // ACM/SIGDA International Symposium on FPGAs

2000 ;—P. 33-40

85.Kim H. J. Factoring large numbers with programmable hardware / H. J. Kim, W. H. Mangione-Smith // ACM/SIGDA International Symposium on FPGAs — 2000 P. 41-48

86.Hauser J. R. A MIPS processor with a reconfigurable coprocessor / J. R. Hauser, J. Wawrzynek // IEEE Symposium on Field-Programmable Custom Computing Machines — 1997 ^P. 12-21

87.Leung K.H. FPGA Implementation of a microcoded elliptic curve cryptographic processor / K.H. Leung, K.W. Ma, W.K. Wong, P.H.W. Leong // IEEE Symposium on Field-Programmable Custom Computing Machines .— 2000 :—P. 68-76

88.Rencher M. Automated target recognition on SPLASH2 / M. Rencher, B. L. Hutchings // IEEE Symposium on Field-Programmable Custom Computing Machines ;— 1997 ^P. 192-200

89.Weinhardt M. Pipeline vectorization for reconfigurable systems / M. Weinhardt, W. Luk // IEEE Symposium on Field-Programmable Custom Computing Machines :— 1999 ^-P. 52-62

90.Huelsbergen L. A representation for dynamic graphs in reconfigurable hardware and its application to fundamental graph algorithms / L. Huelsbergen // ACM/SIGDA International Symposium on FPGAs — 2000 —P. 105-115

91 .Zhong P. Accelerating Boolean satisfiability with configurable hardware / P. Zhong, M. Martinosi, P. Ashar, S. Malik // IEEE Symposium on Field-Programmable Custom Computing Machines r- 1998 .—P. 186-195

92.Huang WJ. A reliable LZ data compressor on reconfigurable coprocessors / W.J. Huang, N. Saxena, E.J. McCluskey // IEEE Symposium on Field-Programmable Custom Computing Machines — 2000 —P. 249-258

93.Graham P. Genetic algorithms in software and in hardware—A performance analysis of workstations and custom computing machine implementations / P. Graham, B. Nelson // IEEE Symposium on FPGAs for Custom Computing Machines :— 1996 :—P. 216-225

94.Кузелин M. О. Современные семейства ПЛИС фирмы Xilinx. Справочное пособие / М. О. Кузелин, Д. А. Кнышев, В. Ю. Зотов —М., 2004 —440 с.

95.Gallagher J.C. A Family of Compact Genetic Algorithms for Intrinsic Evolvable Hardware / J.C. Gallagher, S. Vigraham, G. Kramer // IEEE Transactions on Evolutionary Computation — Vol. 8 April, 2004 —P. 115-126.

96.DeJong K.A. An analysis of the behavior of a class of genetic adaptive systems. Ph.D. dissertation / K.A. DeJong :—Univ. Michigan, Ann Arbor , 1975 :—160 p.

97.Gonzalez С. Analyzing the Population Based Incremental Learning Algorithm by Means of Discrete Dynamical Systems / C. Gonzalez, J. A. Lozano, P. Larranar-raga // Complex Systems Vol. 12(4) 2000 ^465-479

98.Martinez M. Generalized predictive control using genetic algorithms (GAGPC) / M. Martinez, J.S. Senent, X. Blasco // Proceedings of Engineering Applications of Artificial Intelligence, Castellón, Spain, June 1-4, 1998 —Vol. 11 ^Castellón , 1998 :—P. 355-367

99.Новоселов В.Г. Построение проверяющего теста для современных ПЛМ (CPLD) / В.Г. Новоселов, А.В. Борисевич // Вестник СевГТУ. Сер. Информатика, электроника, связь: Сб. научн. трудов =—Вып. 74 :—Севастополь , 2006 :—С. 47-57

100. Борисевич А.В. Некоторые вопросы эффективного построения проверяющего теста для ПЛИС / А.В. Борисевич, В.Г. Новоселов // Системы автоматики и автоматическое управление : материалы Всеукраинской научно-технической конференции, г. Севастополь, 16-18 мая 2006 г. :—Севастополь , 2007 :—С. 14-17

101. Новоселов В.Г. Модель тестовых ситуаций для неисправностей в задаче анализа полноты проверяющих тестов схем БИС и СБИС / В.Г. Новоселов, А.И. Тертычный // Методы логического проектирования ;—1:—Минск , 2002 :—123-128

102. Sastry К. Genetic algorithms / К. Sastry, D. Goldberg, G. Kendall // Search Methodologies — 2005 —P. 54-62.

103. Goldstein L. H. Controllability/Observability Analysis of Digital Circuits / L. H. Goldstein // IEEE Trans, on Circuits and Systems — Vol. CAS-26 — Sept. 1979 ¡—P. 685-693

104. Goldstein L. H. SCOAP: Sandia Controllability/Observability Analysis Program / L. H. Goldstein, E. L. Thigpen // Annual ACM IEEE Design Automation Conference — 1988 :—P. 397-403

105. Savir J. Improved cutting algorithm / J. Savir // IBM J. Res. Develop :—34 :— May 1990 —P. 381-388

106. Seth S. C. PREDICT: Probabilistic estimation of digital circuit testability / S. C. Seth, L. Pan, V. D. Agrawal // Proc. 15th Int. Fault-Tolerant Computer Symp =— June 1985 —P. 220-225

107. Chiou C.C. A Statistic-based Approach to Testability Analysis / C.C. Chiou, C.Y. Wang, Y.C. Chen // 9th International Symposium on Quality Electronic Design 2008 r-P. 267-270

108. Pipatsrisawat K. A Lightweight Component Caching Scheme for Satisfiability Solvers / K. Pipatsrisawat, A. Darwiche // Proceedings of 10th International Conference on Theory and Applications of Satisfiability Testing(SAT) — 2007 —P. 294-299

109. Fogel D. B. Asymptotic convergence properties of genetic algorithms and evolutionary programming: analysis and experiments / D. B. Fogel // Cybernetics and Systems Vol. 25 .— 1994 —P. 389-407

110. Rudolph G. Convergence Properties of Evolutionary Algorithms / G. Rudolph :—Hamburg ;—154 p.

111. Rudolph G. Self-adaptation and global convergence: a counter-example / G. Rudolph // Proceedings of the 1999 Congress on Evolutionary Computation ;—New Jersey —P. 646-651

112. Greenwood G.W. Convergence in Evolutionary Programs with Self-Adaptation / G.W. Greenwood // Evolutionary Computation:—Vol. 9 :— June 2001 :—P. 147-157

113. Rastegar R. A study of the global convergence time complexity ofestimation of distribution algorithms. / R. Rastegar, M. R. Meybodi // Lecture Notes in Artificial Intelligence —3641 — Regina, Canada —P. 441-450

114. Hohfeld M. Towards a theory of population based incremental learning / M. Hohfeld, G. Rudolph // Proceedings of the 4th IEEE Conferences on Evolutionary Computation ;—Indianapolis, USA —P. 1-5

115. Кнут Д. Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, vol.2. Seminumerical Algorithms / Д. Кнут :—M. 2007 :—832

116. L'Ecuyer . Efficient and portable combined random number generators / L'Ecuyer // Communications of the ACM .—Vol. 31.—P. 742-751

117. Matsumoto M. Mersenne Twister: A 623-Dimensionally Equidistri-

buted Uniform Pseudo-Random Number Generator / M. Matsumoto, T. Nishimura // ACM Transactions on Modeling and Computer Simulation :—Vol. 8 .— January 1998 ;—P. 3-30

118. Parreira A.A. Novel Approach to FPGA-based Hardware Fault Modeling and Simulation / A. A. Parreira, J.P. Teixeira // Proc. of the Design and Diagnostics of Electronic Circuits and Syst. Workshop — April 2003 —P. 17-24

119. Ellervee P. Environment for FPGA Based Fault Emulation / P. Ellervee, J. Raik, K. Tammeme, R. Ubar // Proceedings of the Estonian Academy of Sciences. Engineering ^12.03.2002 r- 2006 ^P. 323-335

120. Скатков A.B. Система аппаратного моделирования цифровых схем для построения проверяющих тестов эволюционными методами / А.В. Скатков, А.В. Борисевич // Восточно-Европейский журнал передовых технологий ;—№ 2/6 (26) :— Харьков , 2007 ¡—С. 9-20

121. Борисевич А.В. Эффективная аппаратная реализация генетического алгоритма COMPACT-GA для поиска экстремума функций / А.В. Борисевич // Оптимизация производственных процессов : сб. науч. тр. Севаст. нац. техн. ун-т.— Вып. 10 :—Севастополь , 2007 —С. 189-196

122. Constantinides G. A. Wordlength optimization for linear digital signal processing / G. A. Constantinides, P. Y. Cheung, W. Luk // IEEE Trans. Computer-Aided Design :—Vol. 22 — Oct. 2003 ^P. 1432-1442

123. Constantinides G. A. Optimum wordlength allocation / G. A. Constantinides, P. Y. Cheung, W. Luk // Proc. IEEE Sym. on Field-Programmable Custom Computing Machines — April 2002 —P. 219-228

124. Test generation and evaluation for large sequential circuits / — http://www.cerc.utexas.edu/~jaa/testing/genetic.html

125. CAD Group: download Tools / — http://www.cad.polito.it/tools/

126. Brglez F. Combinational profiles of sequential benchmark circuits / F. Brglez, D. Bryant, K. Kozminski // Proc. Int. Symp. on Circuits And Systems :— 1989 ;—P. 1929-1934

127. Библиотека схем ISCAS-89 / — http://www.fm.vslib.cz/~kes/asic/iscas/

128. Cyclone III Device Handbook / — http ://www. altera, com/ doc/сусЗ vol 12 .pdf

129. Вальпа O.B. Устройства USB. Адаптер USB-AVR / O.B. Вальпа // Схемотехника —№ 9 — 2003 С. 42-48

130. Bench file format / — http://www.cs.ucla.edu/classes/layout/testing/Examples.iscas/ISCAS89/Benchmark.readm e

131. Dev-C++/ — http://www.bloodshed.net/devcpp.html

Приложение А Численные результаты по апробированию методов А.1 Характеристики схем библиотеки 18СА8

Приведенные в таблице А.1 характеристики схем библиотеки 18СА8'89 могут быть найдены в [126] вместе с комментариями о функциях каждой схемы.

Таблица А. 1.

Схемы библиотеки 18СА8 '89

Схема Число Число Число Число

входов выходов триггеров вентилей

Ир!

8208.1 10 1 8 124

8298 3 6 14 143

8344 9 11 15 196

Б349 9 11 15 197

э382 3 6 21 189

з386 7 7 6 180

в400 3 6 21 193

8420.1 18 2 16 254

б444 3 6 21 212

8510 19 7 6 244

8526 3 6 21 224

з526п 3 6 21 225

б641 35 24 19 458

8713 35 23 19 471

8820 18 19 5 332

8832 18 19 5 330

Продолжение таблицы А. 1.

Б838.1 34 1 32 514

б953 16 23 29 464

вИ96 14 14 18 576

з1238 14 14 18 555

81423 17 5 74 754

81488 8 19 6 687

81494 8 19 6 681

85378 35 49 179 3043

89234 19 22 228 5867

813207 31 121 669 8773

815850 14 87 597 10471

835932 35 320 1728 18149

838417 28 106 1636 23950

838584 12 278 1452 20996

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

В таблице А.2 сравниваются численные результаты применения программной реализации метода построения проверяющего теста с помощью алгоритма ОАТТО и смешанного метода, предложенного в разделе 2. Дальнейшие сравнения с другими известными методами не приводятся и могут быть найдены в [63] в виде сравнений с результатами работы алгоритма ОАТТО. Программные реализации методов запускались на одной аппаратной платформе, указанной в параграфе 5.1.

Таблица А.2.

Сравнение методов построения проверяющего теста

'хема КР1 Кр0 N011- N03168 РС0А,% Т0А,С ЬвА Г*С]у[1ХеС1,% Т|у]лхесЬС !^1уПхсс1

208.1 10 1 8 124 91,2 10,11 1096 95,61 6,385 1206

Продолжение таблицы А.2.

>98 3 6 14 143 91,3 10,71 302 97,94 7,128 333

344 9 11 15 196 97,71 8,25 141 98,08 5,597 156

349 9 11 15 197 97,2 8,46 144 98,66 5,73 159

382 3 6 21 189 85,97 22,65 840 86 14,235 924

386 7 7 6 180 91,89 15,75 418 95,39 7,953 460

ЮО 3 6 21 193 84,45 32,85 916 86,45 20,321 1008

т. 1 18 2 16 254 55,77 23,67 797 56,33 13,627 877

144 3 6 21 212 87,13 28,92 1434 88,62 18,191 1578

510 19 7 6 244 100 9,75 989 98,01 6,586 1088

526 3 6 21 224 76,54 32,4 1050 78,29 19,111 1155

526п 3 6 21 225 75,18 32,1 862 78,24 18,921 949

541 35 24 19 458 88,7 30,24 395 93,44 17,019 435

713 35 23 19 471 84,83 36,18 557 89,21 21,13 613

т 18 19 5 332 55,49 50,01 669 58,07 20,492 736

332 18 19 5 330 58,91 43,5 425 60,39 18,051 468

338.1 34 1 32 514 41,02 49,11 1323 41,75 27,122 1456

Ж 16 23 29 464 99,46 24,15 1099 98,06 15,531 1209

1196 14 14 18 576 99,24 59,64 1805 98,05 34,288 1986

1238 14 14 18 555 95,62 66,51 1554 96,4 38,934 1710

1423 17 5 74 754 93,96 104,73 2691 98,06 58,699 2961

1488 8 19 6 687 98,44 69,66 1824 99,01 26,755 2007

1494 8 19 6 681 97,27 53,76 1244 98,09 21,044 1369

5378 35 49 179 3043 71,73 341,28 919 72,17 192,067 1011

Ш4 19 22 228 5867 7,84 1011,09 9 8,42 481,931 10

13207 31 121 669 8773 27,32 1889,04 544 29,29 922,25 599

15850 14 87 597 10471 8,37 2828,31 153 8,94 1268,32 169

35932 35 320 1728 18149 89,85 3995,25 903 90,46 2271,68 994

38417 28 106 1636 23950 20,59 39204,09 1565 21,81 20564,76 1722

38584 12 278 1452 20996 49,9 39528,03 5500 53,39 19740,454 6050

В таблице использованы следующие обозначения: Ыр1 - число входов схемы, Иро - число выходов схемы,

1ЧОРР - число элементов памяти (триггеров) в схеме, ^Оагев- число логических элементов в схеме,

РС0а ~ процент обнаруживаемых неисправностей с помощью теста, построенного методом ОАТТО,

ТС,А ~ время синтеза теста методом ОАТТО,

Ь0А - длина теста (число векторов), синтезированного методом ОАТТО, РОмнхеё - процент обнаруживаемых неисправностей с помощью теста, построенного символьно-эволюционным методом,

Тмкхес! - время синтеза теста символьно-эволюционным методом, ЬМ1хс(1 - длина теста (число векторов), синтезированного символьно-эволюционным методом.

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

Результаты применения предложенного в разделе 3 аппаратно-ориентированного метода к схемам библиотеки 18СА8-89, а также сравнение быстродействия с методом ОАТТО приведено в таблице А.З. В таблице введены следующие обозначения Т - суммарное время построения проверяющего теста в секундах (вместе с временем компиляции в БРОА), ЕС — доля тестируемых неисправностей, ТСА - время построения теста методом ОАТТО, РССА - доля тестируемых неисправностей методом ОАТТО. Реализация метода ОАТТО и программная часть предложенной нами системы запускались на одной аппаратной платформе, указанной в 5.1.

Таблица А.З.

Сравнение методов построения теста

Схема РС0А,% Т0а,С ТвА РСнагсь% ТнагсЬс Ьнага

8208.1 91,2 10,11 1096 93,26 15,19 1151

в298 91,3 10,71 302 96,74 14,479 318

8344 97,71 8,25 141 98,08 9,301 149

8349 97,2 8,46 144 98,05 9,502 152

б382 85,97 22,65 840 86,04 24,457 882

в386 91,89 15,75 418 92,02 17,907 439

ъ400 84,45 32,85 916 90,83 34,962 962

8420.1 55,77 23,67 797 57,69 20,699 837

э444 87,13 28,92 1434 90,43 28,822 1506

в510 100 9,75 989 98,11 9,374 1039

б526 76,54 32,4 1050 78,51 30,689 1103

з526п 75,18 32,1 862 80,39 30,305 906

8641 88,7 30,24 395 90,21 22,287 415

8713 84,83 36,18 557 85,87 26,362 585

в820 55,49 50,01 669 57,05 41,026 703

в832 58,91 43,5 425 59,99 35,81 447

8838.1 41,02 49,11 1323 41,82 29,881 1390

в953 99,46 24,15 1099 98,22 17,187 1154

81196 99,24 59,64 1805 98,09 39,433 1896

э1238 95,62 66,51 1554 98,05 44,592 1632

81423 93,96 104,73 2691 94,4 59,931 2826

81488 98,44 69,66 1824 98,19 42,003 1916

81494 97,27 53,76 1244 99,8 32,511 1307

в5378 71,73 341,28 919 73,95 183,458 965

89234 7,84 1011,09 9 7,87 421,787 10

813207 27,32 1889,04 544 28,3 698,126 572

815850 8,37 2828,31 153 9,02 901,542 161

835932 89,85 3995,25 903 92,02 1105,65 949

Продолжение таблицы А.З.

S38417 20,59 39204,09 1565 22,09 10310,98 1644

s38584 49,9 39528,03 5500 50,35 9705,57 5775

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

Численные результаты сравнения аппаратной сложности средства синтеза теста с логической сложностью тестируемых схем приведен в таблице А.4. Значения сложности S получены по результатам компиляции системы синтеза тестов в САПР Quartus II 8.0.

Таблица А.4

Аппаратная сложность системы синтеза тестов

Схема Число триггеров NDFF Число вентилей Noates Сложность системы синтеза теста S Отношение h=S/(NGates+NDFF)

S208.1 8 124 419 3.769

s298 14 143 486 3.651

s344 15 196 641 3.661

s349 15 197 645 3.66

s382 21 189 643 3.589

s386 6 180 633 3.836

s400 21 193 657 3.589

s420.1 16 254 860 3.671

s444 21 212 727 3.596

s510 6 244 810 3.729

s526 21 224 775 3.617

s526n 21 225 778 3.618

s641 19 458 1462 3.664

s713 19 471 1507 3.657

Продолжение таблицы А.4

Б820 5 332 1118 3.8

Б832 5 330 1110 3.8

Б838Л 32 514 1731 3.62

Б953 29 464 1615 3.612

81196 18 576 2009 3.665

Б1238 18 555 1930 3.662

81423 74 754 2588 3.54

Б1488 6 687 2461 3.734

81494 6 681 2438 3.733

б5378 179 3043 10639 3.578

89234 228 5867 21027 3.61

813207 669 8773 30819 3.544

815850 597 10471 37131 3.576

э35932 1728 18149 63460 3.51

838417 1636 23950 85443 3.555

838584 1452 20996 74114 3.553