Newsgroups: comp.parallel
From: lindgren@sics.se (Thomas Lindgren)
Subject: Re: Recursion removal and parallel code
Organization: Swedish Institute of Computer Science, Kista
Date: 7 Feb 1994 12:58:59 -0500

In the context of Prolog, we are working on a system that generates
parallel code from structurally recursive predicates/procedures. 

The method is described
in H{\aa}kan Millroth's thesis [1,2,3], while compilation issues and
implementation of the runtime system / abstract machine are described 
in mine and Johan Bevemyr's licentiate theses and related papers [4,5,6,7].

The result is an SPMD-style symbolic computation where each 'loop body'
process consists of a sequence of procedure calls. The compiler emits
synchronization and locking instructions when compiling the
parallel procedures and those called by them. This is a bit like
the 'random synchronization' method described by Wolfe [8] but
works with pointer-based datastructures rather than array elements.
The compiler performs a static analysis to determine which data structures
are shared between processes and what data structure accesses must
be sequentialized to preserve sequential semantics.
Speedups compared to sequential Prolog implementations have been good.

Harrison's PARCEL system was described in Lisp & Symbolic Computation
vol 2, no. 3/4 and uses a related method to parallelize recursive
Scheme programs. Larus and Hilfinger described a Lisp 
compiler, Curare, that also optimizes the parallel execution of 
recursive procedures. Papers appeared in PLDI'88, PPEALS'88 and 
also in Lisp & Symbolic Computation (I don't have the precise reference
to that one).

		Regards,
			Thomas
----------------------------------------------------------------------
Technical reports are found as

	ftp.csd.uu.se:pub/papers/reports/* 

while licentiate theses are found as

	ftp.csd.uu.se:pub/papers/licentiate-theses/* 

Filenames ending with .Z must be uncompress'ed, while filenames ending
with .gz must be gunzip'ed.

[1] H. Millroth, Reforming compilation of logic programs,
	Uppsala theses in computer science 10, Uppsala 1990.

[2] H. Millroth, Reforming compilation of logic programs,
	in Proc. ILPS'91. Available as tech-report-67.ps.Z

[3] H. Millroth, Reforming compilation for nonlinear recursion,
	in Proc. LPAR'92. Available as tech-report-70.ps.Z

[4] J. Bevemyr, T. Lindgren, H. Millroth, Exploiting recursion-parallelism
	in Prolog, in Proc. PARLE'93. Available as tech-report-75.{ps,dvi}.Z

[5] J. Bevemyr, T. Lindgren, H. Millroth, Reform Prolog: the language
	and its implementation, in Proc. ICLP'93. Available as
	tech-report-76.{ps,dvi}.Z

[6] J. Bevemyr, A recursion parallel Prolog engine, Uppsala theses in
	computer science, 16/93. Available as bevemyr.ps.Z

[7] T. Lindgren, The compilation and execution of recursion-parallel
	Prolog on shared-memory multiprocessors, Uppsala theses in
	computer science, 18/93. Available as lindgren.ps.gz

[8] M. Wolfe, Optimizing supercompilers for supercomputers, MIT Press, 1989.

--
Thomas Lindgren, Uppsala University, thomasl@csd.uu.se, lindgren@sics.se