2009 · 48 citations · 5 references
EngineeringComputer EngineeringComputer ScienceComputational GeometryComputer ArchitectureHardware-software Co-designLayout OptimizationNetwork Flow AlgorithmsPhysical DesignRoutingRouting AlgorithmsRouting ArchitectureCo-design Of PackageComputational Geometry FoundationsCongestion EstimationCongestion OptimizationDelaunay Triangulation AlgorithmsNetwork Flow FormulationsPlacement AlgorithmsRouting Congestion Analysis
In this paper, we present a novel flip-chip routing algorithm for package-board co-design. Unlike the previous works that can consider only either free- or pre-assignment routing, our router is the first work in the literature that can handle both the free-and pre-assignment routing. Based on the computational geometry techniques (e.g., the Delaunay triangulation and the Voronoi diagram), the router applies a unified network-flow formulation to perform congestion estimation for the pre-assignment routing. According to the congestion map, the network-flow formulation can also consider the free-assignment nets during the routing for the pre-assignment ones. Then, the router modifies the network-flow formulation to optimally assign and route the free-assignment nets, considering the routed pre-assignment nets. With the package and board co-design flow, we can achieve 100% routing completion. Experimental results based on industry designs demonstrate the high-quality of our algorithm.
5
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text
Computational geometry. an introduction
Franco P. Preparata, Michael Ian Shamos · 1985 · 2.4K citations
Area-I/O flip-chip routing for chip-package co-design
Jiawei Fang, Yao‐Wen Chang · 2008 · 38 citations