LISP and Symbolic Computation, 5(4)327-342
Partial Evaluation in ParallelCharles Consel, Department of Computer Science, Yale University, P.O. Box 2158, New Haven, CT 06520, USA
Olivier Danvy, Department of Computing and Information Sciences, Kansas State University, Manhattan, KS 66506, USA
|
Abstract: Partially evaluating a procedural program amounts to
building a series of mutually-recursive specialized procedures. When a
procedure call in the source program gets specialized into a residual
call, the called procedure needs to be processed to occur in the
residual program. Because the order of procedure definitions in the
residual program is immaterial, it does not matter in which order
these two events--building the residual call and building the residual
procedure--are scheduled. Therefore, partial evaluation offers a basic
opportunity for an MIMD type of parallelism with shared global memory
where in essence, the mutually-recursive specialized procedures are
built in parallel as specialization points are met and the relation
binding source and residual procedures is globalized, to preserve its
uniqueness. We have translated a sequential partial evaluator written in T (a dialect of Scheme) into Mul-T (a parallel extension of T) by adding one semaphore with each specialization point and one future to construct the residual procedure in parallel with the current specialization. The resulting parallel partial evaluator has been observed to be faster than the sequential one in proportion to the size of the source program and to the number of specialized procedures in the residual program. Our sequential partial evaluator is self-applicable. Because the semaphores and the future are run-time operations, our parallel partial evaluator is still self-applicable. In principle it can be and in practice we have used it to generate parallel compilers, i.e., specializers dedicated to an interpreter and processing its static and dynamic semantics in parallel, non trivially. Again, parallelism in dedicated specializers is determined by the size of the source program and the number of specialized procedures in the residual program. Keywords: specialization of programs, self application, single threading, scheme, mul-T, automatic generation of parallel programs, from sequential interpreter to parallel compiler. |
[local copy]