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

ВОРОНЕЖСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

„ . » п Лля слуаебного пользования

М 606 С ' Экз. N №

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

ЧЕРНЫХ Ольга Ивановна

УДК 621.382:627,398.8(07)

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

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

А В ТОР Е 5 ЕР А Т

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

Воронел 1990

/'Л ч /.-•> с/

Работа выполнена в Воронежском политехвичеохоы институте.

Научный руководитель:

доктор технических наук, профессор Я.Е. Львович

Официальные оппоненты:

доктор технических наук, профессор А. 11. Вернадский

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

Ведущая организация :

Научно - исследовательский центр электронно-вычислительной техники НПО "ПЕРСЕЙ" (г. Москва)

Защита состоится "24" оентября 1880 г. в чаоов на васедании специализированного совета К 063.81.04 при Воронежском политехническом институте по адресу: 384028, Воронеж, Московский проспект, 14, конференц-зал.

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

Автореферат разослан " " 1890 г.

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

^рЖ/- Львович

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

Актуальность проблемы. Ключевой проблемой отечественной

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

Современный этап развития САПР !.!ЭА характеризуется переходом к интегрированным спстс:;;м, обеспечиваю:^! сквозной цикл проектирования изделия. ТакоЯ цикл пкдэчзет, как правило, следующие основные этапы : стрултур::сз, иерархическое проектирование; логическое иодеяпровагпгэ я синтез тестов; топологическое проектирование; всрт'гнпггл, то есть проверка корректности функционирования схеш с учзтеа ргзльг-К гз^р?.?«, вносим« паразптн!:\':1 емкостями п сопротизлеппс'л элементов п глззссоэдинвииЯ cxer.ii; подготовка и сцдача таяояогпчзскоЯ кфоргаця». Обяаругеике оппбок на этапе верп1нкащ:я приводит к поатсро:Г;::э цзяяа проектирования необходимое число раз, которое удореппт :: увеличивает срокя его проектирования.

Кроме того, увеличение затрат па проектирование связано с ростом размерности о'йткыязацаоншх задач САПР, обусловленный ежегодным повышением уровня интеграции СЕНС а 1,5-2 раза.

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

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

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

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

Работа выполнена по заказу N 158 от 6.04.87 предприятия п/я А-1572 в соответствии с планом работи Ш. All СССР и ПОТ СССР на 1S35-1S90 гг. ¡1 до 2000 года, ориентирована на выполнение теци "Разработка теоретических к экспериментальных основ создания сисоконадепной микроэвм на целой пластине" и соответствует одноиу из основных направлений Воронежского политехнического института "Разработка САПР, роботов и ГАП"

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

Достиаение указанной цел;; предполагает решение следующие основных задач :

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

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

разработка и реализация вероятностных алгоритмов оптимизации топологии 1,'.аБИС ;

интеграция проектных процедур адаптивного размещения S3 на базе САПР SL-2000;

адаптивное управление процессом проектирования.

Объектом_исследования в диссертационной работе является

система автоматизированного топологического проектирования узлов U блоков ИЦП-микроЭВД на основе КШП базовых матричных кристаллов. Методы исследования. При реиении поставленных задач в работо

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

ПАУЧКА новизна. В работе получены и выносятся на защиту сяодуюцие результаты, характеризующиеся иаучноЗ новизной :

ллтолтгпчеслие мозоли кюяокошог и ргагсззвкл СЕУС, рл -тлгл^-ло спзц>'?чку сбюлтл npoertripoDvnm лол;т;;лерлого типа;

п л г о р : í г г " п 2 с i с i о c:;sî'!î сгох-.стлчзсхсЛ олт;;!с:огп"Я, по^гол;:- -•":<> »n осногг лпухуровпопоЛ аг^пт^цнн путем пзрьпроплиия глуС;""« f : о :. с ; с а ссуллстллтл :л:5ор л'>л'Уол:л лт-л сгго;г:'-::: с рлгл''!;

пр'ягслурч прчвятял рл"<лл:П з уологлл:: стол^сплослоЛ л~ллг •••■

Л!"ен::олгл, срлллтлро: лл:": л" "олул 'ллл л ' ¡уст:......: ■ р:лллл ; -

