Hierarchical design based on a calculus of nets

ABSTRACT

We present an algebraic approach to hierarchical design of integrated circuits. This approach is based on a “calculus of nets” which includes topological as well as behavioural aspects of integrated circuits. We have developed a hierarchical design system called CADIC which is build around this calculus in much the same way as e.g. Algol is build around numerics. An example for the design of a family of fast adders will demonstrate the power of this calculus. Finally we will give a summary outline on the structure of procedures which automatically transform the design into lower design levels.

REFERENCES

• 1: L.Cardelli: "An Algebraic Approach to Hardware Description and Verification~ PH.D. Thesis, Edinburgh 1082.
• 2: E.Clarke, Y.Feng: "ESCHER- A geometrical Layout System for Recursively Defined Circuits" CMU-CS-85-150, Department of Computer Science, Carnegie-Mellon University, Pitsburgh 1985.
• 3: E.H~rbst, M.Nett, H.Schw~rtzel: "VENUS - Entwurf yon VLSI'Schaltungen" Springer-Verlag Berlin Heidelberg New-York Tokyo 1986.
• 4: G.Hotz: "Eine Algebraisierung des Syntheseproblems fiir Schaltkreise" EIK 1, 1965, pp.185-205,209-231.
• 5: G.Hotz, B.Becker, R.Kolla, P.Molitor: "Ein logisch-topologischer Kalkiil zur Konstruktion yon integrierten Schaltkreisen" Informatik: Forschung mad Entwicklung, Heft 1 und 2, Springer Verlag 1986.
• 6: C.D.Kloos: "Towards a Formalization of Digital Circuit Design" TUM-I8604, February 1986, Technische Universitiit M~inchen.
• 7: R.Kolla: "Spezifikation und Expansion logisch-topotogischer Netze" Dissertation, Sa~rbriicken 1086/87.
• 8: R.Kolla "Verification of logic-topological Nets" will appear as technical report, SFB124, Saarbriicken 1987.
• 9: C.E.Leiserson, R.Y.Pinter: "Optimal placement for fiver routing" SAM J. Comput. 12, pp.447-462, 1983.
• 10: T.Lengauer, K.Mehlhora: "The HILL-System: A Design Environment for the Hierarchical Specification, Compaction and Simulation of Integrated Circuit Layouts" MIT VLSI Conference 1984, pp.139-149, Artech House.
• 11: P.Molitor: "Layer Assignment by Simulated Annealing" Microprocessing and Microprogramming 16 (1985), pp.345-350, North-Holland.
• 12: P.Molitor: "Uber die Bikategorie der logisch- topologischen Netze und i hre Semantik" Dissertation, Saarbriicken 1986.
• 13: P. Molitor, On the contact-minimization problem, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.420-431, February 1987, Passau, Germany
• 14: P.Molitor: "Free Net Algebras in VLSI-Theory"" in preparation.
• 15: P.Molitor, R.Kolla: "A note on hierarchical layer-assignment" Tit 8/86, SFB124, Saarbriicken 1986.
• 16: R.Y.Pinter: "Optimal layer assignment for interconnect" ICCC 1982, pp.398-401.
• 17: M.Sheeran: "gFP- An algebraic VLSI design language" PH.D. Thesis, University of Oxford, England 1984.
• 18: J. Sklansky "Conditional-sum addition logic" IRE-EC 9, 226-231 (1960)

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

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

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

General Terms:
Design, Theory