Session 3A: Routing

3A-1 (Time: 15:50 - 16:15)

Title MaizeRouter: Engineering an Effective Global Router
Author *Michael D. Moffitt (IBM, USA)
Abstract In 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.
No Slides

3A-2 (Time: 16:15 - 16:40)

Title A New Global Router for Modern Designs
Author *Jhih-Rong Gao, Pei-Ci Wu (Synopsys, Taiwan), Ting-Chi Wang (Nat'l Tsing Hua Univ., Taiwan)
Abstract In 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.
Slides

3A-3 (Time: 16:40 - 17:05)

Title Routability Driven Modification Method of Monotonic Via Assignment for 2-Layer Ball Grid Array Packages
Author *Yoichi Tomioka, Atsushi Takahashi (Tokyo Inst. of Tech., Japan)
Abstract Ball 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.
Slides

3A-4 (Time: 17:05 - 17:30)

Title Ordered Escape Routing Based on Boolean Satisfiability
Author Lijuan Luo, *Martin D.F. Wong (Univ. of Illinois, Urbana-Champaign, USA)
Abstract Routing 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.
No Slides

3A-5 (Time: 17:30 - 17:55)

Title MeshWorks: An Efficient Framework for Planning, Synthesis and Optimization of Clock Mesh Networks
Author *Anand Rajaram, David Z. Pan (Univ. of Texas, Austin, USA)
Abstract A 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.
No Slides
Last Updated on: January 31, 2008