Layer assignment for multichip modules

Abstract

The layer assignment problem that arises in the design of a multichip module, a high-performance compact package for the interconnection of several hundred chips, is studied. The aim is to place each net in a x-y pair of layers, so as to minimize the number of such pairs. An approximation algorithm, running in O(nd) time is presented for minimizing the number of layers, where n is the number of nets and d is the (two-dimensional) density of the problem.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>