Směrování (automatizace elektronického návrhu) - Routing (electronic design automation)

Tento článek je o návrhu integrovaných obvodů jako součásti automatizace elektronického návrhu . Pro další druhy směrování viz směrování (disambiguation) .

V elektronickém designu je směrování drátu , běžně nazývané jednoduše směrování , krokem v konstrukci desek plošných spojů (PCB) a integrovaných obvodů (IC). Staví na předchozím kroku nazvaném umístění , který určuje umístění každého aktivního prvku integrovaného obvodu nebo komponenty na desce plošných spojů. Po umístění krok směrování přidá vodiče potřebné pro správné připojení umístěných komponent při dodržení všech návrhových pravidel pro IC. Kroky umístění a směrování návrhu IC jsou společně známé jako místo a trasa .

Úkol všech směrovačů je stejný. Jsou jim dány některé již existující polygony skládající se z kolíků (nazývaných také svorky) na buňkách a volitelně některé již existující vodiče zvané preroutes. Každý z těchto polygonů je spojen se sítí , obvykle jménem nebo číslem. Primárním úkolem routeru je vytvářet geometrie tak, aby byly připojeny všechny terminály přiřazené ke stejné síti, nebyly připojeny žádné terminály přiřazené různým sítím a byla dodržována všechna pravidla návrhu. Směrovač může selhat nepřipojením terminálů, které by měly být připojeny (otevřený), omylem připojením dvou terminálů, které by neměly být připojeny (zkrat), nebo vytvořením porušení pravidla návrhu. Kromě toho lze od směrovačů očekávat, že správně připojí sítě, aby se ujistil, že design splňuje načasování, nemá problémy s přeslechy , splňuje požadavky na hustotu kovů, netrpí anténními efekty atd. Tento dlouhý seznam často protichůdných cílů je tím, co extrémně ztěžuje směrování.

Je známo, že téměř každý problém spojený se směrováním je neřešitelný . Nejjednodušší problém směrování, nazývaný Steinerův stromový problém, spočívající v nalezení nejkratší trasy pro jednu síť v jedné vrstvě bez překážek a bez konstrukčních pravidel je NP-tvrdý, pokud jsou povoleny všechny úhly, a NP-úplný, pokud jsou povoleny pouze vodorovné a svislé vodiče. . Ukázalo se také, že varianty směrování kanálů jsou NP-úplné, stejně jako směrování, které snižuje přeslechy , počet průchodů atd. Směrovače se proto málokdy pokoušejí najít optimální výsledek. Místo toho je téměř veškeré směrování založeno na heuristice, která se snaží najít dostatečně dobré řešení.

Pravidla návrhu se někdy značně liší od vrstvy k vrstvě. Například povolená šířka a rozteč ve spodních vrstvách mohou být čtyřikrát nebo vícekrát menší než povolené šířky a rozteče v horních vrstvách. To přináší mnoho dalších komplikací, kterým routery pro jiné aplikace, jako je deska s plošnými spoji nebo design s více čipy, kterým čelí . Obzvláštní potíže nastanou, pokud pravidla nejsou jednoduchými vzájemnými násobky a když průchody musí procházet mezi vrstvami s různými pravidly.

Typy směrovačů

Deska plošných spojů jako design na počítači (vlevo) a realizovaný jako sestava desky naplněná komponenty (vpravo). Deska je oboustranná, s pokovením průchozím otvorem, zelenou odolností proti pájení a bílou legendou. Byly použity komponenty pro povrchovou montáž i pro průchozí otvory.

Nejstaršími typy směrovačů EDA byly „ruční směrovače“ - navrhovatel klikl myší na koncový bod každého úsečkového segmentu každé sítě. Moderní návrhový software desek plošných spojů obvykle poskytuje „interaktivní směrovače“ - navrhovatel vybere podložku a klikne na několik míst, aby poskytl nástroju EDA představu o tom, kam jít, a nástroj EDA se pokusí umístit vodiče co nejblíže této cestě, aniž by to narušilo kontrola návrhových pravidel (DRC). Některé pokročilejší interaktivní směrovače mají v interaktivním směrovači funkce „push and shove“ (neboli „shove-away“ nebo „automoving“); nástroj EDA vytlačuje jiné sítě, pokud je to možné, aby umístil nový vodič tam, kde to chce navrhovatel, a přesto se vyhnout porušování DRC. Moderní návrhový software desek plošných spojů také obvykle poskytuje „autoroutery“, které směrují všechna zbývající nevyřízená připojení bez zásahu člověka.

Hlavní typy autorouterů jsou:

Jak směrovače fungují

Mnoho směrovačů provádí následující celkový algoritmus:

  • Nejprve určete přibližný směr pro každou síť, často směrováním na hrubé mřížce. Tento krok se nazývá globální směrování a může volitelně zahrnovat přiřazení vrstev. Globální směrování omezuje velikost a složitost následujících podrobných kroků směrování, které lze provádět mřížku po čtverci.

Pro podrobné směrování je nejběžnější technikou rip-up a reroute aka rip-up a retry :

  • Vyberte sekvenci, ve které mají být sítě směrovány.
  • Veďte každou síť postupně
  • Pokud nelze úspěšně směrovat všechny sítě, použijte některou z různých metod „vyčištění“, při kterých jsou odstraněny vybrané směrování, změní se pořadí zbývajících sítí, které mají být směrovány, a o zbývající směrování se pokusíte znovu.

Tento proces se opakuje, dokud nejsou směrovány všechny sítě nebo se program (nebo uživatel) nevzdá.

Alternativním přístupem je zacházet s kraťasy, porušováním návrhových pravidel, překážkami atd. Na podobném základě jako nadměrná délka drátu - to znamená, že konečné náklady budou sníženy (zpočátku), spíše než absolutně, kterým je třeba se vyhnout. Tato víceprůchodová metoda směrování „iterativního vylepšení“ je popsána následujícím algoritmem:

  • Pro každý z několika iterativních průchodů:
  • Předepište nebo upravte parametry hmotnosti „objektivní funkce“ (s hodnotou parametru hmotnosti pro každou jednotku nadměrné délky drátu a pro každý typ porušení). Např. Pro první průchod může být nadměrná délka drátu typicky dána vysokou cenou, zatímco porušení designu, jako jsou šortky, sousedství atd., Jsou dány nízkou cenou. V pozdějších průchodech se relativní pořadí nákladů změní tak, aby porušení byla nákladná nebo mohla být absolutně zakázána.
  • Vyberte (nebo náhodně) sekvenci, ve které mají být sítě během tohoto průchodu směrovány.
  • „Rozbalit“ (pokud již bylo směrováno) a postupně přesměrovat každou síť, aby se minimalizovala hodnota objektivní funkce pro tuto síť. (Některá z tras budou obecně mít šortky nebo jiná porušení designu.)
  • Pokračujte k dalšímu iteračnímu průchodu, dokud nebude směrování úplné a správné, nebude dále vylepšeno nebo dokud nebude splněno jiné kritérium ukončení.

Většina směrovačů přiřazuje vrstvy elektroinstalace k převážení směrového vedení „x“ nebo „y“, existují však směrovače, které se vyhýbají nebo snižují potřebu takového přiřazení. Každý přístup má své výhody i nevýhody. Omezené směry usnadňují návrh napájecího zdroje a řízení přeslechů mezi vrstvami, ale povolení libovolných tras může snížit potřebu průchodů a snížit počet požadovaných vrstev vedení.

Viz také

Reference

Další čtení

externí odkazy