Three dimensional module packing by simulated annealing

A three-dimensional chip design strategy is of increasing significance in association with miniaturization of VLSI circuits. In the design of 3D VLSI and 3D MCM, the placement which is to locate given 3D objects without overlapping each other in the 3D space, becomes an important issue. The 3D placement under the nonoverlapping constraint is called the 3D packing in which minimizing the volume of the package is required. This paper introduces a new coding system to encode the topology of 3D packing as an extension of BSG (bounded-sliceline grid) for 2D packing. The novel coding system is referred to as three dimensional bounded-sliceplane grid (3DBSG). The topology is a set of relative relations assigned to pairs of 3D modules in such a way that one module shall be either "right-of", "rear-of\´ or "above" the other. Furthermore, we propose an idea to handle L-shaped 3D modules on the 3DBSG. The simulation results in which a standard simulated annealing is utilized as an optimization algorithm, are demonstrated in order to test the validity of our 3D packing method based on the 3DBSG.