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

РГ6 од

о о Х'АРЬКОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ¿ЙНСтаТТ^таДИОЭЛЕКТРОНИКИ им. АКАДЕМИКА М. К. ЯНГЕЛЯ

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

ФОМИН ГЕННАДИЙ ГЕОРГИЕВИЧ

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

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

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

Харьков

— 19 9 3

Работа выполнена в Харьковском ордена Трудового Красного Знамени институте радиоэлектроники имени академика ДА. К. Янгеля.

Научный руководитель — доктор технических наук, профессор II. Ф. ОГОРОДНЕЙЧУК.

Научный консультант — кандидат технических наук, доцент В. В. СЕМЕНЕЦ."

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

— доктор технических наук, профессор С. В. ЯКОВЛЕВ;

— кандидат технических наук, доцент В. В. КАРАСЮК.

Ведущая организация — 110 Харьковский завод электроаппаратуры.

Защита диссертации состоится ,, 22 " ¿¿¿О¿<3- 1993 г. в /3 часов на заседании специализированного совета К 068.37.03 в Харьковском ордена Трудового Красного Знамени институте радиоэлектроники им. академика М. К. Янгеля (310720, г. Харьков, пр. Ленина, 14).

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

Автореферат разослан . 20 • _____1993 г.

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

Э. А. СУКЕСОВ

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

АКТУАЛЬНОСТЬ ТЕШ. Одной из главных задач общей проблемы автоматизации проектирования и конструирования является автоматизация топологического синтеза »пшроэлектронных устройств (МЭУ). О ростом интеграции МЭУ наблюдается устойчивая тенденция :с увеличении сроков их проектирования и ускорению их морального старения. Единственным способом частично разрешить данное противоречие является применение при проектировании высокопроизводительны < ЭВМ V высокоэффективных оптимизационных алгоритмов.

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

Наиболее' сложным этапом топологического егчтбза остается задача трассировки соединений. Для снмяние ее размерности используют иерархический принцип. которому также способствует' регулярность структуру коммутационного пространства, однако дано разделение этапа трассировки на предварительную (глобальную) и окончательную (детальную) но позволяет эффективно ис-¡гользовать мойные оптимизационные средства из-за значительных затрат вычислительных ресурсов. 1< сутествущгаг. в настоящее время САПР используются алгоритмы, ориентированные на определенный технологический процесс изготовления МЭУ. При изменении.технологии производства МЭУ необходимо переходить на новуи систему проектирования или дорабатывать имезпдиеся системы. Кроме того, в известнее качальнке алгоритмы заложен последовательный принцип трассировки. Рф£ективнооть применяемых алгоритмов может оыть оуздетвельо повышена испслгзованием методов о элементами эвтястшс и методов ¡¡скусственного иптеллокта, применение которых тормозктся отсутствием фтрм?.л:еоя$ипмх кнанхй.

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

Для достижения этой цели решались следующие задачи:

1.Разработка единой комбинаторной модели для различных задач канальной трассировки.

2.Исследование системы ограничений задач1/ канальной трассировки с целью выявления допустимого относительного расположения цепей в канале.

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

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

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

Научная новизна диссертационной работы заключается в сле-дулдем:

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

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

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

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

5.Найдены условия трассировки гглаяарлой схема в однослойном четырехстороннем канале.

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

Работа выполнена в соответствия': о планами ИКР Хзрьковоко-го института радиоэлектроники:.с работами по темам проблемы1 01.08.02 целевой комплэксноЯ программы МВССО УССР на 1986 -1990 года (и ГГ 18601200224);с программой МЗССО УССР "Ооздснтм'а развитие С АЛ? и их подсистем" (утворндена приказом МВССО УССР 10.09.86ko Государственной программой 6.4.Сиособи создания компьютерных интегрированных производств (раздел 6.4.1.Интегрированные компьютерные технологии проектирования! ГКНТ Украины 1992 г.

