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

ВВЕДЕНИЕ.

ГЛАВА 1. ЗАДАЧИ ВЕРИФИКАЦИИ И ГЕНЕРАЦИИ ТЕСТОВ СЛОЖНЫХ ЦИФРОВЫХ СХЕМ.

1.1. Этапы верификации объектов проектирования.

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

1.2. Анализ систем генерации тестовых последовательностей.

1.3. Проблемы верификации и генерации тестов сложных цифровых схем.

1.4. Постановка задачи.

ВЫВОДЫ.

ГЛАВА 2. ЛИНГВИСТИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ПОДСИСТЕМЫ ГЕНЕРАЦИИ ТЕСТОВ И ВЕРИФИКАЦИИ БОЛЬШИХ ЦИФРОВЫХ СХЕМ.

2.1. Обоснование структуры прикладных средств генерации тестов и верификации сложных цифровых систем.

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

2.2.1. Разработка лингвистических средств подсистемы генерации тестов и верификации.

2.2.2. Разработка информационного обеспечения подсистемы.

2.2.3. Формирование базы данных.

ВЫВОДЫ.

ГЛАВА 3. АЛГОРИТМИЗАЦИЯ МОДЕЛИРОВАНИЯ НЕИСПРАВНОСТЕЙ И МЕТОДОВ ГЕНЕРАЦИИ ТЕСТОВ СЛОЖНЫХ ЦИФРОВЫХ СХЕМ.

3.1. Алгоритм ускоренного моделирования неисправностей.

3.2. Метод случайной генерации тестов.

3.3. Повышение эффективности алгоритмов направленной генерации тестов70 ВЫВОДЫ.

ГЛАВА 4. СТРУКТУРА, ОСОБЕННОСТИ ПОСТРОЕНИЯ И ХАРАКТЕРИСТИКИ ПРОГРАММНОГО КОМПЛЕКСА ГЕНЕРАЦИИ ТЕСТОВ И ВЕРИФИКАЦИИ СЛОЖНЫХ ЦИФРОВЫХ СХЕМ.

4.1 .Структура и особенности реализации программных средств генерации тестов и верификации сложных цифровых схем.

4.2. Особенности взаимодействия и интеграция разработанных программных средств в общей системе сквозного проектирования.

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

4.4. Методика использования средств генерации тестов и верификации ИС. 99 ВЫВОДЫ:.

Актуальность работы. Современные микроэлектронные технологии обесп печивают создание БИС сложностью порядка 10 элементов на кристалле. Процесс проектирования таких интегральных схем занимает длительное время. Одной из причин подобной ситуации состоит в резком увеличении времени синтеза тестовой последовательности и верификации проекта. Это определяет требования к составу аппаратных и программных средств автоматизации проектных работ по генерации тестов и верификации объектов проектирования

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

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

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

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

Диссертация является частью комплексной работы, проводимой в рамках вузовской научно-технической программы И.Т.601 "Перспективные направления технологии в высшей школе" в рамках основного научного направления ВГТУ "САПР и системы автоматизации производства", их математического и программного обеспечения.

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

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

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

Научная новизна. В диссертации получены следующие основные результаты, характеризующиеся научной новизной:

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

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

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

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

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

Практическая значимость и результаты внедрения. Результаты диссертационной работы положены в основу создания подсистемы генерации тестовых последовательностей и верификации больших цифровых электронных схем на базе отечественных и зарубежных мини- и микроЭВМ типа Pentium (и совместимых с ними ПК) и специализированных процессоров логического моделирования "Электроника МС90". Программно-аппаратный комплекс поддерживается разработанными лингвистическими средствами и соответствующим информационным и программным обеспечением. Созданные программные средства внедрены на ряде предприятий электронной отрасли в гг. Москвы, Воронежа, Уфы, Ульяновска и переданы в ОФАП отрасли. Подсистема генерации тестов и верификации в полном объеме внедрена в ОКБ "Процессор" г. Воронежа (в настоящее время АООТ "ОКБ ПРОЦЕССОР"), научно - исследовательском институте электронной техники АОО "Электроника" и учебный процесс кафедры САПРИС ВГТУ. Система проектирования использовалась при разработке полузаказных БИС на базовых матричных кристаллах на различных предприятиях. Годовой экономический эффект от внедрения системы и целевых подсистем оценивается в 331 млн рублей (в ценах 1997 г.).

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на научно-технических семинарах и конференциях: на семинаре "Передача и обработка данных в системах управления и ЭВМ" (Воронеж, 1989); Всесоюзной школе-семинаре молодых ученых и специалистов "Актуальные проблемы создания интеллектуальных САПР РЭА и СБИС" (Симферополь, 1989); Всесоюзном совещании-семинаре молодых ученых "Разработка и оптимизация 5

