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

М1Н1СТЕРСТВ0 0СВ1ТИ УКРАШИ ХАРКШСЬКИЙ ДЕРЖАВНИЙ ТЕХН1ЧНИЙ УН1ВЕРСИТЕТ фд_РАД10ЕЛЕКТР0Н1КИ_

- 1 ЯНВ 1996 н

' ,м,и На правах рукопису

ЛИТВИНОВА 6ВГЕН1Я 1ВАН1ВНА

УДК 621.3.049.75.001.2:681.3

РОЗРОБКА I ДОСЛ1ДЖЕННЯ ТОПОЛОГ1ЧНИХ МОДЕЛЕЙ БАГАТОШАРОВИХ ПЕЧАТНИХ ПЛАТ ТА АЛГОРНТМ1В ТРАСУВАННЯ М1ЖЗ'6ДНАНЬ

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

Автореферат дисертацИ на здобуття наукового ступени кандидата техшчних наук

X а р к ! в —

1995

Дисерта1пею е рукопис.

Робота виконана на кафедр! Конструювання ЕОМ Хар-к1вського державного техн!чного ушверситету рад1оелектрон1ки.

Науковий кергвник:

доктор техн!чних наук, професор АЛ1ПОВ МИКОЛА ВАСИЛЬОВИЧ.

Офицй1ц опоненти:

1. Доктор техшчних наук, професор СЕМЕНЕЦЬ ВАЛЕР1Й ВАСИЛЬОВИЧ.

2. Кандидат техшчних наук, доцент ГРЕБЕНН1К ВАЛЕР1Й ДАВИДОВИЧ.

Пров1дна оргашзащя: Харк1вськкй державний приладобу-д!вний завод 1м. Т. Г. Шевчешса, МЫстерство машинобудуван-ня, в!йськово-промислового комплексу 1 конверсП Укра!ни.

Захист дисертацп в1дбудеться /Р " ¿/"¿¿¿Л 199/року о ,,/3 " годин! на зас1данн! спец1ал!зовано1 ради К 02.25,03 у Харк1вському державному техшчному ун!верситет1 рад1оелек-трон1ки за адресою: 310726, м. Харк1в, проспект ЛенШа, 14.

3 дисертащею можна ознайомитися у б1блютец! Хар1пвсь-кого державного ун1верситету рад!оелектрон1ки за адресою: 310726, м. Харк1в, проспект Ленша, 14.

Автореферат розклано . " 1995 року.

Вчений секретар спеиЛал!зовано1 ради

В. БЕЗКОРОВАЙНИЙ

ЗЛГЛЛЫ1Л ХАРЛ1СТЕРИСТ№СЛ РОБОТИ

