Layer Assignment for Multichip Modules

We investigate the layer assignment problem that arises in the design of a multichip module (MCM), which is a high performance compact package for the interconnection of several hundred chips. The aim is to place each net in a x-y pair of layers, so as to minimize the number of such pairs. We present an approximation algorithm, running in 0(nd ) time, for minimizing the number of layers, where n is the number of nets and d is the (two dimensional) density of the problem. © 1990 IEEE