Compilation of Functional Languages for Parallel Execution

315.391, SS 1997 (Start: March 13)
Thu 16:30-18:00, T711
Wolfgang Schreiner

This course investigates the formal theory for the compilation of functional programming languages for execution on parallel computers. We will focus on two main branches of execution models of non-strict functional languages:

• demand-driven execution (lazy evaluation, graph reduction),
• data-driven execution (eager evaluation, dataflow).

Furthermore, we will deal with run-time environments of parallel functional languages focusing on methods for parallel garbage collection.

Contents

Background

• Strict compilers.
• Lazy compilers (force-and-delay, graph reduction, abstract machines).
• Lenient compilers (dataflow, multithreaded).

Compilation of Lazy Languages for Parallel Graph Reduction

• Abstract interpretation.
• Evaluation transformers.
• Generating code for parallel graph reduction.

Compilation of Lenient Languages for Multithreaded Execution

• Dataflow graphs.
• Partitioning a function into threads.
• Code generation.

Parallel Garbage Collection

• Reference counting schemes.
• Mark and sweep schemes.
• Copy schemes.

Literature

D I Bevan

Distributed Garbage Collection Using Reference Counting, Parallel Languages and Architectures Europe, Eindhoven, The Netherlands, June 1987, volumes 258/259 of Lecture Notes in Computer Science, W. J. Bakker et al. (eds), Springer, Berlin.

Geoffrey Burn

Lazy Functional Languages: Abstract Interpretation and Compilation, Research Monographs in Parallel and Distributed Computing, Pitman, London, 1991.

Geoffrey Burn

Evaluation Transformers -- A Model for the Parallel Evaluation of Functional Languages (Extended Abstract), Gilles Kahn (ed.), Functional Programming and Computer Architecture, volume 274 of Lecture Notes in Computer Science, pp. 446-470, Portland, Oregon, September 14-16, 1987, Springer Berlin.

Geoffrey Burn

Implementing the Evaluation Transformer Model of Reduction on Parallel Machines, Journal of Functional Programming, 1(2), April 1991.

Chris Clack et al.

Strictness Analysis -- A Practical Approach, Jean-Pierre Jouannaud (ed.), Functional Language and Computer Architecture, volume 201 of Lecture Notes in Computer Science, pages 35-49, Nancy, France, September 16-19, 1985, Springer, Berlin.

D.E. Culler et al.

TAM - A Compiler Controlled Threaded Abstract Machine, Journal of Parallel and Distributed Computing, July 1993, http://www.cs.ucsb.edu/ schauser/papers/93-jpdc-tr.ps.

David Plainfosse and Marc Shapiro

A Survey of Distributed Garbage Collection Techniques, International Workshop on Memory Management, Kinross, Scotland (UK), September 1995, http://www-sor.inria.fr/SOR/docs/SDGC_iwmm95.html.

K.E. Schauser

Compiling Lenient Languages for Parallel Asynchronous Execution, PhD thesis, Computer Science Division, University of California, Berkeley, May 1994, http://www.cs.ucsb.edu/ schauser/papers/94-thesis.ps.

K.E. Schauser et al.

Separation Constraint Partitioning - A New Algorithm for Partitioning Non-strict Programs into Sequential Threads, Proc. Principles of Programming Languages (POPL'95), San Francisco, CA, January 1995, http://www.cs.ucsb.edu/ schauser/papers/95-popl.ps.

Kenneth Traub

Implementation of Non-Strict Functional Programming Languages, Research Monographs in Parallel and Distributed Computing, Pitman, London, 1991.