САПР и ГАП изделий электронной техники на базе высокопроизводительных мини- и микроЭВМ" (Воронеж, 1989); научно-технической конференции конструкторского проектирования РЭА и ЭВА (Пенза 1989); на IV симпозиуме "Эффективность, качество и надежность систем человек - техника" (Воронеж, 1990); межвузовской конференции "Экстремальные задачи и их приложения" (Н.Новгород 1992); на Региональной конференции "Автоматизация проектирования РЭА и ЭВА" (Пенза, 1992); на Международной научно-технической конференции "Методы, средства оценки и повышения надежности приборов устройств и систем" (Пенза, 1999); на отраслевых совещаниях и семинарах.

Диссертация в целом обсуждалась на межкафедральном семинаре Воронежского государственного технического университета.

Публикации результатов работы. По теме диссертации опубликовано 13 печатных работ. Часть результатов отражено в научно-технических отчетах по НИОКР, проведенных в период 1980 - 1999 гг.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 121 наименования. Материал диссертации изложен на 115 страницах машинописного текста, включая иллюстративный материал.

выводы

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

2. Разработан и реализован алгоритм случайной генерации тестов, отличающийся методом сужения тестевой последовательности, основанной на моделировании «неисправной» ИС для каждого входного тест-вектора (кандидата в тест) и его анализе, с точки зрения отбраковки для формирования конечной тестовой последовательности, что позволяет сократить общее число тест-векторов в среднем в 3-10 раз, в зависимости от сложности схемы и используемой в ней типов вентилей.

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

Глава 4. Структура, особенности построения и характеристики программного комплекса генерации тестов и верификации сложных цифровых схем.

Для генерации тестов и верификации сложных цифровых ИС создано программное обеспечение, интегрированное в состав системы логического проектирования БИС и СБИС. Структурно программное обеспечение состоит их двух комплексов «УВЕРТ» и «ТЕСТ». Комплекс программ «УВЕРТ» реализует ускоренное моделирование неисправностей и верификацию сложных цифровых ИС, а комплекс программ «ТЕСТ» синтезирует тестовую последовательность, на основе которой производится верификация.

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

В данной главе рассматриваются структура комплексов «УВЕРТ» и «ТЕСТ», определяется их место в общей системе сквозного проектирования сложных цифровых ИС, оценивается увеличение эффективности проектирования, которое возникает при их использовании, и методики использования средств генерации тестов и верификации ИС.

4.1 .Структура и особенности реализации программных средств генерации тестов и верификации сложных цифровых схем.

Моделирование неисправностей сложный процесс, который имеет свои особенности при увеличении размерности ИС свыше 100 тысяч вентилей. Для его реализации используются пакеты УВЕРТ и ТЕСТ.

Ускоренный метод моделирования неисправностей и верификации сложных ИС

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

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

Данный алгоритм моделирования реализован в отдельном программном комплексе "УВЕРТ", который представлен в рамках системы логического моделирования и генерации. Программный модуль реализован на языке ФОР-ТРАН-77. Все функциональные возможности модуля исправного моделирования системы "ПРАЦИС-ТМ" распространяются на программный модуль "УВЕРТ".

Структура программного модуля может быть проиллюстрирована схемой, приведенной на рис 4.1.

Работа программного комплекса УВЕРТ осуществляется через МОНИТОР, который определяет весь процесс моделирования неисправностей и верификации ИС.

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

Библиотека пакета содержит 95 моделей элементов (примитивов) цифровых узлов от базовых (И, ИЛИ, И-НЕ и т.д.) до АЛУ и ПЗУ. Структурная библиотека микросхем содержит 850 моделей наиболее распространенных микросхем средней степени интеграции.

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

Блок сервисных программ

Рис.4.1. Структура пакета УВЕРТ.

85

Блок моделирования неисправностей осуществляют управление и реализуют стандартные процедуры проектирования для «неисправных ИС».

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

Для ускорения процесса моделирования может быть использоваться ускоритель логического моделирования (УЛМ).

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

Предложен библиотечный принцип организации проектной информации: модулей графических ячеек и символов. Широко используются средства, обеспечивающие компактное представление данных (регулярных структур, шин, жгутов и т.п.). Допускается многократная вложенность модулей. Пакет обеспечивает проведение анализа цифровых схем, содержащих до 10000 и 200000. Допускается иметь до 10 000 модулей в схеме, каждый модуль может иметь 512 входных/выходных линий, а библиотечные элементы - до 127 входов и 127 выходов.

