Floorplanning with abutment constraints based on corner block list

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. (C) 2001 Elsevier Science B.V. All rights reserved.