автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Метод и средства проектирования самосинхронных схем

РГЗ 00

1 5 МАИ 1233 САНКТ-ПЕТЕРБУРГСКИЙ

ГОСУДАРСТВЕННАЯ ЭЛЕКТРОТЕХНИЧЕСКАЯ УНИВЕРСИТЕТ

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

Карпов Сергей-Альбертович

МЕТОД И СРЕДСТВА ПРОЕКТИРОВАНИЯ САМОСШХРОННЫХ СХЕМ

Специальность: 05.13. 05 - Элементы к устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

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

Работа выполнена в Санкт-Петербургском государственном электротехническом университете.

Научный руководитель -доктор технических наук профессор ВАРШАВСКИЙ В. И.

Официальные оппоненты: доктор технических наук профессор ГЕРАСИМОВ И. В. . кандидат технических наук вед. науч. сотр. СТАРОДУБЦЕВ а А.

Ведупря организация - Уфимский государственный

авиационный технический университет

Защита диссертации состоится " " 1ддз г.

б /4 часов на заседании специализированного совета К 063.35.04 Санкт-Петербургского государственного электротехнического университета по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан " ^.е^Ьрс*^? 1993 г.

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

ЮРКОВ ¡0. В.

- 1 -

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

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

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

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

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

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

Отмеченные достоинства предопределяют расширение области использования самосинхронных схем, особенно при разработке СБИС-систем и схем на пластине.

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

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

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

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

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

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

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

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

Нуждаются в совершенствовании и средства автоматизированного проектирования самосинхронных схем.

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

синхронных схем.

Достижение поставленной цели предполагает решение следующих

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

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

3) разработка методик!! логического проектирования самосинхронных схем, включающей использование средств ввода графических описаний и средств автоматизированного ведения библиотек.

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

Научная новизна проведенных исследований состоит в том, что:

1) дано формальное определение и исследованы особенности множества переменных, проекция СГ на которое является достаточной для получения собственной функции элемента схемы;

2) доказано свойство корректности проекции корректного СГ, являющееся необходимым и достаточным условием перехода от проекции СГ к эквивалентной частичной ДП;

3) создан и теоретически обоснован метод синтеза самосинхронных схем по СГ более эффективный в ряде приложений по сравнению с существующими методами синтеза.

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

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

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

- использование разработанной методики проектирования самосинхронных схем позволяет повысить эффективность проектирования схем высокой сложности в среде САПР FORÇAGE,

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

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

Апробация работы. Результаты диссертационной работы- докладывались и обсуждались на следующих конференциях и семинарах:

- всесоюзной конференции "Локальные сети ЭВМ для автоматизации научных исследований и управления производством", Севастополь, 17-18 сентября 1990 г;

- международном семинаре "Территориальные информационные сети" (КОМПАК-91), Рига, Латвия, 15-17 октября 1991 г;

- научно-техническом семинаре "Применение персональных ЭВМ в проектировании и технологии", ДЦНТП, Санкт-Петербург, 30-31 октября 1991 г;

- научно-технических конференциях профессорско-преподавательского состава СПб ТЭТУ, Санкт-Петербург, 1990-1992 г.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами, заключения и списка литературы, включающего 101 наименование. Основная часть работы излогкена на 150 страницах машинописного текста. Работа содержит 41 рисунок, 5 таблиц.

IÎ. КРАТКОЕ■СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность разрабатываемой те-

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

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

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

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

si'- Fi(zlf... ,zi,... ,zn), где zl,... zn -значения сигналов входах i-ro элемента, zi'- "новое" значение сигнала, которое должно появиться на выходе i-ro элемента, fi - булева функция, реализуемая i-ткм элементом (собственная функция элемента).

В модели Маллера принимаются следующие предположения относительно характера задержек: 1) элемент схемы обладает инерци-альной задержкой, произвольной, но конечной величины; 2) собственная. задержка элемента приведена к его выходу; 3) разброс величин задержек в проводах после разветвления пренебрежимо мал по сравнению с задержками элементов. Совокупность перечисленных предположений принято называть гипотезой Маллера.

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

Проведенный обзор двух основных классов моделей - моделей б "глобальных состояниях" (ДП, кумулятивная диаграмма) и событийных моделей (сети Петри, Signal Transition Graph, диаграмма изменений), применяемых для спецификации самосинхронных схем, позволил выявить модель обладающую существенными преимуществами перед другими. Такой моделью является диаграмма изменений (ДИ).

Модель ДИ основана на двух типах причинно-следственных связей между событиями, происходящими в схеме. Событие Ь сильно следует за событием а (а -> Ь), если Ь не может произойти без реализации а. Событие сЗ слабо следует за с (с!-й), если с является причиной й, но с! колет произойти и без с. С каждым событием связывается изменения сигнала на выходе некоторого элемента схемы - имя сигнала, знак изменения ("■+" если переключение происходит из 0 в 1 и "-" в противном случае) и, возможно, номер изменения сигнала.

Начальное состояние ДИ задается посредством указания инициально- активных связей между событиями.

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

Известно, что необходимым и достаточным условием существования самосинхронной-схемы, соответствующей заданному СГ, является корректность СГ. Корректным называется СГ, удовлетворяющий следующим условиям:

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

2) среди множества достижимых событий нет автоконкурентных событий - одновременных событий с одним именем сигнала;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предложена следующая схема определения базиса проецирования: 1) по заданному СГ строятся покрытия единичных и нулевых наборов искомой функции, причем в зти покрытия могут входить не только простые импликанты; 2) переменные, включаемые в базис проецирования, определяются в результате попарного сравнения кубов, принадлежащих противоположным покрытиям.

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

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

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

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

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

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

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

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

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

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

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

