Sponsored By:
3A: Routing
3A-1
| Title | A Novel Performance-Driven Topology Design Algorithm |
| Author | *Min Pan, Chris Chu (Iowa State University, United States), Priyadarsan Patra (Intel Corporation, United States) |
| Abstract | This paper presents a very efficient algorithm for performance-driven topology design for interconnects. Given a net, it first generates A-tree topology using table lookup and net-breaking. Then a performance-driven post-processing heuristic not restricting to A-tree topology improves the obtained topology by considering the sink positions, required time and load capacitance to achieve better timing. Experimental results show that our new technique can produce better topologies in terms of timing and is hundreds times faster than traditional approach. |
| Slides (pdf file) | 3A-1 |
3A-2
| Title | FastRoute 2.0: A High-quality and Efficient Global Router |
| Author | *Min Pan, Chris Chu (Iowa State University, United States) |
| Abstract | Because of the increasing dominance of interconnect issues in advanced IC technology, it is desirable to incorporate global routing into early design stages to get accurate interconnect information. Hence, high-quality and fast global routers are in great demand. In this work, we propose a high-quality and efficient global router, FastRoute 2.0. It can achieve more than an order of magnitude less overflow and very fast runtime compared to three state-of-the-art academic global routers. The promising results make it possible to integrate global routing into early design stages. This could dramatically improve the design solution quality. |
| Slides (pdf file) | 3A-2 |
3A-3
| Title | DpRouter: A Fast and Accurate Dynamic-Pattern-Based Global Routing Algorithm |
| Author | *Zhen Cao, Tong Jing (Tsinghua University, China), Jinjun Xiong, Yu Hu, Lei He (University of California, Los Angeles, United States), Xianlong Hong (Tsinghua University, China) |
| Abstract | This paper presents a fast and accurate global routing algorithm, DpRouter, based on two efficient techniques: (1) dynamic pattern routing (Dpr), and (2) segment movement. These two techniques enable DpRouter to explore large solution space to achieve better routability with low time complexity. Compared with the state-of-the-arts, experimental results show that we consistently obtain better routing quality in terms of both congestion and wire length, while simultaneously achieving a more than 30x runtime speedup. We envision that this algorithm can be further leveraged in other routing applications, such as FPGA routing. |
| Slides (pdf file) | 3A-3 |
3A-4
| Title | A Fast and Stable Algorithm for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction |
| Author | *Pei-Ci Wu, Jhih-Rong Gao, Ting-Chi Wang (National Tsing Hua University, Taiwan) |
| Abstract | In routing, finding a rectilinear Steiner minimal tree (RSMT) is a fundamental problem. Today’s design often contains rectilinear obstacles, like macro cells, IP blocks, and pre-routed nets. Therefore obstacle-avoiding RSMT (OARSMT) construction becomes a very practical problem. In this paper we propose a fast and stable algorithm for this problem. We use a partitioning based method and an ant colony optimization based method to construct obstacle-avoiding Steiner minimal tree (OASMT). Besides, two heuristics are proposed to do the rectilinearization and refinement to further improve wirelegnth performance. The experimental results show our algorithm achieves the best wirelength in most of the test cases and the runtime is very small even for the large case in which the number of terminals and the number of obstacles both are more than 100. |
| Slides (pdf file) | 3A-4 |
3A-5
| Title | A Theoretical Study on Wire Length Estimation Algorithms for Placement with Opaque Blocks |
| Author | *Tan Yan, Shuting Li, Yasuhiro Takashima, Hiroshi Murata (The University of Kitakyushu, Japan) |
| Abstract | How to estimate the shortest routing length when certain blocks are considered as routing obstacles is becoming an essential problem for block placement because HPWL is no longer valid in this case. Although this problem is well studied in computational geometry [6], the research results are neither well-known to the CAD community nor presented in a way easy for CAD researchers to ultilize their establishment. With the help of some recent notions in block placement, this paper interprets the research result in [1,8], which gives the best algorithm for this problem as we know, in a way more concise and more friendly to CAD researchers. Besides, we also tailor its algorithm to VLSI CAD application. As the result, we present a method that estimates the shortest obstacle-avoiding routing length in O(M^2+N) time for a placement with M blocks and N 2-pin nets. |
| Slides | 3A-5 (ppt) |