Обмен информацией с другими подсистемами осуществляется через специально разработанный транслятор. Через указанный транслятор осуществляется передача данных тестовых последовательностей, которые подготавливаются в подсистеме «ТЕСТ».

Подсистема генерации тестовой последовательности "ТЕСТ"

Для генерации тестовой последовательности предусмотрен комплекс программ «ТЕСТ», структурная схема которого приведена на рис. 4.2.

86

Рис.4.2. Структура пакета генерации тестовых последовательностей.

87

Подсистема "ТЕСТ" реализована на языке FORTRAN-77, как часть программного комплекса логического моделирования и генерации тестов . Данный комплекс использует модульный принцип построения программ.

Программный блок «Монитор» управляет всем процессом генерации тестов. Формирование тестовой последовательности осуществляется как в режиме автоматической генерации тестов, так и с помощью генерации тестовой последовательности разработчиком ИС. При автоматической генерации тестовой последовательности используется экспресс-анализ на тестопригодность, с целью уменьшения длины теста. Окончательное формирование тестовой последовательности осуществляется в блоке синтеза тестовой последовательности. Результат моделирования через транслятор передается в комплекс программ моделирования неисправностей.

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

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

При формировании тестовой модели схемы (объекта проектирования) для подсистемы ТЕСТ, налагаются некоторые ограничения на использование типов логических элементов и размер тестируемой схемы. Подсистема ТЕСТ ориентирована на работу со схемами размерностью до 30000 логических элементов, входящих а библиотеку подсистемы (вентильно - триггерный уровень).

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

4.2. Особенности взаимодействия и интеграция разработанных программных средств в общей системе сквозного проектирования

Для генерации тестов и верификации сложных цифровых схем разработано программное обеспечение, которое включено в систему автоматизированного проектирования цифровых ИС.

Структурная схема интегрированного программного комплекса ускоренного проектирования ИЭТ приведена на рис. 4.3

В состав ПМК системы логического проектирования включены следующие программные модули и пакеты : монитор - управляющий модуль системы проектирования; модуль библиотеки компонентов, проектов; модуль ввода и отображения информации по проекту и задающих сигналов в текстовом режиме; пакет ПРИАМ - многоуровневого моделирования электронных схем; пакеты ПРАЦИС-ТМ, ПРАЦИС-100 - логического моделирования, экспресс - анализа схем на тестопригодность, автоматизированной генерации тестов; пакет ПУМА - поддержки работы ускорителя логического моделирования в системе проектирования; пакет ИГРА - отображения графической информации; пакет УВЕРТ - ускоренной верификации сложных ИС; пакет ТЕСТ - генерации тестовых последовательностей; пакет ЭКТА - модуль экспресс - анализа на тестопригодность цифровых схем; пакет ТРЮМ - проектирование топологии СБИС; пакет СИАТ-ИНГРЕД - многослойные печатные платы. Ядром системы является пакет программ логического моделирования "ПРАЦИС-ТМ", который совместно с программным пакетом ПУМА и аппаратным ускорителем логического моделирования обеспечивает смешанное моделирование цифровых схем с использованием функциональных и вентильно -транзисторных моделей со скоростью до 2.5 млн. событий в секунду.

89

Рис.4.3. Структурная схема системы автоматизированного проектирования цифровых схем.

С ядром системы взаимодействуют пакеты программ поведенческого моделирования - ПРИАМ; пакет анализа схем на тестопригодность ЭКТА, и многослойных печатных СИАТ-ИНГРЕД, мощные модули подготовки исходной информации и обработки результатов проектирования и их архивирования. Комплекс обеспечивает быстрый ввод и верификацию описания крупных функциональных блоков, генерацию и ввод описания отдельных схем для этих блоков, моделирование поведения на уровне конечного изделия - кристалла.

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

Монитор системы осуществляет взаимодействие всех программных пакетов и формирует необходимые данные для передачи файлов между пакетами.

Отдельными программными модулями выступают УВЕРТ и ТЕСТ, которые представляет собой комплекс программ - ускоренного моделирования константных неисправностей и верификации сложных цифровых ИС (УВЕТ) и генерации тестовых последовательностей (ТЕСТ).

Программный комплекс сквозного проектирования может осуществлять проектирования ИС как с использованием алгоритма ускоренного моделирования неисправностей и верификации сложных цифровых ИС (УВЕРТ), так и без него. Использование данного модуля имеет смысл только для сложных ИС большой степени интеграции (размерность свыше 20000 вентилей) . Для ИС малой и средней степени интеграции проектирование может осуществляться без данного блока, так как выигрыш во времени в этом случае незначительный.

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

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

Унифицированный алгоритм ориентирован на большое поле оперативной памяти (в режиме моделирования неисправностей). С целью снижения объема необходимой памяти предложено использование динамических массивов.

