TSCSP: Tabu search algorithm for VLSI module placement based on the clustering sequence-pair

Placement is an very important step in the physical design of VLSI circuits. It is the rectangular packing problem: Given a set of rectangular modules of arbitrary sizes, place them non-overlapping on a plane within a rectangle of minimum area. Since the variety of packing is uncountable infinite, the key issue is to find the optimal solution in the finite solution space, hence it is hard to be solved exactly in practical applications. In this paper, Tabu search algorithm is applied to solve module placement problem. Firstly, all modules are merged into some clusters according to the ratio-connectivity of circuit modules, the placement of the large modules (are included by some modules) is then represented by sequence-pairs. The searching of optimal solution of placement is performed by the tabu search algorithm. Some experiment results are shown in order to demonstrate the effectiveness of the proposed method.