A linear programming-based algorithm for floorplanning in VLSI design

In this paper, we consider a floorplanning problem in the physical design of very large scale integration. We focus on the problem of placing a set of blocks (modules) on a chip with the objective of minimizing area of the chip as well as total wire length. The blocks have different areas and their shapes are either fixed (predetermined) or flexible (to be determined). We use the sequence-pair suggested by Murata et al. (see ibid, vol.15, no.12, p.1518-1524, 1996) to represent the topology of nonslicing floorplans and present two methods to obtain a floorplan from a sequence-pair. One is a construction method, and the other is a method based on a linear programming model. The two methods are embedded in simulated annealing algorithms, which are used to find a near optimal floorplan. Results of computational experiments on the Microelectronics Center of North Carolina benchmark examples show that the proposed algorithms work better than existing algorithms.