"л::::Л по Г'лтрлт;^? •5-юус.лпптл>л: л л^слтлсс;:!, сгл:срл"л:ллл:о! ^"л: ••

лрл'-р/рл отрултуул^У ' р;;"гл ллл ■ \л- - л- л л:"г~'--> ::лл: ■ 3 л ллролтлсотоП, лгрл: "-го рол) лолл'::лтлллл;, р>ллл ;'лрл " л—

услол :л ллтрсллллл! уел-: л'^ллл лслелуу'лул":л лголлсл"".:'-..,.., v;rcp.;7.c., рс^рл-.л^----'; ■ рл ГГЛЛ'ЛГ'М, Г: Л'Л-Л'р'.....ПСЛЛ'ЛЛЛ-

; л л лплсУс лстллл слу'"\л"го глрглгл ;.л тлл л л ;гр"л::грз'-" Пллцуулрлл;1 ЛУУУУ'УУ ллУлтл. Г;Л'ЛЛ'Л лл"л у 'ото

л'~слла ел 'ел "лл'лло ллеллл л;г лл'л ;

.""' ' л ' ' р:сгллл;. аре-: .oro, :,> л-.-.лл" ; • л л л" ил-: : л'л1 .ллпрл рлптл;л:о'1 сл'л:"стл'":сло'! спт.'л'лси":! прроллллл:т ссбол кснструктсакуп ссяозу длл ллгерлтлллчлл; л:тсл:сго лллсг ; ергл Сулзгого прогрл'-ллрлглллл.

Р''1л';л'!'"л пллул'.тлгол плУолл. Прэдлс"? :::••"! л ртбогл "ЛТ'""'Л-

т:гпс:с:о лэдэлл л плгерчги автезтпческого рас:'е:;-:;п:я

рзпллсспллч з лодслстсз ¡тро'лалролллля топологии ЛРЛ, ллтзгрлро-л:::люЛ с ::ласлспрлл-лрл'гллу:сл сплолпеЛ С.'Л? S!r-2CC0.

Прогрл^лл'з ерздетга лдлптллпел ептлллллпл:! тспологлл гллд-р:лч л р-'лгл:: леруогеллр-::'! !"!? "Рлгрзботка сшерлтлллол ? ♦"•"•nncîî СП? гскфоГГ! гл ■ гллой пластлло" d ÎIÎÎI-Î ОТ

г. Пороллга с cn'r.W-' » годоглм г::с:!ог:г:оским с^'зктси Е-3,2 тыс. рублгЛ прлатги а 'л"П з г, К::о2э.

Результат'! длсслртрлсллсЛ рСзти пепользуятел в ууебпем пророс •> лрр.-г! СЛГР з Всрслл::с;:см поллтзллэтесксм институте для ■ • л г-- сплл'лллглгеот:! 22.03 и слугзтедел специального факультета

по переподготовке кадрои по специальности "Системы автокптизнро -ванного проектирования".

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

Апробация работы. Основные половения и научные результаты

диссертационной работы докладывались и обсувдались на XV Всесоюзно;.! совецашш-сешшаре "Методы и средства САПР в ГАП ыикроэлек -тропики. Пути развития и внедрения." (г. Москва, 1987 г.); но совецашш-сешшаре молодых ученых и специалистов "Интегрированные систеш автоматизированного проектирования в гибких производ ственных системах" (г. Воронек, 1S88 г.); на научно-технической конференции "Автоматизация конструкторского проектирования РЭА и ЗВА" (г. Пенза, 1988 г.); на Всесоюзной научно-технической конференции "Проектирование вычислительных средств" (г, Каунас, 1689 г.); на школе-семинаре "Цетоди автоматизированного проектирования электронно-вычислительной аппаратуры и СБИС (САПР-89)" (г. Киев, 1989 г.); на Всесоюзной совещании-семинаре молодых ученых и специалистов "Разработка и оптимизация САПР и ГАП изде -лий электронной техники на базе высокопроизводительных мини- и цикроЭВМ" (г.Воронек, 1989); на региональной научно-технической семинаре "Разработка и эксплуатация САПР в радиоэлектронике" (г. Челябинск, 1989 г.); на иколе-семинаре "Автоматизация проек -тирования топологий СБИС и конструкций РЭА" (г. Киев, 1930 г.); на Всесоюзной школе-семинаре молодых ученых и специалистов "Методы искусственного интеллекта в САПР" (Гурзуф, 1990 г.); на научно-технических конференциях ВЛИ (г. Вороне*, 1088 -1990 гг.).

