(Back to Session Schedule)

The 13th Asia and South Pacific Design Automation Conference

Session 3A  Routing
Time: 15:50 - 17:55 Tuesday, January 22, 2008
Location: Room 310A
Chairs: Atsushi Takahashi (Tokyo Institute of Technology, Japan), Jung Dong Cho (Sungkyunkwan Univ., Republic of Korea)

3A-1 (Time: 15:50 - 16:15)
TitleMaizeRouter: Engineering an Effective Global Router
Author*Michael D. Moffitt (IBM Austin Research Lab, United States)
Pagepp. 226 - 231
Keywordglobal routing
AbstractIn this paper, we present MaizeRouter, winner of the inaugural 2007 Global Routing Contest. MaizeRouter reflects a significant leap in progress over existing publicly-available tools, and draws upon simple yet powerful edge-based operations (including extreme edge shifting, a technique aimed at congestion reduction, and edge retraction, a counterpart to extreme edge shifting that reduces unnecessary wirelength). These algorithmic contributions are built upon a framework of interdependent net decomposition, and permit a broad search space that previous algorithms have been unable to achieve.

3A-2 (Time: 16:15 - 16:40)
TitleA New Global Router for Modern Designs
Author*Jhih-Rong Gao, Pei-Ci Wu (Synopsys, Taiwan), Ting-Chi Wang (Nat'l Tsing Hua Univ., Taiwan)
Pagepp. 232 - 237
KeywordGlobal Routing
AbstractIn this paper, we present a new global router, NTHU-Route, for modern designs. NTHU-Route is based on iterative rip-ups and reroutes, and several techniques are proposed to enhance our global router. These techniques include (1) a history based cost function which helps to distribute overflow during iterative rip-ups and reroutes, (2) an adaptive multi-source multi-sink maze routing method to improve the wirelength of maze routing, (3) a congested region identification method to specify the order for nets to be ripped up and rerouted, and (4) a refinement process to further reduce overflow when iterative history based rip-ups and reroutes reach bottleneck. Compared with two state-of-the-art works on ISPD98 benchmarks, NTHU-Route outperforms them in both overflow and wirelength. For the much larger designs from the ISPD07 benchmark suite, our solution quality is better than or comparable to the best results reported in the ISPD07 routing contest.

3A-3 (Time: 16:40 - 17:05)
TitleRoutability Driven Modification Method of Monotonic Via Assignment for 2-Layer Ball Grid Array Packages
Author*Yoichi Tomioka, Atsushi Takahashi (Tokyo Inst. of Tech., Japan)
Pagepp. 238 - 243
Keywordball grid array, monotonic, package, routing
AbstractBall Grid Array packages in which I/O pins are arranged in a grid array pattern realize a number of connections between chips and a printed circuit board, but it takes much time in manual routing. We propose a fast routing method for 2-layer Ball Grid Array packages to support designers. Our method distributes wires evenly on top layer and increases completion ratio of nets by improving via assignment iteratively.

3A-4 (Time: 17:05 - 17:30)
TitleOrdered Escape Routing Based on Boolean Satisfiability
AuthorLijuan Luo, *Martin D.F. Wong (University of Illinois at Urbana-Champaign, United States)
Pagepp. 244 - 249
Keywordescape routing, Boolean satisfiability
AbstractRouting for high-speed boards is largely a time-consuming manual task today. In this paper we consider the ordered escape routing problem which is a key problem in board-level routing. All existing approaches to this problem cannot guarantee to find a routing solution even if one exists. We present in this paper an algorithm to exactly solve this problem based on Boolean satisfiability. Experimental results on escape routing problems from industry show that our algorithm performs well.

3A-5 (Time: 17:30 - 17:55)
TitleMeshWorks: An Efficient Framework for Planning, Synthesis and Optimization of Clock Mesh Networks
Author*Anand Rajaram, David Z. Pan (University of Texas at Austin, United States)
Pagepp. 250 - 257
KeywordClock, Mesh, CTS
AbstractA leaf-level clock mesh is known to be very tolerant to variations [1]. However, its use is limited to a few high-end designs because of the high power/resource requirements and lack of automatic mesh synthesis tools [2]. Most existing works on clock mesh [1], [3]–[7]either deal with semi-custom design or perform optimizations on a given clock mesh. However, the problem of obtaining a good initial clock mesh has not been addressed. Similarly, the problem of achieving a smooth tradeoff between skew and power/resources has not been addressed adequately. In this work, we present MeshWorks, the first comprehensive automated framework for planning, synthesis and optimization of clock mesh networks with the objective of addressing the above issues. Experimental results suggest that our algorithms can achieve an additional reduction of 26% in buffer area, 19% in wirelength and 18% in power, compared to the recent work of [7] with similar worst case maximum frequency under variation.