Flip-chip routing with unified area-I/O pad assignments for package-board co-design

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.