M2R: multilayer routing algorithm for high-performance MCMs

We introduce a new multilayer routing strategy for high-performance MCMs whose objective is to route all nets optimizing routing performance and to satisfy various design constraints (e.g., minimizing coupling between vias as well as between signal lines and minimizing discontinuities such as vias and bends). First we introduce the Pin Pre-wiring and Redistribution Problem, which redistributes the pins or prewired subnets uniformly over the MCM substrate using pin redistribution layers. Pin redistribution is very important in MCM design. Our experience shows that it not only provides a global distribution for the pins congested in the chip site over the chip layer so as to ease the future routing difficulty, but also reduces the capacitive coupling between vias induced by many layers (up to 63 layers) by separating the pins far apart. The goal of the problem is to minimize the number of layers required to redistribute the entire set. An effective approach is proposed for solving this problem. Next we develop four effective algorithms for signal distribution, i.e., two variations on both single-layer routing and xy plane-pair routing paradigms. Based on these algorithms, a mixed version of single-layer routing and xy plane-pair routing techniques is proposed to establish a good trade-off between them to favor circuit performance and/or design objective instead of overemphasizing on the area minimization. One strategy is to apply single-layer routing iteratively until α % of the nets are routed, then route the remaining (100-α)% nets by xy plane-pair routing process. This provides the designer with a trade-off (e.g., between the number of layers and total number of vias) and shows the versatility of the proposed techniques. Various strategies are compared using practical MCM examples (each MCM has 25-100 ICs, 25-60 I/Os per IC, and 50-1,200 nets)