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.

O-chip substrate routing for high density packages is chal-lenging, and the existing substrate routing algorithms often result in a large number of unrouted nets that have to be routed manually. This paper develops an eective yet e-cient diusion-driven method D-Router to improve routabil-ity by a simulated diusion process based on the duality between congestion and concentration. Compared with a recently published A*-based algorithm used in a state of the art commercial tool and with similar routability and run-time as the negotiation based routing, D-Router reduces the number of unrouted nets by 4.6x with up to 94x runtime reduction.

Off-chip substrate routing for high-density packages is on the critical path for time to market. Compared with on-chip routers, existing commercial tools for off-chip routing have lower routability and often result in a large number of unrouted nets for manual routing. In this paper, we explain why planar routing is still required with multiple routing layers for substrate routing and then propose a flexible via-staggering technique to improve routability. In addition, we develop an efficient yet effective substrate routing algorithm, applying dynamic pushing to tackle the net ordering problem and reordering and rerouting to further reduce wire length and congestion. Compared with an industrial design tool that leaves 936 nets unrouted for nine industrial designs with a total of 6100 nets, our algorithm reduces the unrouted nets to 212, a 4.5-times net number reduction, which translates to design time reduction.

Compared with on-chip routers, the existing commercial tools for off-chip routing have a much lower routability and often result in a large number of unrouted nets for manual routing. In this paper, we develop an effective, yet efficient, substrate routing algorithm, applying dynamic pushing to alleviate the net ordering problem and reordering and rerouting for further wire length and congestion reduction. Compared with an industrial design tool that leaves 936 nets unrouted for nine industrial designs with a total of 6100 nets, our algorithm reduces the unrouted nets to 212, a 4.5-times net number reduction and practically more design time reduction.