Optimization by simulated evolution with applications to standard cell placement

ABSTRACT

This paper presents a mathematical formulation of the Simulated Evolution algorithm, a novel optimization technique, followed by a thorough analysis of the associated Markovchain model. We show that the algorithm will reach a global minimum with probability one, and also introduce a novel hierarchical placement technique. Finally, we describe a Standard Cell placement program based on the new approach whose preliminary results are comparable to the best Simulated Annealing algorithms.

REFERENCES

• 1: R.-M. Kling , P. Banerjee, ESP: a new standard cell placement package using simulated evolution, Proceedings of the 24th ACM/IEEE conference on Design automation, p.60-66, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37897]
• 2: R.M. Kling and P. Banerjee, "ESP: Placement by Simulated Evolution," IEEE Trans. Computer-Aided Design, vol. 8, pp. 245-256, Mar. 1989.
• 3: Y-L. Lin, Y-C. Hsu, and F-S. Tsai, "SILK: A Simulated EvoIution Router," IEEE Trans. on Computer-Aided Design, pp. 1108-1114, October 1989.
• 4: Y. Saab , V. Rao, An evolution-based approach to partitioning ASIC systems, Proceedings of the 26th ACM/IEEE conference on Design automation, p.767-770, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74525]
• 5: S.B. Gelfand and S. K. Mitter, "Analysis of simulated annealing for optimization," in Proc. 24th Conf. on Decision and Control, Fort Lauderdale, FL., Dec. 1985.
• 6: D. Mitra, F. Romeo, and A. Sangiovarmi-Vinceltelli, "Convergence and finite-time behavior of simulated annealing," in Proc. 24th Conf. on Decision and Control, Fort Lauderdale, FL., Dee. 1985.
• 7: J. Lain, J. M. Delosme, and C. Sechen, "A New Simulated Annealing Schedule for Row-Based Placement," Proc. Im'l Workshop on Placement and Routing, May 1988.
• 8: S. Kirkpatrick, C. D. Gelatt, and M. P. Veechi, "Optimization by Simulated Annealing," Science, vol. 220, pp. 671-680, May 1983.
• 9: C. Sechen and A. Sangiovanni-Vincentelli, "The TimberWolf Placement and Routing Package," Proc. Custom Integrated Circuits Conf., pp. 522-527, May 1984.
• 10: C. Sechen and K. W. Lee, "An Improved Simulated Annealing Algorithm for Row-based Placement," Proc. Int. Conf. Computer-Aided Design, pp. 478-481, Nov. 1987.
• 11: L.K. Grover, "A New Simulated Annealing Algorithm for Standard Cell Placement," Proc. Int. Conf. on Computer-Aided Design, pp. 378-380, Nov. 1986.
• 12: J.P. Cohoon and W. D. Paris, "Genetic Placement," IEEE Trans. Computer-Aided Design, pp. 956-964, Nov. 1987.
• 13: Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, Proud: a fast sea-of-gates placement algorithm, Proceedings of the 25th ACM/IEEE conference on Design automation, p.318-323, June 12-15, 1988, Atlantic City, New Jersey, United States
• 14: J. L. Snell, Introduction to Probability Theory with Computing. New Jersey: Prentice-Hall, 1975.
• 15: F. Ferschl, Markovketten. Berlin: Springer-Verlag, 1970.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms