µ3L: An HLL-RISC processor for parallel execution of FP-language programs

ABSTRACT

To eliminate the conceptual distance between the hardware instruction set and the user interface, some architects advocate High Level Language (HLL) machines. To obtain simple, fast and cheap machines, some architects advocate Reduced Instruction Set Computer (RISC) machines. This paper reconciles both views and presents an architecture which has both an HLL user interface and a RISC hardware. Each instance of this architecture is a module of an HLL multiprocessor system. Functional programming languages offer a bridge between mathematical models of computation and multiprocessor system environments. We choose the language AFPL (A Functional Programming Language) as the HLL user interface. AFPL's direct execution model, based on a tree structured internal representation, takes advantage of the parallelism inherent in programs by decomposing them on the fly into tasks which can be performed concurrently.

REFERENCES

• 1: U.O. Gagliardi, "Report of Workshop 4: Sofware Related Advances in Computer Hardware," Proceeding of a symposium on the high cost of software, Menlo Park Calif. STANFORD Research Institute, 1973.
• 2: Bashkow, A. Sasson, and A. Kronfeld, "System Design of a FORTRAN Machine," IEEE Transactions on Computers, Vol. EC-16, 1967, pp. 485-499.
• 3: T.R. Bashkow, D. Kroft, and A. Sasson, "Study of a Computer for Direct Execution of List Processing Language," Tech. report 103, Columbia University, January 1968, AFCRL-68-0063
• 4: Y. Chu and M. Abrams, "Programming Languages and Direct-Execution Computer Architecture," Computers, July 1981, pp. 22-32.
• 5: D.R. Ditzel, "Reflections on the High-Level Language Symbol Computer System," Computers, July 1981, pp. 55-66.
• 6: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 7: 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]
• 8: J. P. Sansonnet , M. Castan , C. Percebois, M3L: A list-directed architecture, Proceedings of the 7th annual symposium on Computer Architecture, p.105-112, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801915]
• 9: J.P. Sansonnet, "The 3L-Model: An Alternative to the Von Newmann Architecture," Tech. report LSI Report #77, U.P.S Toulouse, France, January 1980.
• 10: M. Castan, "Conception et Realisation d'une Machine Specialisee dans le Traitement des Formes Arborescentes", These 3eme cycle - U.P.S. Toulouse, France, September 1980
• 11: J. P. Sansonnet , M. Castan , C. Percebois , D. Botella , J. Perez, Direct execution of lisp on a list_directed architecture, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.132-139, March 01-03, 1982, Palo Alto, California, United States
• 12: D. Botella and J. Perez, "Validation du Modele 3L a Travers l'Interpretation de LISP: GLISP/1", Rapport de DEA-U.P.S. Toulouse, France, June 1980
• 13: R. S. Barton, "A System Based on Functional Programming," Aarhus Workshop on Software Engineering, Dept. of Computer Science, Aarhus University, Aarhus, Denmark, 1978, pp. 249-260.
• 14: M. Castan, "Rapport Final de Stage", Institut National de Recherche en Informatique et Automatique, France, November 1981.
• 15: C. Gram and E.I. Organick, "An Easy Functional Programming Language," Tech. report ID923, Danish Technical University, Lyngby, Dept. of Computer Science, September 1980.
• 16: C. Gram and E.I. Organick, "Characteristics of a Functional Programming Language," Tech. report UUCS-80-103, Univ. of Utah, Salt Lake City, July 1980.
• 17: C. Gram and E. I. Organick, "Semantics and Algebra of an Easy Functional Programming Language," Tech. report ID930, Technical University of Denmark, Lyngby, October 1980.
• 18: David A. Patterson , Carlo H. Sequin, RISC I: A Reduced Instruction Set VLSI Computer, Proceedings of the 8th annual symposium on Computer Architecture, p.443-457, May 12-14, 1981, Minneapolis, Minnesota, United States
• 19: J.P. Sansonnet, D. Botella, and J. Perez, "An experience of function in a list-directed architecture," EUROMICRO Journal, 1982.
• 20: A. Tanenbaum, Structured computer organization; (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 21: John C. Reynolds, G/EDANKEN—a simple typeless language based on the principle of completeness and the reference concept, Communications of the ACM, v.13 n.5, p.308-319, May 1970 [doi>10.1145/362349.362364]
• 22: J. Chailloux, "Le modele VLISP: Description, Implementation et Evaluation", These - Paris VI, France, April 1980
• 23: P. Greussay, "Contribution a la definition interpretative et a l'implementation des lambda-languages", These d'etat - Paris VI, 1977
• 24: C. Percebois, "Etude et Realisation d'un Environnement de Microprogrammation Specialisee dans le Traitement des Formes Arborescentes", These 3eme cycle - U.P.S. Toulouse, France, September 1981.
• 25: Guy Lewis Steele, Jr. , Gerald Jay Sussman, Design of a LISP-based microprocessor, Communications of the ACM, v.23 n.11, p.628-645, Nov. 1980 [doi>10.1145/359024.359031]
• 26: G.J. Sussman, J. Holloway, G.L. Steele Jr., and A. Bell, "Scheme-79, LISP on a Chip," Computers, July 1981, pp. 10-21.
• 27: Intel Corp., Introduction to the iAPX 432 Architecture, Santa Clara, CA, 1981, Order Form: 171821-001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

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

          Nouns: FP
      D.3.4 Processors

General Terms:
Design, Languages