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

РГ6 од

1 л • • * тарсогскнл повггехютескш институт ! и ,,¡¿1.1 ........

На правах РУ1ЮПИСИ

КАРПОВ Евгения Васильевич

АДАПТАЦИЯ И ИНТЕЛЛЕКТУАЛИЗАЦИЯ КОШЖЕПТОВ НАТЕ!1АТИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ШНСГРУКТОГСКИХ САПР ЫИКРОЭЛЕКТРОНШХ УСТРОЙСТВ

Специальность 05.13.12 - "систем! автоматизации проектирования"

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук в форме научного дослала

Воронеж - 1993

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

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

Официальные оппоненты: доктор технических наук, профессор Д. И. Батищев,

кандидат технических наук, доцент Шишкин а М.

Ведущая организация: научно-производственное предприятие "Рубин" (г.Пенза)

Защита состоится " 3 " июня_ 1093 г. в 14-00 час

на заседании специализированного совета Д 063.81.02 Воронежского политехнического института по адресу. 394026 г. Боронен, псковский проспект, д. 14.

С диссертацией в Форш научного доклада можно ознакомиться в библиотека Еоронеяского политехнического института

Диссертация разослана 1993 г.

Учений секретарь

специализированного

совета Д 063.81.02

д. т. н., профессор

/ // Я Е. ЛЬВОВИЧ

ОКДЛЛ ХАРАаГГШОТККЛ РЛКОТЫ

Актуальность темы. Смена объектов проектирования САПР микро-электронныу устройств (МЭУ), обусловленная ростом их сложности, изменениями элементной и конструктивной базы, ужесточением технологических, теглозьи, схемотехнических и других требований, повышает значение адаптируемости САПР ЮУ и их компонентов как сродотза повышения качества проектирования, конкурентоспособности и увеличения длительности жизненного цикла математического и программного обеспечений (МО и ПО).

Адаптируемость необходима ¡сак для вновь разрабатываемых, так и для уже эксплуатируемых компонентов МО и НО САПР ¡¿ЗУ. Требование высокой эффективности механизмов адаптации невозможно выполнить без разработки целостного концептуального подхода, опирающегося па общесистемные принципы и определяющего структуру средств адаптации в САПР и согласование их Функций.

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

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

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

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

- г -

левой программой ГКНТ, Госплана и Президиума Академии наук О. Д. 027, задание 05.52.

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

Для достижения указанной цели в работе решались следующие основные задач!;:

- анализ видое адаптационных взаимодействий при смене СП, методов адаптации и интеллектуализации компонентов САПР,

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

- постановка и решение конкретных задач адаптации и интеллектуализации компонентов МО и ПО САПР ЮУ,

- реализация разработанных методов адаптации и интеллектуализации в составе МО и ПО САПР различных ЮУ, их исследование и внедрение в производство и учебный процесс.

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

Научная иор.кзна работы заключается в разработке зффекгиЕНЫХ методов решения задач адаптации и интеллектуализации в рамках предложенной концепции типового объекта проектирования САПР ИЭУ, оснозываидихся на сведении ряда задач к выделению в графах изоморфны:: подграфов, для которого получены новые и более эффективные решения. Ряд задач адаптации и интеллектуализации для традиционных и интегрированных САП? вне упомянутой концепции такие решен на основе сведения к выделению изоморфных подграфов (ЯП), прогнозироьа- . нпл и имитационного моделирования.

На защиту выносятся следующие основные потакания:

1. ВперЕяе разработана базовая концепция типового объекта . проектированш САПР, а также ее расширения, обеспечиваидаэ высокую адаптируемость компонентов Ш и ПО к объекту проектирования I: определяющее архитектурное построение типоьой САПР

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

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

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

5. Разработаны методы адаптации структуры процесса проектирования к учету тепловых требований МЭУ, параметров ОП, ал1 оритмов проектирования и вычислительной сред", отличающиеся ориентацией на разные типа структур и одновременный учет этих парагетров.

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

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

- реализация концепции типового ОП позволила минимизировать объем МО ;и ПО адаптивной типовой САПР МЭУ и упростить ранение задачи адаптации компонентов МО и ПО к смене ОП,

- сведение ряда задач адаптации и интеллектуализации к одной задаче выделения в графе изоморфных подграфов позволило сократить объем МО и ПО для этих задач, сократить сроки разработки средств адаптации и интеллектуализации САПР МЭУ,

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

- методы адаптации процессов проектирования позволили при смене ОП адаптировать у;гэ эксплуатируемые компоненты 1,10 и ПО.

Результаты практической реализации и внедрения состоят в использовании теоретических и экспериментальных исследований в 12 НИР Пензенского политехнического института Компоненты КО и ПО адаптивных САПР матричных-БИС и печатных плат, гибридных микро-

сборок, пакета прикладных программ решения графовых задач внедрены в 5 предприятиях РФ с обш^м экономическим эффектом 132 тыс. руб. в цепах 1080-х гг. и в двух вузах, два средства включены в Госфонд алгоритмов и программ. Учебная версия САПР МАЕИС к плат, структурный анализатор и средства адаптации процессов проектирование использогагы в учебном процессе Пенз. ПИ.

