Routing Algorithms for Chip-Package-Board Co-Design
Date Issued
2009
Date
2009
Author(s)
Fang, Jia-Wei
Abstract
In VLSI deigns, nanometer effects have complicated the designs of chips as well as packages and printed circuit boards. Further, due to higher functionality in modern circuits, the number of I/O’s is also dramatically increased. In order to improve the routability, performance, and convergence of the design, two advanced packaging technologies: ball-grid-array packaging and flip-chip packaging, and chip-package-board co-design are strongly recommended by industry. In this dissertation, we present the first routing algorithms in the literature for chip-package-board co-design based on the two advanced packages. They can not only be applied to complete (1) the routing in the packages and printed circuit boards, but also can consider (2) chip-package co-design, (3) package-board co-design, and (4) chip-package-board co-design. For the routing in the packages and printed circuit boards, our routing algorithms adopt a two-stage technique of global routing followed by detailed routing. In the global routing, the computational geometry techniques (e.g., the Delaunay triangulation and the Voronoi diagram), minimum-cost maximum-flow network algorithm, and integer and linear programming are used to find an optimal global-routing wirelength for the addressed problems. Since we consider the wire congestion in our global-routing networks, the detailed routing can generate a 100% routable sequence to complete the routing. For chip-package co-design, an I/O netlist between a chip and a package can be simultaneously generated with the package layout. Therefore, the total wirelength can be reduced. By considering package-board co-design, the routing information from the chip and the printed circuit board can be kept during the package routing. Consequently, the routability can be improved. In chip-package-board co-design, due to the great design flexibility, we can additionally consider the I/O planning of a package except the package routing. Hence, the design cost can further be reduced in the early stage. Further, we can also get much shorter total wirelength and higher routability. Experimental results based on real industry designs show that our routing algorithms can achieve 100% routability and the optimal global-routing wirelength and satisfy all design constraints, under reasonable CPU times, whereas recent related work results in much inferior solution quality.
Subjects
Computational Geometry
Flip-chip Devices
Flow Networks
Integer Programming
Linear Programming
Physical Design
Placement and Routing
Routing and Layout
Printed Circuits
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-D94943037-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):d76d35a093ac2710de76c8576d7e5646