Near-optimal placement using a quadratic objective function

ABSTRACT

Placement algorithms for IC layout which are optimal are known to be NP-complete 5. As a result, heuristics such as pairwise-interchange techniques must be employed to generate satisfactory placements. Unfortunately, with these algorithms, there is generally no way of knowing just how far away the result is from optimum. With the quadratic metric used in this study, however, a useful absolute lower bound can be calculated for the score. Experiments show that with this metric, at least for homogenous interchangeable devices confined to a square grid, pairwise interchange suffices to move the placement very close to the global optimum over a range of 100 to 1600 devices; in particular, asymptotic approach to optimality is observed with increasing size. In addition, a theoretical model is developed which explains the observed deviation from optimality.

REFERENCES

• 1: John P. Blanks, Initial placement of gate arrays using least-squares methods, Proceedings of the 21st conference on Design automation, p.670-671, June 25-27, 1984, Albuquerque, New Mexico, United States
• 2: Breuer, Melvin A., ed.; Design Automation of Digital System vol. 1 Theory and Techniques, Englewood Cliffs, New Jersey. Prentice-Hall, Inc., 1972.
• 3: Cheng, Chung-Kuan and Kuh, Ernest S., "Module Placement Based on Resistive Network Optimization," IEEE Transactions on Computer-Aided Design, No. 3, July, 1984.
• 4: Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
• 5: W. E. Donath, Complexity theory and design automation, Proceedings of the 17th conference on Design automation, p.412-419, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804563]
• 6: Faddeev, D.K. and Faddeeva, V.N.; Computational Methods of Linear Algebra, W.H. Freeman and Company, San Francisco and London, 1963.
• 7: Kunio Fukunaga , Shoichiro Yamada , Harold S. Stone , Tamotsu Kasai, Placement of circuit modules using a graph space approach, Proceedings of the 20th conference on Design automation, p.465-471, June 27-29, 1983, Miami Beach, Florida, United States
• 8: Hanan, Maurice and Kurtzberg, Jerome M. ; "A Review of the Placement and Quadratic Assignment Problems", Siam Review, April 1972, Vol. 14, No. 2, pp. 324-342.
• 9: Hung, M. and Rom, W.O.; "Solving the Assignment Problem by Relaxation, "Operations Research, Vol. 28, No. 4, (1980)
• 10: Karger, P.G. and Malek, M., "Formulation of Component Placement as a Constrained Optimization Problem", Proceedings IEEE Intl. Conf on Comp. Desk, Oct. 1984, pp. 814-819.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications

General Terms:
Algorithms, Design, Measurement, Performance, Theory