АпррСзциг работ',Основные положения диссертационной работы докладывались и обсуэдались на следующих конференциях, совещаниях и семинарах: всесоюзные - конференция "Теоретические и прикладные вопросы разработки, внедрения и эксплуатации САПР РЭА" (Ереван, 1983), 3 конференция "Автоматизация поискового конструирования и подготовка инженерных кадров" (Иваново,1983), конференция "Теория и практика конструирования и обеспечения надежности и качества электронной ачгаратуры и приборов" (Воронеж, 1934), 6 совещание "Методология проектирования САПР" (Таллинн,1985), 1 конференция "Методы анализа надежности программного обеспечения вычислительных систем реального времени на основе нечеткой логи. и и качественных описаний" (Киэв, 1987), семинар-школа " Автоматизация научных исследований в области качества и наде:кности РЭА и ЭВА" (Москва, 1987), конференция "Моделирование САПР, АСНИ и ГАП" (Тамбов,1989), созешдние-семинар "Разработка и оптимизация САПР и ГАП изделий электронной техники на базе высокопроизводительных мини- и микроЭВМ" (Воронеж, 1989), семинар "САПР в машиностроении" (Ульяновск, 1990); республиканские - конференция "Контроль и автоматизированное проектирование монтажа узлов и устройств цифровой аппаратуры" (Каунас, 1981), конференция 'Автоматизация технического проектирования цифровой аппаратуры" (Каунас, 1984); региональные - конференция "Оценка и обеспечение длителной работоспособности изделий электронной техники ь РЭА народнохозяйственного значения" (Севастополь, 1981), семинары "Автоматизация проектирования ЭЗА" (Ленинград. 1983), "Автоматизация проектирования РЭА в САПР" (Горький, 1983) и "Принятие оптимальных решений в САПР" (Горький,1985), 5-13 конференции "Автоматизация конструкторского проектирования • РЭА и ЭВА" (Пенза, 1978-1986), конференции "Автоматизация проектирования РЭА и ?ВА" (Пенза, 1991,1992), конференции профессорско-проподавателгекого состава Ценз. ПИ.

Публикации. По теме диссертации опубликовано 47 печатных работ и 10 отчетов по НИР. Основные результаты диссертации отражены в 36 публикациях, перечень которых приведен в конце диссертации.

1. АНАЛИЗ ПРОБЛЕМ АДАПТАЦИИ 1! №СТйЛ;ЖТУЛЛИЗЛ1;ЧИ КОШЕЯЕИОЗ САПР МЗУ И АКОЯГ.;.ТтДК ПОСТРОКШШ СРЕДСТП ИХ гшппга

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

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

Предпочтение альтернативной адаптации !сак менее трудоемкой по сравнению с эволюционной ставит задачу распознавания класса ОП, которому соответствуют оптимальные структуры компонентов МО и ПО. С учетом распространенности графовых и гиперграфовых моделей электрических схем ЮУ, монтажно-коммутационных прстрачств, графов теплопроводности и др. целесообразны детерминированные и структурные (лингвистические) методы распознавания.

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

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

- е -

с распределенными по прикладным подсистемам модулями. Первые выполняют адаптацию процесса проектирования в целом, а вторые -адаптацию на отдельных атапах проектирования.

Целесообразно та!ак использование преимуществ известного архитектурного построения МО и ПО адаптируемых САПР на осноеэ модулей типовых алгоритмических решений (ОТАР) или макропроцедур оп-мизационш'х графовых задач. Его недостатком является эзрисгпка «екомпозицпл задачи проектирования МЭУ на ЫТАР, а достоинством. -инвариантность МО и ПО и их эффективное использование.

2. ГОЗЩПП'.ЕП 'ПЛТССОГО ОБЪЕКТА ПР0^а;ЗЮЗА1Ш [ 2-?, 17-19, 22, ZQ-32 1

Базовая концепция типового ОП (ТО) адаптивной САПР удовлетворяет системном принципам целостности, автономности, дополнительности, неопределенности и действия. Расширен.:,! концепции, разработанные по".:ка, повышают ео адаптационные позмошюстп.

Целостность концепции обеспечивается единым подходом к анализу трёх множеств: OII ¡Ык^ }, их моделей и^т^У и алгоритмов проектирования /Мз i >. Ка олекентах множеств заданы два вида системообразующих отношений: отношения пр'шаддежаосги к различимым по структурно-морфологическим признакам классам: Y к; ¿И 3> Кх'G £ К (к[€Кх') ; У ni £ M j! Wz's h' (m^kx'j: VaiCAjl Ax'~ A ( ai^Ax') и биективные отношения вида: k^e—*- v.'L<r-> ы и Kx'<r—S> l'y. <—> Ах (1).

Основным свойством каждого класса является наличие его типового представителя: типового ОП (ТО) кГ<—~> Кх > типовой модели

Т ' гр Г ■

(ТМ) <—>Мх и типового алгоритма (ТА) ах<—>Ах , которые однозначно определяют соответствующие класса.

Суть концепции ТО состоит в той, что отношения (1) ме.'кду классами и их элементами сводятся к отношениям их типовых представителей —> mji <—ах , необходимым условием чего является выводимость любого ОП некоторого класса из ТО этого класса конечной последовательностью операций из заданного набора: Vk-L&. КхЗкх€ € Кт(кь Ь— kl ), где |— знак выводимости. Она гарантируется, если ОП является .фрагментом ТО или совокупностью фрагментов. Второе условие - абстрактность-ТО, необязательность его воплощения в конкретней СП и конструктивной целесообразности последнего. Аналогичные требования предъявляются к ТМ и ТА.

Условия ьшолнимы, если ТО, ТМ и ТА объединяют особенности

- t -

элементов своих классов: к^ - О к;, wj = U ж/, а* = U aL, 1 =1,1. Синтез ТО возможен на уровне ОП, моделей ил;; алгоритмов. Типовые •гюдставители образуют множества: К7= ik}, Ат-~- [аА }.

