Stochastic evolution: a fast effective heuristic for some generic layout problems

ABSTRACT

There are two canonical optimization problems, namely, NETWORK BISECTIONING (NB) and TRAVELING SALESMAN (TS), that emerge from the physical design and layout of integrated circuits. In this paper, we use an analogy between iterative techniques for combinatorial optimization and the evolution of biological species to obtain the Stochastic Evolution (SE) heuristic for solving a wide range of combinatorial optimization problems. We show that SE can be specifically tailored to solve both NB and TS. Experimental results for the NB and TS problems show that the SE algorithm produces better quality solutions and is faster than the Simulated Annealing algorithm in all instances considered.

REFERENCES

• 1: M. Breuer, "Min-Cut Placement," J. Design Automation and Fault-Tolerant Computing, vol. 1, no. 4, pp. 343-362, Oct. 1977.
• 2: A. Dunlop and B. Kemigban, "A Procedure for Placement of Standard-Cell VLSI Circuits," IEEE Trans. Computer-Aided Design, vol. CAD-4, no. 1, pp. 92-98, Jan. 1985.
• 3: Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: B. Kemighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Technical Journal, vol. 49, pp. 291- 307, Feb. 1970,
• 6: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 7: S. Lin and B. Kernighan, "An effective heuristic algorithm for the traveling salesman problem," Operation Research, vol. 21, pp. 498- 516, 1973.
• 8: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 9: j. Lam and J. Delosme, "Simulated Annealing : A Fast Heuristic for Some Generic Layout Problems," Proc. ICCAD Conference, pp. 510- 513, 1988.
• 10: Jimmy Lam , Jean-Marc Delosme, Performance of a new annealing schedule, Proceedings of the 25th ACM/IEEE conference on Design automation, p.306-311, June 12-15, 1988, Atlantic City, New Jersey, United States
• 11: R. Kling and P. Banerjee, "ESP: Placement by simulated evolution," IEEE Trans. Computer- Aided Design, vol. 8, no. 3, pp. 245-256, Mar. 1989.
• 12: B. Dunham, D. Fridshal, R. Fridshal, and J. North, "Design by Natural Selection," Synthese, D. Reidel Publication Company, Dordrecht-Holland, pp. 254-259, 1963.
• 13: J. Cohoon and W. Paris, "Genetic Placement," Proc. IEEE International Conference On Computer-Aided Design, pp. 422-425, 1986.
• 14: Y. Saab and V. Rao, "Optimization by Stochastic Evolution," (submitted to) 1EEE Trans. Computer-Aided Design.
• 15: 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]
• 16: Surendra Nahar , Sartaj Sahni , Eugene Shragowitz, Simulated annealing and combinatorial optimization, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.293-299, July 1986, Las Vegas, Nevada, United States

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design