ЛКТУАЛЫПСТЬ, Швидке зростання складност1 електронно! апаратури й удосконэлегаш технолог!I ÏÎ виробництва призвели до ptonoro зб^ьшоння трудом!сткост1 конструювання печатних вузл1п. Це обумовило появу Г бурхливий розвиток систем авто-матизовэного проектувэння Печатних плат (САПР ШТ), б)лып!сть a яких (зокромз - PCÀD, ORCAD) мають зручгай интерфейс ко-рист.увача та розвинут! сорв!сн! шжлйвост!. Однак Юнуюч! алгоритм« трасування далек! Bi д досконалостt, потребують знач-иих часових ресурс¡в i не в(дображують методику проектувэння доев!дчоного конструктора;- не забезпечують задов!лъно! якост! проектних р i шень при великому р1вн1 складност! ' елэктрнчно! схеш I . оОмекзнШ к!лькост! шар!я. Тому особливу актуаль- , н I сть набувае задача Шдващення швидкодП та продуктивност! алгоритм!в топологИного проектувэння; поиуку нових ефоктав-них способ!в макро- i гДкротрасування.

В дясертац!йн!й робот! розроблена Й досл!дж9на тополо-ri41 ьо модель бзгатошарово! печатноГ плати, на засадах якоГ синтезовзн! швидкод!юч! алгорятш автоматизовано! побудови та оптим!зоцп велико дискретного робочого-поля (ВДРЩ, макро- t к i кротр.ч сувошгл.

ОБ'БКТОМ Д0СЛ1ДШШ с система автоматазованого 'проекту-вання тополог!! багато-лэрових печатних плат, побудована на засадах велшюдискретно!' моде л I.

ПРЕДМЕТ ДОСЛГДНЕИЬ полягас у Шдвиаенн! ивидкодп i * ефективносг! САПР ПЛ.

(датою ДИСЕРТАЦ1ПН01 РОБОТ»! j розробка й досл!дження тополог ¡4HJ1X моделей бзгатошаровйх печатйях плат (БПП), а такоз

сшйбзованих на Тх засадах алгоритм^ автоматизованоГ побудо-ш та оитшЮацЛ веяшсодяскрэтного робочаго поля, макро- 1 ; ы1кроураоування.

ВАДЛЯ ДОСШШННЯ МШ БУЛИ ПОМАВЛШ И ВИР11ШП СЛ1ДТО1 ЗАДАЧ1: '.'.'

■ розробка мат&матично! модел! шчатно! плати 1 формулю-вання умов пербхрэщення трас у каналах;

сщтез алгоритм!в автоматизовано 11 поОудови ! оптим5зац11 ВДРП; V ■ .■■•: •

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

формулювшшя умов перохрещення фрагмент!в трас на етаШ м!кротрасування й синтез алгоритму побудови геометрп про-в!дак!в у каналах;

: розробка алгоритму таророзшшлу трас до тарах. МЁТОДИ ДОШДШНЬ. При вирШеши ЕищеПбред1чених задач викориетан! метода теорП. граф!в, теорП множили, теор11 алгоритм! в та олгебри лог!ки.

■ НАУКОВА I ПРАКТИЧНА НОВИЗНА положень та результатов ди-сортацШноК робота полягпе у тому, шо даерше;

' розробдано ун1версальну матемзтичну модель печатаю!'пла-ти, яка дозволяв повгпстю автоматизувати процес поОудови ВДРП у випадкэх регулярного I нерегулярного розмШення компонен-

■ поставлено й вир!ш№о задачу оптим!зацП ВДРП;

знайдвно снос16 формулювання умов перехрещення трас у : каналах, який дозволяв значно зменшти к1льк1сть математичних вираз!в I, отко, снростити процедуру пошуку шляху в макродискрет! п!д час розповсодженнн хвил!;

збудовано алгоритм "гвучкого" трасування, що вйпдно в!др1зняеться в!д Ыдомих аналоПв 01лшою швидкод1сю, прог-рамною простотою, ун!ворсальн)стя (а сам© - Незалежн1ст!0 в!д кГлысост! тш1орозм1р1в розмЩених на комутац1йнему.пол1 елв-мент1в тэ IX пвреважяоТ ор1снтз?Ш);

розроблено математичя! модел! печатноГ плати I трас, з'сднань, а такой запропоновано нвтрадкц!Яний'спос1б в!добрз-г.оштя тополог}чно! ситуаШ Г у макродискрет! у вйгляд! набору масив!в даних, що дозволяс достатиьо просто здШснювати пера-м1юення ран1и заф1ксовашх на межах каналу в!др!зк1в трас з метой прокладання нових з'еднэнь Г придав алгоритму макротра-сувагом якостЬ влаотив* людаI-конструктору.

синтезовано новяй алгоритм м1кротрасувашгя, метою якого с отримання плоскоГ укладки фрагмент!в трас усеродинI каналу шляхом анэл1зу тополог1чно! ситуацП в остшшьому по зак1нчекн! етапу макротрасуванкя;

зопропсновано иовиД ориг1нэльний. алгоритм перврозпод!лу трас по парах. '■•"..'■ .■':'.

ПРАКТИЧНА ЦШНЙЪ РЕЗУЛЬТАТIВ РОБОВ!; розроблено пакет приклаяпсс програм **АЬ-0Д)", у .якому вир!шено задачу п1дв1ш?шя швидкодН та продуктшзност! систе-ми за рахунок застосувзння математичних моделей, як! дозеоля-ють псвШстю автоматазувати пронес побудови ЕДРП; оптим1зац1К результат1в розмШзшш з штою усунеиня нздлишку мзкродискре-т!в; синтезу нових ефективних алгоритм^ макро- 1 м1кротрэсу-^ вання;

розроблено уш'версальму дискротну тополог¡чну модель печатноГ плати для регулярного й нерегулярного розмження ком-понектГв, а такох р{зних вар1ант!в роэтаиування контоктюпс

площадок но пзриметру установочного м!сця;

с' псовано причини появи 1 шзначено шляхи усунення над-"лншку лкцфодаскрег1в;.

розроОлено комбШований: алгоритм оптяшзац! I ЕДРП; створено теоротачш засади побудови "гнучкнх" алгоритм¿в трасуваиыя зв'язкГв, вданачнйми особлнвоетяки яких е: Б1 д-сутшсть егап!в лобудови ьин ¡мольного зв'язуючого дерева, по-поредаього розыарувошя з'сцнань;, формування та роакраски графа иерехрещень; простота реал!зацН на ЕОМ; моклив!сть знаходюння шляху ми; двома элемента?,ш, як! в'еднуються, в разг його ¡снування й визиачешм в!дсотка трасованост! пе-чатно! плати на задан1й к! лысосп шарзв ще до завершения про-цасу тополог! чтго.проектування;

' ; сштезовано алгоритм аналгзу тополог!чно! оитуацЯ в нагнал!, що дозволяе не т!лькл 1дентЕф1кувати конфл!кт, алв й визначйтя- можливост! його усунешя за рахунок зги ¡ни конф!гу-рацП раши заф1ксоваша фрагмент ¡в трас;

розроблено теоретичш засади побудови алгоритм! в шкро-трасувашш, яге! грунтуються на посл1довнсму анал131 тололо-г!чно5 ситуацП в капал! . \ вГщНзняються простотою реад!за-ц| I на ЕОМ; " : '

