Přeskupení spojů ve sběrnicích

Mnoho návrhových systémů DPS dnes pracuje na principu tzv. floor planningu, což znamená důkladné plánování rozmístění a organizaci elementů (komponenty a jejich rotace, zakázané oblasti, umístění mechanických detailů, …) na desce plošných spojů. Mezi tyto elementy přibyly i sběrnice jako nový styl návrhu. Jsou to svazky spojů, které jsou podle geometrické podobnosti návrhářem nebo automaticky těmto sběrnicím přiřazeny. Návrhář nebo automat (rozumí se tím programová funkce), potom definují potenciální nebo fixní optimální polohu v propojovacím prostoru, kde budou sběrnice umístěny. Nikde však zatím nebyla řešena otázka organizace spojů při vstupu a výstupu z takové sběrnice. Je totiž zřejmé, že ideální stav je tehdy, kdy spoje, které vstupují do sběrnice, jsou seřazeny do nějaké optimální permutace a také z ní vystoupí ve stejném pořadí. Pořadí se v rámci sběrnice nemění (spoje se nepřeskupují ani nemění vrstvy), a to za účelem co nejmenšího rozměru sběrnice, zde součtu šířek tras spojů a mezer mezi nimi. Ty jsou dány nastavením návrhových pravidel. Optimálním seřazením se rozumí stav, kdy segmenty spojů vedoucí od pinů jedné součástky ke vstupu sběrnice a také z jejího výstupu k odpovídajícím pinům druhé součástky jsou navrženy routerem bez jakýchkoliv problémů a co nejméně blokují okolí – viz obr. 1. Zde je množina spojů vstupujících (anebo vystupujících) do sběrnice znázorněna v podobě „vějíře“. Podobná situace se řeší v případě propojení spojů s předem definovanou délkou – viz obr. 2. I zde je nutná reorganizace počátečního pořadí spojů. Zatímco v prostoru nazvaném „Untangling“ je posloupnost spojů pevně dána návrhem meandrů v oblasti nazvané „Length-constrained routing“, je nutné znázorněnou situaci dořešit přeskupením spojů u levé součástky a dosáhnout tak stejného pořadí spojů – korespondence stejně barevných pájecích plošek.

Obr. 1 Znázornění problému vyvedení segmentů spojů od pinů součástky ke vstupu do sběrnice a jejich seřazení ve sběrnici

Obr. 2 Překřížení vodičů je řešeno v sekci „Untangling“

Dále se tedy v tomto textu budeme zabývat problematikou řazení spojů ve sběrnicích. Popíšeme problém a také postup vedoucí k vyřešení překřížení spojů, a to i při manuálním návrhu.

Obr. 3 a) bezproblémové propojení, b) překřížené spoje, c) řešení

Začneme u obr. 3, kde je problém detailně ilustrován. Je evidentní, že spoje seřazené v řešení c) na pravé straně takto budou vstupovat do sběrnic a ve stejném pořadí vystupovat. Přeskupení spojů do sběrnic může být v programových nástrojích generováno jako preprocesor a může být rozšířeno na řešení širšího spektra problémů, např. řešení otázky planarity spojů. Bez újmy na obecnosti můžeme předpokládat, že přeskupené spoje na pravé straně jsou označeny 1, 2, ..., N. Problém je možné formulovat takto:

Je dán sloupec pinů, očíslovaných nějakou permutací čísel bez opakování odshora dolů a úkolem je přeskupit spoje vedoucí od těchto pinů s použitím průchozí kapacity mezi piny tak, aby vzniklé pořadí přeskupených spojů tvořilo přirozenou permutaci, tj. 1, 2, 3, …, N, a spoje měly planární podobu.

Tento problém má více přístupů k řešení. Jedno takové řešení může být konstruováno takto:

• nejprve spojíme piny 1 bez jakékoliv změny (obr. 3c),
• pokračujeme piny odshora dolů, pokud míjíme pin s číslem menším, než je číslo právě propojovaného pinu (zde 2 a 4 na obr. 3c),
• „objedeme“ tento pin zprava, v opačném případě zleva,
• pokud je možné pin propojit přímo s pinem stejného čísla na pravé straně, provedeme toto propojení,
• takto pokračujeme až do vyčerpání všech pinů.

Obr. 4 Upward routing

Uvedenému postupu se říká Upward routing (obr. 4). Zaručuje planaritu spojů, nicméně není příliš praktický, a to z následujících důvodů:

• nebere v úvahu kapacitu mezi sousedními piny,
• takto vygenerovaná řešení mají mnoho průchodů spojů mezi piny, což často nebývá na deskách reálná situace.

Obr. 5 Single-detour routing

Existuje však ještě další řešení – styl zvaný Single-detour routing. Ten zajišťuje, že každý spoj prochází mezi piny jen jednou a pravá strana sloupce pinů (obr. 5) se používá pouze pro přímé spojení. Toto řešení přináší řadu výhod:

• tvar spojů je jednodušší (tedy nižší přetížení),
• pravá strana sloupce pinů je úplně volná a může zde začít definice tvaru spoje s předem definovanou délkou.

Řešení Single-detour routingu spočívá v dynamickém programování, při němž musí být pro řešitelnost splněny jisté podmínky. Při určité permutaci čísel totiž nelze problém vyřešit planárně, což je náš primární požadavek. V tomto případě je nutné rozdělit celou úlohu na několik subproblémů a ty řešit samostatně. Uvedená problematika je součástí tzv. Escape routingu, který byl již na stránkách tohoto časopisu popsán.

Existuje ještě jedna metoda řešení překřížených vodičů stylem Single-detour routing. Na obr. 6 a) je zadání pro přeskupení spojů společně s uvedenými kapacitami průchodnosti mezi piny (čísla nad piny). Obě posloupnosti pinů nemají přirozené permutace, a tak je velmi obtížná jakákoliv orientace ve smyslu, kde začít řešit, zvlášť, je-li úloha komplexnější. Pokud piny v dolním řádku očíslujeme přirozeně ve vzrůstajícím pořadí čísel a v horním řádku na odpovídající pozici původní číslo přepíšeme novým číslováním, dostaneme daleko přehlednější situaci – viz obr. 6 b).

Obr. 6 Jiný přístup k řešení Single-detour routingu a) zadání propojení a kapacity průchodnosti mezi piny b) řešení s využitím kapacit

Obr. 7 Použití Single-detour routing u 15 spojů

Poté spojíme nekolidující spoje (2, 3 a 7) a pokračujeme v realizaci spojů, které zbyly ve vzrůstajícím pořadí, tedy 1, 4, 5, 6 a 8 s využitím kapacit. Tento postup je velice transparentní a jeho algoritmická složitost je řádově nižší než u dynamického programování. Je použitelný, jak bylo zmíněno na začátku, pro manuální řešení takovýchto situací na deskách plošných spojů. Na obr. 7 je potom vidět praktický výsledek použití metody Single-detour routing.