х ~ UX, причем последние целесообразны, если |Kr|<IK|, |МТ|< < |М|, Цт |< Принцип автогюмнос.ч: проявляется в автономности метрик расстояний внутри классов Кх , Ах , !'х , т. е. операциями преобразования ТО в конкретный ОП Принцип неопределенности проявляется з подвижности границ классов Кх , устанавливаемых критериями \КГ\—min, минимума избыточности относительно всех к^Кх, минимума суммарной избыточности всех к£ относительно К и максимальной простоты к* , транзктивно следующей из простоты а*. Эти критерии отражает противоречие между универсальностью и специали-защей ТО, устраняемое переводом части критериев в разряд ограниченна. Принцип действия (порогового значения) проявляется в изменении ТО при появлении новых ОП, существенно отличных от К. Принцип доподрительности (множественности) проявляется в многозэри-• антности образования классов Кк', Мх', Ах'.

Так как ТО объединяет свойств; ч .1 своего класса, г.рсектирова-ние последних сводится к настройке соответствующих ТМ и ТА, а адаптация - к анализу выводимости конкретного ОП из ТО. Пластически из этого следует, что МО и ПО адаптируемой САШ5 в рамках изложиной концепции до.та-го реализовывать лись многгетва ?М, ТА и празил преобразования* их в конкретные модели и алгоритмы. ГО представляет собой структуру se(PxCxD), где B,C,D - множстза типовых- конструкций, ограничений и критериев оптимизации.

Расширение 1 базовой концепции свисаю с ориентацией ТО на

/7

заданное мно.-лество ОП и дополнительное множество Кх так называемых потенциальных ОП: 7 k'KC Кт[ kj\— (Kx'ü Кх ) J, Кх II Кх = Дпричем требование \~> шх характеризует рост адаптационных возможностей и зкивучести МО и ПО. Синтез Кх выполняется двумя методами: на основе морфологического подхода, где элементам !3,C,D соответствуют элементы полной морфологической матрицы с допустимой композициеи элементов строк; на основе прогнозирования ОП по наблюдаемой эволюции их структур и параметров с использованием ДСМ-логики для распознавания закономерности изменения графовой модели структур!-' эволюционирующего ОП.

Pric;LvpeHiio_ 2 объединяет преимущества концепций ТО и МГАГ на основе оог;его свойства инвариантности по трем поправлениям. В первом алгоритмы в концепции ТО, т. е. ТА, уточняются до уровня MTAF '

на основе формального поп::ода к декомпозиции системы критериев и ограничений исходной задачи проецирования при её отображении в пространство типовых и нетидовых подзадач. В частности, декомпозиция систсмы ограничений в иерархии подзадач сводится к разрезании гиперграфа на подграфы с минимизацией весов разрезаемых гиперребер. Второе направление использует поисковый метод эволюционного синтеза структуры алгоритмического решение задачи проектирования множестве Mi АР и неткповых подзадач. Примэпяются альтернативные стратегии - наращивание элементарней линейной структуры и упрощение универсальной пошосвязной структуры. В третьем направлении типовые и нетиповые алгоритмические реыения представляются в форме взаимосвязанных множеств фрагментов, для которых оценивается их инвариантность к множеству требований нового ОП. Задача перестраивать алгоритмических решений на фрагменты трех типов (инвариантных, неинвариантных, т.е. модифицируемых, и дополнительных, разрабатываемых вновь) при представлении алгоритмических решений в форме графов сводился к разрезанию множества графов на подграфы с ограничением внутренней связности ьераиь подграфов.

Концепция ТО определяет структуру так' называемой типовой САПР МЗУ. Транслированное описание поступающего на проектирование нового ОП с помощью специального анализатора сравнивается с транслированными описаниями реализованных в САПР типовчх 0IL По результатам анализа (распознавания) специальный модуль настраивает ТЫ и ТА распознанного класса и соответствующие им компоненты ПО ira проектирование поступившего объекта

3. ЗДЦЧЯ ЛДШ'АШЯ и ШШЭБДОШСОДфШ И 12TQSQ IIX РЕЗНЕ [ 2-4, В, 12-14, 15, 17, 20, 23, 25, 25, 32-3й 3

Ряд задач возникает в рамках концепции ТО, а отдельные задачи характерна для интегрированных САПР МЭУ вне концепции ТО.

