Poznáváme autoroutery: strategie pro Escape routing

V minulých dílech seriálu jsme se zmiňovali o nejčastěji používaných algoritmech při vytváření spojového obrazce. Dnešní díl bude o aktuálním tématu – tzv. escape routingu. Téma není nové, několik známých návrhových systémů (PADS, Allegro,…) má podobné nástroje již několik let zabudovány do rejstříku svých funkcí – např. PADS umožňuje propojení součástek, které mají až 2 048 vývodů, což je pro představu matice o 45×45 vývodech, nicméně stále je co inovovat, neboť součástek s obrovskou hustotou vývodů a zmenšující se geometrií v praxi přibývá, a proto i nástroje, které řeší, jak optimálně vyvést fragmenty spojů na okraj vesměs maticově uspořádaného pole vývodů, musí být zdokonalovány. Při použití co nejmenšího počtu vrstev, což má vliv na cenu a také spolehlivost obvodu. Proto píšu o aktuálním tématu, „ruční řešení“ popsaných problémů zabírá zkušenému návrháři kolem dvou až tří týdnů, což je pro vývoj v elektronice velmi dlouhý čas, navíc není záruka, že „ruční návrh“ povede k úspěchu. To, že téma je aktuální, dokládá velký počet nově vytvořených technik a algoritmů v posledních dvou letech publikovaných na akademické půdě zejména v USA, Tchaj-wanu, Japonsku a také v Číně – jak vidno, všechno kolébky pokroku elektroniky. Dokonce práce [1] uvádí, že v ní uvedený algoritmus vyřešil řadu testovacích příkladů kompletně, kdežto algoritmy v systému Allegro pouze na 70 %, což už je velmi silné tvrzení. Problém je, že většina „akademických routerů“ pracuje s jednoduchými modely a předpoklady, které praxe okamžitě nabourává, a proto jsou použitelné pouze v teoretické rovině a jejich dopracování do praktické podoby je problematické. Nicméně jako zdroj možné inspirace jsou zmíněné práce na vysoké úrovni.

Nyní něco o escape routing. Je třeba rozlišit 2 typy escape routingu, první je věnován té které konkrétní patici součástky – u ní je spojový obrazec vyřešen návrhářem jednou provždy a spojové fragmenty (FANOUTy – viz dále) vedoucí na okraj matice součástek jsou součástí knihovny patic součástek. Ostatní spoje obvodu se napojují na takto dříve vyvedené cesty na hranici součástky.

My se ale budeme věnovat obecnějšímu modelu, kdy je dána geometrie matice (nebo jiné uspořádání) vývodů, vrstva, průměry pájecích plošek, možný počet tras vedoucích mezi piny, návrhová pravidla a další detaily a nejčastějším úkolem je optimální nalezení cest mezi vývody dvou hustě propojených součástek, ať jen na hranice komponenty, anebo celý spoj. Tomuto se říká simultánní escape routing, neboť fragmenty spojových cest se hledají současně u obou součástek na základě jejich konkrétního umístění a rotace na ploše propojovacího prostoru, čímž je dána fixní poloha všech pinů.

Zde již nejde o „pouhé vyvedení“ spojů a hranici součástky jakýmkoliv směrem, ale o optimální návrh fragmentů z hlediska délky spojů.

Jako vždy si pomůžeme několika obrázky, které ilustrují úkol, zadání i vyřešení. Jak jsme již uvedli, escape router má daný úkol buď komplexně vyřešit, nebo nasměrovat návrháře k usnadnění jeho řešení, anebo dát odpověď na to, zda je problém vůbec řešitelný. Vždycky jde ale o obrovskou úsporu času.

Obr. 1 Různě složité uspořádání vývodů komponenty

Samozřejmě složité propojení nemusí být pouze u součástek s maticově uspořádanými vývody, jsou zde další složitěji propojitelné patice součástek, viz obr. č. 1 (různě složité uspořádání vývodů komponenty), i tyto situace jsou předmětem řešení escape routingu, je zde ovšem třeba důkladný rozbor již zmiňované geometrie patice vývodů. Situace se komplikuje, pokud mezi sousedními vývody nelze vést žádnou spojovou cestu.

Obr. 2 FANOUT

Nejprve několik pojmů. V návrhové terminologii je často používán pojem FANOUT. Je to v podstatě buď prefabrikovaný (odstranitelný, pokud nevyhovuje nebo je nevyužit), nebo fixní (převzatý z knihovny součástek) fragment spojové cesty s počátkem v „problematickém“ pinu vesměs ukončený průchodem mezi vrstvami (via). Používá se v oblasti s hustým výskytem pinů té samé součástky na jedné vrstvě a má umožnit při návrhu snadnější přístup k dosud nepropojenému pinu – viz obr. 2. FANOUTy se opatřují vývody ještě před počátkem práce routeru. Jakmile má dojít ve fázi propojení pinu s FANOUTem s dalšími vývody spoje, FANOUT se buď zruší (a tak vznikne prostor pro nalezení cesty k pinu), nebo se použije. V některých případech dopadne návrh tak, že FANOUT je zbytečný, a to u fixních fragmentů, kdy je třeba pin nezapojen.

Dalším pojmem je PLANARITA spojek, což znamená, že spojky vybrané z několika různých spojů lze navrhnout bez křížení na jediné vrstvě. Výběrem maximálních množin takových spojek a pořadím jejich návrhu, což vede k optimalizaci počtu vrstev, se budeme zabývat v dalším díle.