Реализация л внедрение результатов исследований. В результате папоштшх исследований разработано программное» обеспечение подсистему конструкторского проектирования, которое язляет-ся составной чзстьк комплекса программ сквозного проектирования РЭА. Экспериментальные результаты диссертационной работы- использованы в трех хоздоговорных темах, ном.гос.рег.01840050668, 018900811034, '019000509^0. Результата работы вн&,фены на одном из приборостроительных предприятия г.Харькова, а тэюхе используются з учебном процессо Харьковского института радиоэлектро-гажи.

Основные положения, выносимые на защиту:

1. Единая комбинаторная модель для различных задач канальной трассировки.

2. Способ построения нижних. оценок трассируомости мнонэст-ва цепей в двух- л трехслойном каналах.

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

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

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

6. Программное обеспечение подсистемы канальной трассиров-

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на зональной научно-технической конференции "Автоматизация конструкторского проектирования РЭА и ЭВА", (Пенза, 1939-1992гг.); Всесоюзной конференции "Теория и •практика построения интеллектуальных интегрировании САПР РЭА и БИС", (Звенигород, 1989г.); Всэсоюзном семинаре "Дискретная оптимизация'и исследование операций", (Новосибирск, 1990г.); школе-семинаре "Автоматизация проектирования топологии СБИС и конструкций РЭА", (Славское, 1990г.); Всесоюзной конференции "Математическое и имитационное моделирование в системах проектирования и управления", (Чернигов, 1990г.); четвертой Всесоюзной школе "Проектирование автоматизированных систем контроля и управления сложными объектами", (Туапсе, 1990г.); Международной школа "Проектирование автоматизированных систем контроля и управления сложными объектами", (Туапсе, 1992г.); республиканском семинаре Научного Совета АН УССР по проблеме "Техническая электротехника и электронное моделироваше" (Харьков, 1989-1990 гг.).

Публикации. Материалы диссертации опубликованы в И печатных 'работах, в том число 2 работы включены в Государственный фонд алгоритмов и программ и зарегистрированы в Р£АП ИК АН Украины, 1 работа - в отраслевой фонд алгоритмов и программ НИИ ВШ ГК СССР по народному образованию.

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

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

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

В горвой главе рассматриваются методы топологического проектирования МЭУ. Отмечается, что регулярность структуры позво-

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

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

Отмечается, что задача КТ, тек же, как и основные' задачи конструкторского проектирования, является задачей дискретной (комбинаторной) оптимизации. Осуществлена формальная постановке задачи К? кок задачи комбинаторной оптимизации.

Иэгть представляете - одним горизонтальным отрезком - интервалом. В каждом слое могут находиться проводники только одного направления. Слой, в котором располагаются горизонтальные (вертикальные) проводники,называется Я;У)-слоем. Один ряд включает одноименные магистрали на всех Я-слоях. Для каждой цепи множество трасс определяется набором магистралей. Назначение интервалов цепей схемы на магистрали канала однозначно определяет трассировку заданной схемы. Решением задачи канальной трассировки называется такое назначение интервалов цепей на магистрали канала, при котором удовлетворяются вез ограшпэния.

Формальная запись задачи КТ как задачи комбинаторной оптимизации на прямом произволении числовых множеств монет быть представлена в следующем виде:

т1п$(ы)- (1)

« с о ъ п '

ГЫ^х С^х..(2)

С ; ш « С ** 81 (и) 5 С{, 1=173 , (3)

где (0*=^, и^2,..., и^), П^ с .7=171;

I® = ..., I - ппгряна канала, N - число цапай,

Ц - число ограничений, а - число слоев. Предполагаема!} подход требует предварительного определения ширина капала I. Дял ее опредвлашя используются аналитические оценки трасснрувкостн

гмжйсгвв цепоЗ в канале. Элешнт определяет шз©р магистрали в слое на которув назначена цепь 3. Шожестт 1:0-нвчпоо числовое шожаство, шшмэнты которого определяет номэх® магистралей, на которцэ может быть назначена цепь ,1; для кавдой цош Л шоьзство индивидуально. Функционал Ф(ш) отражает качество совместного назначения цепей схемы на магистрали канала. Ситееь!а ограничений позволяет учесть не только гео:латрзчес-кае ограничения, но и функциональные.

