3D CBL: an efficient algorithm for general 3D packing problems

Abstract

The 3D packing problem is important for practical applications. In the field of VLSI design, 3D packing arises from both the packing of the 3D integrated circuits and the task schedule of FPGA design. In this paper, we propose a novel floorplan representation, named 3D-CBL (3D corner block list) to encode the topology of the 3D packing. Based on triple string, we can represent general packings including slicing and nonslicing. Our algorithm is very effective that the transformation from 3D CBL list to the real packing need only linear time computation effort. Based on simulated annealing algorithm, we can optimize the 3D packing effectively. Experimental results show that our algorithm is effective and efficient