Зат;ач? 2. ~ распознавание класса СП в концепции ТО состоит в установлении выводимости ОП из типовых ОП клэссое: kj. |— ко, klс Ç. Кт. Распознавание выполняется на уровне моделей структур электрической схемы, монтало-коммутационного пространства МЗУ, схемы теплового замещения. Моделью ОП ко является граф (гипэрграф) Go , а моделями {кл' х = 1,Х - множество графов <0х (Ex,Ux)i, х - 1,Х. Выводимость сводится к задаче об изоморфном вхождении. Со в <6х>. Она же сводится к выделении общих, изоморфных подграфов (11Л) в г;а-

- 9 -

-т Г Г / -, / / • / Г

ргх (.бо, вх): и 6х (Ex.Uk) € Гх 3 во (Ео.Цо) с- Ги (во у вх) по критерию |Ео |-|!£х |—г-ггзч, где вх - подграф вх, а Гх - множество ого подграфов. Паре соответствует граф псевдообъсдпнення во.х- Со У вх. состоят;!!* из компонент свяпяогт»! во и вх. В наглом из во.х выделяются множества максимальных 121 Гх в разных компг;;ентах. Если найден

во. то класс ОП распознан. При \Ех |<|£о| класс определяется пс- критерг-о структурной близости Гх - (ах |Гх! + Ь у. £\Ех \). где а,Ь - весоЕые коэффициенты. Если исе Гх < Е т:п, то йо образует новый кл~сс ОП как удал гнныи от других кдассоз ОЛ згой САПР.

Згдача 2 - распознавал;: - ушювш ОП з ра.псах концепции ТО. Она решается как задача синтеза ТО через операцию объединен!:;. либо гамм ОП класса к'х - О к.\ (¡/г/й , либо их моделей л/ - V га,, п£с 6 Мх . Есть: модели структур ОП - гргфы И 1.' Г, то Ув1 € Г 3 Ссс-€ Го (во ~ (71). гле Го - множество подграфов во - мчниматьного

иокрчващего графа. Последователь!, и ;.:етод з соответствии с формулой во - ((...(в; и б_> ) и ...^ И 31 ) ре!Г/роизно кспсльзуст сперглин С1-1 и 01 , где 31-1 - результат оС:-едш:гния граГоз с 61

по С1-I . Операция выполняется в 4 этапа: псевдосбгсдинелне и

г >

- в!-/ V С1 ; выделение в 61-/,1 множества чаксимальш« 1ГТ1 тэта,

что: 1/Ш с Г1 .7 !61-/€Г1-I ('31 - 61-/). где С;-.' - подгра>> 01 ;

выделение в в! и в 61-/ 'сстатг.ов К(61)-61/61 л К(31- !)-31-1 /31- / ;

г.севдоибъединенне К{61) „ К(в1-: ) и единствен!!! х представителей

каждого из нножсств 131. В пара"-:льном методе сперва

псевдообъсдин.чютсл все графы, в" - <3, V и ... V 3 , затем в 3"

выделяются дозекмагацие ИЛ по условна ^31,33 с- гЭв!3 г Г ' [(01П

П ви-ец) (63 ¡1 613-613)]. Остальные этапы - по первому методу.

Задача 3 - распознавание (синтез) структур эллогокк и Л длг.

САПР вне концепции ТО - состоит в сравнении структур <51> сСыктсв

подмножества {Кг}, 1-1,/, ч'ьп показатели качества проектировали."!

некотср'з.! компоненте.: 110 Слизки г. э!жгре:'2лы!121. ГТг.с:-,ер>са

о влиянии 31 не пекгзптел:., т.о. о оункцч;! Г($1) сводится к ыпелз-

закономерности методе:: сходства индуктивней ДСИ-лсгг.с;: ЦГ(5 +

+ с151)—> ехСг) У(Р(5 - (£?)—> extr)J >:::1г). г;;- &51,

(132 - гдагглвкыэ доЗзвкк (отлична структур), иЬ'Г ;■ ¿32. &•„•:•« (31}

пр^;;с л* влон'1 гогл {61}, то пене:: спорна; :: егго-

рг.цч:: " с". :■.:■; 31 3 Gj, :' а дс1"^.:к:: ЗЛ.З'^ спроделпмтсл

- ." ./ 63), езз - 33 /(з: Г: 33).

•....... \ у с-тс л ЛИ

.. - '?д:::;л::ч 3 1/ - 31 3^ а:ги.ог:г;::о 1 Сбъ-

единение ИП. полученных для различных пар (в1,6]), определяет граф структуры эталонного ОП Дэ подмножества К. тестирозание компонента ПО этим Яэ подтверждает или отвергает гипотезу ос КБ!).

Задача 4 - семантический анализ экспертных'.знаний в интерфейсах эксперта и когнитолога специализированной экспертной оболочки адаптивной СД1ТР МЗУ. Цель анализа - тестирование 33 разных экспертов, синтез эталонных 33 и метазнаний. Семантической моделью ЭЗ i-.ro эксперта является древоподобная сеть 1=1,1. Направления дуг соответствуют продукциям. Верпкнам Й присвоены метки семантических типов рассуждений и исходных 'ксиом. При сравнении различных 33 информативны различия и сходства 2Г. Сравнение 5), являющееся задачей семантического анализа 33, сводится к выявлению закономерностей в 31 аналогично задаче 3 методом сходства ДСМ-логики. Сункцией гХ~21) является метка корневой вериины-заключения или любой другой ьерщины. Задача сводится к 3-й для случая ориентированных помочоккмх графовь-х юдолей.