Публикации. Основное содержание диссертационной работы опубликовано в 16-ти печатных работах [1-16].

Структура и объем работы. Диссертация состоит из введения ,

четырех глав, заключения, приложение и списка литературы, содер -«вдего U5 наименование. Работа изложена на 180 страницах машинописного текста, содержит 28 рисунков и 10 таблиц.

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

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

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

В первой главе прозеден анализ современных тенденция повызе-

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

Рассматривается несколько подходов к проблеме повышения эффективности КП МаБИС :

повьшение проектируемое™ аппаратуры за счет регулярности структура монтакно-комиутационного пространства;

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

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

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

В результате.исследования тенденций развития конструктивных ргалпзацпй БИС и СЕ.'С сделан вывод о той, что происходит постепенной ослабление требований к унификации конструкции кристалла, при этом основное ого достоинство регулярность структуры, обеспечн-вахоя высокуо степень автоматизации проектирования топологии, в той или кноЗ степеш! сохраняется. В пастояцеа вреия для создания . спрокой номенклатура устройств предпочтение отдается КНОП ЕЖ высокой степени интеграции. Например, для проектирования высоко -производительных ЭЕУ "четвертого поколения в качестве элеиентной базы продполагаатсл использовать Ш'ОП Е'ЛС типа "коре вентилей". При создания изделий электронной техника на целой пластано ( ИЦП КЭТ) использузтся ШШ ШК коллинеарного типа. Отмечается, что париаэт конструкции Ю10П кристалла, содеркаэдй ряды логических ячеек равной нчсоти, наиболее приспособлен к размеренно библиотечных элементов, имеодих одинаков;;» пас т и разную ширину. Линей-

чагой структурой могут Сыть представлены такпо кристаллы ТТЛ, ЕСЛ

¡; яогшгк. На соносашш рассмотренных структур Б!..'К сделан вы-код о том, что с точки зрения современных технологий наиболее прдкткчиыма являются кристаллы коллинеарного типа, обеспечизакщие удобство формализации и оптимизации топологии.

Подчеркивается, что ва&ным средством поддержки проектирова -ния СБИС высокой степени интеграции является многообразное применение иерархической методологии проектирования ; структурная декомпозиция объекта проектирования, декомпозиция проблемы размещения. Указывается, что традиционное разбиение синтеза топологии СБИС на три взаимосвязанные задачи : 1. компоновка узлов сильносвязанных элеыентов;2. размещение узлов в ионтакно-коммутацпонноп пространстве }.!аБИС ( в линейках Б!.!К коллинеарного типа);3. размещение внутренних элементов узлов в заданной подобласти ЫФ является нерациональны».! способом декомпозиции задачи размещения СО СБИС коллинеарного типа. Игнорирование длин ыесузловых связей на отапе компоновки узлов приводит к менее качественным проектный росзниям и росту вычислительных затрат.

Указываются. такие недостатки существующих подходов к линей -ному размещению СЗ и намечаются пути их преодоления.

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

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

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

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

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

растеризуются так ке наибольшей эффективность» при ргсении задач большой размерности.

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

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

Во второй главе диссертационной работы рассматриваются н

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

ГШ - § § с.«* хп —> п1п (1)

1-1 >1

при ограничениях

§ ху - 1 , ; § ху - 1 , 1-1,п ; ху - р

где с^ - расстояние цеаду 1 - и и j - и городами. Ограничения

(2) означают, что в любой город моано войти и из любого города цогно выйти только один раз. Ограничение, требующее отсутствие подциклоз в ыарзруте, и записи ( 1 )-( 2 ) не присутствует, оно выполняется алгоритмически.Функция цели (1) соответствует длине всего маршрута кошивоязера.

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

вероятностен. Далео сформулированы условия, позволяющие адаптивно

(2)

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

N Н-1 N

Р^ - Рц * Чи + Ри (3)

и условия локального улучшения, записанного в вариациях относительно сага движения Рц :

и т(ГСХ)) - I! Г ,<Г(Х)) О .

