Autoroutingproblemet

[SvenW]

Jag håller på att studera Autorouting-problemet, dvs att mer eller mindre automatiskt överföra en SCH-representation av en krets till en PCB-dito. Finns det någon som har tips och input att ge?
Litteratur, algoritmer, strategier och metoder på matematisk eller praktisk nivå. Jag är inte intresserad av namn på program som innehåller funktionen, utan vill förstå problemet från grunden.

[limpan4all]

Googla på "manhattan routing" och "shaped based routing".
Och för komponentplaceringen "cluster placement".

Vid all normal PCB konstruktion ligger den viktigaste delen i komponentplaceringen och till en viss del i hur grindar/pinnar används. Med en underbar komponentplacering går routandet snabbt och enkelt.
Men komponetplaceringen kräver avsevärt mera kompetens än ledningsdragningen.

[SvenW]

Tack för tipset. Har hittat en del, även om många artiklar mest har varumärkesexponering som syfte eller stöder Predikaren i hans ord: --Ingen ände är det på det myckna bokskrivandet, och mycket studerande gör kroppen trött.
Jag laborerar med a-star algoritmen och tänker lägga in den i en stokastisk process, i stil med 'simulated annealing'. Är det så de kommersiella programmen fungerar?
Jag vill ha in autorouting i Hec innan jag fortsätter med crossprobing. Vad gäller komponentplacering tänker jag mig att den ska vara manuell. Just nu har jag bara en termometerskala som visar summan av avstånden pin-pin. Har kommersiella program automatfunktioner för komponentplacering?

[flippy]

testa att söka på typ "vlsi routing", när jag letade efter samma sak så fanns det en del bra sidor, hittade även nån bok som verkade bra. Det var nog nåt kapitel om routing, en vlsi bok var det då.

[SvenW]

Tack. Jag hittade en hel del.
Fast de talar ofta om miljoner komponenter, och jag nöjer mig med några dussin. Jag siktar mot mönsterkort för hobbyister, och vem orkar löda miljoner lödpunkter? Men en del grundläggande är förmodligen gemensamt.

[SvenW]

Har nu jobbat med en autorouting-algoritm några månader, och har en dellösning som ser ut att fungera. Det är fascinerande att se hur snabbt den hittar ett bra mönster.

Den testar något tusental varianter per sekund och väljer ut den bästa.

Jobbet är fascinerande, och om någon programmeringskunnig vill prova och kanske förbättra algoritmen så är det lätt för mig att lägga ut den på min webbsida. Eljest håller jag nog på och putsa ett par månader till, innan den kommer med i en ny patch-level av Hec.

[blueint]

Vilken licens har du tänkt dig?
För övrigt kanske algoritmen bör ta hänsyn till crosstalk, differential ledningar, belastning, isolationsavstånd etc..

[SvenW]

Licensen är GPL.
'Crosstalk, differential ledningar, belastning, isolationsavstånd etc...' är postprocessing.
Jag tar inte in detta i algoritmen primärt, men det kommer sedan in som korrektioner. Isolationsavstånd, alias clearance, finns redan rudimentärt.
Man kan för övrigt flytta sin layout till gEDA::pcb och där göra vidareprocessing.
Hec skall bli kompatibelt med gschem och PCB vad gäller filformat. Inte fullt ut ännu, men det går bra att flytta en Hec-konstruktion till gEDA::pcb.

[blueint]

Har hänt mer än en gång att jag skulle vilja skriva en "netlist" direkt med text och ha ett program som gör både schema och pcb av det.
Vore jättebra om du fick det att fungera. Skulle underlätta routing av t.ex. Minimig projektet.

[SvenW]

Väcker den här tråden igen efter ett par år.

Jag håller fortfarande på att studera autorouteralgoritmer och vill gärna veta om någon har fler tips.
Mer specifikt:
Hur bygger man idag en PCB-autorouter. Lättläst litteratur i ämnet, gärna på nätet, eller om någon har bra idéer och kan beskriva dem.
Jag har kommit en bit på vägen genom att testa algoritmer i xhec.
Välkommen att testa/kriticera/vidareutveckla den. Eller kanske att testa/presentera helt nya idéer. Just nu har jag lite idetorka.

[psynoise]

Söker man på http://www.inspec.org kommer det upp ganska många resultat från tidningen Printed Circuit Design, tyvärr finns den inte på Chalmers bibliotek men det kanske går att beställa hem. Tror även att det finns några datorer på biblioteket som man kommer åt utan att vara student, och där finns det Inspec och IeeeXplore som borde ha mängder med information i ämnet.

[blueint]

Kanske är som optimeringsproblemet med plockepin där ett antal pinnar av olika längd efter varann ska kombineras för att få in flest i en ram där längden är begränsad på ett håll (Y), och man ska använda så lite längd åt det andra hållet(X). Enda svaret matteprofessorn kom upp med var trial-and-error. Dvs man får låta datorn prova alla kombinationer tills det passar.

Lite nyttiga länkar:
SvenW hemsida
xhec hemsida

[SvenW]

Det var ett tag sedan jag var student, men ett besök på Chalmersbiblioteket vore kanske värt besväret. Antar att allmännheten kommer in, åtmistone för att läsa tidskrifter.

Den autorouter som nu finns i xhec fungerar just efter trial-and-error-principen. Den betygsätter ett valfritt antal lösningar, typisk några tusen, och väljer ut den bästa. Men antalet kombinationer blir astronomiskt när pinnantalet växer. Den optimala lösningen kan man i allmänhet inte hitta, men förhoppningsvis en som är tillräckligt bra.
Det går i alla fall tusen gånger fortare än att pröva sig fram manuellt. Speciellt vid enlagersproblem.

[limpan4all]

Efter att faktiskt ha använt autorouters i 15 år för PCB layout.
Gör dina algoritmer massivt parallella, iallafall för varje enskilt seed.
Sedan kan en enkel singelprocess utvärdera vilken lösning som skall gå vidare till nästa seedomgång.
Detta då dagens processorer bara får fler och fler parallella beräkningsenheter, och den rent sekventiella lösningsmetoden faktiskt bara blir långsammare (eller bara blir marginellt snabbare).