Задача Б - синтез основного словаря V графовол грамматики Федора Г = I, /?> или дополнительного словаря V грамматики Пав-лидиса для структурного (лингвистического) распознавания класса ОП. 2сли оОучалц&л выборка образована графовыми »моделями структур ОП одного класса {ГЛ), 1-1,1, то примитивами словаря, ч,>ей внутренней стру:сгурой иэто пренебречь, целесообразно в: ¡брать макси- . мальные ЦП гра-^ок тСа,'. С;:и удовлетворяют трек, основным требованиям к V Гили V): кэдпашютк описания структуры ОП предложениями ягпта ЦГ) и минимума объема словарей У,!/ ввиду максимальной размерности 7С; <&ягаешдеьной полноты V, V. Доказательство последней тр;и.кпл!.ко: л.ч;Со>: из прлмитпвев ксг.о.тьвуегся -при при описании по крайпг.й мере одного из СП, поскольку Ш выделяются именно в обучающем мно>;';стье <С1). Следовательно, язьсс ЦГ) достаточен для описа- . нин V'(р . Особ<?н::остью пр;цйт;.йов является их примыкание по вершинам пли ребрам в оосттичсту.ки с множеством правил !?, что -соот-вогстьу^.т поресечеп;;:о щ по ворсинам и ребра:.'..

Задача 5 - идентификация примитивов словарей 7,1/ в графовой модели во структуры ОП л структурных методах распознавания. Если 7 есть множество градов {ОН, 1, то идентификация сводится к последовательном'/ ияегоякя ЦД г. графах псуздосбгедииьикй бГ = - Со II 01 тс с-;;:>:, что: ^ б'о С Го У Си £ V (Л ) с го.'_:;.л:л:ым пе-

рсолч^лн:-;!,! но л г^рлльлм ИП еднего или рззкых шокссхв. Подмко-:лстлс 7'с 7, используемое в описании во, ыйяраотся ¡,о критерию

- И -

|Го|—>тп по результатам вхокдения вериин бс в различнее сочетания пересекающихся Ж

Задача 7 - структурная адаптация иерархического процесса проектирования (ПП) },ЕУ к ОП - заключается в распознавании оптимального по трудоемкости и качеству проектирования ;:ере;ч декомпозиции Т общей задачи на подзадачи различной размерности к типов. Решение находится с помощью имитационной модели (#.!), настаиваемой на А. группы параметров: параметры ОП - размерность !,!ЭУ и его фрагментов, связность элементов, совместимость элементов и Фрагментов, ресурсы монтажно-коммутационного пространства; параметры' алгоритмов проектирования - сцепки временной слояюсти и качества р-'ш&зяй; параметры Г - число его уровней к распределение'числа фрагментов по уровням; параметр вычислительной среды'- количество параллельно выполняемых операций проектирования или декомпозиции.

КзадыЯ квасе ОП характеризуется фиксированными значлгиям;! параметров либо функция!,-.и их распределения. в:-53-У}Л моделирует проектирование "сверху вниз" и "снизу вверх". Варьирование параметров в имитационном эксперименте выявляет оптимальную структуру "

Садача 8 - адаптация последовательного типового Ш (линейна структура ПП) к тепловым требованиям. Метод•решения опирается па прогнозирование риска возникновения перегрева, принпипы гарантированного результата и оптимальности по Р. Беллману, использует связь ме.вду распределениями метричеожх параметров монтажного про^трапст- , ва и распределением тепловых характеристик элементов.

В типовой Ш встраиваются 8 компонентов МО и ПО: С1 - расчет самонагрева элемзнтов на подлохках с применением ТМ - графов теплопередачи, настраиваемых на варианты конструкций МЗУ и материалы; С2 - расчет взаимных перегревов элементов; СЗ - синтез функции распределения межэлементкых расстояний для подло.тек произвольной конфигурации; С4 - синтез Функции распределения г.осррхностпгЛ плотно-ти тепловыделения-с учетом площади зле-ментов; С5 - оптимизация размеров "зон зац'цты" термокритичных с-^мсотса до-и в процессе размещения с учетом результатов СЗ и СЛ\ С6 - расчет интегрального (суммарного) взаимного перегрева элементов подложи с учетом результатов СЗ и СЛ\ С7 - определение зектороз смещения элементов при их переразмещекии; СЯ - декомпозиция элементов па дискреты.

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

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

4. 1СТОДЫ ВЫДЕЛЕНИЯ В ГРЛ1К И30!,ЛРЙШХ ПОДГРЛфС И РАЗРЕЗАНИЯ ГРА2А НА ПОДГРАЖ

С 1, 6 - 11, 15, 20, 24, 27, 31 1

К задаче выделения ИП в графе сведен ряд аадач адаптации и интеллектуализации. Известно сведение к ней задач компоновки МЭУ -типизации и покрытия схем. Она входит в число МГАР типовой САПР,

Известный точный метод выделения ц ИП в л-вершинном графе в ориентирован на узкий класс графов без нетель и кратных ребер, имеет высокую емкостную сложность ввиду возведения 6 в степень ц и определения неплотности последнего. В предлагаемом точном методе анализируется N - л (п-1)/2 -вершинный граф в рёберного отображения в,- имеющий коатмые (взвешенные) ребра. Метод сскокан на свойстве ребер ИП графа в при отображении в вершны в образовывать N пустых непересекающихся д-ьершинных подграфов, полностью построенных на подмножествах вершин С*, соответствующих рёбрам 3 разной кратности. Вершины пустых подграфов образуют N непересекающихся треугольных решетчатых графов Ь п х л, в которых вершины каждой строки или столбца попарно смежны*. Структура I л х л инвариантна к его размерности, что упрощает его распознавание.

