Array optimization for VLSI synthesis

ABSTRACT

We present in this paper an algorithm that solves a general array optimization problem. The algorithm can be used for compacting Gate Matrix layouts, SLA's, Weinberger Arrays, and for multiple folding of PLA's. Our approach is based on the technique of simulated annealing. A major contribution of this paper is the formulation of the solution space which facilitates an effective search for an optimal solution. Experimental results are very encouraging.

REFERENCES

• 1: Srinivas Devadas , A. R. Newton, GENIE: a generalized array optimizer for VLSI synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.631-637, July 1986, Las Vegas, Nevada, United States
• 2: Giovanni De Micheli , Alberto Sangiovanni-Vincentelli, PLEASURE: a computer program for simple/multiple constrained/unconstrained folding of Programmable Logic Arrays, Proceedings of the 20th conference on Design automation, p.530-537, June 27-29, 1983, Miami Beach, Florida, United States
• 3: G.D. Hachtel, A. Newton, and A. Sangiovanni- Vincentelli, "An Algorithm for Optimal PLA Folding," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems,'" Vol. CAD-I, (,9sz), 62-76.
• 4: S. Kirkpa~rick, C. D. Gelatt Jr. and M. P. Veeehi, L'C)ptlmizatlon by Simulated Annealing," Science, Vol. 220, (1983), 671-680.
• 5: C. Sechen and A. Sangiovanni-Vincentelli, "The Timberwolf Placement and Routing Package," IEEE Journal o{ Solid-State Circuits, Vol. SC-20, No.2, (1985), 510-522.
• 6: D.F. Wong, H. W. Leong, and C. L. biu, "Multiple PLA Folding by The Method of Simulated Annealing," Proc. of th~ IEEE Custom integrated Circuits Conference, (1986), 351-355.
• 7: D. F. Wong , C. L. Liu, A new algorithm for floorplan design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.101-107, July 1986, Las Vegas, Nevada, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
      B.7.2 Design Aids
          Subjects: Layout

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