автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Графово-трассовый подход к оценке переходных процессов в ПЛИС на этапе логического проектирования

Государственный Комитет Российской Федерации по высшему образованию Московский государственный инженерно-физический институт (технический университет)

Р Г Б ОД

УДК 622:658.512.22.011.56(043.3)

На правах рукописи ГОРБАТОВА МАРИНА ВЯЧЕСЛАВОВНА

Графсво-трассовый подход к оценке переходных процессов в ПЛИС на этапе логического проектирования

05.13.05 - "Элементы и устройства вычислительной

техники и автоматики" 05.13.12 - "Системы автоматизации проектирования"

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

Москва, 1994

Работа выполнена в Московском государственном инженерно-физическом институте (техническом университете).

Научный руководитель профессор, д.т.н Першенков B.C. Официальные оппоненты: . % . - Л;

академик, профессор, д.т.н. Редкозубое С.А., 'л ' доцент, к.т.н. Метечко В. И. ^ Ведущая организация Московский государственный институт электроники и математики (технический университет) \ ; :

Защита диссертации состоится 17 октября 1994г. в 4Т час. на заседании специализированного совета IC-053.03.03 в Московском государственном инженерно-физическом институте по адресу: 115409, Москва, Каширское ш.,31. \

С диссертацией можно ознакомиться в библиотеке Московского государственного инженерно-физического института. Автореферат разослан S сен^брй 1994г.

Ученый секретарь специализированного ученого совета к.т.н., доц. * Оншценко В.М.

Подписано в печать /З-б^У Заказ ¿/f^

Типография Мй&И, Каширское шоссе, 31 \

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

Данная диссертационная работа посвящена вопросам разработки инструментальных программных средств, позволяющих оценить переходные процессы в проектируемых интегральных схемах { ИС ), и, тем самым, дать объективную оценку динамики нового проекта ИС путем его логического моделирования на базе персональных ЭВМ РС АТ. Предложенные инструментальные средства доведены до промышленного внедрения при логическом проектировании современных ИС - перепрограммируемых логических интегральных сред (ПЛИС).

Актуальность темы. В настоящее время одним из путей увеличения производительности вычислительных и управляющих цифровых систем, в том числе систем реального времени, является повышение быстродейств?1я используемых ИС, особенно ПЛИС, позволяющих эффективно использовать принцип временной декомпозиции при реализации сложных алгоритмов. Каждый элемент ПЛИС, выпускаемый в настоящее время промышленностью, представляет собой ИС, настраиваемую на любую булеву функцию от четырех переменных. Элементы ПЛИС с помощью коммуникационной структуры объединяются в интегральную среду, реализующую заданную систему булевых функций. При повышении быстродействия, время срабатывания элементов ИС становится сравнимо с длительностью ложных сигналов, возникающих из неодновременного переключения входных каналов элемента ИС ( явление риска, состязания ), что повысило опасность нарушения закона функционирования спроектированной ИС.

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

Работа выполнялась в рамках раздела 3.1 " Прикладные программные средства" комплексной целевой программы АН СССР и

Министерства электронной промышленности " Развитие программных средств для персональных ЭВМ до 2000 г. " , темы 12.9.1.1.15 " Создание элементов автоматизированного проектирования и управления горнодобывающими предприятиями " программы АН СССР исследований в области естественных наук до 2000 г., раздела 6 " Разработка теоретических основ проектирования и создания автоматизированных и роботизированных технологий добычи и переработки твердых полезных ископаемых ", федеральной научно-технической программы " Океантехника ", а так же, в рамках хоздоговорных работ.

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

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

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

Основные научные положения, разработанные лично соискателем и их новизна:

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

2. Найдены объективные условия возникновения ложной информации во время переходных процессов при переключении двух, трех,..., К вх ( К вх - входной коэффициент элемента) входных каналов выходного элемента ИС, основанные на учете функциональных свойств выходного элемента.

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

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

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

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

Практическая значимость работы состоит: • в разработке программных средств оценки переходных процессов в ПЛИС на этапе логического проектирования ( операционные модули ДИФФЕРЕНЦИРОВАНИЕ, РИСК, ТРАССА, АНТИСИНДРОМ, ПРОТИВОРЕЧИЕ, СВЯЗНОСТЬ, ЛИНЕАРИЗАЦИЯ, ОЦЕНИВАНИЕ, ВС-программа (Входная Сигнальная программа )), образующих инструментальную среду в персональных ЭВМ РС АТ, в которой успешно решаются задачи:

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

