Some experimental results on placement techniques

ABSTRACT

Seven placement algorithms - one constructive-initial placement algorithm and six iterative-improvement algorithms - were programmed and run on six problems ranging in size from 60 to 1300 modules. These problems included placing IC packs on a card, cards on a board and circuits on an LSI chip. It was found that the new force-directed pairwise relaxation algorithm was the best algorithm for the larger problems and was competitive with the other algorithms for the smaller problems. Other questions relating to placement strategies (such as, what are the advantages of constructive - initial start vs. random start and what is the best transformation of the placement problem to an associated quadratic assignment problem) are also answered.

REFERENCES

• 1: W. E. Donath, "Placement and Average Interconnection Length of Computer Logic", Submitted to IEEE Trans. on Comp.
• 2: W. E. Donath and A. J. Hoffman, "Algorithms for Partitioning of Graphsand Computer Logic Based on Eigenvectors of Connection Matrices", IBM Tech. Discl. Bull., Vol. 15, No. 3 (August 1972) pp. 938-944.
• 3: M. Hanan and J. M. Kurtzberg, "Placement Techniques", Chap. 5 in Design Automation of Digital Systems: Theory and Techniques, Vol. 1 (Ed. M. A. Breuer) Prentice-Hall, N.J. (1972) pp. 213-282.
• 4: M. Hanan and J. M. Kurtzberg, "A Review of the Placement and Quadratic Assignment Problems", SIAM Rev. Vol. 14, No. 2 (April 1972) pp. 324-342.
• 5: M. Hanan, J. M. Kurtzberg and F. Gracer, "A Comparison of Force-Vector Placement Techniques", in preparation.
• 6: G. Hsi, private communication.
• 7: U. Kodres, "Partitioning and Card Selection", Chap. 4 in Design Automation of Digital Systems: Theory and Techniques, Vol. 1 (Ed. M. A. Breuer) Prentice-Hall, N.J. (1972) pp. 173-212.
• 8: J. M. Kurtzberg, "Algorithms for Backplane Formation", in Microelectronics in Large Systems, Spartan Books (1965) pp. 51-76.
• 9: H. Nakahara, private communication.
• 10: A. M. Patel, "A Partitioning-Interchange Algorithm for Positioning Logic Elements on Electronic Chips", Ph.D. Theses, The State Univ. of N.Y. at Buffalo, (May 1971).
• 11: R. L. Russo, P. H. Oden and P. K. Wolff, Sr., "An Algorithm for the Partitioning and Mapping of Computer Logic Blocks to Modules", IEEE Trans. on Comp., Vol. C-20, No. 12 (Dec. 1971) pp. 1455-1462.
• 12: R. A. Rutman, "An Algorithm for Placement of Interconnected Elements Based on Minimum Wire Length", Proc. SJCC (1964) pp. 477-491.
• 13: D. G. Schweikert , B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th workshop on Design automation, p.57-62, June 26-28, 1972 [doi>10.1145/800153.804930]
• 14: L. Steinberg, "The Backboard Wiring Problem: A Placement Algorithm", SIAM Rev., Vol. 3, No. 1 (Jan. 1961), pp. 37-50.
• 15: James Edward Stevens, Jr., Fast heuristic techniques for placing and wiring printed circuit boards, 1972

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design