Метод обеспечивает управляемость выделения ИП заданием их рёберного состава Тождественность б*матрице связности в упрощает реализацию метода, выполняемого в два этапа: выделение .в б*множества пустых подграфов; выбор подмножеств, образующих Ь п х л .

Разработаны модификации известного параллельно-послэдователь- • кого метода повершинного наращивания (МЛН) ИП: понижена зременная сложность за счет исключения алгоритмически сложного этапа локадь-ной оптимизации на промежуточных этапах и за счет сведения трудоемкой операции обработки матриц к быстрой лексикографической сортировке их блоков-строк. тЬетья модификация повышает размерность ИП за счет введения их пересечения по вершинам, что требуется в задачах 5 и б раздела 3. Ш! адаптирован к множеству ограничений СП: учету совместимости ьериш г, ИП, их директивного назначении, ограничению ш;у>трапноц и ы^.ой связности и сумми весов морщин/ребер.

Последовательны:; :л-тод разр ¡иътя гк:;,1гг::, ::осохьоу-

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

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

5. РЕип.^УУ'Л И АЗШИЗ МЕТОДОВ АДАПТАЦИИ И Ш1ГЕХТКС1УЛЛ){ЗЛЦ5Л1

I 1, 2, 5, 7 ■ 17. 21, 25, 28, 30 - 32, 35, 35 ]

Разработанные ¡методы воплощены в 'альтернативных программных комплексах САП? '©У. Стру.^урный анализатор "STRA.\"' распознает класс ОП, чьи электрическая схема или монтажно-коммутационное пространство моделируются графами согласно задачам 1 и 6 раздела 3. Реализован на ПЭВМ и IBM PC. В отличие от известных, не ограничен определенным:! типами срукгур. Есчючает разработанные процедуры выделения изоморфных подграфов в графе.

Прототип специализированной экспертной оболочки длг адаптивной САПР выполняет автоматизированный семантический <"нали:> ЭЗ, прсдставлеып.:;-: в форме ИЛЛИ-сети рассуждений, в рам!^ах интерфейсов эксперта и когнитолога, согласно задаче 4 раздела 3. Включает модул:: поддержки типовых рассуждений, компиляции ЭЗ в И/ИЛИ-сеть, автоматического анализа ЭЗ в "ST"V."\ Реализован на IBM PC.

Программа анализа и сбест." :./ тепловых режимов многокряс-тальных гибридных мшсрэсборок "/».'::.?" решает задач'/ 8 раздела 3 как автономное :: встраиваемое в САПР микросборок средство. В ней впервые была реализована концепция ТО, когда вместо 5 различны;: тепловых расчетных моделей была синтезирована одна ТМ, а соответствующий ей ТО заинтересовал заклзчпгл как. потенциально перспективный вариант конструкции. Объем,и ПО и МО, сроки их разработки, трудоемкость адаптации к снопе ОП сократились в 4... 5 раз. Реализация на ЕС ЗВ.Ч

Пакет прикладных программ "ВОЛНА" решает задачи выделения Iffl в графе и разрезания графа на подграфы в задачах компоновки МЭУ и задачах адаптации и интеллектуализации. Адаптирован к множеству огра-

ничений. Исследование модификаций ШН ИП показало сокращение трудоемкости ресекия более чем на порядок. С помощью адаптированной ПРВ решались задачи объединения логических функций в ячейка:: МАБИС. Пакет реализован' на ЕС ЭВМ.

Пакет из шести альтернативных имитационных БРББ-моделей решает эадачу 7 раздела 3 с различным уровнем абстрактности представления ПП по числу учитываемых параметров. На их основе выполнялись вычислительные эксперименты по адаптации структуры дерева декомпозиции к ОП Реализован на ЕС ЭВМ.

САПР "СПАРК" - типовая двухобъектная САПР матричных БИС и печатных плат - ориентирована на типовой ОП с произвольным числом ев коммутации, унифицированные посадочные места с возможностью операций пространственного преобразования в них, произвольное располо-. жение межслойных переходов и др. Ориентация на ТО позволила сократить объемы МО и ПО и сроки их-разработки в 1,8...2 раза, легко адаптировать их к новым ОП. САПР реализована на ЕС ЭЬМ.

А

ЗАКЛЮЧЕНИЕ

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

Е диссертации получены следующие результаты:

1. Разработаны базовая концепция типового ОН и ее расширения, обеспечивающие эффективное решние задач адаптации компонентов к .смене ОП, сокращение объема Ш и ГО, и определяющие архитектурное построение МО и ПО типовой САПР КВУ.

2. Разработаны альтернативные методы решения задач распознава- ■ ния классов ОП, синтеза эталонных и типовых ОП, семантического анализа 33 в экспертной оболочке САПР на основе единого подхода - -выделения в графе изоморфных подграфов, что сокращает объемы Ш, ПО

и сроки решения этих задач.

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

4. Разработан структурный анализатор ОП , эффективно распознающий структурный класс ОП без ограничений на типы структур. Анализатор такта реализует функции когнитолога по семантическому анализу 33 в специализированной экспертной оболочке САП? МЭУ.

5. Разработаны средства адаптации иерархического и последовательного процессов проектирования .!/5У к требованиям ОП на основе компонентов прогнозирования и имитационного моделирования ПП.

6. Разработанные методы реализованы в состав? программных комплексов автоматизированного проектирования различных типов МЗУ.

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

