| Title | Efficient Multi-Layer Obstacle-Avoiding Preferred Direction Rectilinear Steiner Tree Construction |
| Author | *Jia-Ru Chuang, Jai-Ming Lin (National Cheng Kung University, Taiwan) |
| Page | pp. 527 - 532 |
| Keyword | Routing, Multi-Layer, Obstacle-Avoiding, Rectilinear Steiner Tree, Preferred Direction |
| Abstract | Constructing rectilinear Steiner trees for signal nets is a very important procedure for placement and routing because we can use it to find topologies of nets and measure the design quality. However, in modern VLSI designs, pins are located in multiple routing layers, each routing layer has its own preferred direction, and there exist numerous routing obstacles incurred from IP blocks, power networks, pre-routed nets, etc, which make us need to consider multilayer obstacle-avoiding preferred direction rectilinear Steiner minimal tree (ML-OAPDRSMT) problem. This significantly increases the complexity of the problem, and an efficient and effective algorithm to deal with the problem is desired. In this paper, we propose a very simple and effective approach to deal with ML-OAPDRSMT problem. Unlike previous works usually build a spanning graph and find a spanning tree to deal with this problem, which takes a lot of time, we first determine a connection ordering for all pins, and then iteratively connect every two neighboring pins by a greedy heuristic algorithm. The experimental results show that our method has average 5.78% improvement over [7] and at least five times speed up comparing with their approach. |
| Title | Cut-Demand Based Routing Resource Allocation and Consolidation for Routability Enhancement |
| Author | *Fong-Yuan Chang (National Tsing Hua University, Taiwan), Sheng-Hsiung Chen (SpringSoft, Taiwan), Ren-Song Tsay, Wai-Kei Mak (National Tsing Hua University, Taiwan) |
| Page | pp. 533 - 538 |
| Keyword | Cut-Demand, Resource, Routability, Routability, placement |
| Abstract | To successfully route a design, one essential requirement is to allocate sufficient routing resources. In this paper, we show that allocating routing resources based on horizontal and vertical (H/V) cut-demands can greatly improve routability especially for designs with thin areas. We then derive methods to predict the maximum H/V cut-demands and propose two cut-demand based approaches, one is to allocate routing resources considering the maximum H/V cut-demands and the other is to consolidate fragmented metal-1 routing resources for effective resource utilization. Experimental results demonstrate that the resource allocation method can determine design areas more precisely and the resource consolidation method can significantly improve routability. With better routability, the routing time is about 5 times faster on average and the design area can be further reduced by 2-15%. |
| Slides | |
| Title | Negotiation-Based Layer Assignment for Via Count and Via Overflow Minimization |
| Author | *Wen-Hao Liu, Yih-Lang Li (National Chiao Tung University, Taiwan) |
| Page | pp. 539 - 544 |
| Keyword | Physical design, Global routing, Layer assignment, Via count, Via overflow |
| Abstract | Layer assignment determines on which layer the wires or vias should be placed; and the assignment results influence the circuit’s delay, crosstalk, and via counts. How to minimize via count and via overflow during layer assignment has received considerable attention in recent years. Traditional layer assignment to minimize via count tends to produce varying qualities of assignment results using different net orderings. This work develops a negotiation-based via count minimization algorithm (NVM) that can achieve lower via counts than in previous works. As for via overflow minimization, we observe via overflow can be well minimized if via overflow minimization is performed following stacked via minimization. The stacked via minimization adopts the proposed NVM, while via overflow minimization adopts a modified NVM by replacing via cost with via overflow cost. |
| Title | Wire Synthesizable Global Routing for Timing Closure |
| Author | Michael Moffitt (IBM Corporation, U.S.A.), *C. N. Sze (IBM Research, U.S.A.) |
| Page | pp. 545 - 550 |
| Keyword | Routing, Placement, Timing, Algorithm |
| Abstract | Despite remarkable progress in the area of global routing, the burdens imposed by modern physical synthesis flows are far greater than those expected or anticipated by available (academic) routing engines. As interconnects dominate the path delay, physical synthesis such as buffer insertion and gate sizing has to integrate with layer assignment. Layer directives – commonly generated during wire synthesis to meet tight frequency targets – play a critical role in reducing interconnect delay of smaller technology nodes. Unfortunately, they are not presently understood or honored by leading global routers, nor do existing techniques trivially extend toward their resolution. The shortcomings contribute to a dangerous blindspot in optimization and timing closure, leading to unroutable and/or underperforming designs. In this paper, we aim to resolve the layer compliance problem in routing congestion evaluation and global routing, which is very critical for timing closure with physical synthesis. We propose a method of progressive projection to account for wire tags and layer directives, in which classes of nets are successively applied and locked while performing partial aggregation. The method effectively models the resource contention of layer constraints by faithfully accumulating capacity of bounded layer ranges, enabling threedimensional assignment to subsequently achieve complete directive compliance. The approach is general, and can piggyback on existing interfaces used to communicate with popular academic engines. Empirical results on the ICCAD 2009 benchmarks demonstrate that our approach successfully routes many designs that are otherwise unroutable with existing techniques and naïve approaches. |