Effective congestion reduction for IC package substrate routing

Off-chip substrate routing for high-density packages is challenging due to requirements such as high density, lack of vertical detour, non-Manhattan routing, and primarily planar routing. The existing substrate routing algorithms often result in a large number of unrouted nets that have to be routed manually. This article develops an effective yet efficient diffusion-driven method D-Router to reduce congestion. Starting with an initial routing, we develop an effective diffusion-based congestion reduction. We iteratively find a congested window and spread out connections to reduce congestion inside the window by a simulated diffusion process based on the duality between congestion and concentration. The window is released after the congestion is eliminated. Compared with the state-of-the-art substrate routing method that leads to 480 nets unrouted for ten industrial designs with a total of 6415 nets, the D-Router reduces the amount of unrouted nets to 104, a reduction to the 4.6 multiple. In addition, the D-Router obtains a similar reduction on unrouted nets but runs up to 94 times faster when compared with a negotiation-based substrate routing.