К о&цэй постановке (1)-(3) сведены различные частные задаче квн&шшЭ трассировки: задача двухслойно!} ЯУ-трасснровки; задачи трехслоЕной НУЯ(УНУ)-трассировки, в которых порвий в гртнй слон иссольвуотся для горизонтальных (вортадальныз) проводников, а второй - для вертикальных (горизонтальных); задача «еногослоапой КТ (1ЖТ). Для задачи УИУ-трассировка известный алгоржпз левого края позволяет получать опиашльноэ решение только в отношения ширина канала, но нэ учнтазает такаа критерии, кап длина вертикальных проводников и длина налогэнЕй вер-■пшальшк проводников на различных слоях.

Единая постановка дает воздаяность строить общув схеку решения для задач КТ и затеи па ее осеовэ - алгоритмы решения Еоякрзтшлс задач. Постановка (1)-(3) позволяет легко учитывать дрполшгг&льныо ограничения на расположение цепей. Исходя из подставленной постановки задачи К?, определена задачи исследования.

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

GH=(!/,E.rf), в котором' множество вершин U соответствует цепям. Плотность качала D равна плотности графа GR - <p(Gg). Граф (?н является графом интервалов, для которого х(Оп)=ф(Сн). где X(Gjj) - хроматическое число графа GR. Любой подграф графе GH является также графем интервалов.

Если на вертикали канала находятся выводы на верхней и ния-ной линейках канала, то между соответствующими цепями существует вертикальное ограничение (ВО): одна из цепей должна располагаться внше другой. Множество ВО обозначается Еу и представляется ориентированным графом вертикальных. ограничений (ГВО) Gv=(í/,E ), в котором множество вершин соответствует гопям, а

дуга, проведенная от вершины и* к вершине и . , означает, что

•Ч "2

цепь .ij должна быть размещена вше цели j?. Длина пути в Gy-

р(и^,пк) определяется числом вершин этого пути, включая начальную ич и конечную и^.

графом* обобщенной конфликтности (ГОК) называется неориентированный граф G'lt (У, E^UEн), у которого ребро (u^.u^) в Е^, если в ГЕО существует путь от вершины и^ к вершине и^.

Далее в работе рассматривается два фрагмента ГВО. Первый фрагмент представляет собой линейный путь. Фрагменты -такого вида будем называть фрагментами первого рода (ФПР).

Фрагментом второго рода (ФБР) называется орграф, для кото-, poro выполняются следумцио условия:

1) S"(u3) > 1; 2) S'(Ujj) > 1; 3) |Q| - |«7| = X > O, (4)

где (S+ (u..)) - полустепень захода (исхода) вершины u^,

Q = {и±: з píuj.uj) л ptuj.i^)}; J = {ut« Q : Pv(«á.uk)}; iM'-^) - начальная (конечная) вершина ФВР.

Пусть цепь о назначена на магистраль и пусть Р = Q \ v (Uj.Uj,) . Минимальное допустимо расстояние между трассами цепей J и й, т.е. нишяя оценка трассируемости множества цепей Р, которому соответствует ГВО в виде ГОР и ФВР, вычисляется в соответствии со следующими выражениями, доказательство истинности которых приведено в диссертации: -для ФПР: aíj.k) * uy- Uj - i = Vuj»V ~ ?>

-для ФБР; аЧЗ,Ы .- а^ - о^ - 1 (6)

« ¿^ - - Л » • (?)

гдэ т=1 для И7-трассировки; '1=2 для ЬТй-трэсскровки.

Традиционным нашими оценками трассируемоети заданной схе^а в канале являвтся: с^ = °г= Внра2еакя (б)-

