An Efficient Tile-Based ECO Router with Routing Graph Reduction and Enhanced Global Routing Flow: An Efficient Tile-Based ECO Router with Routing Graph Reduction and Enhanced Global Routing Flow Jin-Yih Li Yih-Lang Li Computer & Information TSMC Science Department, National Chiao-Tung University (NCTU)


Outline: Introduction New ECO Routing Design Flow Experimental Results Conclusion Introduction Outline


ECO Routing: ECO Routing ECO routing is commonly requested toward the end of the design process to optimize delay and noise or to complete an imperfect layout. ECO routing is highly complicated many existing interconnections different design rules for delay and noise issues Most of ECO routing can be solved by p2p routing.


The Design Flow of Tile-Based Router: The Design Flow of Tile-Based Router Routing Flow Corner-Stitching Tile Plane Construction Tile Propagation Path Construction 8 tiles


Tile Propagation: Tile Propagation S T C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11


Path Construction: Path Construction Path Construction generates a minimum-corner path that passes through the list of visited tiles. * *


Routing Example: Routing Example Contour Insertion


Routing Example: Routing Example Corner Stitching Tile Plane Creation


Routing Example: Routing Example Tile Propagation


Routing Example: Routing Example Path construction


Challenges for Tile-based ECO Routing: Challenges for Tile-based ECO Routing Tile fragmentation – too many slim tiles Reducing the no. of tiles can promote router speed A horizontal-layer tile plane without contour insertion A horizontal-layer tile plane after contour insertion


Contributions of This Work: Contributions of This Work We propose routing graph reduction to reduce tile fragmentation so that the ECO router can run twice as fast without sacrificing routing quality. We propose a newly enhanced global routing flow to reduce the runtime of ECO routing by around 89%


Slide13: Introduction New ECO Routing Design Flow Experimental Results Conclusions New ECO Routing Design Flow


New ECO Routing Design Flow: New ECO Routing Design Flow Tile Propagation Path Construction Neighboring Tiles Alignment Feasible Solution Found ExtendedRouting No Feasible Solution Success Fail Build corner-stitching tile planes Routing Graph Reduction Global Routing Redundant Tiles Removal GCell Restructuring Enhanced Global Routing Flow


Redundant Tiles Removal: Redundant Tiles Removal Definition conjunct tile. A tile A is referred to a conjunct tile of a tile B if the tile propagation from A to B on the same layer or across adjacent layer is feasible. Definition 1-conjunct. A space tile is said to be one-conjunct if it has only one conjunct tile. Definition 0-conjunct. A space tile is said to be 0-conjunct if it has no conjunct tile.


Redundant Tiles Removal: Redundant Tiles Removal The 1-conjunct space tile is redundant because those paths that enter a 1-conjunct space tile have no exit. The 0-conjunct space tile is redundant because it can not be reached from any other space tile. We remove these redundant tiles within an enumeration over the whole tile plane.


Redundant Tiles Removal: Redundant Tiles Removal T1(1-conjunct) T2(0-conjunct) T3(1-conjunct) Block Tile Space Tile Via region Block Tile : 10 Space Tile: 16 ( the region that can accommodate new via)


Redundant Tiles Removal: Redundant Tiles Removal Block Tile : 10  6 Space Tile: 16  13 26  19


Neighboring Tiles Alignment: Neighboring Tiles Alignment We can adjust and align the left and right sides of two adjacent block tiles to merge them as a block tile. Adjusting border is to enlarge block tiles and to shrink space tiles. Cut lines


Neighboring Tiles Alignment: Neighboring Tiles Alignment T2 T1 T3 T4 T5 T6 (T1,T2) (T3,T4) (T5,T6)


Four Shrinking Cases: Ta Four Shrinking Cases Ta (3) Ta Ta (4) (1) (2) Ta active tile (the tile under process) T1 T1 T2 T3 T2 T3 T2 T3 T2 T3 All these four cases are trying to merge block tiles T2 and T3 T1 T1


Shrinking Rule: Shrinking Rule Ta (a) illegal (b) illegal T2 Stop position Stop position Start position Start position T1 T1 Ta Case 1


Shrinking Example: Shrinking Example T2 Block Tile : 5 Space Tile: 11 Ta Shrunk tile


Shrinking Example: Shrinking Example T2 Block Tile : 5 Space Tile: 11 Total 16  10


Enhanced Global Routing Flow: Enhanced Global Routing Flow Tile Propagation Path Construction Neighbor Tiles Alignment Feasible Solution Found ExtendedRouting No Feasible Solution Success Fail Build corner-stitching tile planes Routing Graph Reduction Global Routing Redundant Tiles Removal GCell Restructuring Enhanced Global Routing Flow


Partition Layout into GCell: Partition Layout into GCell


Create Global Routing Graph: Create Global Routing Graph


Internal Edge of A GCell: Internal Edge of A GCell nw ws se en ew ns nw ws se en ew ns nw ws se en ew ns nw ws se en ew ns A B C D


Cost Function: Cost Function For each vertex v in G, we define a cost c VC = VA/A VC: Via capacity of a GCell VA: The total via region of a GCell A : The area of a GCell For each edge e in G, we define a length cost lc = 2/t.


Find Minimum-Cost Path: Find Minimum-Cost Path GCell on minimum cost path : Active GCell Other: idle GCell


Idle Path Heap: Idle Path Heap T3 T1 T2 P1 P2 P1 GCell A (idle) GCell B (active)


Blocked GCell: Blocked GCell A B C D E


Extended Routing: Extended Routing Pop up cells D and E’s idle path heaps and continue tile propagation A B C D E


Successful Extending Routing: Successful Extending Routing


GCell Restructuring: GCell Restructuring GCell restructuring is performed if extended routing fails. nw ws se en ew ns B C & E’s idle path heaps are empty, so we disconnect internal edges nw and ew E C A D


GCell Rescheduling: GCell Rescheduling G F D


GCell Rescheduling: GCell Rescheduling G D F


Slide38: Introduction New ECO Routing Design Flow Experimental Results Conclusions Experimental Results


Experimental Results: Experimental Results Table 2. The number of tiles on the corner stitching tile planes ※ RGR: Routing Graph Reduction Table 3. The pre-process time before routing Table 1. Statistics of the design under test


Experimental Results: Experimental Results ※T1 : (Ta-Tb)/Ta, T2 : (Ta-(Tb+Trgr))/Ta ※RT : routing time(second), WL: wire length(um) Table 4. Routing results with applying Routing Graph Reduction


Experimental Results: Experimental Results Table 5. Routing results with applying Enhanced Global Routing ※ T3 : (Ta-Tc)/Ta, W : (Wc-Wa)/Wa, V: (Vc-Va)/Va ※ ER : Extended Routing, GCRS: GCell restructuring and rescheduling


Slide42: Introduction New ECO Routing Design Flow Experimental Results Conclusions Conclusions


Conclusions: Conclusions We propose a new ECO routing design flow to promote router speed. routing graph reduction can reduce tile fragmentation so that tile propagation speed can be doubled. With the enhanced global routing flow, ECO router can perform much faster at the cost of a small decline in routing quality.


Slide44: THANK YOU VERY MUCH