Decomposition of logic networks into silicon

ABSTRACT

This paper describes a module compiler for decomposing arbitrary functional units of any complexity into abstract cells for customized VLSI layouts. The compiler takes the description of a functional unit as input and builds a dependence graph representation. The graph is then partitioned and the nodes are packed into abstract cell output descriptions. The algorithm will tailor the design to a given area and aspect ratio. Routing is done automatically through the cells.

REFERENCES

• Breu77: M. A. Breuer, "Min-Cut Placement", Journal of Design Automation and Fault-Tolerant Computing, Vol. 1, No. 4, October 1977, pp. 343-362.
• FiMa82: 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
• GaBo84: D. D. Gajski, J. J. Bozek, "ARSENIC: Methodology and Implementation", Proceedings of tile International Conference on Computer-Aided Design, November 1984, pp. 116-118.
• GaKu83: D. Gajski, R. Kuhn, "New VLSI Tools," Computer Magazine, December 1983, pp. 11-14.
• GoSc73: A. J. Qoldstein, D. G. Schweikert, "A Proper Model for Testing the Planarity of Electrical Circuits", The Bell System Technical Journal, 52:1, pp. 135-142.
• KeLi70: B. W. Kernighan, S. Lia, '"An Efficient Heuristic Procedure for Partitioning Graphs", The Bell System Technical Journal, 49:2, pp. 291-307.
• KiMS84: J. H. Kim, J. McDermott, D. P. Siewiorek "Exploiting Domain Knowledge in iC Cell Layout", IEEE Design and Test, Vol. 1, No. 3, August 1984, pp. 52-64.
• Laut79: Ulrich Lauther, A min-cut placement algorithm for general cell assemblies based on a graph representation, Proceedings of the 16th Conference on Design automation, p.1-10, June 25-27, 1979, San Diego, CA, United States
• LuGa84: Chidchanok Lursinsap , Daniel Gajski, Cell compilation with constraints, Proceedings of the 21st conference on Design automation, p.103-108, June 25-27, 1984, Albuquerque, New Mexico, United States
• MaBC83: T. G. Matheson, M. R. Buric, C. Christensen, "Embedding Electrical and Geometric Constraints in Hierarchical Circuit-Layout Generators", Proceedings of the International Conference on Computer-Aided Design, September 1983, pp. 3-5.
• MeCo80: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• ScKe72: D. G. Schweikert , B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th workshop on Design automation, p.57-62, June 26-28, 1972 [doi>10.1145/800153.804930]
• Tarj74: R. Tarjan, "Finding Dominators in Directed Graphs", SIAM Journal of Computing, Vol. 3, No. 1, March 1974, pp. 62-89.
• Vuil83: J. E. Vuillemin, "A Combinatorial Limit To The Computing Power Of VLSI Circuits", IEEE Transaelion8 on Computers, Vol. C-32, No. 3, March 1983, pp. 294-300.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

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