Building Block Placement Based on Stairway Grid Model

摘要

A new Constraint Graph (CG) based representation, SL, was devised first in the paper to represent the non-slicing structure of placement. Research on the CG model proves that a nearly O(n) placement algorithm can be designed over the SL representation. With the assumption of the meta-grid, we can derive the so-called Stairway Grid (SG) model, which has been proposed firstly by our research group. It needs n(3+(lg n)) bits for a placement of n rectangular blocks. The solution space of SG is n~2~(3n-7). For a SG representation, it takes only O(n) time to transform it to its corresponding placement. It had been proved that all slicing structures could be represented by SG. And SG can also represent non-slicing structure. The placement algorithm based on SG can be embedded in a Simulated Annealing (SA) process. Experiment results on SG model demonstrated that it is a concise and effective representation of non-slicing structure.