1. Вернадский А. К , Еодрягиь ЕЖ , ЕаицешГХТГ, Карпов Е. В. гйлнозой алгоритм объединения компонентов схемы в ячейки матричных БКС// Вопросы радиоэлектроники. Сер. ЭРТ. -1982. -Выл. 10. -С. 28-35.

2. Вернадский А. 11, Водряпш 3. И. , Зайцева ;?» Н. , Карпов Е. В. Типовая система автоматизированного проектирования матричных боль-сих интегральных схем// "Вопросы радиоэлектроники. Сер. ЗШ. -1985. -Еып. 9. -и. 35-41.

3. Бершадский А. М., Кзрпов Е. В. Метод реализации прикладного программного обеспечения адаптивной САПР на основе типовых объектов проектирования// Там же. -С. 42-47.

4. Бершадский А. М., Бодрягин В. И. , Зайцева К. Н. , Карлов Г. Т: Об организации компонентов математического и программного обеспечения з интегрированной САПР изделий ЗЗ.ч// Автоматкзацп.1 конструкторского проектирования в радиоолэктронике и Еьпнслнтельной технике: Мекзуз. сб. научн. тр. Т. 4. / Каун. ПИ. -Вильнюс, 1904. -С. 124-130.

5. Вернадский А. М. . Карпов 2.3. , Тукллоь В. Применение функции загруженности монтажного пространства при коммутационно}-, проектировании матричных БКС и "33// Автоматизация конструкторского про-ектисовання в радиоэлектронике и вычислительной технике: '.'.зжвуз. сб. научн. тр. Т. 5. / Каун. Ш. -Вильнюс, 1985. -С. 07-72.

6. Вернадский А. М., Карпов Е. В. Принципы построения типовых объектов моделей при решении отдельных задач в САПР// Автоматизация пооектирОЕанил электронной аппаратуры: Междуьед. тематич. сб. Вып. 4. / ТРТ11 -Таганрог, 1985. -С. 18-22.

7. Вернадский А. М , Карпов Е. В. Альтернативное методологичео-!сое и программное обеспечение подсистемы автоматизированного про-ектисозанил МАЕ,"С// Автоматизация проектирования электронно-вычислительной аппаратуры: .Матер, семин. -Л.: ЛДКТП, 19;.'3. -С. 19-25.

8. Карпов £. Е Алгоритмический метод выделения з графе изоморфных подграфов с минимальной емкостной сложностью// Применение вычислительных методов в на^'чно- технических исследованиях: Можвуз. сб. научн. тр. /ППИ. -Пенза, 1984'. -С. 81-85.

9. Карпоз Е. а Об одном подходе к синтезу структуры базовых элементов БИС// Вычислительная техника з автоматизированных системах контроля и управления: Шжзуз. сб. каучн. тр. / ППИ. -Пенза, 19ВЗ. -С. 99-103.

10. Каппов Е. Е Автоматизированное преобразование схем цифровых устройств в систему конструктивных модулей с гаданным распределением их параметров// Вычислительная техника в а .г, оматкзированных системах контроля и управления: Межвуз. сб. нау^н. тр. /ПГИ. -Пенза, 1934. -С. 97-100.

11. Щорбаль Л. Б., Карпов Е. а Универсальная программа решения еадчч типиэмдаи и покрытия // Автоматизация конструкторского проектирования РЭ и СБА: Сб. статей. -Изд-во Саратов ун-та, 1981. -С. 17-21.

12. Сапожков К. А., Карпов Е. В. Методика использования программы теплового анализа в подсистеме размещения// Математическое, программное, информационное и техническое обеспечение САПР// Сб. статей. -Илд во Саратов, ун-та, 1961- -С. 65-68.

13. Сапожсв ¡i.A., Карпе? Е. В. К вопросу анализа и обеспечения тепловых режимов в подсис!еме автоматизированного проектирования микрос-Зорок// Автоматизированное проектирование узлов и устройств цифровой аппаратуры: Сб. статей. -Изд-во Саратов, ун-та, 1982. -С. 64-67.

14. Карпов Е. В. Оптимизация тепловых режимов элементов в САПР микросборок пр.. выборе конструктивных параметров// Малинные методы конструкторского проектирования РЭА и ГВА: Сб. статей, -Изд-ьо Саратовского ун-та, 1983. -С. 64-67.

15. Бор ладе кий Л. 1.L . Гл'рпов Е. В. , Щербаиь A.B. -Алгоритм и программа несения задачи типиза:и:и. П00"280// Алгоритмы и программы: Инф. бюлл. ГосФАП. -1983. -Вып. 4. -С. 47.

16. Вернадский А.)I , Лебедев R Б. , Карпов Е. В. Программа и алгоритм анализа тепловых режимов элементов гибридных микросборок. ГО07835// Алгоритмы и программы: Инф. бюлл. ГосФАП. -1985. -Вып. 1. -С. 84.

17. Вернадский А. У.. , ЛсбедеЕ В. Б., Карпов ¿.В. .Методология анализа тепловых-режимов в CAIiP микресборок// Вычислительная техника: Тез. докл. респ. конф. Контроль и автоматизированное проектирование монтаж^ узлов и устосйств цифровой аппаратуры. '-Гаунас, 1981. -С. 65-86. " -

18. Вернадский А. М. . Лебедев В. Б., Карпов Е. В. Об использовании типовых моделей и объектов проектирования в САПР РЭА// Теоретические и накладные вопросы разработки, внедрения и эксплуатации САПР РЭА: Тез. докл. всссоюзн. конф. -11, 1983. -С. 8-10.