91

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

Разделяется постоянная и переменная части информации.

Вводятся новые элементы - развилки (РС), автоматически создаваемые программой, что дает возможность уменьшить число последователей до одного и, как следствие, все неисправности привязать к выходам элементов, а задержки вводить обычным порядком на входе элементов.

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

Для оценки эффективности использования разработанных программных были проведены экспериментальные расчеты различных схем, получены на мини-ЭВМ "ЭЛЕКТРОНИКА-82". Результаты, представленны в таблице 4.1.

Выбранные схемы для проведения экспериментальных исследований алгоритма разнообразны по своей структуре, функциональному назначению и размерности. Полнота построенного теста определялась способом ускоренного моделирования модулем «УВЕРТ». Адекватные оценки полноты теста получены также и в режиме неисправного моделирования тестов конкурентным методом. Как видно из таблицы, применение модуля «УВЕРТ» показало получение точных оценок полноты теста для комбинационных схем, с точностью 7% - для последовательностных схем, при 10-20-кратном ускорении процесса моделирования.

Заключение

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

В ходе выполнения указанной работы были решены следующие задачи:

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

2. Создано лингвистическое обеспечение подсистемы, основу которого представляют разработанные автором языки МОС и ЯЗП, обеспечивающие удобство использования, универсальность и свойство открытости по отношению другим языкам.

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

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

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

Метод случайной генерации тестов, отличается сужением тестовой последовательности, за счет моделирования «неисправной» ИС, для каждого входного тест-вектора (кандидата в тест) и его анализа, с точки зрения отбраковки для формирования конечной тестовой последовательности. Такой подход позволяет сократить общее число тест-векторов в среднем в 3-10 раз, в зависимости от сложности схемы и используемых в ней типов вентилей.

104

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

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

7. Проведено исследование эффективности применения разработанных комплексов программ, которая показала увеличение эффективности за счет сокращения вычислительных затрат от 20 до 50 раз, полученных при определение полноты теста при числе ошибок больше 10000.

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

9. Разработано методическое обеспечение для использования разработанных программных комплексов.

10. Разработанные средства нашли применение в ОКБ завода «Процессор».

11. С помощью разработанных алгоритмов и программных комплексов были спроектированы ряд серий полузаказных БИС на базовых матричных кристаллах на различных предприятиях страны

1. Авдеев Е.А., Еремин А.Т., Норенков И.П., Песков М.И. Системы автоматизированного проектирования в радиоэлектронике: справочник// под ред. И.П. Норенкова. - М. :Радио и Связь, 1986. 368 с.

2. Амелио Г.Ф. Рынкам 90-х годов требуется микросхемы, удовлетворяющие специальным требованиям заказчика//Электроника 1993 . 11-12 с.7-8.

3. Андрюхин А.И Оптимизация времени построения тестов.// Электронное моделирование. 1996.18,№5. с.71-72.

4. Бадулин С.С., Барнаулов Ю.М., Бердышев В.А. и др.; Автоматизированное проектирование цифровых устройств // под ред. С.С.Бадулина.- М.; Радио и Связь, 1981.

5. Берски Д. Цифровые ИС 1990-х годов: почти неограниченные ресурсы на кристалле // Электроника, N2. 1990. с. 29 - 39.

6. Биргер А.Г., Использование отношения подобия между неисправностями при построении проверяющих тестов цифровых устройств // Автоматика и телемеханика. 1977. N 9, с. 150 - 157.

7. Богословский В.В., Криворушко В.М., Левицкий Д.ОА Метод сверхбыстрой оценки полноты логико-динамических тестов СБИС\\ Известия вуз. Электроника №3-4, 1997. с. 93-98.

8. Буиза Джефри., Кофман Гордон., Томсон Эд. Основные направления развития автоматизации проектирования в 1990 годах.// Электроника. 2. 1990. с. 39-43.

9. Бьюлоу Фред. Верификация проектов: каков объем моделирования можно считать достаточным.// Электроника. 12 13. 1990. с. 38-44.

10. Ю.Горяшко Л.П. Синтез диагностируемых систем вычислительных устройств// М: Наука, глав. ред. физ.мат. лит., 1987.

11. Гробман Д.Н. Статистический способ определения полноты тестов// -в кн. Проектирование и контроль логических схем и устройств.// ИНЭУМ, труды института, вып.76, М. 1979.

12. Алгоритм ускоренного моделирования неисправных логических схем / Г.В.Зизин, Е.В.Марцинковский, В.Е.Межов, В.Н.Харин // Автометрия. 1989. т.З. с. 54-57.

