muFP, a language for VLSI design

ABSTRACT

In this paper, we present a VLSI design language &mgr;FP, which is a variant of Backus' FP [Backus 78, 81]. &mgr;FP differs from conventional VLSI design languages in that it can describe both the semantics (or behaviour) of a circuit and its layout (or floorplan) [Sheeran 83]. We chose to base our design language on FP for several reasons. Functional programs are easier to write and to reason about than imperative ones. We hope to bring some of these benefits to IC design. FP, in particular, is designed to allow the programmer to reason about his or her programs by manipulating the programs themselves. Likewise, in &mgr;FP, programs (or circuit descriptions) are just expressions “made” from a small number of primitive functions and combining forms (functionals that map functions into functions). These functions and combining forms (CFs) were chosen because they have nice algebraic properties. Thus, circuit descriptions are concise and can be easily manipulated using the algebraic laws of the language. Also, each CF has a simple geometric interpretation, so that every &mgr;FP expression has an associated floorplan. This interpretation exists because &mgr;FP expressions represent functions rather than objects, allowing us to associate a function with each section of the floorplan. Most VLSI design languages are designed either for layout description or for behavioural specification. &mgr;FP, with its dual interpretation, allows the designer to consider the effect on the final layout of a particular design decision or to manipulate the layout while keeping the semantics constant. In the following sections, we show how &mgr;FP is constructed from FP by the addition of a single combining form &mgr;, which encapsulates a very simple notion of “state”.

REFERENCES

• 1: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 2: J. Backus: "The Algebra of Functional Programs: Function Level Reasoning, Linear Equations, and Extended Definitions" Proc. Symposium on Functional Languages and Computer Architecture, Gothenberg, June 1981.
• 3: S. Finn: "LVIS - A VLSI Transformation System" M. Sc. Dissertation, Programming Research Group, University of Oxford, Sept. 1983.
• 4: Peter Henderson, Functional geometry, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.179-187, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802148]
• 5: P. Henderson, G. A. Jones, S. B. Jones: "The LispKit Manual, Volume 1" Tech. Monograph PRG-32(1), Programming Research Group, University of Oxford, June 1983.
• 6: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 7: M. Sheeran: "Functional Geometry and Integrated Circuit Layout" M. Sc. Dissertation, Programming Research Group, University of Oxford, Sept. 1981.
• 8: M. Sheeran: " &mgr;FP, an Algebraic VLSI Design Language" D.Phil. Thesis, Programming Research Group, University of Oxford, 1983.
• 9: J. Williams: "Notes on the FP Style of Functional Programming" in "Functional Programming and its Applications", Cambridge University Press, 1981.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: muFP

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FP

General Terms:
Design, Languages