Research On Substrate Topological Routing Algorithms For System In Package

Off-chip substrate routing for high density packages, especially for system in package (SiP), is challenging due to requirements such as high-density, non-Manhattan, and primarily planar routing. The existing substrate routing algorithms often result in a large number of unrouted nets that have to be routed manually.A fast routability estimation algorithm for IC physical design is first proposed in the paper, which serves incremental placement or guides routing to shorten the physical design period. This estimation algorithm first extends an existing combinatorial model with the extended bounding box for flat two-pin nets/sections to pre-estimate congestion probabilistically. It then routes all nets guided by the pre-estimation to obtain more accurate congestion estimation. The proposed algorithm gives a good reference to the research on the latter package substrate topological routing algorithms.Afterwards, this thesis proposes several algorithms to achieve high rout- ability and short wire length, and perform congestion optimization for SiP sub- strate routing. The main contributions include:1. To meet the requirements of the deep submicron packaging process, this thesis proposes an end-zone model for package substrate routing considering the staggered via pitch. With the help of the end-zone, the algorithms considers the substrate topological routing simultaneously with the staggered via assignment and obtains more flexibility to select the routing destinations for each net, which improves the routability and reduces wire length.2. An efficient yet effective substrate routing algorithm ADS~* is proposed, applying dynamic pushing to tackle the net ordering problem, a flexible via-staggering technique based on end-zone to improve the routability, and reordering and rerouting to further reduce wire length and congestion. Compared with an industrial design tool, the algorithm achieves a 4.4-times net number reduction, which translates to design time reduction. 3. As for the congestion reduction optimization, a negotiated congestion (NC) based substrate topological routing is proposed, by enhancing the evaluation function of the ADS~* algorithm with the present and history congestion information. Compared with the ADS~* algorithm, the number of unrouted nets is reduced from 480 to 461.4. Furthermore a diffusion-driven congestion reduction algorithm D-Router is designed for the substrate topological routing. D-Router iteratively finds a highly congested window and spreads out connections to reduce the 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 NC based ADS~* algorithm, D-Router reduces the number of unrouted nets by 4.4-times with 4.2-times runtime reduction.