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

Санкт-Петербургский Государственный Институт Точной Механики и Оптики (Технический Университет)

На правах рукописи

Денисова Эльвира Викторовна

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

НА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОМ УРОВНЕ

Специальность 05.33.22 - Системы Автоматизации Проектирования

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 1998

Работа выполнена в Санкт-Петербургском Государственном Институте Точной Механики и Оптики (Техническом Университете)

Научный руководитель: профессор, доктор технических наук

Немолочнов Олег Фомич

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

Фомичев Владимир Степанович

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

Ведущее предприятие: ОКБ «Электроавтоматика»

Защита диссертации состоится «\1» циарто- 1998 года в {5 часов 20 минут на заседании Специализированного Совета К.054.26.04 при Санкт-Петербургском Институте Точной Механики и Оптики (ТУ) по адресу: 197101, Санкт-Петербург, улица Саблинская, дом 14.

С диссертацией можно ознакомиться в библиотеке института. Автореферат разослан «.-/-У» 1998 года.

Ученый секретарь Специализированного Совета К054.26.04

А

¡и>ь* ^ доцент,

кандидат технических наук Поляков Владимир Иванович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

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

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

Элементы ЦУ на структурном уровне и уровне межрегистровых передач отличаются степенью детализации, но имеют ряд общих характерных особенностей, позволяющих разработать единое математическое, программное и информационное обеспечение САПР. Такими особенностями являются: функциональная завершенность;

закон функционирования включает множество арифметических и логических операций;

фиксированное число внешних контактов.

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

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

• контроль и управление ходом проектирования в зависимости от результатов;

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

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

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

Таким образом, для организации интерактивного проектирования тестов для ЦУ необходимо:

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

• разработать дедуктивный метод анализа полноты тестов на функциональном уровне представления ЦУ и программное обеспечение, реализующее данный метод в рамках единой САПР;

• разработать методику проектирования тестов в интерактивном режиме;

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

Методы исследования. При выполнении работы использовались математический аппарат теории графов, методы математического моделирования, методы структурного программирования, теория построения САПР.

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

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

• разработана многоуровневая система функционально-логического моделирования, ориентированная на широкий класс ЦУ на основе БИС;

• разработана подсистема интерактивного проектирования тестов.

Внедрение результатов. Система САПР-ПМ используется в СПбГИТМО для выполнения лабораторных работ по курсу «Автоматизация логического проектирования ЭВС» для студентов специальности 2205 - «Конструирование и технология ЭВС».

Апробация работы. По материалам диссертации сделан доклад "Вопросы

верификации заказных БИС методом технической диагностики" на конференции "ИСАПР-94", Таганрог, 1994г. и доклад на XXIX научно-технической конференции профессорско-преподавательского состава ИТМО, секция «Вычислительная техника и программирование», СПбГИТМО, 1997г..

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 41 наименования, содержит 125 страниц основного текста, 13 рисунков, 12 таблиц и 4 приложения.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ.

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

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

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

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

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

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

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

Обосновываются основные требования к системе моделирования, предназначенной для иерархического проектирования ЦУ:

• обработка ЦУ, построенных на основе ИС различной степени интеграции;

• возможность перехода от одного уровня описания ЦУ к другому в пределах функционального уровня представления.

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

Во второй главе определяется понятие макроэлемента, приводится математическая модель макроэлемента. Макроэлементами назовем минимальные, неделимые подсхемы, используемые в САПР. Исследуемо ЦУ представим в виде совокупности макроэлементов и списка связей макроэлементов между собой. Удобной формой такого представления может быть схемный список.

Макроэлементы представляют собой подсхемы с одним выходом и множеством входов. Входы и выход могут быть векторными. Цифровая схема может быть выбрана в качестве макроэлемента, если ее состояние на ¡-ом наборе однозначно определяется множеством входных слов Х={Х|,...,Х|<}, где к-число входных слов и выходным словом Макроэлемент характеризуется следующими параметрами:

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

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

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

Машинная модель представляет собой файл, который будем называть файлом схемы и в котором собраны воедино все массивы, составляющие структуру данных

для представления в САПР. В разработанной САПР-ПМ в качестве удобного средства исходного описания ЦУ используется три пакета системы PCAD:

• PC-CAPS - для проектирования электрических схем (файл с расширением «.sch»);

• PC-NODES - для извлечения списка связей из графического образа электрической схемы (файл с расширением «.nit»);

• PC-FORM - для формирования текстового описания схемы на уровне списка компонентов и связей между ними (файл с расширением «.сшр»).

Для проектирования ЦУ нужно иметь следующую техническую документацию и программное обеспечение:

• техническое задание на проектирование ЦУ (логическую схему ЦУ на уровне элементов логического базиса);

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

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

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

Интерактивный режим предназначен для работы на уровне макроэлементов. В машинной модели ЦУ каждому макроэлементу присваивается уникальный номер, по которому можно определить характеристики макроэлемента и его расположение в схеме, .Диалоговый режим в системе проектирования тестов используется в следующих двух вариантах: 8

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

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

применяется для анализа готовых тестов, либо ручного (неавтоматического) синтеза новых тестов.

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

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

• проверяет ли тест заданное множество неисправностей из выбранного класса. В этом

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

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

Основным методом решения первой задачи является моделирование. В исправную схему вносится требуемая неисправность и выполняется моделирование исправной и неисправной схемы. Анализ полученных результатов позволяет сделать вывод о проверке данной неисправности.

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

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

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

синхронизирующих векторов; > реализация функциональной зависимости, заданной управляющим вектором, над

информационным вектором; » распространение полученного результата до выхода схемы при соответствующих значениях управляющих и синхронизирующих векторов. Каноническая схема макроэлемента показана на рис. 1.

Рис. 1. Каноническая схема МЭ. 1П - информационный вектор; 1у - управляющий вектор; 1с - синхронизирующий вектор; Ср - блок, позволяющий разбить 1„ на поля, каждое из которых может участвовать в

качестве параметра при вычислении блоком ¡=1,...,п£ где - число реализуемых функций макроэлемента; Рь Рг—, Ре - параметры выполняемой функции. Блок Би вырабатывает на выходе сигнал разрешения выдачи информации Ш для блоков а блок С - сигналы с, для стробированияШ. Блок задержки А позволяет вычислить новое значение выхода с учетом предыдущего выходного значения Ог'. Каноническая схема является математической моделью макроэлемента.

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

• неисправность схемы проверяется только в том случае, если она транспортируется до внешних выходов ЦУ, то есть должен существовать активизированный путь от

места внесения неисправности до одного из выходов схемы;

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

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

Предлагается двойной метод анализа полноты, являющийся дальнейшим развитием метода обратного прослеживания неисправностей для ЦУ на

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

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

Дедуктивный метод.

1. Метод является дальнейшим развитием метода обратного прослеживания неисправностей. Разработанный в диссертации метод позволяет обрабатывать не только комбинационные, но и последовательностные схемы.

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

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

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

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

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

Двойной метод.

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

2. Программное обеспечение включает усовершенствованную программу моделирования, позволяющую моделировать исправную схему и отдельные МЭ с зеисправностями. Программа непосредственного анализа использует в качестве [сходных данных не только результаты моделирования исправной схемы, но и информацию о транспортировке через МЭ всех возможных на данном тесте ^исправностей на его входах. Данная информация является избыточной, так как в дальнейшем в активные пути через схему включаются лишь некоторые активные :ути через МЭ.

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

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

В четвертой главе представлен монитор разработанной системы штоматизированного проектирования ЦУ САПР-ПМ.

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

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

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

Система функционирует в среде операционной системы MS DOS на персональных компьютерах типа IBM PC XT/AT и совместимых с ними. Система написана на алгоритмическом языке Си.

Система САПР-ПМ предоставляет разработчику ЦУ следующие возможности:

• выполнить все этапы проектирования ЦУ в среде САПР-ПМ;

• выполнить компоновку проектируемой схемы средствами PCADa в среде системы ;

• вывести графическое изображение схемы (элементы выводимой на экран схемы ранжируются по уровням срабатывания; различные типы элементов выводятся на экран различным цветом);

• выполнить анализ схемы (двоичное моделирование служит для проверки правильности синтеза ЦУ путем моделирования на входных наборах из единичного и нулевого покрытия на схему; троичное моделирование позволяет выявить возможный риск сбоя на выходе схемы при смене входных воздействий);

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

В приложении приводится пример использования РСАБа в рамках САПР-ПМ, для получения текстового файла, содержащего схемный список, и используемого :истемой САПР-ПМ; язык описания схемы ЦУ и синтаксис языка ввода неисправностей в схему.

В заключении сформулированы основные результаты и выводы циссертационной работы.

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

Разработаны методы и алгоритмы анализа полноты тестовых последовательностей для :хем МП БИС на функциональном уровне представления для нескольких классов неисправностей с учетом различных видов компенсаций.

Разработана многоуровневая система моделирования и подсистема интерактивного проектирования тестов, ориентированные на обработку широкого класса схем от ИС малого и среднего уровня интеграции до центральных процессоров микро-ЭВМ. В замках системы разработаны принципы сопряжения компилятивных, интерпретационных и компилятивно-интерпретационных моделей узлов ЦУ на различных уровнях представления.

Разработанные программы и структура данных повышают производительность труда

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

Результаты внедрены в учебный процесс по курсу «Автоматизация логического проектирования ЭВС» по специальности 2205 - «Конструирование и технология ЭВС».

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ.

1. Немолочнов О.Ф., Раков С.В., Денисова Э.В. Автоматизация логического проектирования. СПбГИТМО, Санкт-Петербург, 1995г.

2. доклад "Вопросы верификации заказных БИС методом технической диагностики" на конференции "ИСАПР-94", Таганрог, 1994г.;

3. доклад на XXIX научно-технической конференции профессорско-преподавательского состава ИТМО, секция «Вычислительная техника и программирование», СПбГИТМО, 1997г..