M(2)R - MULTILAYER ROUTING ALGORITHM FOR HIGH-PERFORMANCE MCMS

We introduce a new multilayer routing strategy for high-performance MC Ms 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 discontinu ities such as vias and bends). First we introduce the Pin Pre-wiring a nd Redistribution Problem, which redistributes the pins or prewired su bnets uniformly over the MCM substrate using pin redistribution layers . Pin redistribution is very important in MCM design. Our experience s hows that it not only provides a global distribution for the pins cong ested in the chip site over the chip layer so as to ease the future ro uting difficulty, but also reduces the capacitive coupling between via s 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 req uired to redistribute the entire set. An effective approach is propose d for solving this problem. Next we develop four effective algorithms for signal distribution, i.e., two variations on both single-layer rou ting and xy plane-pair routing paradigms. Based on these algorithms, a mixed version of single-layer routing and xy plane-pair routing techn iques 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 routi ng iteratively until alpha % of the nets are routed, then route the re maining (100 - alpha)% nets by xy plane-pair routing process. This pro vides the designer with a trade-off (e.g., between the number of layer s and total number of vias) and shows the versatility of the proposed techniques. Various strategies are compared using practical MCM exampl es (each MCM has 25-100 ICs, 25-60 I/Os per IC, and 50-1,200 nets).