Optimal folding of standard and custom cells

ABSTRACT

We study the problem of folding an ordered list of standard and custom cells into rows of a chip so as to minimize either the routing area or the total chip area. Nine versions of the folding problem are formulated and fast polynomial time algorithms are obtained for each. Two of our formulations correspond to problems formulated in Paik and Sahni [1993] for the folding of a stack of bit-slice components. Our algorithms for these two formulations are asymptotically superior to those of Paik and Sahni [1993].

REFERENCES

• 1: Glenn W. Cox , B. D. Carroll, The Standard Transistor Array (star) (Part II automatic cell placement techniques), Proceedings of the 17th conference on Design automation, p.451-457, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804569]
• 2: FREDERICKSON, a.N. 1992. Optimal parametric search algorithms in trees I: Tree partitioning. Purdue Univ., Tech. Rep. CSD-TR-1029.
• 3: Greg N. Frederickson, Optimal algorithms for tree partitioning, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.168-177, January 28-30, 1991, San Francisco, California, United States
• 4: FREDERICKSON, a. N. AND JOHNSON, D. B. 1983. Finding kth paths and p-centers by generating and searching good data structures. J. Algorithms 4, 61-80.
• 5: FREDERICKSON, a. N. AND JOHNSON, D.B.1984. Generalized selection and ranking: sorted matrices. SIAM J. Comput. 13, 14-30.
• 6: W. R. Heller , W. F. Michail , W. E. Donath, Prediction of wiring space requirements for LSI, Proceedings of the 14th conference on Design automation, p.32-42, January 1977
• 7: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• 8: Ellis Horowitz , Sartaj Sahni, Fundamentals of data structures in PASCAL, Computer Science Press, Inc., New York, NY, 1984
• 9: Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
• 10: PAIK, D. AND SAHNI, S. 1993. Optimal folding of bit sliced stacks. IEEE Trans. CAD Integrated Circuits Syst. 12, 11 (Nov.), 1679-1685.
• 11: Eugene Shragowitz , Jong Lee , Sartaj Sahni, Place-router for “Sea-of Gates” design style, Progress in computer-aided VLSI design: techniques, Ablex Publishing Corp., Norwood, NJ, 1990
• 12: E. Shragowitz , L. Lin , S. Sahi, Models and algorithms for structured layout, Computer-Aided Design, v.20 n.5, p.263-271, June 1988 [doi>10.1016/0010-4485(88)90072-3]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

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: Routing and layout

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

Keywords:
custom cell folding, layout area, standard cell folding