The authors introduce the pin redistribution problem (PRP), which arises from layout design of multi-chip modules. The problem is to redistribute the pins uniformly over the MCM substrate using a number of pin redistribution layers. Pin redistribution is very important in MCM design because it has been used to not only provide a minimum spacing between signal wires in dense signal distribution layers, but also provide engineering change capability. Moreover, experience has shown that the capacitive coupling noise between vias (one of the major problems in designing MCMs) induced by many layers (up to 63 layers) can be reduced using the pin redistribution technique. The goal of the problem is to minimize the number of layers required to redistribute the entire set. As a net is undefined, a number of challenging issues arise. Three effective approaches are proposed for solving this problem.