19. .Карпов Е. В. Об особенностях организации типового объекта проектирования в учеоной САПР РЭА и ЭВА// Автоматизация поискового конструирования и подготовка инженерных кадров: Тез. докл. всесонзн. конф. -Иваново. 1983. -С. 145.

20. Вернадский А. М. , Карпов Е. В. Автоматизация компоноеки в САПР !.!ЭУ по критерию минимума паразитш:\- воздействий// Теория и практика конструирования и обеспечения надежности и качества электронной аппаратуры и приборов: Тез. докл. всессюзн. конф. -М.: Радио и связь, 19d4. -С. 4о-47.

21. Вернадский А. М. , Карпов Е. Е , Тужилов И. В. Размещение ячеек матричных БИС по критерию минимально, загрузки монтажного поля

// Вычислительная техника: Тез. докл. респ. конф. Автоматизация техки- . ческого проектирования цифровой аппаратуры. -Каунас, 1984. -С. 59-50.

22. Бершадский А. М- , Карпов Е. В. Синтез моделей объектов конструирования типовой САП? изделий РЭА и ЭВА морфологическим методом /.' Методология проектирования САПР: Тез. докл. всессюзн. совещ. 4.1. -Таллинн. 1985. -С. 74-75.

23. Карпов Е. В. Экспертная система оценки программного обеспечения вычислительны-: систем на основе методоз установления изоморфизма графов// Методы анализа надежности программного обеспечения вычислительных систем реального времени на основе моделей нечеткой логики и 1сачественных описаний: Тез. докл. всесоюзн. конф. -Киев, 1987. -С. 61.

24. Карпов Е. В. Координация системы ограничений в иерархии подзадач САП? МАБКС и ТЗЗ// Киоеркетика, АСУ, математические методы в технике и народном хозяйстве: Тез. докл. регион, конф. -Томск, 1986. -С. 82.

25. Карпов Е. Е Стоуктурный анализатор схем на основе выделения изоморфных подграфов для адаптивной САПР ЭВА// САПР в машиностроении: Тез. докл. всесоюзн. конф. -Ульяновск» 1090. -С. 73.

26. Карпов Е. Е Структурный анализатор для УИ САПР на базе сональной ЗЕМУ/ Разработка и оптимизация САПР и ГАП изделий электронной техники на базе высокопроизводительных мини- и микроэвм: Тез. докл. всесоюзн. совещ. -сомин. -Воронеж, 1989. -С. 142.

27. Вернадский А. Н , Карпов Е. Е Пакет прикладных программ "Волна"// Технический прогресс в атомной промышленности. Сер. Организация производства л прогрессивная технология в приборостроении. -1990. -Вып. 7-8. -С. 56.

28. Вернадский А. М. , Карпов 2. Е , Тужилов И. Е и др. Система автоматизированного проектирования матричных БИС "CIIAFF."// Там го. -С. 55.

29. Карпов Е. Е Некоторые принципы декомпозиции ограничений и критериев конструирования в адаптивной САПР МЗА// Автоматизация конструкторского проектирования РЭА и ЭВА: Тез. докл. семин. -Пенза ПДШП. 1984. -С. 27-29.

30. Б^-шадский А. 'Л , Карпов Е. Е , Тужилов К. В. Методика у1'ета системы схемотехнических ограничений з подсистеме автоматизированного проектирования ТЗЗ// Там ге. -С. 5-6.

31. Бершадский А. Ii -, Карпов Е. R , Тужилов И. Е Структура программного обеспечения подсистем размещения САПР НАБИО и ТЭЗ// Автоматизация конструкторского проектирования РЭА и ЭВА: Тез. докл. конф. -Пенза: ПДЧГП, 1983.--С. 12-13.

32. Бершадский A. Ii , Карпов Е. Е Синтез структуры типового объекта проектирования в САПР МАБИС и ТЭЗ// Там же. -С. 34-35.

33. Карпов Е. Е Подсистема прогнозирования сбъеотов проектирования интегрированной САПР МЗУ//Автоматизация конструкто;>ского проецирования РЭА и ЭВА: Ted. докл. конф. -Пенза: ПДНТП.1935. -с. 15-16.

34. Разработка ко'^понентов подсистемы трассировки ИСАПР МАБИС: Отчет по НИР ГР iJo 01.84.003494/ Вернадский A. IL - научн. руков. , Карпов Е. Е - отв. исполн. и др. Пенза: Пенз. ПИ, 1986. -С. 13-27.

35. Кзрпов E.R 05 особенностях имитационного моделирования как средства адаптации САПР СБИС// Автоматизация проектирования РЭА и ЭВА: Тез. докл. конф. -Пенза: ПДЭНТЗ, 1991. -С. 17-18.

36. Карпов Е. Е Экспертная оболочка для САПР изделий электронной техники// Автоматизация проектирования гЭА и ЭВА: Тез. докл. конф. -Пенза ВДНТП, 1992. -С. 10-11.

Попписано в печать 22.04.93.Объем 1,0 усь.печ.л. Уч.-изд.л. 1.0.ТЛ00 скэ. Заказ .

Воронежский политехнический институт 394026 Воронеж , Московский пр.,14 Участок оперативной полиграфии Воронежского политехнического института