Crosstalk-minimum layer assignment

A novel layer assignment algorithm for high-performance multilayer packages, such as multichip modules (MCMs), is proposed. The focus is on assigning nets to layers to minimize the crosstalk between nets, while simultaneously minimizing the number of vias and layers. A novel net interference measure based on potential crosstalk and planarity is used to construct a net interference graph (NIG), and a new graph coloring and permutation algorithm is used to find an interference-minimized subset in each layer and a minimum crosstalk between layers. Theoretical and experimental results on this multilayer assignment approach are presented. The proposed maximum linear permutation heuristic is very robust and allows the incorporation of various design constraints (e.g., crosstalk, crossover, and critical area) and cost criteria