(7) ШБШдали предаэгнть рад новых, более аффективных, штшт оценок трасотруемости шоггества цепей в канасе. Дия етого к ГВО Су(0,Еу) добавляются две вершины б н Г и дуги от вершины й ко всей вершинам множества {и^е V .'¿"(и^О} и от всех вершин ш-гвстза {и^« и :3+(и5)=0) до вершины 2". Такой ГВО называется юдЕфацированным графом вертикальных ограничений (МГВО) и обозначается Е*).

В работе показано, что лвбоа ориентированный граф, а следовательно, лхйой МГВО, когет быть разон"? конечным числом способов на последовательность фрагментов первого и второго рода, таздв чго Ъ£ ,

6—1

2) V в ш ЗПрТ П = = <8е»1>» (9)

гдэ . 1г - сбцзо количество фрагггзншв для /-го способа разбнз-1£яя С^; ~ е-й фрагмент для /--то способа разблогшя.

Та;.; кт; кезду вериавама Я и 5' существует путь, то корна ала дуемая назвал оценка трассируемоста шюзшсгвз цепей схема в канадо:

ьх

а . «агГЕ + - 1)). / = 17®, (10)

. где Э - количество способов разбиения МГВО; аоГое'*е^ " 03201115 оцзнка для е-го фрагмента при /-м способе разбиения.

Если нианяя оценка трассируемости множества цепей, которым соответствует ФБР, определяется вырагшнием (6), то будет получена оценка а^, а если вырагением (7), то а4. Так как для гытаслвння оценка а4 необходимо определять нлотность графа об-r -.ru веда, то рассматриваются только те ФБР, да которых

i;Tn3x(Uj,Uj,) < а, где Neonat.

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

торне пересекают зоны ZLvi ZUI, А -- ?iü Pi+1, A.L= А \ Pi+1, \ Pi- Р. работе доказана следующая оценка:

D+1, если не существуем тс;

Dt-1, если min l1L,av>D для любой парк соседних зон и

а ^ vmax 1

э ^j+l' плотность хотя бы одной из которых равна D;

D, в противном случае, (11)

