Sponsored By:
ASP-DAC 2006 Archives
6C-1
| Title | DraXRouter: Global Routing in X-Architecture with Dynamic Resource Assignment |
| Author | *Zhen Cao, Tong Jing (Computer Science & Technology Department, Tsinghua University, China), Yu Hu, Yiyu Shi (University of California, Los Angeles, United States), Xianlong Hong (Computer Science & Technology Department, Tsinghua University, China), Xiaodong Hu, Guiying Yan (Institute of Applied Mathematics, Chinese Academy of Sciences, China) |
| Abstract | In recent years, the X-Architecture is introduced to obtain better performance for integrated circuit physical design. This paper reformulates the global routing problem in X-Architecture under the liquid routing model. Then, a dynamic resource assignment (Dra) method is presented to reduce potential vias. At last, a global router called DraXRouter, is designed, in which we adopt a dynamic-tabulist-based tree construction algorithm and a stochastic optimization strategy to gain high quality routing solution. Tested on ISPD’98 benchmarks, DraXRouter achieves better routing performance compared with two recent global routers. |
| Slides (pdf file) | 6C-1 |
6C-2
| Title | Diagonal Routing in High Performance Microprocessor Design |
| Author | Noriyuki Ito, Hideaki Katagiri, Ryoichi Yamashita, Hiroshi Ikeda, Hiroyuki Sugiyama, *Hiroaki Komatsu, Yoshiyasu Tanamura, Akihiko Yoshitake, Kazuhiro Nonomura, Kinya Ishizaka, Hiroaki Adachi, Yutaka Mori, Yutaka Isoda, Yaroku Sugiyama (Fujitsu Limited, Japan) |
| Abstract | This paper presents a diagonal routing method which is applied to an actual microprocessor prototype chip. While including the layout functions for the conventional Manhattan routing, a new diagonal routing capability is added as one of the routing functions. With this enhancement, diagonal routing becomes an additional strategy for improving delays of critical paths in the microprocessor design. The prototype chip proved that our method was effective in reducing the total net length and improving path delays. |
| Slides (pdf file) | 6C-2 |
6C-3
| Title | CDCTree: Novel Obstacle-Avoiding Routing Tree Construction based on Current Driven Circuit Model |
| Author | Yiyu Shi (University of California, Los Angeles, United States), Tong Jing (Tsinghua University, China), *Lei He (University of California, Los Angeles, United States), Zhe Feng, Xianlong Hong (Tsinghua University, China) |
| Abstract | Routing tree construction is a fundamental problem in modern VLSI design. In this paper we propose CDCTree, an Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) heuristic algorithm to construct an OARSMT. CDCTree is based on the current driven circuit (CDC) model mapped from an escape graph. The circuit structure comes from the topology of the escape graph, with each edge replaced by a resistor indicating the wirelength of that edge. By performing DC analysis on the circuit and selecting the edges according to the current distribution to construct an OARSMT, the resulting tree has short wirelength. The algorithm has been implemented and tested on cases of different scales and with different shapes of obstacles. Experiments show that CDCTree can achieve shorter wirelength than the existing best algorithm, An-OARSMan, when the terminal number of a net is less than 50. |
| Slides (pdf file) | 6C-3 |
6C-4
| Title | A Novel Framework for Multilevel Full-Chip Gridless Routing |
| Author | *Tai-Chen Chen, Yao-Wen Chang (National Taiwan University, Taiwan), Shyh-Chang Lin (SpringSoft, Inc., Taiwan) |
| Abstract | Due to its great flexibility, gridless routing is desirable for nanometer circuit designs that use variable wire widths and spacings. Nevertheless, it is much more difficult than grid-based routing because of its larger solution space. In this paper, we present a novel "V-shaped" multilevel framework (called VMF) for full-chip gridless routing. Unlike the traditional "Lambda-shaped" multilevel framework (inaccurately called the "V-cycle" framework in the literature), our VMF works in the V-shaped manner: top-down uncoarsening followed by bottom-up coarsening. Based on the novel framework, we develop a multilevel full-chip gridless router (called VMGR) for large-scale circuit designs. The top-down uncoarsening stage of VMGR starts from the coarsest regions and then processes down to finest ones level by level; at each level, it performs global pattern routing and detailed routing for local nets and then estimate the routing resource for the next level. Then, the bottom-up coarsening stage performs global maze routing and detailed routing to reroute failed connections and refine the solution level by level from the finest level to the coarsest one. We employ a dynamic congestion map to guide the global routing at all stages and propose a new cost function for congestion control. Experimental results show that VMGR achieves the best routability among all published gridless routers based on a set of commonly used MCNC benchmarks. Besides, VMGR can obtain significantly less wirelength, smaller critical path delay, and smaller average net delay than the previous works. In particular, VMF is general and thus can readily apply to other problems. |
| Slides (pdf file) | 6C-4 |
6C-5
| Title | Monotonic Parallel and Orthogonal Routing for Single-Layer Ball Grid Array Packages |
| Author | *Yoichi Tomioka, Atsushi Takahashi (Department of Communications and Integrated Systems, Tokyo Institute of Technology, Japan) |
| Abstract | In this paper, we give the necessary and sufficient condition that all nets can be connected by monotonic routes when a net consists of a finger and a ball and fingers are on the two parallel boundaries of the Ball Grid Array package, and propose a monotonic routing method based on this condition. Moreover, we give a necessary condition and a sufficient condition when fingers are on the two orthogonal boundaries, and propose a monotonic routing method based on the necessary condition. |
| Slides (pdf file) | 6C-5 |