13. Исследование и разработка методов и алгоритмов автоматизированной генерации тестов проверки ТЭЗ'зов / Отчет по НИР "Турнир // НПО "Электроника". У11759. Воронеж. 1986.107

14. Исследование и разработка алгоритмов и экспериментальных программ для специализированного процессора моделирования// Научнотехнический отчет по НИР ТРОПИК 1988 г. У42917.

15. Исследование и разработка алгоритмов и экспериментальных программ для специализированного процессора логического моделирования / отчет по НИР "Тропик"// НПО "Электроника" N У42917. Воронеж. 1988.

16. Киносита К., Асада К., Карасу О., Логическое проектирование СБИС // -М; Мир. 1988. 309 с.

17. Костелло Д.Б. Следующее развитие САПР электроники: общее ускорение процессов проектирования и электроники// Электроника. 1992. V. 11-12. с. 44-46.

18. Коробков А.И., Степанюк А.Е., Шагурин И.И Определение длины псевдослучайного теста комбинационной части БИС с помощью структурных описаний./.// Микроэлектроника 1996 - 25.,№2. с. 166 - 168.

19. Коул Б.К. Повышение плотности упаковки вентильных матриц в рамках 2-хмикронной технологии. // Электроника. 3. 1989 г. с.49-52.

20. Коробков А.И., Павлов М.Ю., Шагурин И.И Методы и средства повышения тестируемости цифровых БИС. // Изв. Вузов. Электроника 1997- №3-4 с. 8592

21. Креницкий А.П. Информационные среды САПР дискретных систем III Методы кибернетики и информационные технологии 1997 -№2 с.110.

22. Методы и средства диагностирования КМОП БИС/ Под.ред. В.М. Криво-рушко М.; Радио и связь, 1993. 240 с.

23. Куфлева И.Б., Евтушенко Р.В Синтез проверяющих тестов для недетерминированных автоматов относительно редукции.,// Автоматика и вычислительная техника. 1998 №3. с.10-20.108

24. Люлькин А.Е. Структурный метод построения тестовых последовательностей для K-МОП интегральных схем// Микроэлектроника. 1995. 24. №2. с.150-155.

25. Левов Ю.А., Межов В.Е., Чевычелов Ю.А., Кононыхина H.A., Система ускоренного проектирования БИС.// Электронная промышленность. 4-5. 1994. с. 96-98.

26. Межов В.Е., Чевычелов Ю.А., Зизин Г.В.и др. Принципы и алгоритмы направленной генерации тестов в системе "Працис-ТМ"// Автометрия . 1989. т.4. с. 56-59.

27. Межов В.Е., Зизин Г.В. Язык модульного описания интегральных схем // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. трудов Воронеж. ВГТУ. 1999. с.72-76.

28. Лопатин B.C., Межов В.Е., Чевычелов Ю.А., Горохов A.B. Программное обеспечение системы ускоренного проектирование БИС.// Электронная промышленность. 4-5. 1994. с. 99-100.

29. Люлькин А.Е К тестовой проверке логических схем на K-МОП элементах.// Микроэлектроника -1996 -25 №2- с. 139-142 .

30. Маклауд Дж. Сверхскоростные средства моделирования и имитаторы, значительно упрощающие отказ от моделирования.// Электроника. 1988. N11.C.12- 13.

31. Маклоуд Д. Интегрированный комплекс программных средств SYSTEM HILO фирмы GENRED, обеспечивающий моделирование и разработку тестов.//Электроника. 12 13. 1990. с. 124-126.109

32. Маклоуд Д. Новый имитатор, позволяющий быстро моделировать схемы с ошибками.//Электроника. 12 13. 1990. с. 121-124.

33. Малиньяк JL Дальнейшее расширение функциональных возможностей САПР. // Электроника 11-12. 1991. с. 15-31.

34. Мангир Т.Э. Источники отказов и повышение выхода годных СБИС. ТИИЭР 1984 .т.72. N6. с. 36-56.

35. Межов В.Е., Зизин Г.В. Подсистема ускоренной верификации тестов // Интеллектуальные информационные системы: Тез. докл. науч.-техн. конф. -Воронеж: ВГТУ, 1999. с 43.

36. Подсистема ускоренной верификации тестов «УВЕРТ» / В.Е.Межов, В.Н.Харин, Г.В.Зизин, Е.В.Марцинковский // Эффективность, качество и надежность систем «человек-техника»: Тез. докл. IX симпозиума. Воронеж: ВПИ, 1990, Ч.П. с.105-106 .

37. Межов В.Е., Чевычелов Ю.А., Бочаров О.С. Построение функционально-логической модели объекта проектирования.// Оптимизация и моделирование в автоматизированных системах. Межвуз. сб. научных тр. Воронеж -1995.-c.63 -67.

