An effective soft module floorplanning algorithm based on sequence pair

An effective soft module floorplanning algorithm is proposed. It uses simulated annealing framework based on the sequence pair representation. Because a soft module may have many possible shapes, so it will take long time to find a good solution in simulated annealing method. We proposed a method which finds four candidates of module shape to be chosen in a simulated annealing process for each module. These candidates provide a better choice toward local optimal packing. We combine our method with a fast sequence pair evaluation algorithm and keep the same time complexity nlogn of a sequence pair evaluation. During the simulated annealing process, it either chooses to change the shape of one module or to swap the modules in the sequence pair. We have implemented this algorithm. For all MCNC benchmark soft module floorplanning problems, we have obtained more compact floorplan with much less run time comparing to a previous work . For example, for the MCNC benchmark ami49, our algorithm obtained 0.48% of dead space in 142 seconds using a 440 MHz Ultra10 workstation. The previous work to Lagrangian relaxation approach obtained 7.7% of dead space and 2354 seconds using a 600 MHz Pentium III processor.