| Title | A Separation and Minimum Wire Length Constrained Maze Routing Algorithm under Nanometer Wiring Rules |
| Author | *Fong-Yuan Chang, Ren-Song Tsay, Wai-Kei Mak (National Tsing Hua University, Taiwan), Sheng-Hsiung Chen (Springsoft, Taiwan) |
| Page | pp. 175 - 180 |
| Keyword | Maze, Routing, Nanometer Wiring Rules, DFM, minimum wire length |
| Abstract | Due to process limitations, wiring rules are imposed by foundries on chip layout. Under nanometer wiring rules, the required separation between two wire ends is dependent on their surrounding wires, and there is a limit on the minimum length of each wire segment. Yet, traditional maze routing algorithms are not designed to handle these rules, so rule violations must be corrected by post-processing and the quality of result is seriously impacted. For this reason, we propose a new maze routing algorithm capable of handling these wiring rules. The proposed algorithm is proved to find a legal shortest path with runtime complexity of O(n), where n is the number of grid point. Experiments with seven tight industrial cases show that the success rate of getting a DRC clean routing by a commercial router is improved, and the average runtime is reduced by 2.3 times. |
| Slides |
| Title | An ILP-based Automatic Bus Planner for Dense PCBs |
| Author | Pei-Ci Wu (University of Illinois at Urbana-Champaign, U.S.A.), Qiang Ma (Synopsys, Inc., U.S.A.), *Martin D. F. Wong (University of Illinois at Urbana-Champaign, U.S.A.) |
| Page | pp. 181 - 186 |
| Keyword | bus planner, printed circuit boards |
| Abstract | Modern PCBs have to be routed manually since no EDA tools can successfully route these complex boards. An autorouter for PCBs would improve design productivity tremendously since each board takes about 2 months to route manually. This paper focuses on a major step in PCB routing called bus planning. In the bus planning problem, we need to simultaneously solve the bus decomposition, escape routing, layer assignment and global bus routing. This problem was partially addressed by Kong et al. in [3] where they only focused on the layer assignment and global bus routing, assuming bus decomposition and escape rout- ing are given. In this paper, we present an ILP-based solution to the entire bus planning problem. We apply our bus planner to an industrial PCB (with over 7000 nets and 12 signal layers) which was previously successfully routed manually, and compare with a state-of-the-art industrial internal tool where the layer assignment and global bus routing are based on the algorithm in [3]. Our bus planner successfully routed 97.4% of all the nets. This is a huge improvement over the industrial tool which could only achieve 84.7% routing completion for this board. |
| Title | Layer Minimization in Escape Routing for Staggered-Pin-Array PCBs |
| Author | *Yuan-Kai Ho, Xin-Wei Shih, Yao-Wen Chang (National Taiwan University, Taiwan), Chung-Kuan Cheng (University of California, San Diego, U.S.A.) |
| Page | pp. 187 - 192 |
| Keyword | Escape routing, PCB routing |
| Abstract | As the technology advances, the pin number of a high-end PCB
design keeps increasing while the size of a PCB keeps shrinking.
The staggered pin array is used to accommodate a larger pin number
than the grid pin array of the same area. Nevertheless, escaping a
large pin number to the boundary of a dense staggered pin array,
namely multilayer escape routing for staggered pin arrays, is
significantly harder than that for grid pin arrays. This paper
addresses this multilayer escape routing problem to minimize the
number of used layers in a staggered pin array for manufacturing
cost reduction. We first present an escaped pin selection method
to assign a maximal number of escaped pins in the current layer
and also to increase useful routing regions for subsequent layers.
Missing pins are also modeled in our routing network to utilize
the routing resource effectively. Experimental results show that
our approach can significantly reduce the required layer number
for escape routing. |
| Title | Network Flow Modeling for Escape Routing on Staggered Pin Arrays |
| Author | Pei-Ci Wu, *Martin D. F. Wong (University of Illinois at Urbana-Champaign, U.S.A.) |
| Page | pp. 193 - 198 |
| Keyword | escape routing, staggered pin array, network flow modeling |
| Abstract | Recently staggered pin arrays are introduced for modern designs with high pin density. Although some studies have been done on escape routing for hexagonal arrays, the hexagonal array is only a special kind of staggered pin array. There exist other kinds of staggered pin arrays in current industrial designs, and the existing works cannot be extended to solve them. In this paper, we study the escape routing problem on staggered pin arrays. Network flow models are proposed to correctly model the capacity constraints of staggered pin arrays. Our models are guaranteed to find an escape routing satisfying the capacity constraints if there exists one. The correctness of these models lead to an optimal algorithm. |