38. Межов В.Е., Чевычелов Ю.А., Сергеев Б.С. и др. Микропроцессорные вычислительные средства для построения САПР и информационных управляющих структур.//Воронеж. 1996. с. 256.110

39. Нисков В.Я. Перспективы создания полузаказных УБИС на 1 миллион логических вентилей.// Электронная промышленность N4-5 1994. с.28 34

40. Ноткин Р.Г. Об одной задаче, возникающей при построении контролирующих тестов для логических сетей // Автоматика и телемеханика. 1975. N6. с.126-131.

41. Петренко В.И., Лошаков И.Н., Тотельбаум А.Я., Шрамченко Б.Л. Автоматизированное проектирование СБИС на базовых кристаллах // М.; Радио и связь. 1988.

42. Пол Р. Метод быстрой оценки неисправностей, упрощающий построение тестовых векторов.// Электроника. 1990 N6 с. 75-82.

43. Разработка и внедрение программного обеспечения логического моделирования ТЭЗ'ов с помощью отраслевого комплекса "Кулон-3"// Отчет по ОКР "Транзит-77 НПО "Электроника", У01479. - Воронеж, 1984.

44. Разработка и внедрение программного обеспечения автоматизированной генерации тестовых последовательностей проверки цифровых схем с помощью ИГС "КУЛОН-47: отчет ОКР Турнир"/ НПО "Электроника". У24244, Воронеж, 1986.

45. Разработка и внедрение программного обеспечения ускорителя логического моделирования // научно технический отчет по ОКР ТРОПИК-1. 1990 г. ГУ 11092.

46. Разработка программ автоматизированной генерации тестов крупногабаритных ТЕЗ'ов с применением МАБИС и микропроцессорных наборов с помощью ИГС "Кулон-47 Отчет по ОКР "Турнир-27 НПО "Электроника"; У37201. Воронеж. 1988.

47. Романенко Ю.А Организация функционального диагностирования сложных объектов на базе динамических тестов.// Информационные технологии в проектировании и производстве 1996. №364 - с.53-59 .

48. Романкевич A.M., Гроль В.В. Метод построения тестопригодных цифровых схем, ориентированных псевдослучайное тестирование./ //Электронное моделирование 1996 - 18,№5 - с.29-33.

49. Румянцев В.В Современные аспекты автоматизированного проектирования и производства БИС и СБИС./.// Изв. С-П элект-тех. Института. 1992 № 448 -с. 34-38.1.l

50. Рындин A.A., Межов A.B., Зибров A.A. Универсальная информационная среда проектирования для создания интегрированных САПР БИС // Вопросы радиоэлектроники. Серия ЭВТ. Выпуск 2. 1994. с. 51-56.

51. Рындин A.A., Чевычелов Ю.А., Межов A.B. Развитие графических средств системы ускоренного проектирования БИС // Высокие технологии в технике и медицине: Межвузовский сборник научных трудов МУВТ. -Воронеж, 1994. с. 27-31.

52. Скобцев Ю.А., Скобцев В.Ю. Система логического моделирования и генерации тестов АСМИД -П.,\\ Управляющие системы и машины. 1996- № 1-2. с. 39-45.

53. Сергеев A.A. Алгоритм выделения повторного сходящихся и циклических путей в схемном графе // "Вопросы радиоэлектроники". 11, с. 86-91.

54. Смирнов А.А Автоматизация расчетов показателей надежности БИС.// Современные проблемы радиотехники, электроники и связи: Науч. тех. конф. Минск 4-5 мая 1995. с. 406.

55. ФлоресИ. Структура и управление данными// М. Финансы и статистика. 1982.

56. Фролкин В.Е., Мощняга В.Г., Тихомирова Е.М., Гындя С.И. Аппаратные ускорители новый инструмент логического моделирования БИС// Зарубежная электроника, 1990, N6. с. 23-25.

57. Чевычелов Ю.А., Золотарев С.Н. Минимизация стоимостной функции в задачах генерации тестовых последовательностей. // Меж. вуз. конф. "Экс112тремальные задачи и их приложения". Тез.док. Н. Новгород. Н.Новгородский Госунивер. июль 1992.

58. Чевычелов Ю.А., Марцинковский Е.В. Алгоритм моделирования неисправностей // Оптимизация и моделирование в автоматизированных системах. Межвуз. сб. научных тр. Воронеж 1995 г с.58 62.

59. Чевычелов Ю.А., Марцинковский Е.В. Повышение эффективности САПР логического проектирования цифровых схем // Математическое обеспечение высоких технологий в техническом образовании и медицине. Тез. Док. Всеросс. совещание семинар, с. 16 - 17.