— оценки динамических свойств проекта ПЛИС на этапе логического проектирования

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

(практически на несколько порядков) времени логического моделирования динамики ИС.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на 9-м Всесоюзном симпозиуме " Логическое управление в промышленности " ( г. Ташкент, 1986 г. ), семинаре " Системные средства САПР " в Российском доме знаний ( г, Москва, 1988 г. >, 10-м - 14-м Всесоюзных симпозиумах " Логическое управление с использованием ЭВМ " г. Устинов, 1987 г., г. Орджоникидзе, 1988 г., г. Симферополь, 1989 г., г. Симеиз, 1990 г., г. Феодосия, 1991 г.). Всемирных Конгрессах ITS-92 " Information Communications, Nets, Systems and Technologies " ( г. Москва, 1992 г, ) и ITS-93 (г.Москва, 199*3).

Публикации. Основное содержание диссертационной работы отражено в пятнадцати публикациях, в том числе в двух отчетах по НИР. Структура и объем работы. Диссертационная работа общим объемом 121 страница машинописного текста состоит из введения, четырех глав, заключения, списка использованной литературы из 63 наименований, 18 рисунков, I таблицы.

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

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

-6- L

ем входного вектора, закончился. В самосинхронных схемах реализуется запрос-ответный режим (С.Ангер - 1977 г., А.Фридман -1978 г.), что и определяет их промежуточное положение между синхронными и асинхронными схемами.

Методы исследования динамических свойств, основанные на ннтег-ро-дифференцйальных моделях ( В.Н.Рогинский - 1962 г., В.И.Левин - 1975 г.), не получили практического применения и развития в силу сложности решения интегро-дифференциальных уравнений, несмотря на использование моделей конечномерной математики и ЭВМ.

Методы, основанные на моделях дискретной математики, восходят к работам Д.Хафмена (1957 г.), А.Д.Таланцева (1959 г.) и образуют три периода развития этого направления.

1-й период - 50-60 годы.