где тс - допустимый набор пэр цепей {i o'j.) J^ ¿¿.ig« }; lvmax~ наибольшего пути в ГВО после слияния взршин в со-

ответстБ™ с допустимым набором-пар-цепей % ..

Пусть' а таблице сон есть 7 таких зон, для которых d(Zi)=

- D, i - T7f. Pj - множество цепей, принадлежащих зоне Z^. Тогда верна следующая оценка:

а6=ГО>-2-т)/г1 + Ги1п >Ги1п. >/*1. Ü2)

ЭК <Й

где i?*6 s я . Я =• Я1х «?2х ...х д ге =■ ТГП?Т; Л1= Р,п ^ = : 3~(Uj) = 0), i = TTf; if- s 7f, J? = J^x ... x Я ж = if|Jt|> Я, = р. я = {J : ef(t/j) - 0}, ( = ТТт.

Проведенный в главе анализ системы ограничений позволяет существенно ограничить область поиска допустимого решения или, точнее, отсечь те области, в которых гарантированно не существует допустимое рееьяие. Допустимое решение для j-й цепи, если оно существует, может быть найдено среди элементов множества: Qj = { с^, u^tl, ..., о)^}. Значение o>jj(u*j) разно наименьшему (наибольшему) номеру магистрали, на которую momgt быть назначена трасса цепи Предложен набор решающих правил для определения граничных элементов допустимого диапазона каждой из цепей.

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

ГО канала) трассы цепи J. Подсчет йижних оценок траосируемости множества цепей afS.u^J и aïu^.T] позволяет определить начальные значения с^ и

Правило 1.

ujj •= a(S,иу + 1; = г - a[u^TJ, (13)

где afS.UjKfalUj.T}) - нижняя оценка трассируомости множества цепей в канале, которому на МГВО соответствует ориентированный подграф, ограниченный вершинами S и (и^ и !').

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

Если оценке с^ = Я,то з П = {(jltJ2), ,1,«* j2e i4i+1},

при котором а и*а о. V jgt: /îi41 э : e

Правило 2.

mac min u^1} ы't2= min [u^2, max ut5J.(14)

¿о

Пусть a1. Тогда верно следующее правило.

Правило 3.

3 1 d

1»)^= 1, ijä fij ; u^2= Ut2= z, j2«= nL . (16)

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

В третьей главе рассмотрен оптимизационный подход к решению задачи- KT.

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

0, если ы <з С

Р'(ы) = * Р°(ы), Р°(и)= о (16)

1Е1Х1(е1(и) ~ с1)»0ййЯ ь> « 0.

гдэ х1>> 1 - штраЗше коэффацгента, конэчвса цвльв оптямязсцшз стсяоблтся лолучокзз ¡хзнемзлкюго рвсоняя, пранадлогавдэго области досустаах значени!: ш*а С. Перетод к задаче безусловна опгагяацзз позсоляот расяфятъ чисто псгошоуекд отгашзаца-онхгтх йЛГ0р!Гге03 И ПОВЫСИТЬ 33 а'К«КТ1Г'ИОСТ!>. Г'рсмэ того, нс-оользоззшгэ аппарата итра<|пп функция псзголяет срокштть варианты рбЕзнзЭ. нэ удовлетворяющие ряду аш веем огрэшгшвя-ям. Оптамззяцгонная задача с учетом преобразования фушщзя наш (16) запишется в вздв:

с>*= сгя Шп ?'(«)• (17)

и с О

П^Х . . . X . (18)

В каждое из множеств ^ = 173 вводятся по одному адвкопту соответствующему неЕазпачекив цепи на магистрали канала. Вследствие этого С вводятся .^ошлштальпоэ ограничение, соответ-стЕущве неполному решении:

|ИЛ - ш°| > О , ¿ = (19)

и доопределяется критерий соответствущэЗ функцией штрафов:

N 0 Г 1г о=Ь

Р(ы) = Р'{ы) + Е А.? • а(ыл,ы°,), о(а,ЪМ (20)

,1=1 3 3 л I О, агЪ.

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

может бнть габран вектор ш°= ... 1соторий ссотетт-

ствуег яеназначонал всех цепей схемы.

Рациональное решение задачи (17)-(18) о учетом догоднвниЯ

(19)-(20) получается в результате реаения гослвдоватэльгостя

подзадач

= агв яС/г Р(ш) , й = 0,1,2,...; (21)

Ш е 0((<^) С О

0(ь£) = П^х , (22)

* *

где - некоторая окрестность комбинаторного объекта ш^.

Прочее получения рационального решенни делится на фпсси-

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

О1«^1) С О2«^) С ... С (TiwQ, (23)

где г - число этапов.

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

о1 (ш!1) = <w : е (1 - оц,^1)) s 1 ); (?4)

J=1 J J

02(Ü^) = {ы : - а «■>.,, w*» * 2 ); (25)

O3^3): t0j3= s1 у u)j3= f = ITp, s^ s2 , (26) где s2- номера магистралей.

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

IIa основе предложенного подхода разработаны алгоритмы решения частных задач KT. В качестве критерия для задачи HV(H\'H)~ трассировки Ф(со) выбрана интегральная оценка отклонений текущих положений цепей от их "целевых" магистралей. Ка качество полу-

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

Для задачи W/V-трассировки, кроме основного требования -получения допустимого решения, выдвигаются дополнительные -минимизация длины вертикальных проводников и длина наложений вертикальных сегментов, последнее из которых рассматривается при ранении задач /77- м //7Я-трассировя»г в качестве ЕО.

При реиэнш задачи MKT, а отлив от Я7(ШП-трассировкЕ, вертикальные проводник:! могут располагаться в разных слоях. В связи с этим нет всзмозшости определить допустимый дчапазоя магистралей и целэЕые магистрали для цепей. Предлагаем подход позволяет эффективно резать задачу 1ЯСТ даже тогда, когда выводи расположены внутри многослойной структуры. В этом случае добавляются дополнительные "глубиншэ" ограничения на расшлозэние цепей.

Если конструктив значительно загружен транзитными трассами, то увеличивается число вертикальных ограничений в каналах, которые яэ !,;огут быть использованы .для ушньпения области поиска, однако, которые увеличивают сложность задачи." В этом случае следующим после глобальной трассировки должен быто этап расслоения, на котором задача трэсафовки многослойного канала разделяется на ряд задач меньсей размерности дзух- или трехслойной трассировки. Задача расслоения топологии поило глобальной трассировки может быть рассмотрена как "глобальная трассировка в глубину" конструктива. Такой подход позволяет выбирать критерий расслоения, ориентированный непосредственно на получение допустимого решения в канале.

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

Пусть Х0={1,2.....п), Г0- {0,1,2, ...,П1).

Условие. Пусть схема размещена без пересечений в четырехстороннем однослойном капале "р. Трассировка схемы в канале t)

возмокна только тогда, когда

г г= кх, п г Лу, (27)

где п = п -2;

тах к(х), » тах КАу),

* Т « X Ту^уУ

О "О

К(х){Е(у)) - число цопай, у которых существуют контакты

и (х2,!/2) такие, что 1^1 < х < \хг\ Пу^ < у < |1/2|).

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

Четвертая глава посвящен» вопросам практической реализации предложенных моделей и алгоритмов. Разработан алгоритм приведения ГВО к ациклическому виду, так как методика анализа системы ограничений задачи КТ, а текке предложенные оптимизационные алгоритмы, предполагают отсутствие орциклов в ГВО.

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

Показано, что если рассматривать одну и ту г.е задачу КТ, то для задачи ЬУЯ-трассирсвки ВО будут оказывать влияние значительно Сольаеэ, чем для /^-трассировки. Вследствие этого область поиска задачи для етя-трассировки сукаэтея сильнее, чем для НУ- трассировки. Для 40 каналов, взятых из реальных МК МСБ, применение правил 1-3 позволило уменьшать облггть поиска допустимого решения в среднем на 20-25% для задачи ^'-трассировки и 30-35* для задачи Н7Н- трассировки.

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

прэвил на эффективность работы итерационного алгоритма для задач ?Г/- и гл/Я-храссирэвки. При а4<гЬ/2, большинство цепей имеют пдарокий допустимый диапазон для назначения на магистрали канала. При этом существует большое количество допустимых решений. Для такой задача КТ правила уменьшения области пояска малоэффективны. Порядок выбора цепей такяе оказывает очень небольшое влияние на результаты работы.

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

В главе прэдетавлэно сравнение результатов работы итераци-ошого алгоритма на ряде известных тестовых задач по модели ¡Г/-, Н7И-, УЯУ-трассировки с результатами работы изеостных алгоритмов КТ. Анализ представленных результатов позволяет заключить, что эффективность итерационного алгоритма для задачи двухслойной трассировки сравнима с эффективностью известных трассировщиков, а для задач трехслойной трассировки имеет превосходство как в отношении ширины капала, так и в отношении длины проводников. К примеру, для Трудного лргаера Дойча нижняя оценка а4 приняла значение, равное 28. Прлмпнениэ системы рэ-шавдих правил позволило уменьшить область поиска решения па 26%, а для б цепей сузить целевой дгатазон до 1 магистрали, т.е. до этапа трассировки однозначно определить трассы для соответствующих цепей. Оптимальное решение итерационным алгоритмом было получено за 21с на ЭВМ ЕС 1066.

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

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

Недостатком применяемого подхода являются дополнительные вычислительные затраты на предварительные преобразования и анализ системы ограничений задачи КТ, но эти затрата полностью оправданы и,в конечном счете, приводйт к сокращению времени Проектирования МЭУ.

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

Подсистема КТ позволяет выполнять трассировку соединений в прямоугольных каналах, каналах неравномерной ширины и з каналах с предварительно протрассированными проводниками по равномерной сотке в одно-, двух- и многослойных конструкциях. Подсистема реализовала б операционной системе ОС НУТ 6.1 на ЭВМ ЕС 1056. 3 состав подсистемы входит 54 процедуры, надиоанзыв на языке Фортран IV.

Эксплуатация подсистемы показала преимущество предлагаемы^ алгоритмов КТ по эффективности и времени счета в сравнении с исиользуешш при проектирования МК МСБ кмеюхимися. конструкторскими пакетами программ. Бремя решения практических задач составляет от единиц до десятков секунд и определяется, главным образом,количеством используемых етапов оптимизации. В среднем время реаения рассмотренных задач выие, чем у известных алгоритмов. Главным же достоинством предложенного итерационного алгоритма является возможность непосредственного учета эвристических условий реализации соединен?:.} в канале и адаптации к различным дополнительным требование.

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

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

1. Предложена единая комбинаторная модель для различных задач КГ, на базе которой разработана общая формальная постановка для рассматриваемых задач.

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

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

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

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

6. Найдены условия и предложен алгоритм трассировки однослойного канала как частного случая задачи многослойной канальной трассировкь.

7. На основе предложенных в диссертационной работе моделей • и алгоритмов разработано программное обеспечение подсистема канальной трассировки, являющейся составной частью комплекса сквозного проектирования РЭА.- Программные средства внедрена в

проиэаодотво и используются в учебном процессе.

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

1. Семенец В.В., Храмцов В.Н., Фомин Г.Г. Оптимизация распределения цепей по слоям печатной платы. - Доп. б УкрНШГГИ 8.09.88, К2272 Ук-68. - 11с.

2. Программный комплекс для решения задач размещения элементов мккроэлектрокных устройств / Огороднейчук И.Ф., Семзнец В.В., Co.Viffl Г.Г. И др. - РФАП ШС /Л УССР, кнв. Ш6360, ТОАП N5069000945.- 1989.- 190 с.

3. Программа оптимального распределения внешних контактных плоиодок михроэлектренных устройств между сигнальными слоями / Б.В.Семанец, В.Н.Храмцов, С.В.Пореходнов, Г.Г.Фомин. - РФЛП ШС АН УССР, инв. N06330, ГФАП, N30900000558.- 1990.- 56 с.

4. Сомэкэц В.В., Переходов C.B., Семин Г.Г. Глобальный трассировщик канальных структур. - СФАЛ ММ Elii, Государственный комитет по народному образованию.-1990. - 56с.

5. Семенец В.В», Фомин Г.Г. Канальный алгоритм трассировки однослойного канала // Тезисы докладов зональной конференции "Автоматизация проектирования F3A и ЭЗл Пенза.- 1989,- с. 53-55.

6. Семанец В.В., Переходной C.B., Фомин Г.Г. Моделирование этапа трассировки при проектировании топологии матричных БИС // Математическое и идттащюнное моделирование в системах проектирования и управления: Тезисы докладов Всесоюзной науч.-■гехн. копСорегаши . - Чернигов,- 1990. -с. 297-299.

V. Свшнец В.В., Переходяов C.B., Фомин Г.Г. Теоретические вопроса разработки САПР многослойных структур // Всесоюзная школа "Проектирование автоматизированных систем контроля и управления сложными объектами":- Харьков, 1990.- с.25.

8. Саманец В.В., Сомин Г.Г. Моделирование процесса трассировки соединений в канале /' Проблемы бионики: Респ. межвед. научи.-техн. cö. - 1990.- Вып.45. - с. 123-129.

9. Семенец З.В., Сом;ш Г.Г., Пероходнов C.B. Алгоритм трассировки однослойного канала для многопроцессорной ЭВМ // Автоматизация проектирования РЭА и ODA : Тезисы докладов зо-

няльноК конференции. - Пенза.- 1990. - з. 6м-56.

Ю. секинэц 5.В., Хремцоа В.Н., Фожз Г.Г. Оптимизационные алгоритма канальной трассировки // Тезиса докладов зональной конференции "Лвтомопшция проектирогапя РЭА и ЭЗА".- Пенза.-1991.- с,51-53.

11. Секзноц В.В., Храмов В.Н., £с:'ли Г.Г. Применение петелов комбинаторной оптимизации лли рвпення задач' канальной трассировки // Мездународаая школа " Проектирование автоматпзи-ровашах систем контроля и уяраь'Лс.::-. «¡ика ось-эктагш" : -Харьков- Туапсе,- 1992. - с. 29-30.