Module placement on BSG-structure with pre-placed modules and rectilinear modules

Abstract

A main task in designing IC/PCB is to pack rectilinear modules under various constraints and objectives. If modules are all rectangles without any positional constraint, recently proposed BSG and Sequence-pair based packing algorithms have been proved to work fast enough for practical use. Focusing BSC, to support an effective use, this paper develops techniques to handle rectilinear modules and modules with positional constraints. First a solution is proposed for pre-placed modules. It is to give a linear order to the floating modules following which they are embedded in packing. In the course, the pre-placed modules are considered as the constraints such that no floating modules are forbidden to be placed. The packing of modules including rectilinear ones is solved by applying the above techniques after rectilinear modules are sliced into a set of rectangles. Experimental results on industrial PCB-data showed that the proposed algorithm outputs high quality packings.