60. Чу наев В. С Логические .параметрические неисправности в комбинационных структурах БИС./.// Микроэлектроника 1993. 22. №1. с. 61-71.

61. Электроника СБИС. Проектирование микроструктур. Под ред. Айнс-прукаН.М. Мир. 1989.

62. Ярмольник В.Н., Янушкевич А.И., Карловски М.Г Iddg тестирование итерационных структур, реализованных на К-МОП - логике/.// Микроэлектроника - 1997 - 26, №2 - с. 151- 155.

63. Armstrong D.B. A deductive method for simulation faults in logic circuits // IEEE Trans. 1972. - C-21. №5. -p.464.

64. Abadir Hagdy, Kapur Rohin Cost driven ranking of memory elements for partial intrucsion // IEEE Desm and Test Comput -1997 - 14, №3 p.45-50.

65. Aitcen Robert C. Modeling the unmolable: Algorithmic fault diagnostic/.// IEEE Des. End Test Comput, -1997 -14, №3. p. 98-103.

66. Agrawal V.D., Jain S.K. Statisticall Fault Analisis// IEEE. Design\& Test, Feb. 1985. p 38-44.

67. Agrawal V.D., Seth S.C., Agrawal P. Proc. Des. Autom. Conf,. 18th, Nfshville,Tennesse, p. 196-203, 1981.

68. Brgles F.,Pownal P., Hum R. Applicapions of testability analysis:from ATPG to critical delay path tracing // Proc. Int. Test Conf. Philadelphia. 1984 p. 705712.

69. Breuer M.A. and Friedman A.D. Diagnosis and Reliable of Digital Systems. // Ch.4, Computer Seience Press 1976 .

70. Braynt R.E. A switch level model and simulator for MOS digital system // IEEE Trans. Comput. vol. C-33, p.160 - 177. feb. 1984.113

71. Chapell S.G., Chang H.Y., Elmendort C.H., Schmidt L.D. A comparison of parallel and deductive simulation techniques // IEEE Trans. 1974 C-23. N 11., p. 1132- 1139.

72. Chen Pao Chuan и др A direcded seach test generation system per sequotial cicuits./.// Proc. Nat. Sci. Counc. Repabl. China. J Phys/ Sci and Eng. - 1992-16. №1- p. 55-62.

73. Gening P. Fault simulation strives for designer acceptence comput.// Design. Jan. N 1,1987.

74. Goel P., Rosales B.C. PODEM-X: An Automatic Test Generation SYSTEM for VLSI Logic Structures. 18th Design Automation Conference. 1981. p. 260 -268.

75. Goel P. An implicit enumeration algorithm to generate test for combinational logic circuits // IEEE Trans. Comput.-1981, C-30. March . p. 215.

76. Goldstein L.H. Controllability/observability analisys of digital circuits // IEEE Trans, on circuits and syst., v.cas-26, n 9, p. 685 -693, sept. 1979.

77. Fujiwara H., Toida S. The complexity of fault detection by approach to design for testability // In proc. 12.TH.INT.SYMP. Fault tolerant compit, june 1982. p.101 108.

78. Fukazawe Yoshivo., Tanno Masaaki, и др Система проектирования БИС с контролируемой тестируемостью.// NTTR. J.- 1995- 44№11 р.129-134.

79. Hideo Fujiwara, Takeshi Simono On the acceleration of the test generation algorithm // IEEE Trans.Comput>-1983-c-32 N12 -p.l 135.

80. Hurrcey Brian T. Hoys John PTesting IC's: Getting the cove the problems// Computer -1996 -29,№11, p.32-33.

81. Langschert Thomas. Die Zeit ist keits Formle Verikation als Wunderwaffe // Elektron/ Ind. 1998. 29. №2. p.60, 62, 64.

82. Lattin W. VLSI design methodology: the problem of the 80's formicroproc-essor design. // Proc. 16th Design Automation Conf.(San Diego.CA) p. 548549. June 1979.

83. Lisanke R., Brgles F., Degeus A.J., Gregory D. Testability-Driven Random Test-Pattern Generation// IEEE TRAN. ON COMPUTER DESIGN. VOL.CAD-6 NO 6 NOVEMBER 1987. p. 1087-1807.

84. Mc.Cluskey E., Clegg E.W. Fault equalence in combinational logic networks // IEEE Trans. 1971,v.C-20, N 11, p. 1286- 1293.114

85. Min Y., Su S. Testing functional faults in VLSI. // 19th Des. Auto. Conf. Proc., 1982.

86. Miranda Jose M A BIST and boundary scan economics framework.//Des. And Test Comput -1997 -14. №3. p. 17 - 23.