' запропоновано сраПнальний спос\б дарерозпод[ лу трас по шарах, «о дозволяв отримати в 2-3 рази юниу юлыисть пере-хгдних отв!р1в, и!я при трасуванш за допомогою САПР РСАВ. НА ЗАХИСХ ВЙНОСЯТЬСЯ СЛ1ДУ30Ч1 ПОЖЭДШНЯ: пакет ириклздщх. програм ПА1~СА1)" ,• у якому за рахунок оастаоувзгат повюс математичних моделей повн1стю автоматизо-вано процес побудови-ВДРЯ; знайдено й викоркстано реэерви . БночногоШдаидешт швИдаодП та ефактивноет! САПР Щ шляхом

введения отапу олтим1зацН розультэттв розм(щення компонента з метов усувення надлкшсу макродискрат!в, синтезу нових ефвк-тивних алгоритм!в макро- 1 м!кротрасувштя;

ун:Еврее,льна великодискретна модель печатно1 лдати, яка однэково придатка для регулярного й нерегулярного розм!щення элемент(в та Д0350ЛЯс павШстю реал(зувати етапи макро- Г м!кротрг>сування топологИно; '

алгоритми автоматизовано! юбудови I оптим1зац11 ВДРЛ, то дозволяють усунутй надлишки макродискрет!в;

сп1вв1дношення,. як! описуктъ умови порохрещепня трас у каналах;

алгоритм тополог!чного макрограсувашя, шо.дозволяв ви-конувати деформацГю ран1ш заф1ксованих трас", мае б1льшу аввд-код1ю, Шй в|дом1 до настулного часу аналоги, й в)др1зняегь-ся прогромною простотой; . •

спосГб оц!нки ивйдоодН алгоритму розпод¡лу лакшяЧв по макродискретах;

. сшВЕ|дноп;еняя, як! ошеують умов« перехрещоння фрагмента трас у каналах;

. алгоритм м1кротрасувашт, основною кетон лкого е усунеп-ня наклэдзяня та порохреконня в!др1зк1в трас у мпкродискрет! за допомогою введения додаткових вортжалышх Г горизонтзль-шк переппив;

алгоритм перзрозлод;лу трос по иарах.

' РЕЗУЛЬТАТА БПРОВЛДШШЯ. Результата робати отршаи! ! рэал1зован1 в щхлюсл вгасонання деркбндаютних НДР: "Ексоко-продуктива! паралольн! обчиелввальн!' система реального час:/ по обробц! <5агатовкм1рнип сигналов" Шн.!стерстга Осв!ти Укрэ-1ня. "Розробка I доел! ляшня тополог!чкях ' моделей багатошэ-■.

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

АЕСР0БАЦ1Я Р0БОТИ ТА ПУБЛШЦН. Науков! результата дос-л!даань докладались i обговорювались на науково-техШ чн i й конференцН професорсько-викладацького складу Харк1воького державного технНного университету рад!оолектрон1ка (1993 р.); на трот!й м!кнародн1й науково-техш чнШ конференцИ "Контроль и управление в тохшяескпх системах" у м!ст! Bimm-ця (1995 р.); на мiхнзродн!ft науково-техш чнШконференцП "Прогрессивная технйкз и технологии мэдшостроения" у MiCTt Севастополь (1995 р.); на ШзшароднШ' науково-техн{чн!й кон-ферещЦ i "Теория а техника передачи, приема и обработки информации" у Micti Туапсе (1995 р.). ■

Smict ррботи десять повно в!добрахело у восьми пубЛ1кац!я£. •■'-•

СТРУКТУРА I ОБСЯГ РОБОТИ. ДисортаШя мае у своему склад! • вотуп, чотири роздиы й закЫчешш, виклоден! на 136 стор!н-Ках,; м1стить 18 додотк!в, 27 малюшчв, 8 таблиць та б!бл!о-граф1ю з 102 назв.

SMICT РОБОТИ

: У вступ! стисло осв!тлено предает доел!дкення, обгрунто- ' вайо актуальн!сть теми, дано загальну характеристику ррботи. Вдалздоно: моту досл1дкешя! задач!, що розв'язуються; за-галья! пожшння, як) виноояться на захист; наукову новизну та практичну ц!тнсть результат 1 в.'

У первому роздШ виконано анал!тичнмй огляд 1снуючих , мзтемйгйчниг; моделей печатних плат i алгоритм!в тополог!чного

проектування, який вйявив, що в облает! розробхи тополог1ч-них метод(в конструювання с ряд Hemipinmraix проблем. А саме:

вГдеутш ШЕ55ДКОДtюч! алгоритми "гнучкого" трасувашш БШ1 !з нерегуляргам розм!шенням компонент^; " .

(снуюч! велякодискротн! тополог!чн1 моде л t печати плат не дозволяють повн i сто автоматизувзти процес яобудови ВДИТ;

актуально» е задача оптим)зацМ ВДРП а метою зменшэшм к1лькоет( макродискрет1в та, отже, часу трасування 1 потребного об'ему naw'flTi ЕОМ;

алгоритм трасувашш з'еднань на засадах комбШовано! молол!, що дозволяс виконувати доформац!I ран!и проведених трас, складний в реал1зац!Г I потребуе значних витрат машинного часу' та оперативно! пач'ят! на фррмування велико- й дрЮнодискретного рабочих пол!в;

у д!ючих алгоритмах-тополог1чйого проектувэння передба-чено вйр/иення задач! м!яротрэсування трэдиц{йними слоеобами за допомогою хвильових або канальних алгоритмiв, що нерац!о-нзльно, бо в результат! виконэння трпюго етапу отримана та-кий розпод!л трас по макродискретах, що дае можлив!сть зроби-ти íx укладання по маПстралях без горехрещень. Тому доц1дьно провести роботу по розробш швидкодШчих алгоритм!в. м!кротра-сувэння, метою яких с визначегош тако! сукушюст! точок пэре-пш1в трас, за яко! остэнн! не перэхрещуються í не наклада-ються одна на одну. •

Все скоззне обумовило влтеперел1чен! задач! досл!джшшя. У другому розд!л1 наведено розв'язання сл!дуючих задач: розробка уШверсально! великодискретноТ тополог! чноУ. Модел! печагноГ плати; нобудова 1 оптишзашя ВЛРП для регулярного та нерегулярного розм}шэння,;. а також.р!зних,варгант1в розтз-

■ . ю

аування контактних площадок по периметру установочного м!сця; визнвчвння способу опису тополог!чно! ситуацН в макродискрет! й формуваиня умов дерехрещення трас.

Задля реал1!зацН принципу поэтапного трасування оапро-понованэ модель, в як(й комутаШйне поле вображено у вигляд! сукупност! макродаскрет!в, отриманих шляхом продовження л1-Н1й, що обмонують усшгавочн! м!сця елегодаЧв. Приг.и, за до-помогою яких здШсшоеться роздад!л комуташИного простору, <3ули назван $ сжучиш. К1льк1сть дискрет {в залежить вгд выносного розташуващя й сполучення типорозм1р!в елемент!в, розм!щевих у вертикалью«. 1 горизонтальних рядах. У дисерта-ц!йв!й робот! розглянут! питания покращення результату пер-в1СНого розм!щення без зм^ни в!даосного розташування елемон-•г!в. Задача вир1шуеться в два втапи. На тршому етапГ зд!йс-ншяься нвзначн! порем!щення компвнент!в у межах вертикального абр горизонтального ряду з метою установления л!кого ниж-цього або правого верхнього кут|в прямокутника,.що описуе ус-, таноБочие шсце, на ближч! до них секуч! в!сей ОХ та ОУ. Дана задача вир¡иона за допомогою процедури, яка нагадуе розпов-свдження хвмл!, джерелом яко! е елемент, розташований поблизу л!вого нижаього кута печатно! плати. На другому еташоптим!-зацП ВДРП виконуеться м!н!м1защя к1лькост! секучих за раху-нок зм 1 ни типорозм 1 р 19 компонентов. Суть цього етапу. полягае в.уоуненн! секучих, на яких не разташован! ряди контактних площадок компонент!в. •

Задля реал!зац11 алгоритму поСудови та- оптим]зацП ВДРП використан! вх!дн! Й робоч! масиви даних, структура яких доклодно вислоьлова в Дисэртед!йн1й робот!«

Тополог!чна модель трас початних з'еднань базуеться на

и

тоор! I множили. Кстзн макродискрет, то являс собою канал для трасування да, в1дадрэжуеться сукупн1ст» чотирьох впорядкона-них Шдмножин Ьа (3=Т7?), елемонтами яких с номари трас, що

проходлть в1дпов}дно чероз л}ву, праву, нижнв й верхню боки дискрету. Кома п|доножинэ становить с!мейство п1дмножин,

а

як! не перес 1каються, тобто де К - множила

№докс1в. Ло п!дмнонини Ьд й!даесен1 першГ т елеменг1в п!д-

мнокшш Ьд , до щ - рэшта елсмент!в, де т - номер иагЧстрал!

дйскрету, узлов» якоТ проходить траса Й в 1а , ио проклада-

еть'ся. Ш» магистралями каналу ва" та позициями Шдмножини Ьа задана взасмно однозначна в}дпов!дН1сть П^ОдИ-Р^Ь^),

де 1г-то магистраль дискрету Ба: Рк(Ьа )- к-тз позиШя

Шдмноиши Ь„ . 0ск1льки хвиля коке п1д1йта до будь-якоТ сто-

■розни каналу, к!льк?сть. мозкливих кснфл}ктних ситуацШ усеродо-н! дискрету, кожна з яких описусться за допомогою окремого матоматичного виразу, дор!внюе двомстам явом. Введения додат-кових параметр)в р(р=Т7?),р1,р2,р3, що визначають номери сто-р]н каналу, як! пэретинзе хвиля» дозволило спроститл умови лерехрещення трас 1 зменшти к!льк1сть сШвв1дношвиь в!д двохсот двох до шести.

„ _ | (|3+2)тос14, яйцо р={1,3): ^ _ Г (р+3)то<14, якщо р={1,3); 1 ((}И)тос14, якщо р=сг,4>; 2 I (р+2)тос14, якщо р=С2,4};"

