A general and fast floorplanning by Reduct-Seq representation

摘要

A fundamental issue in floorplan design is in how to represent a candidate solution. After discussing the difference between floorplanning and packing, this paper proposes a new data structure Reduct-Seq for floorplan. A floorplan of ii rooms is encoded to a unique Reduct-Seq of length 3n. Also a decoding algorithm from a Reduct-Seq to a unique floorplan is presented. The computational complexities of encoding and decoding are both only O(n). The number of distinct Reduct-Seq's is counted and revealed that it is not much larger than that of floorplans of the slicing structure. Thus our contribution is to show that the general floorplans can he searched without much larger computation cost than that for searching the slicing structure floorplans. Experiments revealed good performances for several circuits.