Методы синтеза тестов для цифровых синхронных схем на основе реконфигурируемых аппаратных средств тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Борисевич, Алексей Валерьевич
- Специальность ВАК РФ05.13.05
- Количество страниц 227
Оглавление диссертации кандидат технических наук Борисевич, Алексей Валерьевич
СОДЕРЖАНИЕ
ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ ВВЕДЕНИЕ
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 - оперативное запоминающее устройство, ГА - генетический алгоритм.
Рекомендованный список диссертаций по специальности «Элементы и устройства вычислительной техники и систем управления», 05.13.05 шифр ВАК
Разработка и исследование методов и алгоритмов построения тестов последовательностных схем на основе непрерывного подхода2004 год, кандидат технических наук Данилов, Сергей Олегович
Анализ и синтез логических схем для проверки функциональных и нефункциональных требований для компонентов телекоммуникационных систем2021 год, кандидат наук Лапутенко Андрей Владимирович
Методология автоматизации тестопригодного проектирования аналого-цифровых интегральных схем2022 год, доктор наук Мосин Сергей Геннадьевич
Повышение быстродействия логических схем за счет выявления неисправностей задержек путей с последующим их маскированием и определения ложных путей (на основе использования операций над ROBDD-графами)2022 год, кандидат наук Чернышов Семен Владимирович
Методы и средства автоматизации тестопригодного проектирования смешанных интегральных схем2013 год, доктор технических наук Мосин, Сергей Геннадьевич
Введение диссертации (часть автореферата) на тему «Методы синтеза тестов для цифровых синхронных схем на основе реконфигурируемых аппаратных средств»
ВВЕДЕНИЕ
Актуальность темы исследования. Современные системы автоматизированного управления, связи, обработки сигналов, представляют собой электронные схемы сверхбольшой сложности, тестирование и верификация которых является важнейшей задачей, решаемой на этапе выпуска готовой продукции и при ее эксплуатации, неотъемлемой частью которой является синтез проверяющих и диагностических тестов.
Распространенный подход, основанный на внутрисхемном тестировании, позволяет значительно сократить время контроля качества интегральной схемы как продукта производства (и для сверхсложных интегральных схем делает вообще возможным адекватный процесс тестирования). Однако, аппаратные средства, реализующие внутрисхемное тестирование, занимают до 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 тезисов докладов в сборниках материалов научных конференций.
Похожие диссертационные работы по специальности «Элементы и устройства вычислительной техники и систем управления», 05.13.05 шифр ВАК
Алгоритмы синтеза легко тестируемых комбинационных схем и тестов для кратных константных неисправностей и неисправностей задержек путей2011 год, кандидат технических наук Николаева, Екатерина Александровна
Минимизация проверяющих тестов для систем логического управления методами теории конечных автоматов2000 год, кандидат технических наук Прокопенко, Светлана Анатольевна
Диагностика параллельных магистралей и памяти бортовых ЦВМ2012 год, кандидат технических наук Выборнов, Петр Владимирович
Обеспечение сокращения аппаратурных затрат в схемах логического управления со свойствами самопроверяемости, самотестируемости и отказоустойчивости2009 год, кандидат технических наук Андреева, Валентина Валерьевна
Разработка математического обеспечения специализированных систем контроля цифровых узлов на основе автоморфизмов тестовых последовательностей1999 год, кандидат технических наук Петрухнова, Галина Викторовна
Список литературы диссертационного исследования кандидат технических наук Борисевич, Алексей Валерьевич, 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
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.