A module placement algorithm based on sequence pair by introducing the concept of clustering

Chip area minimization and total wire length minimization are the two main objectives in module placement problems. Most previous research solved this problem by providing a simulated annealing based algorithm with a linear cost function composed of chip area and total wire length. However, due to consideration of the multiple optimization goals at the same time, it is very difficult to find the balance point for deciding the weighted cofactors on each objective. In this paper, we firstly analyze the interconnection relation of nets among modules and further perform module clustering according to the analyzed result on interconnection. For each cluster, a pure area minimization oriented subfloorplan is built by a sequence pair based simulated annealing algorithm. By concatenating the sub-sequences of subfloorplans, we can build the sequence-pair of an initial solution. Through the refinement of the initial solution, the final solution can be generated. Experimental results on MCNC benchmarks show that our approach is quite promising.