Obr. 3 Počáteční situace – zadané propojení 2 součástek vzdušnými spoji A–L

Na obr. č. 3 je zobrazena počáteční situace – propojení dvou součástek s maticově uspořádanými vývody, definice propojení je znázorněna vzdušnými spojnicemi. Jak vidno, situace vypadá chaoticky.

Postup řešení z obr. 3 je opět zmiňován v principech. Je zde mnoho detailů, které přímo nesouvisí s tématem článku, a z těchto důvodů nejsou v textu zmiňovány. Autorovi jde především o osvětlení problému escape routingu a vytvoření dostatečně výkonného nástroje jako pomůcky návrháři při tvorbě spojového obrazce.

Řešení propojení s co nejmenším počtem vrstev je autorovým algoritmem a spočívá v postupné eliminaci křížení mezi vzdušnými spoji a vytváření maximálních skupin planárních spojek. Redukuje se tak počet průchodů nutných ke změně vrstvy a samozřejmě šetří místo v už tak hustém poli pinů.

Obr. 4 Matice křížení spojek A–L

Když mluvíme o křížení, tak z matice křížení – viz obr. č. 4 – je patrno, které vzdušné spoje A–L se kříží. Naším úkolem bude navrhnout FANOUTy u spojek A–L u levé i pravé součástky a dovést je na osy LE a RE, prostor mezi osami jsem nazval kanálem a jde v podstatě o jakýkoliv prostor v propojovacím prostoru, kde lze vést neprotínající se soustavu cest, z níž je možno vytvořit jakýsi svazek.

Postup

Promítneme všechny piny levé součástky na osu LE (obr. č. 5) a totéž provedeme s piny pravé součástky, projekci na osu RE. Získáme tak dvojí posloupnost písmen A–L. Ideální případ by byl, kdyby posloupnosti byly totožné, stačilo by propojení odpovídajících bodů (písmen) v rámci kanálu mezi LE a RE a spojky by se nekřížily. Takto musíme postupně eliminovat jednotlivá křížení. Na obou osách jsou vidět i volné kapacity (průchodnost na opačnou stranu kanálu).

Obr. 5 Vyhledání počáteční množiny nekřížících se spojek a jejich zpracování

Začneme výběrem maximální množiny spojek (vzdušných vodičů), které se navzájem neprotínají. Výběr takové množiny je prací samostatného algoritmu, který zde není uveden z důvodů přesahujících srozumitelnou a spíše populárně popisnou formu tohoto článku. Zdrojem pro výpočet je matice křížení a graf spojnic. Výsledkem algoritmu je nalezení množiny spojek E, K, I, B, A (což je možné vysledovat i ze zadání) a jejich zpracování podle jejich vzrůstající manhattanské délky – viz obr. č. 5, výsledek znázorněn silnějšími spojnicemi. Tento postup vede k maximální PLANARITĚ. Spojnice odpovídajících bodů na osách LE a RE s body uvnitř pole pinů (např. LE(A) a A u levé součástky představují budoucí tvar FANOUTu (označeno černě) – samozřejmě s respektováním geometrie patice, v níž se pin nachází.

Obr. 6 Další částečné řešení se zpracováním spojek H, F, C

Po zpracování počátečního výběru algoritmus pokračuje v dalším řešení vždy výběrem spojnice, která protíná maximum již zpracovaných spojek, v případě stejného počtu nalezených křížení má prioritu spojka s menší manhattanskou délkou. V našem případě byla vybrána spojka H (3 křížení, s A, B, I), dále F, C, výsledek je na obr. č. 6. Předtím však dojde k uvolnění projekce nezpracovaných bodů na osách a spojky začnou „obcházet“ již realizovaná propojení.

Obr. 7 Konečné řešení s doplněním spojek J, G, D a L

Přitom platí, že zpracované spojky jsou jakýmsi magnetem, k němuž se nově zpracovávané přimykají (hugging), je to z důvodu nezablokování ještě nepropojených pinů (viz situace kolem pinu C pravé součástky). Při prvotním průchodu návrhu jde o dost násilný hugging kvůli úspoře místa kolem ještě nezpracovaných pinů, v dalším kroku po komplexním vyřešení propojení je situace z hlediska tvaru spojových cest optimalizována. Konečné řešení je zobrazeno na obr. č. 7. To, jestli uživatel využije celý návrh propojení (tzn. fragment spoje u levé součástky, u pravé a také spojení v kanálu mezi osami), nebo pouze oba FANOUTy, je pouze na jeho volbě.

Určitě je patrné, že problém escape routingu je velmi komplexní. Zde jsme se zabývali pouze jednodušší situací dle zadání příkladu, v praxi však bývá propojeno velmi hustě více součástek mezi sebou a najít shluky pinů (clustery), které by navzájem nekolidovaly, je velmi složitá úloha, zde escape routing přechází v tzv. buss routing. Navíc je zde problém FANOUTů – každý pin u maticové součástky bývá opatřen FANOUtem s průchodem před začátkem návrhu, čímž je prostor mezi piny ještě více zneprůchodněn. Zdá se, že původně používané strategie návrhů, jako je pořadí spojů, preference směrů vedení spojů na vrstvách atd., berou nyní za své při řešení escape routingu. Výše popisované situace na deskách PBS nebo čipech budou do budoucna velkým algoritmickým oříškem.