и0 1Г 1

получено следующее неравенство : Л Л-1

Ри *(3Г ) < Ри *(31 " V* (4)

где

Н-1 N-1

в 2 с + с + ^ * 2 с

1 пЧ Ыс.а* кз* "-1 >к

Н-1 N-1 п N-1

%2 *с **Р « + с * *Р *

(5)

¿^к.э 1з з к з к

Оно позволяет путем сравнения двух величин : (средняя длина

трехреберного частичного маршрута, содержащего ребро (к,з*)) и

(ожидаемая длина частичного маршрута, содераащего ребро (в*,к)),

3

получить рекомендации по адаптивному изменению шага двиеения рц

на Л-П итерации.

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

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

N

точность» выбирать направление движения71 ..При это«, по аналогии

кэ

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

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

Будем формировать окрестность к -ой точки по следующему правилу :

e(k) - { i: i с Z Л p,d > А ) ,

гдо А - некоторое пороговое значение вероятности. Допустим, глубина поиска а » 2, тогда формула для вычисления оценки условного математического огидання (У!!0) выводится в предположении, что фиксируется дзухробер'лые частичные маршруты к -> з -> г, гдо з с е(10, г с о(о) и представляется в следующем виде :

Gksr°cl(3- ^ cisPia~c3iPsl'fCsr~ 2 «irPir^srPsr^rlPrr 2 c3jP3j ieZ 1с2 jcZ

Таким образом, выполнение условия локального улучзения. в этом случае иогет осуществляться по следующей схеме. Для всех точек з из окрестности It -ой верзины - oik) и точек г из окрестности я -ой серпны - е(з) - вычисляем величину Скзг. Ищем пару

(а*,г*) такую, что

G¡t3v "sS№r •

ree(s) « N-l

и полагаем ir -1, n¡<3 =0 . Vs*s .irypy Vi:{icM,i*k}, VjcM.

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

Sj - алгоритм вычисления Акд Vsce(k) npn а - 1;

52 - алгоритм вычисления G^gy. Vsce(k), гсе(з) при а - 2;

53 - алгоритм вычисления Qk3l4 Vace(k),rce(3),tce(r) при а - 3.

Через |е| в таблице обозначена максимальная модность мнояества исследуемых точек из окрестности фиксированной вершины.

Табл. 1.

Алгоритм Верхняя оценка вычислительной сложности

|е| -п ,Ие| < п

Б 1 5 (п-1)2 Ы1 п п(п-1) 4 * I (п-1Н*- 1-1 2

Б 2 Д 2 3* 2 С(п-1-1)*(п-1) 3 1=1 2 п з * ^«г (п-1) 1-1

3 3 й ' 2 5* 1 [(п-1) *(п-1-1)*(п-1-2)] 1=1 5» Л 5 (п-1) 1-1

Вычислительные эксперименты показали преимущество оценки С){ЗГ

над Акз и акзг1 .

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

П о 12 1 Е(р)- I £--*(р - - ) + - ], (8)

1=1 (е-1)2 1 е е

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

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

минимальное значение псевдоэнтропии достигается на единичном векторе вероятностей;

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

Утверждение. Дшгонае эида (0) в икогостсе случп;!тг: сектороэ обеспзчммот монотонно умсиьсешм -птроп'лл систол при

1

р г, (А-1)/(2*А-1) . В >. 1 , А •< 1+ -- (?)

ц 2(В*Н-1)

Просбразосан::э ^ср-гул (7) к виду

р „ - , В ь 1, О « ? с *

и Е:М+у

позволяет сделать емзод о тем, что сходимость энтропии к 0 достигается за счет довольно с.чг.б!.^: ограиичзп'.'.й на ри . т.к. из после,'?.ннх бор:1ул следует, что при Н —>со ри—> у . гдо т - лпбое

число из [0,13.

Так как минимальному значен::» энтропии соотпотствуот единичной вектор распределения вероятностей, то полученные утверждения о монотонном умены:еш'л энтропии з процессе поиска позволяя? сделать гмпод о тем, что происходит постепенное преобразование случайного процесса поиска в детертшированииЗ.

В тпотье'? главе диссертационной работы рассматривается ».тате—

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

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

F(X) = !!! ! aijxirxjqlr~^l —> oin r=l q»l i»l j-1 при ограничениях

VM.n,

(0)

ji> ч< DL

Ы

Vr-1,0.

Переменная является булевой и определяется следующим образом: Х|Г 1, если 1-ый элемент назначен в г - ы8 ряд и -0, в

противно» случае.

Математическая запись задачи компоновки в виде < 8 ) - ( 9 ) позволяет отнести ее к типовой модели квадратичной задачи о назначениях. Заметим, что использований модульной штрики |г-ч| обеспечивает компоновку элементов а узды-линейка со слабш учотоы

расстояния ыевду линейками, в то время, как квадратичная (г-я)^

или кубическая |г-<1|3 метрики позволяют более дифференцированно оценить расстояние ыеаду рядами. Поэтону целесообразно в ходе итерационного процесса-поиска, редения задача ( 8 )-( 8 ) периодически переключаться с одной метрики на другую.

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

Математическую ыодель размещения элементов в линейко по выбранному критерии МЧГО запишем в следующем виде:

£ xik - 1 ° VM.n; 5 xik = 1 Vk-i.n; . dl)