_ Г Р+1. Г1 и,

якщо р=0,3>; явдо р-(2,4).

Р

Таким чином, ланциг N « Ъ^ п Ьр^. ГО> проходить через ггротилеж-

н! сторони дискрету, поретанае вс! ран!ш прокладеш траси для яких й!рно сшвв1дношення:

В робот? сформульован! такок умови пврехрещшшя для траси N. яка проходить через сумЬкн! стороня каналу ^(3-]}]'

I траси N. яка перетинас дашв одну сторону дискрету [н « Ь^ п |: докладно описана структура роботах масив!в.

Викона»! в цъому роздШ доел{даэнвя дозволили: розробати уШверсальну даскротну тополог!чну модель пе-чатно! плата для регулярного й нерегулярного розшщедая компонент! в, а також р]зних вар!ант1в розм^щення контактяих площадок по периметру установочного -м1сця;

шявити причини даяви 1 визначити шляхи усунення над- ■ лишку даенрот!в; .

розробити комб1нований алгоритм оптим!зацП ВДРП, який дозволяе змешшти к1льк!сть дискрет!в за рахунок покращэння результату неравного розмщення компонент $ в без зм!ни в!д-носного розташування останн1х;"

сформулговати умови перехрещення трас у дискрет!; сиитезувати алгоритм аналгзу тополог(чно! ситуацП в канал! , який дозволяе не т!льки 1дентиф1кувати ковыикт, ала а ьизначити могяив1сть його усунення за рахунок зм1ни конф!гу-рацП ран1Ш зйф^ксовэша фрагмента трас.

У третьему роздШ изведен) р!шошя задач синтезу алгоритм 1ь тополог¡чного (макро-) I геометричного (шкро-) тра-

сувапня,визначен! стратег!Г та збудован! алгоритми процедур розподКяу провшпп^в по макродискротах ! ф!ксацп трао у каналах . Розроблений спос! б горврозпод 1 лу лашшг 1 в по слоям.

■Беликодискретна модель печатно!" плати, яка оцисана у другому розд!л!, дозволяв вир¡шита задачу пошуку шляху м!ж ' деома ■ точками А ! В за допомогою модаф 1 кованого хвильового алгоритму, у якому шля поширюсться но макродискретах. Дзяв-релом хвил! е один !з сумшшх канал!в, то м! стать в соб! по-чаткову вершину (точку А) з'еднання. Приймачем хвил1 вважа-сться одни 13 сушкних дискрет ¡в, до яких належать чаргова верадана розглядаемого ланцюга (точка В) або ранш розпод1ле-. ний фрагмент траси. Це дозволяе вшигочити этап поСудовн тп\~ мальяого зв'язуючого дерева, яке практично немоклиао реал^зу-вати без змт у взгляд! тополог!чного рисунка, особливо - при велик!й шлькост! зв*язк!в. Задача побудови кваз¡оптимального дерева В1ф туеться поел!довно для кожного ланцюга з ураху-, ванням конкретно! тополог¡чно'Г ситуац! 1. При псширенш хвил! враховуеться мовдш!сть проведения траси у иаггрямку кожного з сум5жнмх дискретов. Якщо побудова-шшху без конфлтт1в 1з рант призиаченими до каналу трасавд немоялнва, то в!дпов!дний; сукнжний дискрет не мота бути включений у фронт. Лроцес роз-повсюдшння хвил1 завершуеться, якщо у фронт включений один 1з сум!жних каналгв, що м!стить точку В, у напрямку яко! усе-редин! дискрету моиливв будування траси без перехрещень. Ямцо прокладання шляху в канал¡-приймэч! не мокливе - за останнШ вважають друтяй дискрет, до якого наложить точка В, та гфоцэс пошуку шляху продовжують.

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

pea/сумi«hí канали, 1ндекс довжини якщс зменшусться на-одини-шо. Зэповнешя íaapiB печатаю! плати зд!йснюеться госыИдовно один, за другим» то дозволяв виключити етапи побудови графа: перехрещэнь i його роскраски. У вшадку необхГдност! зменщен-ия к!лькост1 шар!'в моливший перерозпод!л трас,■ що розм!щен}

на нздлшшових шарах за допомогою введения мгкшарових перехода.

Дал! в роздШ наведена к!льк!сна оц!нка потрЮних мэшинних ресурс i в та швидкодН алгоритму макротрасування. Об'ем оперативно! пам'.ят! ЕОМ, необх!дний для в!дображення ЕДРП, визиачаеться за допомогою шндуючого виразу:

V = 2-е-(nx+ny+2) (байт),

да с - ккпькГсть з'еднань електрично! схеми; пх,Пу - парамет-ри, що характеризуюсь к!льк!сть секучих прямих в!сей ОХ та ОУ на етвп1 розпод1лу комутац!йного простору на канали. Час, не-обхштй для вибору вар1ант!в закр!пленяя траси у дискрет.!, можлнво прйблизно оц!нити за допомогою виразу:

T=(VV

^vT^ja-^p^-p^-s-p^-pJ,

де ty-чзс операц!? вибору дэних !а.робочого мэсиву; тс- час старэШ i пор!шяння: p^.pj- середня пропускна спромокн!сть бок!в дискрету.

Час Т у канал! , шо мае пропуски! спроможност1

U w

3 метой вир!вгоняя задач! м1кротрасуванкя, ао палягас:в

1+

<Pi-i)

2

пошуку такого вар(анта роэташування фрагментов трас, призна-чених у дат® канал, при яксму в1др1аки пров1днпк1в ко пора-хрещуються та не накладаються ода на одний, сформульаван! додатков! умови перехрещення фрагмент!в трас у канал) для р1зних вар [ант ¡в конф!гурацН ланцюга N. Ланцюг И е п

що проходить через протилекн! бога дискрету уздовж маг!стра-

лей т1,ш2 I мае подвШшй вертикальний перегин на мэг1страл1 Шд, перотинас траси для яких справедлив! сшвв^дношення:

«1ЦА { \ и \ ) ■';»16%п 14и\) -

Шдмножини Ьа формуються так, як це Оуло описано вждв, з

т!сю лише р!зшцею, що мдожина шдексЯв для й Х^ склада-

еться з трьох елемашпв {1,2,3), а для Ьр, 1 I»- з двох:

р1 р2

Для того, щоб на втап! м!кротрасування уяикнути перехре-щень траси N )з траоами нобх1дно виконати сл!дуюч! опера-ц(1: ввести додатков! вертикальнГ та горизонталь«! пэреГини для траси перед побудовою геометр}У траси N заразервувати в!др!зки маНстралей для пров!даик!в, як! вона моав перотииа-тк у подальшому. ''

Алгоритм перероздад1лу трас по шарах базуеться на вив-ченн! тополог!чноГ сихуацн за допомогою парев!рки умов перехрещення прямол!нШтх фрагментов пров!дщт1в, наведейих у п!дрозд1л! 3.6, й близький по своему принципу дП до м!рку-вань людшш-конструктора, що вир!шус под1бну задачу.

На баз! шпсошшях досл!докень роэроблэм!: стратег)я "гнучкого" трасування, в як!й передбачен! сл1-. душ! процедури: анал!з тополог!'гаоГ еитуац! Г, змша конфггу-рацЯ ранш заф!ксованих фрагмент]в трас з метою усунення конфлйачв ! визнзчвння в(дсотка трасованост} печатно? плати на задан!й к!лькост! шар¡в щэ до завершения пронесу тополо-г!чного проектування;

