Poznáváme autoroutery: paprskový, kanálový a LEA algoritmus

V minulém, úvodním díle seriálu o autorouterech, jsme popsali asi nejpoužívanější prohledávací techniku při návrhu spojového obrazce – Leeův algortimus. V tomto článku popíšeme jednodušší, rychlejší, ale méně účinné metody při hledání tras budoucího spojového obrazce. Rád bych zdůraznil, že popisované metody jsou vysvětlovány principiálně, v jednoduchých modelech, kdy každá technika a technologie propojování má mnoho modifikací, a to podle specifických aplikací.

Paprskový algoritmus

Jako vždy předpokládáme, že propojovací prostor tvoří grid (mřížka) a v ní jsou rozmístěné překážky, vývody součástek a již dříve navržené segmenty spojového obrazce. Úkolem algoritmu je opět nalézt cestu – množinu mřížových bodů – ze startu S (vývod součástky nebo segment spoje) do cíle T (opět vývod nebo část spoje). Počáteční situaci ilustruje obr. 1a – mřížka, start S, cíl T a překážky.

Obr. 1a Mřížka s umístěním překážek, S a T

Obr. 1b Paprsek ze startu S ve čtyřech směrech

Obr. 1c Paprsky z bodů 0 s identifikačním číslem 1

Obr. 1d Paprsky z bodů 1 s identifikací číslem 2

Principem algoritmu je vyslat paprsek ze startu S do volných buněk ve směrech doleva, doprava, nahoru a dolů tak dlouhý, až narazí na překážku nebo hranice propojovacího prostoru, a přiřadit jí identifikaci – zde označení dosažených buněk číslem 0.

Situaci popisuje obr. 1b – počáteční paprsky ze startu S. Každý takto dosažený bod mřížky (označený číslem 0) se stává novým zdrojem pro další paprsek, tentokrát budou nově dosažené body mřížky označeny číslem 1 (viz obr. 1c) – paprsky s identifikací číslem 1. Podobně obr. 1d a obr. 1e ukazují vytvoření paprsků č. 2, resp. 3, a dosažení cíle.

Obr. 1e Paprsky z bodů 2 s identifikací číslem 3

Obr. 1f Vyznačení zpětné cesty šipkami

Obr. 1g Vyčištění mřížky od paprsků a označení nové překážky

Zbývá najít zpětnou cestu ke startu S. Tu zjistíme „couváním“ po paprsku s číslem, kterým jsme dosáhli cíle (3), a to tak dlouho, dokud nenarazíme na paprsek s číslem menším (2), totéž se opakuje, dokud s paprskem č. 0 nedorazíme do startu S. Na obr. 1f je cesta zpět do startu S označena šipkami. Zbývá vyčistit mřížku od identifikačních čísel paprsků a nově vzniklou cestu zařadit jako překážku pro další, dosud nepropojené a nenavržené spoje.

Ve srovnání s Leeovým algoritmem je algoritmus rychlejší, ale cesta nemusí být nejkratší. I tady má uvedený model hledání cesty samozřejmě mnoho variant, které vedou k úspoře paměti nebo ke zrychlení práce algoritmu. Toho lze docílit třeba tím, že se paprsky šíří ze startu a cíle proti sobě, tím se ušetří zhruba polovina času na prohledávání. V praxi bývají startem i cílem nejen vývody součástek, ale i celé segmenty spojů. I tento algoritmus je geniální svou jednoduchostí, protože pokud existuje řešení, algoritmus ho nalezne, ale cesta nemusí být optimální. Tato nevýhoda proti jiným algoritmům se smazává, neboť někdy se spojový obrazec modifikuje tak, že některé spoje prostě nejsou nejkratší za cenu kompletní propojitelnosti spojového obrazce. Popsaný algoritmus je dílem významných japonských matematiků Mikami a Tabuchiho.

Kanálový algoritmus

Dalším typem prohledávacího algoritmu, řešícím specifická propojení, je kanálový algoritmus, který bývá aplikován převážně u návrhu čipů a hradlových polí. V propojovacím prostoru jsou umístěny „bloky“ obdélníkového tvaru a mezi bloky, uspořádanými do řad, jsou vytvořeny „kanály“, které umožňují propojení bloků mezi sebou – ilustrace popsaného případu je na obr. 2a – bloky různé velikosti a kanály mezi nimi.

