×

Floorplanning with abutment constraints based on corner block list. (English) Zbl 0995.68198

Summary: Corner Block List (CBL) was recently proposed as an efficient representation of general rectangle packing: different from other topological representations, CBL needs a smaller amount of encoding storage and linear time computation effort to generate each placement configuration. To extend its applicability to simple rectangle packings, this paper addresses the problem of handling abutment constraints in the context of the CBL representation. We can obtain the abutment information by scanning the intermediate solutions represented by CBL in linear time during the simulated annealing process and fix the CBL by the heuristic method in case the constraints are violated. A novel penalty function is derived to measure the violation of the abutment constraints and help to ensure all the constraints are satisfied at the end of the annealing process. The experimental results are demonstrated by several examples of MCNC benchmarks and the performance shows the effectiveness of the proposed method.

MSC:

68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)
Full Text: DOI