Г8(х)-1 I § 2апХ1кХл<Р Уп=1,п-1; (12)

1{»1 1-з+1 1-1 ¿-1 здесь х^ - булева переменная, определяющая назначение 1-го С>Э на

к -е место, п - количество элементов (мест), а]С| - элемент матрицы смегности, Р - оценка максимального допустимого числа провод -ников з горизонтально« канале. Таким образом, функция цели ( 10 )' является математической записыэ критерия 11ЧПС, группа равенств ( 11 ) требует, чтобы на калдое место был назначен только один элемент и каздДО элемент был назначен только на одно место. Ограничения (12) выражают требования на пропускную способность вертикальных сечений, нетрудно видеть, что

С(х) °"Ё1Г3(х) (13)

з=1

Покаяем связь предложенного критерия МЧПС вида (10) с критерием минимума суш'зр.чоЛ длины горизонтальных соединений (НСДС), но учитывающим геометрические размеры "О :

С"<х>-£ 5 2 Ьп х^х.^к-И -» П1п (14)

1-1 к=1 1-1

Утверждение. Если 5Э схемы считать гссцзтрпчсскгагл точками, то критерии вида (10) и (14) эквивалентны.

Это утверждение приводит к выводу о замене критерия вида (10) критерием 1'СДС (14), более простым с вычислительно!! точки зрения. Однако,равенство (13) показывает возмозность другого решения. Там, где ограничение на пропускную способность не критично, будем использовать математическую модель (14), (11); в остальных случаях процесс разнесения будем моделировать с поноцыо формул (10),(11), (12). Существенным преимуществом критерия ИСДС вида (14) по отно-сепкп к критерии ИЧПС (10) является возможность минимизации длины с£!.о!х протлгешш соединения путем перехода от модульной метрики

|и-1| к степоииоЯ : (к-1)2, |1<-1)3 и т.д. Таким образом, скон-струнрогаки Деэ альторнатпвкыэ модели размещения, различающиеся по стэпена вычислительной сложности. При этом необходимо отметить, что рзпение, полученноо по критерия ИСДС, целесообразно проверить парад этапом трассировки на выполнение ограничения (12).

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

I'i

компоновки б данную линейку, обособленно от остальных элементов схемы, с которой! o:i;¡ могут бить взаимосвязаны. Для согласования

виделешйл: подзадач разнеу-зквя вводев, ток наиизаемыЛ, вектор проекций, разделении?, на согиэпти. Перед началом линейного размещения элементов донного узла исследуатся нл связи с у:;е раемеден-нши элементами в друп;х узлах и, как Си, "проецируются" ни соответствующе сегменты вектора проекции. • В результате это!; процедуры строится матрица ско-иости В - {by}, i=i,n , оломэпт которой b¡ ^ покасмсает чвело связей ыехуу i -:¡ элементе:.: рассматриваемой лкиейкк и j-n ссгшитоа вектора проекц.и;. Тогда, польяя-атся уоогае»ству..-::е добавон:;иг члени к цзлев!.:.! (¡упкцндм ¡: пункциям огрхжчэиг.5..

Для учета ограничош;П на пропускную способность (12) введен: итрауная функция вида :

у(;:ЬС (::)+£!, (х) •»• Со(х) -»• 2 асЛС,.(х) + с1с<я) + g2„<::>),

