Placement Algorithms for Arbitrarily Shaped Blocks

New placement algorithms have been developed which are suitable for the layout of Very Large Scale Integrated (VLSI) circuits. Hierarchical decomposition is used to reduce the circuit function to a size that can be comprehended by the designer and is computationally feasible to layout. At each hierarchical level the problem consists of the placement of interconnected rectangular blocks of arbitrary size and shape such that the area occupied by the blocks and their interconnections is minimal. Constructive initial placement and iterative improvement algorithms are presented.