хвильовий алгоритм мокротрасування, В1дзначними особли-востямм шсого е: простота реал!зац1 Г на ЕОМ; В1дсугн!сть ета-П!в побудови ьиШмалыгого зв'язуючого дерева, розяарування з'сднань та розкраекя графа перэхрещень; можлив!еть зваход-жошш шляху мЬ'с елементэ.ми, як! з'едауються, у випадку його 1снува!шя; •

спас16 оц!нки ивидкод!Г алгоритму розпод!лу ланцюг!в по дискретах;

спос!б опису додотковах умов перехрошення фрагмент!в трас у каналах;

стратеПя м!кротрасування» основною кетою яко! е усунення накладацня й герехрощешт фрагментов трас у дискрет! шляхом введения додатковкх вертикальних ! горизоытальних пере-гип!в;

алгоритм побудови геометр!I пров!дник!в, що базуеться на шсл^довному в.чшп31 топологIчко! ситуащ{ в канал! й в!др!з~ нясться простотою реал!зац!Г на ЕОМ; .

умови перехресцення сртогональних фрагмент!в трас 1 алгоритм перерозпод!лу трас по шарах, Принцип дН якого основан по всебИчному анэлЫ нообх!даост1 установления дар0х!дних отв1р!в, ко дозволяе уникнути появи невиправдано•велико! .в1лькост1 • останн!х, •

У четвертому роздШ описан! склад i структура пакету прикла.цних програм (ПЩ) "AI-CAD", що розроблений на засадах тополог 1чного методу трасування багатошарових печатних плат.

ППП "AL-CAD" м!стить сл!дуюч! прогреми! блоки: введения початкових даних; побудова. й оптим1зац1я великодискретного робочого поля; макротрасування; м!кротрае'увания; перерозпод1л трас по шарах; узгодження формату вих!дноТ ¡пформаиП ЛИП "AL-CAD" та вх1дного формату САПР P0AD.

Комплекс програм реал!зован на мов! Turbo Pascal для IBM ' PC/AT.

Обмеження на проектування: потр1бний об'ем оперативно ï > пам'ят! - 640 H; максимальна к!льк!сть вершин графа з'едаань-1000; максимальна,к1льк!сть елемент1в схемн - 50; максимальна к!льк!стьз'едаань - 330; максимальн! габарита плати - 240 х 360 мм; максимально можлива к!льк1сть шар!в - 10.

У зв'язку з велико» к!льк!стю д!Я, що виконуються, t обмеженГстю оперативно? пам'ят! розм!ром 640К ППП "AL-CAD" побудований по модульному принципу. Причому б!льшсть модулей оверлсйнt й завантакуються в пам'ять по м!р| необх!дност!, Формування вх1дних масив!в ланцюг!в та установочных м!сць зд!йснюеться,в Интерактивному режим! t завершуеться утворен-ням двох тип! зованих файл i в !з початковими 'данями, як1 вико-ристовуються в подальаюму. Для виконання власно тополог!чного проектування розроблений ряд програмних модулей та процедур, що докладно; описан! в даному роздШ й м1стять процедури да-иуиу 1 побудови шляху, перемiщешя ран 1 ш зафшсовшшх на межах каналу фрагмент!в трас та in. Прагноння скоротити розм!р программ дозволило знвйти рац!ональну структуру робочих маси-в!в та вибрати ун!кальний шб!р параметр^, аа.допбмогою чого

.•■■"'.-' 18

вдадося ¡ив ö iльшо спростити ум'ови шрэхрешшм трас i об'еднати ïx в одному вираз!: :

3(JKL « Д л JKM е В) ((N0R=N0R1 л L2 / О) v V (ВД=ШЯ1 ~ NOR /■ HASI А 12=0)),

де 3MîHHi NOS, N0R1 визначають номери трас, Шдведених до елекеатI и топологI !, ¡до розмШен! в1дпов1дно за адресами JKL 1 JKM в основному робочому масив!; зм)нш HAS1 » 12 В1Д0бра-жують номери контакта-пркйлача траси ) установочного Мсця (у випадку п!дключення до ран i ш заф!ксованого фрагмента' ланцюга значения HAS1 дор!вн»е номеру останнього й Ь2=0); впорядаова-И1 п! данокини А,В (множини допустимих значонь зшнких JKL, .JKM) складаються з элемент i в, що являють номера маг! стрелой каналу, i станоавдть п!дмножшга Ъп .

У цьому к розд!л! наведен! результата ексдарнментэльно! перу в i prat ефективност! роботи ГОШ "AL-CAD". Дана пор!шяльна ouiнка останнього з найб!льш розповсюджэним сьогодн! аналогом САПР Шй вере!ï 4.5.

Суттсвмми да.ревагами ГОШ "AL-GAD" с: простота в ояану-вшш!, високэ шввдксд!я та як!сгь топологгчлого рисунка.

У додагкох наведен! копИ акт!в про впроаэдження Й вико-ристстмя результат!в дисортац!йно'[ роботи, а такок текста програмних модулей ППП "АЬ-САБ".

0СН0ВИ1 РЕЗУЛЬТАТ» РОБОТИ ТА ВЙСНОВКИ

1. Ззпропонована унi ворсальна модель нечатноТ. плати для регулярного, й нерегулярного розм/дення «элемент ¡в, яка дозволяв .реая1оувати отзш макро- 1 м1кротрзсування тополог!чно, а

тонок, па вШлШу в1д в!домих аналог! в, шин i стю автоматизу-вати пронес .побудови велшсодмскретного робочого поля.

2.' Внявленi причшш появи Г визначаш шляхи усунення нэдлижку канал i в.

3. Розробдеш алгоритма автсматизовано? побудови та опта,ifзац! i ВДРП. .

'4. Отриман! сп1вв1днош0щи, що ошсують умови перехрэ-щенля трас у дискрет!; синтезований алгоритм &нал!зу тополо-г!чиоТ ситуацП' в канал!, що дозволяв не тiльки достатньо просто !дентнф[кувати конфд]кт, але й визнвчити можлизЮтъ ñopo усунення.за рахунок бшни конф!гурацп paiiiui заф^ксова-нмх Фрагмент!в трас.

5. Побудовашй алгоритм тополог!чного макротрасувэння, шо мае б!льшу швидкод!ю, и!» в!дом! до наступного часу аналога, 1 характеризуемся рядом особливостей: простотою реал!-зац!! на EQM; в!дсутн!стю етаШв; формувашш м1н1малыюго зв'язуючого дерева, розшарування з'еднань та розкраски графа порехрещонь; гарантоваиою мозкливЮтю знаходження шляху mí ж элементами, що з'еднуються, за умов його 1снування.

6. Запропонований ориг!налыщй cnoc¡6 побудови геометр!! лр0в!дник!в на баз!. поол1довиого анал!зу топологí'«¡oí ситуа-ц! i в каналi, що в!др!зняеться простотою роал1зоц)í на ЕОМ.

7. Розроблений пакет прнкладнкх нрограм "AL-CAD".

Перел!чеи! вище ocHOBÍii результата робота е Шдтверджен-

ням того, що завдяки внкористаншо резерв! в, як i нэдае нова унiверсальна дискретна топологiчна модель печатноК плати, i нетрадиц!йним п!дходзм до вибору структура масив!в даних й орган!зац!Г пронесу пошуку конфл!кт!в вдалося синтезувати швидкод!юч!, yHtBepcaJibHl алгоритм тополог i чного проектуван-

ни. Ошв мокна зробити висновок, що в робот1 створен! теорв-, тичн!7 математичн! та прогреми! основй побудови ефективних систем овтоматизовйного проектування багатошарових печатни:? плат-.

Осношшй зы1ст дисертиЦ1£ опубл!ковано у таких роботах?

1. Алгоритм построения геометрии трасс в макродискретах / Алипов Н.В., Литвинова Е.И.; Харьк. техн. ун-т радиоэлектроники,- Харьков, 1994.- 18 е.: ил.- Библиогр.: 2 назв.- Рус.-Дан. в ГНТБ Украины 17.02.95, Н438-Ук95.

2. Алгоритм построения минимального связывающего дерева на ортогональной сетке /Алипов Н.В., Литвинова Е.И.; Харьк. техн. ун-т радиоэлектроники.- Харьков Л994.-21 е.: ил.- Библиогр.: 3 назв.- Рус.- Дек. в ГНТБ Украины 01.08.94, К1462-УК94.

3. Дискретная топологическая модель печатной платы / Алипов Н.В., Литвинова Е.И.; Харьк. техн. ун-т радиоэлектроники.-Хорьков. 1994.- 13с.:ил.- Библиогр.: 3 назв.- Рус.- Деп. в ПП'Б Украшш Ш.03.94, N 1466-Ук94.

4. Комбинированна алгоритм оптимизации крупнодаскретного рабочего поля / Алипов Н.В., Литвинова Е.И..; Харьк. техн,. ун-т радиоэлектроники.- Харьков* 1994.- 15 е.: ил.- Библиогр.; 2 Назв.- Рус.- Деп. в ПП'Б Украины 17.02.95, Ы429-Ук95.

5. Подсистема трассировки многослойных печатных плат на основе крупнодаскрэткой модели / Алипов Н.В., Литвинова Е.И.; Харьк. техн. ун-т радиоэлектроники.- Харьков, 1994.- 22 е.: ил.- Библиогр.: 1 назв.- Рус.-Деп. в ГНТВ Украины 15.08.94 .Н1627-УК94.

('ч -.Алипов Н.В., 'Лятюиоло Е.И. Гибкий алгоритм трассировки многослойных печатных плат // Прогрессивная техника и техно-

21 // 7

логии машиностроения. Тезиси докладов международной научно-, технической конференции. 12-15' сентября 1995 г.- Донецк; ДонГТУ, 1995.-0.7.

7, Алипов Н.В.,. Литвинова Е.И..Пакет„прикладных программ для' проектирования топологии многослойных печатных плат / Международная .конференция "Теория ¿.техника передачи,„приема и обработки 'информации": Тез. докл./ХТУРЭ, Туапсе, 1995.- с,152.

8. Алипов Н.В., Литвинова 3.И, Проектирование топологии многослойных печатных плат, на основа крупно дискретной .модели // 'Гези доповIдвй третыл мпшэродпо! науково-техШчжн кон-фер&нц! 47 "Контроль I управл!шя в т&хШчних системах".-'ВШ-ниця, 1995.

Особиста участь автора в отршагап наукових результата. Дисертац!йна робота о Шдсумком особисто! робота автора, В роботах, написания у сп1вавторств!, особисто автором розроблено: ун!версалъну великодискретну модель печатпаГ плати; алгоритма • автоматизовано! побудови та оптишэашВДРП; сп1ввШюаешш, як! описують умови перехрещення; трас у каналах; алгоритм тополог1чного макротрасуваяна; спосЮ оц!шси швидкод!1 алгоритму розпод!лу ланцюг!в по макродискретах; сп!вв!дношення, як! описують умови перехрещення фрагмент!в трас у каналах; алгоритм м!кротрасувашм; алгоритм перерозпо-д!лу трас по шарах; пакет прикладных програм "ЛЪ-САВ".

. • • АННОТАЦИЯ

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

тизации проектирования. Харьковский государственный технический университет радиоэлектроники, Харьков. 1995. Диссертацией является рукопись.

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

синтезирован алгоритм топологической макротрассировки, обла-♦

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

SUMMARY.

Litvinova ЕЛ. Designing and research of topology models of multilayer prlnted-clrcult-Poards and algorithms oi Interconnections routing. The dissertation for the Candidal« degree of the technical sciences on the speciality 05.13.05 -Computer Aided Dsaign, The Kharkov State Technical University of Radioelectronics, Kharkov, 1995. , The dissertation Is manuscript.

ïhs universal large-alsed diskrete model of printed-circuit-board for-regular and irregular accomodation.of elements is developed. It has allowed to realize the stages reak-

го- and niiororoute topological]^ and, In difference from Known analogues, completely to automate the process of construction of large-sised dlskrete working field. The task of large-siaed dlskrete working field optlMzatlonia set and solved, The expressions, which circumscribe of routes intersection conditions in dlskrete, are reseived on the basis of which the snacroroute topological algorithm, having of large speed, than analogues known till now is developed. The original way of routes geometry construction , based on consecutive analysis of topological situation in channel and distinguished by simplicity of realieation on computer 1в offerred. The pack of applied programs "AL-CAD" is developed. •

Листов* слова» система автоматизовайого проектування (САПР), алгоритм, программ, модуль, ефективи1сть. Шщс6д1а, ЛЕродук-тивн1сть, анал i а, тополог 1чна Модель, багатоаарова печатна . плата, умоей перехрещення трас; тополог!чнз ctrryaui«. конфликт, секу48, фронт хвил! * зона усталеяого розм! щення, дасере-ло, приймач, макротрасування, Шкротрасування, оптйм!зац!я, ' розм1щення, великодискретне робоче поле, дерево Штейнера, макродискрет, канал, деформэшя фрагмент!в трас, розповсюд-ження хвил1, перерозпод!л трас, пакет прикладнях програм "AL-0AD". , ' '

Тира-; ICQ ftp

Об'ей 1,25. д. а.

Друкарня ХБУ, пл. Сдобод::, 5