Obr. 2a Bloky různé velikosti a kanály mezi nimi

Obr. 2b Propojení v daném kanálu

Obr. 2c Realizace propojení mezi bloky A a B

Úkolem je realizovat propojení dané netlistem mezi vývody bloku A na horním okraji kanálu a vývody bloku B na spodním okraji kanálu. K dispozici jsou 2 vrstvy, horizontální segmenty na jedné vrstvě, vertikální na druhé, změny vrstev jsou realizovány průchody – situaci ilustruje obr. 2a, kanál je označen žlutě mezi bloky A a B.

Snahou algoritmu je uspořádat segmenty vzhledem ke kapacitě kanálu tak, aby propojení bylo realizováno podle návrhových pravidel, eventuálně, aby se kanál mohl zúžit, a tak dosáhnout minimalizace rozměrů čipu, pokud stejnou strategii uplatníme na všech kanálech propojovacího prostoru. Propojení, které má být provedeno v našem kanálu, je zobrazeno na obr. 2b. Podobnou situaci jako na čipu můžeme najít v praxi na deskách plošných spojů. Jak je vidět na obrázku, kanál může být využit i cizími spoji, které ho využívají jako průchozí, tím samozřejmě snižují kapacitu kanálu a možnosti propojení mezi bloky A a B. Zatímco u dříve popisovaných algoritmů šlo o jednoduché, intuitivní postupy při hledání cesty, v tomto případě nastupuje poměrně složitý aparát z teorie grafů, jehož cílem je srovnání segmentů v kanálu co nejoptimálněji.

Detailní popis řešení by přesáhl rámec časopisu, protože je velmi rozsáhlý a svým způsobem nezáživný. Na obr. 2c je jedno z možných řešení, kdy 1 spojení zůstalo nerealizováno. Existuje opět mnoho modifikací a přístupů, jak řešit křížící se propojení v kanálu. Zmíním se alespoň o jedné základní propojovací technice, zvané LEA (Left Edge Algoritmus).

LEA algoritmus

Jako vždy si pomůžeme při výkladu obrázkem.

Obr. 3 Pojem lokální a globální hustoty: m1 a m2 jsou metalické vrstvy čipu a zároveň určují směr vedení vodičů

Nejprve několik pojmů:

• počet protnutých segmentů svislou čarou v kterémkoliv místě kanálu se nazývá lokální hustota,
• maximální lokální hustota je nazývána globální hustota. Ta je v místě, kde je kanál využit na 100 %. Oba pojmy jsou znázorněny na obr. 3.

Na obr. 3 je zároveň uveden „netlist“ – předpis propojení mezi vývody bloků A a B. 0 značí nepropojený vývod, ostatní čísla popisují propojení stejně označených vývodů.

LEA algoritmus pracuje takto:

1. Seřazení spojů podle horizontálních segmentů zleva (od levých počátků segmentů).
2. Přiřazení prvního spoje prvnímu volnému kanálu odspodu.
3. Přiřazení dalšího segmentu, který nepřekrývá dosud vybrané segmenty, stejnému kanálu.
4. Opakování bodu C), dokud takové segmenty existují.
5. Opakování bodů B)–D), dokud nejsou zpracovány všechny horizontální segmenty.

Obr. č. 4 a) pořadí segmentů zleva podle levého počátku každého segmentu, b) seřazení nepřekrývajících se segmentů v jednotlivých kanálech, např. segmenty 1, 4, 6 a 9 v prvním spodním kanálu, c) výsledné propojení horizontálních a vertikálních segmentů

Celý proces znázorňuje obr. 4. Výsledek na obr. 4 bychom mohli optimalizovat, např. zbavením se průchodů u segmentů 2, 4, 6, 9 a 10 a také zkrátit spoj 10. To jsou však další, dílčí úpravy realizované po práci algoritmu. Právě popsané přiřazení určuje zároveň šířku kanálu. Pokud je šířka kanálu určena dopředu a algoritmus se nedokáže při řešení vejít do globální hustoty, je nutné změnit rozmístění bloků.

V příštím díle seriálu bychom se globálně podívali na propojovací problémy, se kterými se v dnešní době potýkají návrhy DPS, tzv. escape routing a buss routing.