A new method for floor planning using topological constraint reduction

Abstract

An approach to the constraint-based floor planning of flexible, fixed, and preplaced blocks that is based on the removal of redundant constraints and the reshaping of flexible blocks is discussed. A floor plan is said to respect a given constraint set if is satisfies either a vertical or a horizontal constraint in the set for each pair of blocks. The approach presented is to construct a floor plan of optimal area that respects the input constraint set, which is assumed to be derived from a relative placement of the blocks. Reasons for considering this method are delineated, and a heuristic floor-planning algorithm based on constraint reduction and block reshaping is given. A simple example illustrates the algorithm. Several real floor-planning examples are also given.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>