Для формирования базовых и доминантных кубов предложена модель "опорная диаграмма". Опорная диаграмма корректного СГ определена как ориентированный граф, изоморфный М-развертке СГ, вершинам которого поставлены в соответствие опорные состояний -двойки вида <В(аО;Р-(аО>, где В(аО - базовое состояние, а Р-(аО - кумулятивный код параллелизма события а1 М-развертки.

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

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

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

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

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

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

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

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

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

Разработаны способы построения базисов проецирования I и II рода для синтеза несамозависимой формы функции.

Итогом проведенного исследования является предлагаемый метод синтеза самссинхронных дистрибутивных схем, включающий следующие основные зтапы: 1) анализ свойств корректности и хорошей сформированности заданного СГ и коррекция СГ при нарушении указанных свойств, 2) построение опорной диаграммы, 3) вычисление базисов проецирований искомых функций, 4) построение проекций ДП по исходному СГ ri поиск тупиковых форм функций, 5) формирование модели Маллера схемы ка основе полученных тупиковых форм.

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

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

Известная САПР самосинхронных схем FORÇAGE обладающая существенными преимуществами перед другими существующими средствами автоматизированного проектирования самосинхронных схем. Основными компонентам! САПР FORÇAGE являются:

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

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

Ряд недостатков САПР FORÇAGE, к которым можно отнести:

- недостатки языков описания входных объектов (цифровых схем и диаграмм изменений);

- отсутствие средств автоматизированного ведения библиотек;

- недостаточность средств логического проектирования, значительно снижают эффективность проектирования в среде данной САПР.

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

тов. За основу при разработке средств ввода графических описаний для САПР FORÇAGE выбран графический схемный редактор PCAPS из пакета САПР FORÇAGE. Для преобразования файлов графических описаний, формируемых с помощью схемного редактора FCAPS, в файлы описаний на входных языках САПР FORÇAGE была разработана подсистема преобразования.

Подсистема преобразования реализует алгоритм, состоящий из двух этапов. На первом этапе файл графического описания преобразуется в текстовый файл в формате PDIF (PCAD DataBase' Intercange Fonrat) схемной модификации. Такое преобразование выполняется с помощью утилиты транслятора PDIF-0UT, входяшэй в пакет САПР PCAD. На втором этапе на основе информации, содержащейся в полученном текстовом файле, формируется файл описания на одном из входных языков САПР PCAD.

Включение подсистемы преобразования в состав САПР FORÇAGE, позволяет использовать средства САПР PCAD, а именно - графический схемный редактор PCCAPS и утилиту PCLIB, для автоматизированного ведения библиотек в САПР FORÇAGE.

Рассматриваются принципы построения и способы организации двух основных классов библиотек в САПР FORÇAGE - библиотеки самосинхронных схем и библиотеки поведенческих спецификаций.

Реализованный интерфейс между САПР FORÇAGE и САПР PCAD позволяет использовать в процессе проектирования самосинхронных схем некоторые традиционные средства логического проектирования из состава САПР PCAD для выполнения логического моделирования, синтеза тестов, формирования таблиц цепей и т.д.

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

Включение в состав САПР FORÇAGE новых средств проектирования и сложность самого процесса проектирования привели к необходимости сознания методики логического проектирования самосинхронных схем, призванной обеспечить эффективность проектирования в среде САПР FORÇAGE. Разработана методика логического проектирования самосинхронных схем с использованием рассмотренных средств проектирования и включающая из процедуры нисходящего и восходящего проектирования. Отличительная особенность данной мето-

- 15 -

дики - ориентация на разработку сложных схем.

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

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

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

III. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6. Разработаны средства ввода графических описаний входных объектов и средства автоматизированного ведения библиотек для САПР самосинхронкых схем FORÇAGE.

7. Предложена методика логического проектирования самосикх-

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

По материалам диссертации опубликованы следующие работы:

1. Волков Д. В., Карпов С. А. Интерфейс системы автоматизированного проектирования FORÇAGE с САПР PCAD // Применение персональных ЭВМ в проектировании и технологии: Материалы научно-технического семинара/ Под ред. _Б. К Деньдобренко, Санкт-Петербург, 30-31 OKT. 1991. - СПб, 1991.- С. 53-55.

2. Волков Д. В., Карпов С. А. Организация отказоустойчивого интерфейса слабосвязной многопроцессорной вычислительной системы //Изв. Ленингр. элактротехн. ин-та им. В. И. Ульянова (Ленина): Сб. науч. тр.- Л, 1991. - Вып. 435. - С. 88-92.

3. Отказоустойчивый интерфейс многопроцессорной вычислительной системы с архитектурой типа кольцевой моноканал / Д. В. Волков, Е Я. Володарский, С. А. Карпов, В. В. Мараховский // Территориальные информационные сети: Труды международного семинара (КОМПАК-91), Рига, 15-17 окт. 1991.- Рига, 1991. - С. 130-132.

Подп. к печ. 22. 02. 93 Формат 60 х 84 1/16.

Офсетная печать. Печ. л. 1,0; уч.-изд. л. 1,0. Тираж 100 экз. Зак. N Бесплатно

Ротапринт ПО - 3 "Ленуприздата" 191104, Саккт Петербург, Литейный пр. , дом 55