An analytical algorithm for placement of arbitrarily sized rectangular blocks

ABSTRACT

This paper presents a novel mathematical formulation to the placement of arbitrarily sized rectangles that simultaneously account for the topological and geometrical characteristics of the placement problem. Special attention is paid to maintain the continuity of the formulation. Two examples are given to demonstrate the performance of the algorithm. Identical placement is obtained from two different initial placements of an example which has 8 movable components and 29 signal nets. For a practical example with 15 movable blocks and 142 signal nets, a final placement which is manual solution comparable is obtained using random initial positions.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  J. Computer Applications

General Terms:
Algorithms, Design, Performance, Theory