| Title | Efficient Simulated Evolution Based Rerouting and Congestion-Relaxed Layer Assignment on 3-D Global Routing |
| Author | Ke-Ren Dai, *Wen-Hao Liu, Yih-Lang Li (National Chiao Tung University, Taiwan) |
| Page | pp. 570 - 575 |
| Keyword | Global Routing, layer assignment, simulated evolution |
| Abstract | The increasing complexity of interconnection designs has enhanced the importance of research into global routing when seeking high-routability (low overflow) results or rapid search paths that report wire-length estimations to a placer. This work presents two routing techniques, namely adaptive pseudo-random net-ordering routing and evolution-based rip-up and reroute using a two-stage cost function in a high-performance congestion-driven 2-D global router. We also propose two efficient via-minimization methods, namely congestion relaxation by layer shifting and rip-up and re-assignment, for a dynamic programming-based layer assignment. Experimental results demonstrate that our router achieves performance similar to the first two winning routers in ISPD 2008 Routing Contest in terms of both routability and wire length at a 1.42X and 25.84X faster routing speed. Besides, our layer assignment yields 3.5% to 5.6% fewer vias, 2.2% to 3.3% shorter wire-length and 13% to 27% less runtime than COLA. |
| Title | FastRoute 4.0: Global Router with Efficient Via Minimization |
| Author | *Yue Xu, Yanheng Zhang, Chris Chu (Iowa State University, United States) |
| Page | pp. 576 - 581 |
| Keyword | Global Routing, Layer Assignment, 3-Bend Routing |
| Abstract | The number of vias generated during the global routing stage is a critical factor for the yield of final circuits. However, most global routers only approach the problem by charging a cost for vias in the maze routing cost function. In this paper, we present a global router that addresses the via number optimization problem throughout the entire global routing flow. We introduce the via aware Steiner tree generation, 3-bend routing and spiral layer assignment algorithm to reduce via count. We integrate these three techniques into FastRoute 3.0 and achieve significant reduction in both via count and runtime. |
| Title | High-Performance Global Routing with Fast Overflow Reduction |
| Author | *Huang-Yu Chen, Chin-Hsiung Hsu, Yao-Wen Chang (National Taiwan University, Taiwan) |
| Page | pp. 582 - 587 |
| Keyword | Global Routing, Routing |
| Abstract | We develop a new global router, NTUgr, that contains three major steps: prerouting, initial routing, and iterative forbidden-region rip-up/rerouting (IFR). Prerouting employs a two-stage technique of congestion-hotspot historical cost pre-increment followed by small bounding-box area routing. Initial routing is based on efficient iterative monotonic routing. Finally, IFR features three techniques of (1) multiple forbidden regions expansion, (2) critical subnet rerouting selection, and (3) look-ahead historical cost increment. Experiments show that NTUgr achieves high-quality results for ISPD'07 and ISPD'08 benchmarks. |
| Title | IO Connection Assignment and RDL Routing for Flip-Chip Designs |
| Author | Jin-Tai Yan, *Zhi-Wei Chen (Chung Hua University, Taiwan) |
| Page | pp. 588 - 593 |
| Keyword | Flip-chip, RDL routing, IO connection |
| Abstract | Given a set of IO buffers and bump balls with the capacity constraints between bump balls, an O(n2) IO assignment and RDL routing algorithm is proposed to assign all the IO connections and minimize the total wirelength with satisfying the capacity constraints and guarantee 100% routability if the capacity constraint is permitted, where n is the number of bump balls in a flip-chip design. Compared with the combination of the greedy IO assignment and our RDL routing, our IO assignment reduces the global wirelength by 7.6% after global routing and improves the routability by 8.8% after detailed routing on the average. Compared with the combination of our IO assignment, the single-layer BGA global router[7] and our detailed routing phase, our RDL routing reduces the global wirelength by 15.9% after global routing and improve the routability by 10.6% after detailed routing on the average for some tested circuits in reasonable CPU time. |
| Title | On Using SAT to Ordered Escape Problems |
| Author | Lijuan Luo, *Martin D.F. Wong (University of Illinois at Urbana-Champaign, United States) |
| Page | pp. 594 - 599 |
| Keyword | PCB routing, SAT |
| Abstract | Routing for high-speed boards is largely a time-consuming manual task today. The ordered escape routing problem is one of the key problems in board-level routing, and Boolean Satisfiability (SAT) based approach \cite{my-paper} is the only solution to this problem so far. In this paper, we first solve the major deficiency of the original SAT formulation so that the escape problem is completely resolved. Then we propose two techniques to extend SAT approach for large-scale problems. Experimental results on industrial benchmarks show that our methods perform well in terms of both speed and routability. |
| Title | A Fast Longer Path Algorithm for Routing Grid with Obstacles using Biconnectivity based Length Upper Bound |
| Author | *Yukihide Kohira, Suguru Suehiro, Atsushi Takahashi (Tokyo Institute of Technology, Japan) |
| Page | pp. 600 - 605 |
| Keyword | longer path algorithm, upper bound of wire length, routing design of PCB |
| Abstract | In this paper, a fast longer path algorithm that generates a path of a net in routing grid so that the length is increased as much as possible is proposed. In the proposed algorithm, an upper bound for the length in which the structure of a routing area is taken into account is used. Experiments show that our algorithm utilizes a routing area with obstacles efficiently. |