GCP. "

где- R={ s: í3(::hsLJ::)+B2j(y.)>P }, ífa(>:)4üla(x)+e2i,(::)-P)/P.

Тогда процесс ы;-лв;и;:задю; функции (19) при ограничениях (íi)-(32) сводится к поеледоеате.-мюотя росасмых садач : если П « 0, то i;:¡-нкм.'.зируется целееая ¡-лткцхл (10), иаачо ¡.ихнм.нелр/ется escolie«! сумма пеьяеол.

В основу сгохестаческоГ. алгоритмизаций садач компоновки и размещения полсмены идеи технические приема адаптивной оптими -сацпн, изложенные ;м< примере седачл кс:..млг.олаера во ьторсП главе.

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

В четвертой глаг.»; рассматривается реадиггцая продке^запмх

мйтеиатическш: моделей.*' адаптивные: алгоритмов автоматического разнесения в подсистеме проектирования топология ;\DA. Программное обеспечение подсистемы ADA в соответствии со структурно?. декомпозицией задачи синтеза размещения разделено не два пакета приклад: j

ннх программ: AKOí.íP— ППП компоновки <10 в узлы-линейки БМК; ARAS7-

ППП линейного размещения 'I-Э. Логические и информационные связи указанны:: ППП регламентируются Гласи:!.! монитором системы. 5ункци-ошфованпе подснсте?™ ADA в автономном регкмо не представляет практического интереса. В целя:: интеграции ее а составе САПР, реализующей сквозной цикл проектирования, за основу взята СА.ТР SL-2C00, являющаяся высокопроизводительной системой проектирова -нпя, допускающей возможность расширения я замены модулей. В свою ■ очередь, соединенно САПР SL-20C0 с альтернативной подсистемой размещения повышает адаптационные возможности этой системы. Рассматриваются способы оптимального выбора мар'.грута проектирования во мнонсстве альтернативны:: алгоритмов на основе методов структурной адаптации. Приводятся результаты опытной эксплуатации ПС ADA при проектировании схемы управления память» ИЦП - микроЗВМ на базовом матричном кристалле ТЕРЕКЗ. Экспериментально установ -лево, что наилучший результат размещения получен в результате последовательного применения программ ADA и GPLACE.

Основные результаты работы заключаются в следующем :

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

2. Разработаны математические модели кошоновки и размещения СЭ л::нейчатых СБИС. Предложены две альтернативные модели линейного размещения - по критериям !.!СДС и МЧПС и указаны условия та предпочтительного выбора.

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

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

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

4. Предложены процедуры структурной адаптации, позволяющие

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

5. Разработанные программные средства нашли практическое применение для топологического проектирования узлов и блоков ИШ-микроЭВМ, изготовленных по КМОП-технологии и приняты в межотраслевой ФАП в г. Киеве. Ожидаемый годовой экономический эффект от внедрения разработанных программных средств составляет 56,2 тыс. руб. Результаты работы в форме программных средств и методических указаний к ним используются в учебном процессе ВПИ.

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

1. Каплинский А.И., Чернызова Г.Д., Черных О.И. Адаптивный выбор ограничений при алгоритмизации булевой задачи математичес -кого программирования на основе вероятностного варианта метода ветвей и границ // Моделирование и оптимизация сложных систем.-Воронеж: ВПИ.-1988.-С. 87-94.

2. Горбунов В.Г., Черных О.И. Определение проектных решений в условиях многокритериальной оценки их качества // Методическое руководство к лабораторной работе по курсам "Теоретические основы построения САПР", "Теория принятия проектно - конструкторских решений".-Воронеж: ВШГ.-1987.- 12 с.

3. Чернышева Г.Д., Черных О.И. Вероятностная алгоритмизация в задаче компоновки // Математическое и алгоритмическое обеспечение оптимизации сложных систем.-Воронеа: ВПИ.-1837.- С.59-64.

4. Львович Я.Е., Рындан A.A., Черных О.И. Алгоритмическое обеспечение автоматизированного проектирования микроэвм на одной пластине // Автоматизированное проектирование в радиоэлектронике и приборостроении.-Ленинград: ЯЗТИ,-1887,-С.93-97.