87. Monachino M. Design Verification System For Large-Scale LSI Designs // AGM IEEE 9th Des. Autom. Conf. Proc.(Las Vegas, Juni 14-16,1982) p. 8390.

88. Nachman Zama h ap A novel approach to random pattern testing of sequential circuits //IEEE Trans. Comput 1998 - 47.№1. p. 129-134.

89. Patel S., Patel J. Effectiveness of heuristics measures for automatic test pattern generation // IEEE. Proc. 23rd Design Automation Conference, p. 547 552 .

90. Roadnop Mulady T. TEST equipment and SIA.// Solid-State Tecnol.-1996-39 №2. p.52, 54, 57.

91. Saladha A., Brayton R. Equivalence of robust delay-fault and single stuckfault test generation. // Proc. of Design Automation Conf. 1992. - p. 173-176.

92. Sevendel Y.H., Menon P.R. Fault simulation methods extentions and comparison // Bell system technical JornaL, USA, 1984, NOV, V.60, N 9, p. 2234 -2258.

93. Stual Donald h ap Diagsing IC faultries in a fast enviroment/.// IEEE Des. And Test Comput/ 1997 -14,№3 p.70-75.

94. Tang B., Munich S. Benchmarking steers logic simulation selection // Computer Design. 1986, V.25,N10, p. 69-73.

95. Tatatvy Sherin. VLSI Prafsysteme fur die Fertigung. Productonic/ 1994. 14. №10. p. 40, 42, 44.

96. Turino Jon. Test economics in the 2Istcentury / // IEEE Des/ and Test Comput-1997. 14. №3. p. 41-44.

97. Ulrich E. Conçurent simulation at switch, gate and registerlevels. // Proc.Int. Conf. Filadelfia, PA.Nov.l985.

98. Ulrich E. Exclusitive simulasion of activity in digital networks.// COMM.ACM.VOL 12,- 1969 p. 102-110.

99. Vallet David P. IC failure analysis: The importent of test and diagnostics // IEEE Des and Test Comput/ 1997- 14. №3. p. 76-82.

100. VHDL/Verilog synthesys adds boundary SCAN // Electron/ENG (Gr. Brit.). 1994. 66. №813. C5/ 12.115

101. Williams T.W., Brown N.C. IEEE Trans. Comput. C-30 987-988 1981.

102. Williams T.W.,Parker K.S. Testing logic network and design for testability // IEEE Trans, Comput. v. 12, N 10 p. 9 -19. 1979 .

103. Xe Xin Hua, Gone Yunrhan STG based verification and test genaration // J. Electron China - 1996 - 13,№1 - p. 68-73.

104. УТВЕРЖДАЮ» директор ОАО «ОКБ;ПР"ОЦЕССОР», к.т.н.

105. B.C. ЛОПАТИН ■;V-<< 199вг:1. АКТвнедрения пакета программ автоматизированной генерации тестовых последовательностей и верификации сложных цифровыхсхем

106. В ОАО «ОКБ ПРОЦЕССОР» внедрен и используется пакет программ автоматизированной генерации тестовых последовательностей и верификации сложных цифровых схем, разработанный в рамках ОКР «Турнир -2», ответственный исполнитель ведущий инженер Зизин Г.В.

107. По качественным показателям пакет программ находится на уровне лучших зарубежных пакетов для ЭВМ типа DEC, совместимых с ними и ПЭВМ типа ЮМ PC и совместимых с ними.

108. АКТ О ВНЕДРЕНИИ в учебный процесс Воронежской государственной лесотехнической академии результатов научной работы соискателя кафедры Вычислительной техники Зизина Г.В.

109. Комиссия в составе: председателя доктора технических наук, профессора Межова В.Е.,доктора технических наук, профессора Чевычелова Ю.А., доктора технических наук, профессора Зольникова В.К. установила, что

110. Председатель комиссии д.т.н., проф. Члены комиссии: д.т.н., проф.д.т.н., проф.

111. В.Е. Межов Ю.А. Чевычелов В.К. Зольников

112. УТВЕРЖДАЙ" Д и р е к т а^МШЬгЗ-л е к т р о н н о йтонких1. АКТзнедрения з НИИ электронной техники подсистемы моделирования и генерации тестов проверки схем и блоков биполярных МАБИС "ПРнЦйС 1йй'

113. Опытная эксплуатация подсистемы позволяет сделать вывод о том, что ее внедрение позволит сократить сроки проектирования СБИС в 1,5-2 раза.

114. Ожидаемый годовой экономический Эффект от внедрения подсистемы "ПРАЦИС 100" составляет 5-13 млн. руб. (в ценах 1994 года).начальник отделав. п.2. ¿¿ЭУ.