Transcription
B-Escape: A Simultaneous Escape RoutingAlgorithm Based on Boundary RoutingLijuan Luo1, Tan Yan1, Qiang Ma1Martin Wong1, Toshiyuki Shibuya21.ECE Department, University of Illinois, Urbana-Champaign2Fujitsu Laboratories of America, Inc.
Outline IntroductionOur Algorithm (B-Escape) Boundary RoutingDynamic Net OrderingImplementation DetailsExperimental ResultsConclusion
PCB RoutingEscape routing
Escape Routing Problems15412212134235(a) Unordered Escape134545(b) Ordered Escape51323345(c) Simultaneous Escape24
Previous Approaches Manual routing Pattern Routing Time ConsumingLimited ability to do complex escapesNegotiated Congestion Routing Difficult to resolve crossings
Our Contributions Introduce a boundary routing approachCapable of handling complicatedproblems in very short timeSolved 14 industrial benchmarks whileCadence Allegro only solved 7.
Focus on 1-side Escape Without loss of generality, we only consider 1-side Escape.
Ordered Escape Use ordered escape to present our boundary routingapproachFoundation of our simultaneous escape
Routing Boundary The boundary of the maximum routableregion for the unrouted pinsShrinks as we route more pins
Boundary Routing Methodology16121117131415(a) Boundary routing 16121117131415(b) Routing based on shortest pathTend to leave more space for the unrouted pins
Routing Modes810161211171376423191415Upward ModeDownward Mode5
Example Upward Mode321
Routing Modes Up-down Mode Alternate between the up and down modesTrapped
Routing Modes Detour Modes Go leftward to reach the boundary Detour upwardDetour downwardDetour up-downBlocked(a) Upward(b) Detour upward
Six Routing Modes
Optimality for Monotonic Routing Guarantee an escape solution for monotonicallyescapable problemsMonotonic routing (a); Non-monotonic routing (b) (c)
Dynamic Net Ordering Huge routability differences caused by slightlydifferent net orderingsDifficult to decide the correct ordering beforehand.
Dynamic Net Ordering Tentatively route each remaining net (usingboundary routing)Choose the “best” one as the next net
Cost Function Trap cost: #Pin unroutableBlock Cost: #Pin blocked (still routable)The overall cost takes both components intoaccount.
Reordering Sometimes pins may get trappedBacktrack and get a different ordering
Detailed Modeling of Routing Grid Need to capture diagonal routing
Detailed Modeling of Routing Grid Introduce “Switch-box” into the grid structureThe switching condition: TrackNo crossingSatisfy capacity constraint
Routing Differential Pairs Pair constraint: If two nets belong to a differentialpair, they are required to route together.Solution Order the paired nets successively. (avoid (b))Define a new boundary for paired nets.
Routing Differential Pairs
Experimental Setup Implemented in C Pentium 4 2.8 GHz system with 4GB memoryBenchmarks: 14 Industrial benchmarksManually solved by designers for 8hours/benchmark#Net (18 64)Grid size (16 14 38 36)
Experimental x12100%100%Ex1370%100%Ex1480%100%# routed problem7/1414/14 Routability comparisonwith Cadence AllegroPCB Router: 14/14 v.s. 7/14Run time: B-Escape: 0.2s 691.3sNegotiated CongestionRouter: 55.8s 6189.0s
Experimental Results
Conclusion Currently escape problems are mostlysolved manuallyWe have presented a boundary routingmethod to solve complicated escapeproblemsB-Escape outperforms the commercialPCB router.
Outline Introduction Our Algorithm (B-Escape) Boundary Routing Dynamic Net Ordering Implementation Details Experimental Results Conclusion