5. Львович Я.Е.,Рывдия A.A., Чернышева Г.Д., Черных О.И. Интегрированная подсистема топологического проектирования МаБИС КДОП-ткпа на основе адаптивных алгоритмов // Автоматизация копе -трукторского проектирования в радиоэлектронике и вычислительной технике : Меявуз. сб. науч. тр.- Вильнюс, 1988.- С. 135-139.

8. Черных О.И. Модели и адаптивные алгоритмы компоновки в интегрированной САПР ¡ШОП матричных БИС// Интегрированные систем автоматизированного проектирования в гибких производственных системах: Тез. докл. совещан.-семин. молодых ученых и специлистов. -Воронеж: ВПИ, 19Ö8.- С.36.

7. Ворожеева C.B., Чернышова Г.Д., Черных О.И. Построение вероятностных алгоритмов оптимизации с использованием модифици -рованной функции Лаграяжа для задач САПР // Оптимизация и моделирование в автоматизированных системах.-Вороне»: ВПИ,1988.-С,87-90.

8. Горбунов В.Г., Черных О.И. Оценка и выбор метода оптиш -зацин для проектной процедуры // Методическое руководство к лабораторной работе по курсам "Теоретические основы построения САПР", "Теория систем и ее приложения".-Вороне»: ВПИ, 1988. - 18 о.

9. Львович Я.Б., Рындин A.A..Черных О.И. Модели и адаптивные алгоритмы Компоновки и размещения в интегрированных САПР КМОП матричных СБИС // Автоматизация конструкторского проектирования РЭА и ЭВА: Тез. докл. науч.-техн. конф.-Пенза,1988.-С. 22-23,

10. Каплинский А.И., Чернышова Г.Д., Черных О.И. Методика конструирования адаптивных алгоритмов оптимизации топологии СБИС/ /Проектирование вычислительных средств: Тез. докл. Всесоюзн. науч. -техн. конф.-Каунас, 1989.-С. 188-190.

11. Чернигова Г.Д., Черных О.И. Адаптивная алгоритмизация в гадаче размещения функциональных элементов МаБИС//Иодели и алго -ритмы оптимизации в автоматизированных системах.-Воронеж, ВПИ, 1689.-С. 38-39.

12. Черных О.И. Анализ вычислительной сложности адаптивных алгоритмов ревения задач оптимизации топологии СБИС // Разработка п оптпмяэащя САПР и ГАП изделий электронной техники на базе вы -сокопроизводнтелышх мини- и микроЭВМ: Тез. докл. BcecoDSH. совет, -семинара молодых учета и специалистов.-Воронеа:ВПИ,1989.-С.128.

13. Рындин A.A., Савинков О.В., Черных О.И. Вероятностная алгоритмизация оптимизационных задач топологического проектиро -вання // Разработка и оптимизация САПР и ГАП изделий электронной техники на базе высокопроизводительных мини- н микроЭВМ:Тез. докл. Всесоюзн. совещан.-семинара молодых ученых и специалистов. -Воронен: ВПИ, 1989.С. 130.

14. Львович Я.Е., Рындин A.A., Черных О.И. Проблемы создания интегрированной САПР СБИС на основе адаптивных алгоритмов // Разработка и эксплуатация САПР в радиоэлектронике: Тез. докл. регионального науч'.-техн. семинара.-Челябинск, 1989.-С. 21-22.

15. Каплинский А.И., Львович Я.Б., Чернышова Г.Д..Черных О.И. Методические указания к построению программных средств дискретной оптимизации в САПР для студентов специальности 22.03.-Воронеж: ВПИ, 1989.-32 с.

16. Львович Я.Б., Чернышева Г.Д., Черных 0.И. Разработка оптимизационных моделей и адаптивных процедур топологического проектирования СБИС // Методы искусственного интеллекта в САПР: Тез. докл. Всесоюзн. совещания-семинара молодых ученых и специалистов. - Воронеж, 1990.-С. 107-108.

Наряд-заказ #121. Подписано в печать 12.07.90. Объём 1,0 усл.п.л. Тираж 95 экз. Зак. № £ . Бесплатно.

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

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