| Title | A Novel Performance-Driven Topology Design Algorithm |
| Author | *Min Pan, Chris Chu (Iowa State University, United States), Priyadarsan Patra (Intel Corporation, United States) |
| Page | pp. 244 - 249 |
| Keyword | Interconnect, Performance, Topology |
| 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. |
| PDF file |
| Title | FastRoute 2.0: A High-quality and Efficient Global Router |
| Author | *Min Pan, Chris Chu (Iowa State University, United States) |
| Page | pp. 250 - 255 |
| Keyword | Global routing, Steiner trees, congestion |
| 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. |
| PDF file |
| 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) |
| Page | pp. 256 - 261 |
| Keyword | Routing, Routability, Physical Design, Congestion |
| 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. |
| PDF file |
| 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) |
| Page | pp. 268 - 273 |
| Keyword | Wire length estimation, Block placement, Routing obstacle, Shortest path |
| 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. |
| PDF file |