On handling arbitrary rectilinear shape constraint

Nonrectangular (rectilinear) shape occurs very often in deep submicron floorplanning. Most previous algorithms are designed to handle only convex rectilinear blocks. However, handling concave rectilinear shape is necessary since a simple "U" shape is concave. A few works could address concave rectilinear block explicitly. In (K. Fujiyoshi, et al., (1999)), a necessary and sufficient condition of feasible sequence pair is proposed for arbitrary rectilinear shape in terms of constraint graph. However, no constraint is imposed on sequence pair representation itself. The search for feasible sequence pair mainly depends on the simulated annealing, which implies unnecessary inefficiency. In many cases, it takes very long time or even is unable to find the feasible placement. Furthermore, it takes O(n³) runtime to evaluate each sequence pair, which leaves much space for improvement. We propose a new method to handle arbitrary rectilinear shape constraint based on sequence pair representation. We explore the topological property of feasible sequence pair, and use it to eliminate lots of infeasible sequence pairs, which implies speeding up the convergence of simulated annealing process. The evaluation of a sequence pair is based on longest common subsequence computation, and achieves significantly faster runtime (O(mnloglogn) time where m is the number of rectilinear-shape constraints, n is the number of rectangular blocks/subblocks). The algorithm can handle fixed-frame floorplanning and min-area floorplanning as well.