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

М1Н1СТЕРСТВ0 0СВ1ТИ УКРА1НИ ХАРШВСЬКИЙ ДЕРЖАВНИЙ ТЕХН1ЧНИЙ УН1ВЕРСИТЕТ гй лп РАДЮЕЛЕКТР0Н1КИ__

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

УДК 621.3.049.75.001.2:681.3

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

т—од—

- 1 ЯНВ 1996

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

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

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

X а р к ! в —

1995

Дисерташею е рукопис,

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

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

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

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

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

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

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

Захист дисертацп в1дбудеться // " С( 199/року о

,,/3 " годин 1 на зас!данн1 спец1ал1зовано! ради К 02.25.03 у Харк1вському державному техшчному ушверситет! рад!оелек-трон!ки за адресою: 310726, м. Харк1в, проспект Лен1на, 14.

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

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

Вчений секретар «

спец1ал!зовано1 ради В. БЬЗКОРОВАИНИЙ

ЗЛГМЫ1Л ХАРА1ШИ1С!ШКА РОБОТЙ

ЛКТУМЬШСТЬ, Шведке зростання складност! електронно!-апаратури й удосконалення технологП П виробшщтва призвели до р!зкого збМьшоння трудом!сткост! конструювання печатша вузл1п. Це обумовило появу 1 бурхливий розвиток систем авто-матизовзного проектування печатшк плат (САПР Ш), <Ялып!сть а яких (¡зокремз - РСАП, ОЙСАБ) ибють зручний интерфейс ко-ристувача та розвинут! серв!сн! можлйвостК Однак ¡снуюч! эл-горитми трасування далек! в!д досконаЛост1, потребують знач-них часовях ресурс!в < не в(добракувть методику проектування доев)дчзного конструктора;- не забезпечують задов!льно!' якост! прооктних р!шень при великому р!вн1, складност!' електрично! схеми ! . обмекэшй К1лькост! шар1в. Тому осооливу актуаль-н!сть набувае задача п!двищення швидкод!! та продуктивном 1 алгоритмов топологИного проектування; пошуку нових ефентив-них способ!в макро- 1 м!.кротрасувэння,

В дисэртацШпй робот! розроблена Й досл1джвна гополо-г!чна модель бпгатошарово! печатно! плати, на засадах яко!' синтезован! швидкодПоч! алгоритми автоматизованоI побудови та оптишзаш1 великодискретного робочого поля (ВДРП), макро- I мпфотрасування.

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

ПРЕДМЕТ Д0СЛ1Д2ЕНЬ полягас у Шдвикенн! швидкодН ! . ефективност! САПР ПЛ.

МЕТОЮ ДЙСЕРТАЩПН01 РОБОТИ ^ розробкэ й досл1даення тополог 1чних моделей бзгатоиарових печатай плат (БПП), а такоз

синтвзованих на 1х засадах алгоритмов автоматизова1|оТ побудо-ш те онтим1зацН велшсодискрэтного рооочого поля, макро- I Шкротрасування.

ЗАДЛЯ ДОСЯПШНЯ МЕТИ БУЛИ ПОЙРАВЛЕНГ И ВИР1ШЕН1 СЛ1ДУЮЧ1 задачи

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

синтез алгоритм ¡в автоматизовано? посудови 1 оптПзацп

вдрп;

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

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

■ ■ розробка алгоритму П9рврозтад1лу трас по шарах. МйТОДИ дослцдань. При вир1шешй -Еищеперелгчеыих задач викориатан! методи теор! 1 граф!в, тоор1 Т шозкини, теорП алгоритм! в та алгебри лог1ки.

' НАУКОВА 1 ПРАКТИЧНА НОВИЗНА положень та результат ¡в ди-сертаШйноГ роботи шлягае у тому, шо вперше:

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

поставлено й шр!шено задачу оптишзац II ВДРП; знайдвно ояос)б формулювання умов пэрехрещення трас у , каналах, який дозволяе значно зменшти к1льк!сть математичних вираз1в I, отжо, агростити процедуру пошуку шляху в макродискрет! п!д час рсзпоБСюджешш хайл! ;