Основы теории состязаний (риска) разработаны Д.Хафменом (1957 г.), для устранения которых им предлагается введение специальных задержек (1954 г.), реализованных позже А.Фридманом (1966 г.). • Вводятся понятия "производной от булевой функции" (С.Рид, 1954 г.) и "оператор перехода" (А.Д.Таланцев - 1959 г.), позволяющие аналитически представлять условия переключения каналов в логических схемах. Оба понятия по существу определяют условия изменения значения функциональной переменной /при изменении заданной переменной д-( для булевой функции /(х/, х2.....Д7.....хп)- Понятие

производной от булевой функции получает дальнейшее развитие в работах С.Акерса (1959 г.) иД.Бохмана (1968 г.). С.Акерсом показано, что любая булева функция представима через значения собственно

функции и ее смешанных производных первого, второго...../;-го

порядка в любой точке булева пространства . Д.Бохманом найдены

условия переключения булевой функции / (х/, Х2,.... .V,-.....хп). при

переключении ее к переменных.

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

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

Условия возникновения состязаний в двухуровневых ИС сформулированы Е.МакКласки (1962 г.). Возникновение ошибки на выходном канале схемы при переключении нескольких входов рассмотрел Е.Эйхельбергер (1965 г.). Им предложено, а М.Йоели и С.Рико (1964 г.) развито, использование троичной логики при обнаружении состязаний. ■;■••'-■'. ■•.'■. .,'"' ..■','• С. у - .

2-й период - 70 - е годы. /* "./..••

Для моделирования взаимодействующих асинхронных параллельно протекающих процессов в логических схемах, стали использовать сети Петри. Сеть Петри (1962 г.), носящая имя немецкого ученого К.А.Петри, представляет собой взвешенный граф Кенига (двудольный.граф), в котором вершины одной доли взаимнооднозначно соответствуют событиям, вершины другой - условиям, при которых событие осуществляется. При схемной интерпретации сетей Петри событие соответствует функциональному элементу, условие - состоянию канала. К этим исследованиям относятся работы С.Патила и Дж:Денниса (1972 г.); М.Бленгерда, Дж.Гиллона, Дж.Кавароса и Дж.Готреза (1972г.). Недостатком сетевого подхода к моделированию логических схем является большая мощность носителя соответствующего графа Кенига и отсутствие фактических временных длительностей моделируемых событий. Дальнейшее развитие теории сетей Петри (временные сети - П.Мерлин,числовые сети - Б.Джонотан, Е-сети - П.Лауэр , Дж:Ной , Т-сети - Т.Крупа) не устранили эти недостатки.

3-й период - 80-90 -е годы.

В конце 70-х - начале 80-х годов начались разрабатываться крупномасштабные программы по созданию и моделированию больших интегральных схем (БИС). Был выдвинут тезис (Ч.Сейц. Дж.Деннис, 1980 г.) о том, что синхронный подход не в состоянии гарантировать получение работоспособных БИС в условиях субмикронной технологии, при которой величины задержек каналов больше, чем задержки сигналов на ключах (вентилях).

Для задания и верификации интегральных схем (ИС) стала использоваться темпоральная логика (Ю.Малечи , С.Овиски - 1981 г.; Дж.Бочмен - 1982г.). Былавидвинута гипотеза "трехвторых" (Б.Миш-ра, Е.Кларк - 1985 г.) - "суммарная задержка трех элементов всегда

превышает задержку двух", что ¡вызвало необходимость разработки новых методов моделирования ИС.

Кроме темпоральной логики стали разрабатываться и другие формализмы для моделирования ИС: теоретико-графовые модели, семиотические (семиологические) модели. К теоретико-графовым моделям, наряду с сетями Петри, можно отнести сигнальные графы, диаграммы изменений ( В.Й.Варшавский, 1986 г., 1988 г.), в которых вершинам -событиям ставятся в соответствие изменения переменных, а дугам -причинно-следствеиные связи между событиями.

В качестве семиотической модели следует указать на бурно развивающееся направление - теориютреисрв (М.Рем, Дж.Сне'пчит, Дж.Адинг - 1983 г.) , где под трейсом понимается последовательность символов, отражающая возможные пути в диаграммах переходов или графах . допустимых паркировок при функционировании ИС в заданной переключательной среде. Трейсовый подход: применим' на этапе экс, плуатации ИС, когда задано ее поведение. Другим подходом этого 1 направленна, который также применим на этапе эксплуатации 'ИС, является логический'подход (Д.Бохман, 1984г.). При этом подходе определяется искажение выходного сигнала ИС при заданных входных сигнальных последовательностях.

Для оценки динамических свойств ИС на ранних стадиях проектирования - на этапе логического проектирования впервые в рамках семиотического направления в диссертации введено понятие "трасса" (1986 г.) й предложен графово-трассовый подход. ,

Трассой Т(Ха,Хь) булевой функции/('Л7 называется цепь решетчатого интервала / = [Х<„ Хь] , где

у(Ха) - минимальный элемент, соответствующий вектору Ха. интервала /; ' ' ,

у(Хь) - максимальный элемент, соответствующий вектору Хь , интервала I:

(Ч\'(Х1) е/ и ( *Ха) < \<Х0) &ЫХ1) < к'(Хь))). ■при этом ; ■

/(Ха)=/(ХЬ),

/(Х0=7(ХьЦ*а,Ь

векторы Ха. Хь, XI рассматриваются как идентификаторы соответствующих вершин, а интервал [Ха, ЗД - как решетка, в которой \'(Ха) играет роль теоретике- решетчатого "0м, а \'(Хь) - "1".

Свойства трассы Т(Ха,Хь)-

- i ХаП Хь I - п - к в и-мерном булевом пространстве,

- Н(Xa,Xb) = к, Н(Ха,Хь) - расстояние по Хеммингу между точками ХанХь,

- I { Ti (Ха.Хь) } i < к !

Эквивалентная запись трассы Т(Ха,ХьУ-

Т(Ха,Хь):<->Т(ха\,ха2,—,хок),

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

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

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

В настоящее время разработаны многочисленные инструментальные программные средства : SPICE-1, SPICE-2, POWERSPIСЁ (ЭВМ VAX 1 1/780, CRAY-1, DEC-10, SX-250, Х-2000), С LASSIE (ЭВМ CRAY-1), СПРОС и другие, предназначенные для моделирования правильности логического функционирования (в статике), схемотехнического и топологического моделирования. Отсутствуют инструментальные программные средства спецификации аномальных областей при учете динамических свойств ИС, позволяющие оценить переходной процесс на этапе логического "проектирования ИС.

Рассмотрим математическое обеспечение таких средств.

Расширим гипотезу Мишры-Кларка и сформулируем ее как "Суммарная задержка к элементов всегда превышает задержку k-i, i s 1, к>2", тогда условие риска сбоя R(xat. ха2.....хак) ИС, реализующей

булеву функцию /("X) при переключении к входных каналов, определяется следующей формулой:

R(xai,xa2,-,xak) =—--- & ( 3 Са{хьх,хьъ...,хьк) е

о \Xai,Xa2,.:,Xak)

е {Ci(xix,xi2,...,XikXh,i2.....¿к) = реггп(а[,аг,...,ак), (1)

})

(-М-& . дУ &_¿£_& &_

дхьх д{хь\,хь2) д(хЬ1,::Ь2<хЬз) д{хь],хь2,...,хЬ((с-\)) где

К(хсц,хаг,.~,хак) - функция риска сбоя,

1,если возможен сбой хотя бы на одной нз к! цепей

Са(хь1,хь2.....хьк)

О— в противном случае

Я(Ха\,Ха2,---,Хак) —

Cpf

-ъ-г- производная от булевой функции /по переменным

Xa\iXa2*—,Xak, единичное значение которой указывает на изменение значения функции / при "одновременном" изменении значений переменных Xai,Xa2,.-,Xak;

3 - квантор существования,

perm(a\,ai,...,ak) - результат перестановки (permutation) индексов а\,а2,-.,ак\

переменные хь\,хь2,—,хьк попарно не равны друг другу.

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

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

Это же явление определяет логические состязания. Поэтому в дан- • ной работе виды состязаний не различаются, все они находятся с помощью формулы (1). •;.'••.;':'

С учетом вероятной "фильтрации" ошибок невыходными элементами ИС, предложена модель ИС, представляющая собой граф Сд</ = < Ум, Ым >, гомеоморфный графу С и С (каждая вершина взаимнооднозначно соответствует элементу ИС, дуга - соответствующему каналу) и. отличающийся от него наличием вершин V//,/=1,2,..., к Вх - входной коэффициент выходного элемента ИС, коинцидентных входным каналам /'-го выходного элемента ИС. Каждая вершина уд соответствует линии переменной задержки, приведенной к входным каналам/-го выходного элемента ИС. -

Тушп — Ту — Тутах • Гутт - минимальное время задержки прохождения сигнала (переключения) от входного канала ИС до /-го входного канала/-го выходного элемента ИС, определяемое соответствующей активизируемой цепью;

• Щпак - максимальное время задержки аналогичного, что и г//ш1п характера. Значение ту носит статистический характер.

Разность Д Ц,]) = ч/шах - г/утщ называется временным дебалансом ¿'-го входного канала относительно /-го выходного элемента.

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

1°. Каждому из выходных элементов И С сопоставляем корень строящегося дерева <К Г>. Вычисляем производные 1-го, 2-го, ... , -го порядков от функции^дга[,Хй| ......Та^), описывающей/-й выходной элемент ИС.

2". Каждому концу дуги, исходящей изкорня дерева сопоставляем "одновременное" переключение пары, тройки, ... , всех /свх входных каналов /-го выходного элемента И С.

Очевидно, что 1Г(уо)! -2кт -кзх - 1, где Г(уо) - сечение корня гу ■дерева. ' ••;

Определяем пары двойственных наборов

. |(ой1,ой2,...,ойр),(ой1,оа2.....оар)},

р-2, 3,. . . ,квх ; а1,02,...,ар е|сл,й2.....й*™}-.

для которых

Д-хд! .....-^«р)

и имеется хотя бы одна цепь, удовлетворяющая соотношению (1).

Решетчатый интервал 1( X а, Хь), содержащий хотя бы одну трассу Т(Ха.Хь), называется критическим. Каждому критическому интервалу сопоставляется вершина следующего яруса дерева <У,Г>. Выделяем все трассы в каждом критическом решетчатом интервале. Каждой трассе сопоставляем висячую вершину в строящемся дерене.

Для эффективного вычисления производных булевы функции /¿(х],х2,.--,хп) задаются в виде соответствующих графов Кеиига (двудольных графов). При этом исходное булево пространство размерности п представляется в виде декартова произведения булевых пространств

размерности ] (.[ ] - знак ближайшего целого) и п - ] соответственно. Каждой точке булева пространства размерности ] взаимнооднозначно сопоставляются вершины верхней доли, каждой точке пространства размерности п - ] - вершины нижней доли. Ребро

графа Кенига взаимнооднозначно соответствует точке исходного пространства размерности п, в которой функция /¡(х1,х2,—хп) принимает единичное значение. При этом вычисление производных от булевой функции /¡(х1,х2,...,хп) сводится к определению нечетности

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

3°. Определяем переключения.входных каналов ИС, порождающие переключение Ха Хъ, соответствующее критическому интервалу на входных каналах выходного элемента Бвых ИС. Для этого отображаем каждый критический интервал 1квх-[-Хв|А&| пространства Р квх размерности кВ\ в интервал Iпг[Ха',Хь'] заданного пространства Рл ( «-число входных каналов ИС).

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

Если найдется элемент В}, не обеспечивающий согласованное функционирование цепей (условия поведения элемента В] противоречивы), то соответствующий критический интервал I = [Ха,Хь] является нереализуемые, п в дальнейшем не рассматривается.

4°. Для оптимального по времени выявления всех аномалий динамических свойств ИС введем граф связности Сев:

сся = <{:<1 },и>,

в котором каждая вершина взаимнооднозначно соответствует вектору X'/, ребро {ХьХ}) - критическому решетчатому интервалу КХ^Х/),

и * £/<->/?(ВД) = 1.

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

Дл : |Пмизации времени формирования входных векторов Л'/ при моделировании необходимо отсутствие их повторения, следовательно, граф Сев должен быть гамильтоновым. Используя характеризационный анализ можно показать, что граф связности Сев эйлеров и гамильтонов тогда и только тогда, когда его цикломатическое число^(С Св ) равно нулю и его степень х(С св ) не превышает двух:

ОКСса) =0) & ( .ч(Ссв)<2)

При ЭТИХ условиях графСсв является линейно упорядочиваемым.

5°. Если, граф Сев является эйлеровым и гамильтоновым, то переходим к п.7", в противном случае, - к п.6 *.

б'.Расширением носителя {Д Xi) в графе Сев устраняем запрещенные фигуры.

Анализ графа связности для реальных ИС показал их малую связность. Учитывая это свойство, был предложен следующий эффективный алгоритм расширения носителя {Л Xi\ графа Gcb •

1) G св : = Gi.

2) s(Gi)S 2 - ?

"Да"- к п.З , "нет" - к п.4.

3) tfipi) > - О ?

"Да"- к п.4 , "нет" - к п.7*.

4) Определяем цепь максимальной длины тгтах. в пределе остов, графа Gi. !

5) Gi \ лтах : = Gi, "штрихуя" в результирующем графе повторяющиеся векторы Xi.

Переход к п.2) .

7*. Линейно упорядочиваем граф < { Xi U АXi, U >.

Формируем входную сигнальную программу (ВС-программу) для моделирования аномалий динамических свойств ИС.

8". Для оценки переходного процесса в ИС предложим чистовую характеристику в виде соответствующего функционала <p(Xi,Xj), учитывающего распределение трасс, функциональные и топологические свойства ИС и временной дебаланс активизируемых цепей ИС:

<p(Xi,Xj) = шах fe ( 2 mXuXj))• s ij

■ (Я(ВД)! Г1 • Дгтах (nXi,Xj)))s , (2)

где f(T(Xi,Xj)) - частота (количество) цепей (Xi.Xj) решетчатого интервала I=[Xi,Xj\, для которого функция риска сбоя s-oro выходного канала Rs( Xi,Xj)=l;

H(Xi,Xj) - расстояние по Хеммингу между точками Xi и Xj в булевом квxs- мерном пространстве,

Дгшах (T(Xi,Xj))s - временной дебаланс s-oro выходного элемента,

Д Гшах (T(Xi,Xj))—шах( П s шах - Тк s min ), к, s

где rjfcsniax- максимальная величина задержки сигнала при прохождении от входного канала ИС до к-го входного канала s -го выходного элемента ИС, к - идентификатор одного из переключающихся каналов выходного элемента при

Xi -+ Xj\

Tt s min - минимальная величина задержки, аналогичная т* s max ,

Atmax (T(Xi,Xj)) мажорирует длительность возможного ложного сигнала на 5-м выходном канале ИС, s=l,2,...,/n, т-число выходных каналов ИС.

. Для удобства практического применения оценка(f{Xi,Xj) вычисляется с использованием логарифмической шкалы. .

Предложенные стратегия и алгоритмы реализованы в виде соответствующих средств, включающих в себя разработанные программные операционные модули ДИФФЕРЕНЦИРОВАНИЕ, РИСК/ТРАССА, АНТИСИНДРОМ, ПРОТИВОРЕЧИЕ, СВЯЗНОСТЬ, ЛИНЕАРИЗАЦИЯ, ОЦЕНИВАНИЕ, ВС-программа.

Программные средства разработаны для ПЭВМ РС/АТ-386(486) в MS DOS с использованием языка Турбо Си. Предусмотрены сервисные средства, позволяющие объявлять выходным элементом любой элемент ИС. Разработанные программные средства позволяют оценивать переходые процессы ИС на этапе их автоматизированного логического проектирования со сложностью до 106 вентилей при среднем времени логического моделирования динамики одного вентиля - 10" с.

Созданные программные средства использовались как расширение пакета прикладных программ (ППП) P-CAD. Найденная этими средствами последовательность входных векторов формировалась в виде соответствующего файла, настраивающего входные генераторы ППП P-CAD, кроме того; разработанные средства могут с успехом использоваться автономно. При внедрении созданных программных средств на промышленных предприятиях (Быковский завод средств логического управления, ГосНПО "Альтлир" ) были оценены автоматизированные проекты ПЛИС, в том числе построенных с использованием нейронной технологии. Элемент ПЛИС при этом представляет цифровой нейрон гексагональной структуры, настраиваемый на одну из булевых функций от четырех переменных. К спроектированным ПЛИС предъявлялись жесткие временные требования, в силу их применения в системах реального времени - в системах обработки радиолокационной, акустической информации, в том числе при гидрогеологоразведке железистых конкреций.

Результаты практического внедрения показали:

•уменьшение временной сложности ВС-программы при . логическом моделировании динамики ИС на несколько порядков по сравнению с применяемыми методами: вместо ВС-программ с

временной сложностью, равной 2" ~-1-(2п - 1), п-число входных каналов ИС, разработанные программные средства синтезируют ВС-программу, для практических случаев, со сложностью равной 3 п\

' 100%-ную гарантию быстрого выявления всех аномалий динамических свойств ИС, по сравнению с негарантированным их определением при использовании датчика случайных чисел при настройке ' входных генераторов в современных ППП моделирования (Р-САБ и др.); •выявление трасс, , специфицирующих критическое подпространство на логическом этапе проектирования, существенно упрощает временное моделирование ИС на этапе схемотехнического проектирования.

Результаты диссертационных исследований были внедрены на промышленных предприятиях (Быковский завод средств логического управления, ГосНПО "Альтаир") при автоматизированном проектировании систем реального времени, в том числе при логическом проектировании ПЛИС логического вывода для гидрогеологоразведке месторождений железистых конкреций с использованием нейронной технологии.

Основные выводы и результаты работы:

1. На основе введенного понятия "трасса" и расширенной гипотезы Мишры-Кларка предложен графово-трассовый подход к оценке переходных процессов в интегральных структурах (ИС) на этапе их логического проектирования.

Предложенный подход принципиально отличается от других подходов семиотического направления. Известные подходы этого направления: трейсовый (М.Рем, Дж.Снепчит, Дж.Адинг - 1983 г.) и логический (Д.Бохман - 1984 г.) ориентированы на логическое моделирование ИС на более позднем этапе - на этапе эксплуатации, для их использования необходимо знание входных сигнальных последовательностей. Предложенный подход является первым, который позво-

ляет оценить переходные процессы в ИС на этапе их логического проектирования.

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

3. Найдены объективные условия возникновения ложной информации во время переходных процессов при переключении ^ входных каналов (2 < х < кВк, ¿вх - входной коэффициент элемента), выходного элемента ИС, для чего предложена функция риска сбоя, учитывающая распределение трасс в булевом пространстве и использующая аппарат булевого дифференцирования:

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

5. Найдена характеризация линейности введенного графа связности критических пар входных векторов, на основе которой предложен алгоритм оптимального расширения носителя нелинейного графа связности при его линеаризации и построения соответствующей входной сигнальной программы (ВС-программы), оптимальной как по временной, так и по емкостной сложности. Синтезированная ВС-программа 100%-но гарантирует выявление всех аномалий динамических свойств ИС.

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

7. На основе предложенных алгоритмов разработаны программные средства оценки динамических свойств ИС на этапе логического' проектирования, образующие инструментальную среду для ПЭВМ РС/АТ-386(486), в которой успешно решена задача нахождения критическое подпространства с целью борьбы с аномалиями динамических свойств ИС. Программные средства позволяют исследовать

*инамику ПЛИС сложностью до 106 вентилей со средней 'реактивностью" обработки одного вентиля 10~2 с.

8. Внедрение разработанных средств в практику реального автоматизированного проектирования ПЛИС на промышленных предприятиях (ГосНПО "Альтаир", Быковский завод средстц логиче-:кого управления ) в "автономном" виде и в виде расширения ППП P-CAD показало при моделировании динамических свойств ПЛИС на этапе логического проектирования уменьшение временных затрат на несколько порядков, 100%-ое выявление аномалий динамики и повышение качества ПЛИС,

Основные положения диссертации опубликованы в следующих работах:

I.Горбатова М.В.Моделирование логических структур. В сб. Логическое управление в промышленности. - АН СССР, Ташкент, 1986, 68 -69. - ¿''"■■"'•■л ..

г 2.Горбатова М.В. Порождение тестовых последовательностей. В сб. Логическое управление с использованием ЭВМ. - АН СССР, М. -Устинов, 1987,54 -58.

3.Горбатова М.В. Структурное моделирование. - В кн.: САПР систем логического управления, Энергоатомиздат, М., 1988, 176 - 187.

4.Першенков B.C., Горбатова М.В. Решение прямой и обратной задачи в GAniP биполярных микросхем, - В сб. Логическое управление с использованием ЭВМ, АН СССР, М. - Орджоникидзе, 1988,106 - 110. . 5,Швецов - Шиловский И.Н., Горбатова М.В., Морозов И.В., Пого-сян Н.В., Харитонов A.B. Система проектирования элементов БИС "СЕРП". В сб. Логическое управление с использованием ЭВМ, АН СССР, М. - Орджоникидзе, 1988,111 - 113.

: б.Горбатова М.В. Характеризация размещения критических пар при логическом моделировании цифровых биполярных микросхем. В сб. Логическое управление с использованием ЭВМ, АН СССР, М. - Симферополь, 1989, 34-38.

7.Горбатова М.В..Кулиев Г.Б., Набиев В.В. Получение оптимальных тестовых последовательностей для проверки схем с интегральной структурой. В сб. Логическое управление с использованием ЭВМ, АН СССР, М. - Симферополь, 1989, 76 - 78.

- 8.Горбатова-М.В.,Федоров Н.В. Набиев В.В. Логическое моделирование биполярных микросхем на ЭВМ. - В сб.: Системные средства САПР, МДНТП им. Ф.Э. Дзержинского, М., 1989,51 - 60.

9.Горбатова М.В., Сумцов В.Л., Торхов В.Л. Разработка инструмен тальных средств этапа логического проектирования ПЛИС с использо ванием ПЭВМ. Отчет по НИР, N гос. регистр. 01890014972, МГИ, М 1989,108 с.

Ю.Горбатова М.В., Федоров Н.В. Обратный метод анализа критиче ских переходов в биполярных микросхемах. - В сб. Логическое удрав ление с использованием ЭВМ. - М. - Симеиз, 1990, 193 - 196.

П.Горбатова М.В. Оценка переходных процессов в интегральны схемах на ПЭВМ. - В сб.: Логическое управление с использование! ЭВМ, АН СССР, М. - Феодосия, 1991, 250 -254.

12.Горбатова М.В. Моделирование распределенных систем на осно ве Т - сетей. - В кн.: Логическое управление распределенными систе мами. - М., Энергоатомиздат, 1991, 264 - 283.

13.Горбатова М.В. Инструментальные средства оценки динамиче скнх свойств логических схем. в сб. "Информационные коммуникацш сети, системы и технологии." Труды Всемирного Конгресса ITS - 52. М., IIA, 1992, 201 - 202.

14. Горбатова М.В.,Торхов В.Л.,РябовЛ.П.,РякинО.М., Разработк концепций и принципов математического и программного обеспечени САПР и управления в горном деле на основе искусственного интеллек та. -МГГУ, М., 1993, 120 с.

15. Горбатова М.В., Теория трасс - В сб.: Информационные комм} никации, сети, системы и технологии, Труды Всемирного Конгресс ITS-93, М., IIA, 1993, 44-52.