Automatic Parallelization of Lazy Functional Programs

G. Hogen, A. Kindler, R. Loogen

	   We present a parallelizing compiler	for lazy functional
	   programs that uses strictness analysis to detect the
	   implicit parallelism within programs and generates an
	   intermediate functional program, where a new syntactic
	   construct _letpar_, which is semantically equivalent to the
	   well-known _let_-construct, is used to indicate subexpressions
	   for which a parallel execution is allowed. In order to avoid
	   that the communication overhead outweighs the benefits of the
	   parallel execution, the parallelizing compiler has to use some
	   heuristics to estimate the complexity of expressions. Only
	   for sufficiently complex expressions, a parallelization
	   will be worthwhile. Using the distributed implementation
	   of parallelized functional programs described in [Loogen et
	   al.~89], we investigated the impact of various parallelization
	   strategies on the runtimes and speedups. The strategy,
	   which only allows the parallel execution of non-predefined
	   function calls in strict positions, shows the best runtimes
	   and reasonable speedup results.