збудовано алгоритм "гаучкого" трасування, що виг(Дно в1др!зняеться в!д в!домих аналог!в сИльшою швидкод! си, программно простотою, ун!вврсальн!ст!о (а сама - незалвжн!стю в!д . кГлькост! типорозм!р!в розмщоних на комутац!йному.пол! елв-мент!в та 1х перевакноГ ор!ентацМ);

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

спитезовано новий алгоритм м1крйтрасувашш, метою якого е о тримзния плоско! укладки фрагмента трас у серо дин ( каналу шляхом анал!зу тополог {чяо! ситуац!!• в останньому по закИгеенн! етапу макротрасуваняя; .

запропоновано новий ориг!дальний алгоритм пер9розпод!лу трас по шарах. '

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

розроблено уш'версальну дискротну тополог¡чну модель печатноГ плати для рогулярного й нерегулярного розмщсння ком; понект!в, а такой р!зних вар!ант!в рочтаиувзння контакта«

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

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

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

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

розроблено теоретичп! Засада побудови алгоритмов мнсро-траеувашм, як! грунтуються на посл!довному анал1з! тополо-НчшТ ситуацП в канал! I в!др1зняються простотою рэал!за-ц11 на ЕОМ;

' запропоновано срщчналышй снос ¡6 перерозподму трас по шарах,, що дозволяв отршати в 2-3 рази мешу кичыисть пере-хШшх отв!р1в, н!ж при трасуванш за допомогою C¿ШP РСАВ. НА ЗЛХКС1 ВИНОСЯГЬСЯ СЛ1ДУЮЧ1 ПОЛОХЕШШ: пакет ирикладних програм "АЬ-САЗ" ,■ у якому за рахунок оастооування иових математичних моделей повн!стю автоматизо-вапо процес побудови. ВДРП; снайдено й викор^етано резерви зиачноГо шдаищення щвидкод!! та ефоктивноет! САП? Ш шлягом

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

ун!нереальна ввликодискретпа модель печатно1 длати, яка одаоково при дат« а для регулярного й нерегулярного розм!аення элементIв та дозволяе повШстю реал}зувати отапи макро- 1 м1кротрасування тополог 1тшо;

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

сп{вв1днош0йня,. як1 олисують умови торвхрещоння трас у каналах;

алгоритм тополог! чного макротра'сування» що. дозволяс ви-конувати деформац!ю ран!ш заф!ксованих трас'» мае б!льшу швид-код!ю, н(ж в1дом! до настугшого часу аналоги, а в1др(зняегь-ся програмною простотою; • •

спос!б оц!нки иввдсодП алгоритму розггод1лу. лаидаПв по макродискрвтах;

сшввШюиення, якГ огшеуютъ умови порехрещоння фраткен-т!в трас у каналах;

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

алгоритм перэрозлодглу трос но шарах. РЕЗУЛЬТАТ«! ЕПРОВЛДЖЕгШЯ. Результата роботи отриман! I реал1зован! в процосл вшеонання деркОкдазтнпх НДР: "Високо-продуктизп! наралвльн! обчколювалън!' система реального час;' по обробц! багатовж!рш1к, сигнал ¡ в" Ш нЮтерстаа Осв)ти Укра-1ни, "Розробка 1 доел)дження тополог! чнпх моделей багатоаэ-

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

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

Зьист роботи досить повно воображено ■ у восьми пуОЛ1кац{ях.

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

ЗШСТ РОБОТИ

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

У першому роздШ виконано анал!тичний огляд ]снуючих . мат&матапге« моделей шчэтних плат ! алгоритм ¡в тополог ¡чного

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

в!дсутш швидкод!юч1 алгоритм "гнучкого" трасування БПП !з нерегулярнам розм!иенням компонент^;

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

актуальною с задача оптю.НзацМ ВДРП а метою змэншвння к1лькоет! макродискрет!в та, отже, часу трасування i потр!б~ ного об'ему ттам'ят! БОМ;

алгоритм трасування э'едйань на засадах комб1нованоТ мо-дэл(, що дозаоляе виконувати деформацН ран!и проведених трас, складний в реал!зацц !• поТребуе значних витрат машинного часу та оперативно! пам'ят! tía формування велико- й др!Онодискретного робочих пол!в;

у д!ючйх алгоритмах-тополог i чного проектування йервдба-чено вяр1ионня задач! м!кротрасування трздиц1йними способами за допомогом хвильових або канальних алгоритм1в, що нерацio-на л ьно, бо в результат! виконэння' пераого етапу отримано та-кий розпод!л трас по макродискретах, що дае можливЮть зроби-ти Тх уклздання по маг!стралях без перехрещень. Тому доц!льно провести роботу по розробц! швидкод!ючих алгоритм! в. м!кротра-сувэння, метою яких о визначення такоТ суку1шост! точок перегнав трас, за яка! остзнн! не перехрещуються 1 не наклада-ються одна на одну.

Все сказана обумошло вищбперел!чен! задач! досл!джеш?я. У другому роздШ наведено розв'язання сл!дуючих задач: розробка ун1версалыю! великодискретно! тополог!чно!. модэл' печатно! плати; побудова i оттаизащя ВДРП для регулярного та нерегулярного розм!шання,- а такок р!зних.взр!ант1в розта-

ю

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

Задля реал1зацЯ принципу поэтапного трасування оапро-понована модель, в як!й комутац!йне. поле зображено у виг ляд! сукупност! макродискрет}в, отриманих шляхом продовження л!~ н!й, що обменують уотановочн! м!сця ел91>:етмв. Прям!, за до- помого» яких здШсшоеться розпод!л ко,чуташ Иного простору, були назван! С1кучими. К!льк!сть дискрет!» залежить В1д выносного розташува1шя й сполучення типорозм!р!в елемент!в, розмЩених у вертшальних 1 горизонтальных рядах. У дисерта-ц!йн!й робот! розглдаут! питания покращення результату пер-в!сного розм1щешш без знаки в!дносного розташування елемен-' т!в. Задача вир!шуеться в два етапи. На першому.етаШ здШс-ншться незначн! горемщення компонентов у межах вертикального абр горизонтального ряду з метою установления л!еого ниж-нього або правого верхнього кут|в прямокутника, що описуе ус--тановочне «¡ецэ, на ближч! до них секуч! в!сей ОХ та ОУ. Дана задача вир¡йена за допомогою процедури, яка нагадуе розпов-сюдження хвил1, даералом яко! с елемент, розташований поблизу л!вого нижнього кута дачатна! плати. На другому етапI оптим!-зацН ВДРП виконуеться м1н!м!защя шлъкаст! секучих за раху-нок зм!ни типорозм!р1р компонентIв. Суть цього етапу полягае в.уоуненн! секучих, на яких не разташован1 ряда контактних площадок компонент!в.

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

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

Toopi ï множиш!. Кожен макродискрет, що являе собою канал для

трасування Da, В1добрзхуеться сукупн1стю чотирьох впорядкова-

них п!дмножин Ьд элементами яких с номери трас, що

J

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

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

!ндотсс1в. До пIдмнокини В1даесен1 перш! m елеменПв п!д-

тотлпт Ьд , до - рэшта еломент1в, де m - номер магЮтрал! «î »Î

дискрету, уздовк hkoï проходить траса К «s Ьа , що проклада-

еться. Mis мапстраляшг каналу Ва та позюОями Шдмножни Ьд задана взаемно однозначна в1дпов(дн!сть М^Од^^Ьд >.

да îih(Da)- h-та маг!страль дискрету Da; Pk(La )- k-та позиц!я

Шдмножпга ъ„ . Оскглыш хвиля може п!д(Яти до будъ-якоУ сто-

пони каналу, к!лыс!сть можливих конфчИктних ситуац!й усереди-Hi дискрету, ко:кна з яких описуеться за допомогою окремого^ матоматичного вирззу, дор!внке двомстам двсм. Введения додат-кових параметр]в р(р=ТТ7),р1,р2,р3, що визначэють номери сто-piH каналу, як! пэретинас хвиля, дозволило спросится умови лерехрощення трас ! змейаити к!льк!сть сШвв1дяошень в!д двохсот двох до шести.

р = .f (pi2)mod4, якщо p=U,3): р _ f (p+3)mod4, якщо p={f,3); 1 {. (pf-1)mod4, якщо р={2,4>; 2 1 (p+2)mod4, якщо р={2,4);'

р : Г р+1, якщо p={t,3); I р-1, якщо р={2,4).

т>гт.~11Я псштп »1 — Т л Т тг\ ГТГ\^ V Г\ ТТ1Г гч Т. иат^О

В робот! сформульован! також умови пэрехрещоння для траси N.

{ траси К, яка перетинас лише одну сторону дискрету

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

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

■розробити комб!нований алгоритм оптишзац!! ВДРЛ, який дозволяе зменшити К1льк!сть дискрет!в за радунок покращення результату гюрв^сного розмщення компонент!в без зм!ни в!д-носного розташування останн!х;'

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

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

яка проходить через сум1жн! стороня каналу

докладно описана структура робочих масив!в.

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

■ Великодискретна модель печатжп плати, яка описана у другому роздш, дозволяе вир»ш1ти задачу поиуку шляху м!зв двсма • точками А I В за допомогою моднф1кованого хвильового алгоритму, у якому хвиля поширюеться по макродискретах.- Дне-релом хвил! е один {з сум!«них каналов, адо м!стать в соб! по-чаткову вершину (точку А) з'еднання. Приймачем хвшп ввазка-еться одаш ¡3 сумIжних дискрет¡в, до яких налегать чоргова вершин? розглядаемого лаицюга (точка В) або ранш розпод!ле-ний фрагмент траси. Це дозволяе виключити етап побудови м»ш-мального зв'язуючого дерева, яке практично немсжлиаа реал1зу-Еати без зм1н у вигляд! тополог!чного рисунка, особливо - при велик¡Я шлькост! зв*язк!в. Задача побудови квазIоптимального дерева виршусться посл!довно для-кожного ланцюга з ураху-. ванням конкретно! тополог¡чноТ ситуацП. При помиреш! хвил! враховуеться можлив!сть проведения траси у напрямку кожного з сум!жвих дискретов. Яйцо побудова-шляху без конфингачв !з ра-нш призиаченими до каналу трасамн неыоялива, то в1дпов!дний сум!жний дискрет не маке бути включений у фронт. Процео роэ-повсюдження хвил! завершуеться, якщо у фронт включений один 1з сум1жних канал!в, ш.о мостить точку В, у напрямку яко! усе-редан! дискрету мокливо будувашя траси без горехрещень. Якщо прокладання шляху в канал!-приймач! не можливе - за останнШ вважають другий дискрет, до. якого наложить точка В, та процес пошуку шляху продовжують.

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

рез сум!кн! капали, 1ндекс довжини яких зменшуеться наодини-шо. Загговнэння шар1в печатно! Плати зд1йснюеться посл!довно один за другим, шо дозволяе виключити етапи побудови графа перехрещонь I його роскраски. У випадку необх!даост1 зменшен-ня к1 лысост! шар ¡в мокливий перерозпод(л трас,- що розмщэн! на надлшкових шарах за допомогою введения ьижшарових перехода.

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

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

де г0-час опорац!? еибору даних 1з.робочого масиву; тс- час оперэиП пор!вняння; Р^Р-р сере дня пропускна спромокн!сть бок!в дискрету.

Чт- Ф иопа п! С1П мле» ттлпупт! ГГТППМПЖНПГ.Т I О.=О.=10:

V = 2-е- (г^+Пу+2) (байт),

пошуку такого варианта розташування фрагмент!в трас, призна-чених у даний канал, при яксму в!др!зки пров1дшк!в ье поре-хрещуютьея та ие накладаються один на одний, «{юрмульованI додатков! умови перехрэщення фрагмент!в трас у канал! для р!зних вар!ант1в конф!гурацП' ланцюга N. Ланцюг Н е л Ь^,

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

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

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

т ? Л1Л пт«пнл т» 4 г>гт-гг» гол »«тл«л*сг*л » тт*тлт»>л т г-. «тел Т Л- Т ткПп-.гл ..

Для того, щоб на етап! м!кротрасування уншшути перехре-щень траси N 1з трасаш нобх1дао вшсонати сл! дукш опора-ц!Т: ввести додатков! вертикальн! та горизонтальн! перегини для траси Н; перед побудовою геометр!! траси N зарезервувати в!др!зки маг!стралей для цров!дник!в, як! вона може перетина-ти у подальшому.

Алгоритм перерозпод1лу трас по шарах Сазуеться на вив-ченн! тополог ¡чно'1 ситуацЛ за допокогою перев!рки умов нерв-хрещення прямол!н!йних фрагмент!в пров!дш1к1в, наведених у п!дрозд!л! з.б, й близысий по своему принципу дП до М1рку-вань ладини-конструктора, що вир!щуе под!Сну задачу.

2

1 1

Ka tí£.oi ишонаних досл!джень розроблен!: стратегия "гнучкого" трасування, в якШ перадбачен! сл!-. дукт процедури: анал!з топологiчноТ еитуацН, змша конф!гу-рац} Т ранги заф!ксованих фрагмент!в трас з метою усунення kohíutíktíв i визначення в!дсотка трасованост! печатно! плати на задан!й к!лькост! шарiв ще до завершения пронесу тоголо-г!чного проектува1шя;

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

спос1б оц!нки ивидаодП алгоритму розпод!лу ланшоПв по дискретах;

снос i б оггасу додаткових умов перехрещення фрагментiв трас у каналах?

стратег! я м 1 кротрасування, основною метою яко"! с усунення накладашш й перехрежоиня фрагментiв трас у дискрет! шляхом введения додаткових вертакальних i горизонтально перегнав;

алгоритм побудови геометрП пров1Дник!в, то базуетьоя на посл'довпсму aHaj:Í3i тополог1чно! ситуацп в канал! й в!др!з-нясться простотой рэал!зацН на ЕОМ;

ушви перехрещення ортогональних фрагмент!в трас ! алгоритм перерозпод!лу трас по шарах, принцип Д11 якого основан На всеб!чному анэл|з! наобхшгасл установления нерех!дних OTBipíB, ко. дозволяе уникнути появи невиправдано • велико Г к!лы;ост1 octíihhíx.

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

ППП "AI-CAD" Ml стить сл1дуюч! програмн! блоки: введения початкових даних; побудова й оптим!зац1я великодискретного робочого поля; макротрасування; м1кротрас'ування; перерозпод!л трас по шарах; узгодження формату вих1дно! ¡нформацП ППП "Air-CAD" та bxî дного формату САПР PCAD.

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

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

У зв'язку з великой к!льк!стю д1й, цо виконушъся, ! обметан¡стю оперативно! пам'ят! розмi ром 640К ППП "AL-CAD" побудований по модульному принципу. Причому öIльшiсть модулей оверлойнi й завантакуються в пам'ять по м!р! нообх!дност!, Формування вх1 дких масив!в ланцюг}в та установочних м!сць здШснюеться.в 1нтерактивному режим! I завершуеться утворен-ням двох тиц1зованих файл!в !з початковиш даними, як1 вико-ристовуються в подалыпому. Для виконання власно топологi4Horo проектування розроблений ряд програмних модулей та процедур, що докладно описан! в даному роздгл! й м!стять процедури по-шуку ! побудови шляху, перем!щення ран1ш зафшсовашх на межах каналу фрагмент!в трас та in. Йрагнэння скоротити розм1р програми дозволило знайти рац! она льну структуру робочих маси-в!в та вибрати ун!кальний Haötp параметр^,, за.допомогою чого

вдадоея u,e ö i льше спростити умови шрехрвщення трас 1 об'еднати 1х в одному вираз!:

3(JKL «Ал JKM е В) ((NOR=NOR1 ~ L2 * О) v v (N0R=N0R1 - HÖR / HAS1 л 12=0)),

де змпш! NOR, NORI еизнвчаютъ номера трас, ni две дета до елоыйнтi в тополог)!, що розм!щея! в1даов!дао за адресами JKL 1 JKM в основному робочому масив!; зм!нн1 HAS1» 12 в^добра-жують номери контокта-приймача траси I установочного М!сця (у вшгадку п!дключення до ран!ш зоф1ксованого фрагмента' ланцюга значения HAS1 дор!внюе номеру останнього й 12=0); впорядкова-Н1 niданоязши А,В (множини допустмих значень зм1нних JKL, JKM) счиюдаються з елементiв, що авляють номери маг!стралой каналу, 1 становлять Шдмножшш Ьп .

У цьому к розд!л! наведенi результата експериментально! поре в i рки ефективност! робота ППП "AL-GAD". Дана пор!вняльна оц!нкэ останнього з най01льш розповс-юджэннм сьогодн! аналогом САПР PGAD вере Ii 4.5.

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

У додаткох наведен! коп(1 акт}в про впровадшння й вико-рпстпиня результат!в дисортзц!йноТ роботи, а також текста програмних модулей 1Ш "AL-CAD".

ОСНОВ!! I РЕЗУЛЬТАТЫ РОБОТИ ТА ВИСНОВКИ

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

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

2.-ВИ1№ЛвН1 прнчшш Л0Я8И 1 ЕИЗНЭЧвН! шляхи уоуненая надлишку канал!в.

3. розроблеш алгоритм! автоматизовано! побудови та оп-тим!зац!I ВДРП.

4. Отримаш сп1вв1дношв1шя, що описувть умови перехре-щення трас у дискрет!; синтезований алгоритм &нал1зу тополо-г!чно1 ситуащ { в каналI, що дозволяв но ткпьки достатньо просто ¡ден'Л1ф[куваги конфя!кт, але й визнвчити можлив!сть його усунешя за рахунок змнш конф!гурэцп раийи заф!ксова-них фрагмент!в трас.

5. Побудованпй алгоритм тополог!чного макротрасування, що мае б1льшу швидкод!ю, в1к в)дом! до наступного часу аналоги, 1 характеризуемся рядом особливостей: простотою рёал!-зацЯ на ЕОМ; в1дсутшстю етап!в формування м!н!мального зв'язуючого дерева, розшарування з'еднань та розкраски графа порехрещеиь; гарантованою моюшв1стю знаходаення шляху мш элементами, шо з'сднуються, за умов його !снування.

6. Запропонований орпгшальний спос1б побудови геометр!'! пров!дник!в на баз!.поел!добного анал!зу тополог!чноТ ситуа-ц!1 в канал!,, ио в!др!зняеться простотою реал!зацП на ЕОМ.

7. Розроблений пакет прикладник програм "АЬ-САВ".

Перед1чен1 виде основн! результата роботи с п1дтвврдаен-

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

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

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

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

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

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

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

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

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

8.'Алипов Н.В., Литвинова Е.И. Проектирование топологии многослойных печатных плат, на основе крупнодискретной модели // Тези додав¡дей третьо! мкшародно!' науково-техдпчжн кон-ференцИ' "Контроль 1 управл!ння в техн!чних системах".- В1н-нйця, 1995.

Особиста участь автора в отрныанш наукових результатов. ДисертацШш робота е шдсумком особисто! робота автора, В роботах, написания у сп!вавторств1, особисто автором розроблено: уШверсальну великодискретну модель печатноГ плати; алгоритм!! автоматизовано! побудови та оптишзащ К ВДРП; сп1 ев!Д1ЮИ81ШЯ, як! описують умови перехрещення трас у каналах; алгоритм тополог!чного макротрасування; спос1б оц!шот ивидкод!I алгоритму розпод1лу ланщиЧв по макродискретах; сшвв!дношепня, як! описують умови перехрещення фрагмент¡в трас у каналах; алгоритм м1кротрасувзння; алгоритм перерозпо-д1лу трас по шарах; пакет прикладаих програм "АЬ-САВ".

. АННОТАЦИЯ

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

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

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

THE SUMMARY

LltYlnova E.I. Designing and research of topology models Of multilayer prlnted-clrcult-hoards and algorithms of Interconnections routing. The dissertation for the Candidate degree of the technical sciences on the speciality 05.13.05 -Computer Aided Design. The Kharkov state Technical University of Radioelectronics, Kharkov, 1995.. The dissertation is manuscript .

The universal large-sized diskrete model of printed-circuit-board for regular and irregular accomodation.of elements is developed. It has allowed to realize the stages mak-

го- and raicroroute topologically and. In difference from taoim analogues, completely to automate the process of construction of large-aiaed diekrete working field. The task of large-sized diskrete »oriting field optimization 18 set and-solved, The expressions, which circumscribe of routes intersection conditions in diskrete, are reseived on the basis of which the macroroute topological algorittan, having of large speed, than analogues known till now la developed. The original way of routes geometry construction , based on consecutive analysis of topological situation in channel and distinguished by simplicity of realisation on computer la offerred. The pack of applied program "AL-CAD" is developed. •

Киотов! слова! система автоматизованого проектування (САПР), алгоритм, програма, модуль, еф9ктивн1сть. шщвгод1я, продук-тивнfстъ, анал!з, тополог1чна модель, багатоиарова печатна плата, умови перехрещання трас, тополог!чна ситуац!я, конф-л!кт, секуча, фронт хвил!, зона усталеного розм!щення, дквре-ло, приймач, макротрасування, м!кротрасування, оптим!зац!я, ' розм!щення, великодискретне робочв поле, дерево Штойнера, макродискрет, канал, деформэц1Я фрагмента трас, роэповсюд-ження хвил!, перерозпод!л трас, пакет прикладних програм "AL-CAD".

Шдгшсако до друку 29.II.S5 р. Об'ем 1,25. д.а. Обл.-аидаа, а.1

Формат паперу 60x04 Тиран 100 пр. '-'•'•■■-•'> ' Зам. 22/268

' Друкарня .ХЗ/, пл. Свободе, 5