An application of genetic algorithms to solve the layer assignment problem in multi chip modules

The authors investigate the layer assignment problem that occurs in the design of multichip modules (MCMs). An MCM is a high-performance compact package for the interconnection of several hundred chips, which are interconnected by several thousand nets. The aim is to place each net on an x-y pair of layers so as to minimize the number of such layers, with the constraint that the nets do not intersect one another. The authors present a genetic algorithm (GA) approach to solve the problem of minimizing the number of layers. Results obtained for the GA model demonstrate that it is an effective heuristic for the layer assignment problem in MCMs