A simple and efficient implmentation approach for single assignment languages

ABSTRACT

Functional and single assignment languages have semantically pure features that do not permit side effects. This lack of side effects makes detection of parallelism in programs much easier. However, the same property poses a challenge in implementing these languages efficiently. A preliminary implementation of a compiler for the single assignment language, SISAL, is described. The compiler uses reference counts for memory management and copy avoidance. Performance results on a wide range of benchmark programs show that SISAL programs compiled by our implementation run 2-3 times slower on average than the same programs written in C, Pascal, and Fortran, and orders of magnitude faster than other implementations of single assignment languages. Extensions of these techniques for multiprocessor implementations are proposed.

REFERENCES

• 1: W. B. Acherman , J. B. Dennis , William B Ackerman, VAL- ORIENTED ALGORITHMIC LANGUAGE, PRELIMINARY REFERENCE MANUAL, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 2: Arvind et al. An A.wnchronous Programming Language and Computing Machine. Technical Report 114A, UC Irvine, December 1978.
• 3: Arvind and R. E. Thomas. }-Structures: An Ej~cient Data Type for Functional Languages. Tedmical Report MIT/LCS/TM-210, MIT, i981.
• 4: 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]
• 5: James R. Celoni a.nd John L. Hennessy. SAL : A Single A~aignment Language for Parallel Algorithms. Technical Report CLaSSic-83-01, Stanford University, September 1983.
• 6: Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
• 7: Ron Cytron and Jealn:te Ferran{e. What~ in a Name? -or- The Value of Renaming for Parallelism Detectior, and Storage Allocation. Techlfical l:leport RC 12785 (#55984), mM T. J. Watson Research Center, Jmuary 1987.
• 8: A. L. Davis and R. M. Keller. Data flow progrant graphs. IEEE Computer, 15(2), February 1982.
• 9: John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
• 10: K. Gopinath, Copy elimination in single assignment languages, Stanford University, Stanford, CA, 1988
• 11: J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
• 12: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• 13: Paul Hudak , Adrienne Bloss, The aggregate update problem in functional programming systems, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.300-314, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318660]
• 14: on Parallel MIMD computation: HEP supercomputer and its applications, June 1985
• 15: J. McGraw et a l. SISAL: Streams and Iteration.q in. a Single A,.~ignment Language~ Language 12eference Manual, Version 1.~. Technical Report M-146, LLNL, Ma.rch 1985.
• 16: Rodney R. Oldehoeft , David C. Cann, Applicative Parallelism on a Shared-Memory Multiprocessor, IEEE Software, v.5 n.1, p.62-70, January 1988 [doi>10.1109/52.1995]
• 17: Constantine Demetrios Polychronopoulos, On program restructuring, scheduling, and communication for parallel processor systems, 1986
• 18: Vivek Sa.rkar. Pariitioning and Scheduling Para. Ilel Programs for Ezecution on M'ultiproce.qsor~. PhD thesis, Stanford University, April 1987. (Technical Report CSL-TR-87-328).
• 19: S. t(. Skedzielewski and J. Glauert. IF1 - An Intermediate Form for Applicative Lang~age.~, VeT, ion 1.0. Technical Report M-170, LLNL, July 1985.
• 20: S. K. Skedzielewski , R. K. Yates , R. R. Oldehoeft, DI: an interactive debugging interpreter for applicative languages, Papers of the Symposium on Interpreters and interpretive techniques, p.102-112, June 24-26, 1987, St. Paul, Minnesota, United States
• 21: M. L. Welcolne a.nd S. K. Skedzielewski. Data. flow editor, Functional Programming Languages and Computer Architecture, $pringer-Vcrlag, 1985.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Design, Languages, Performance