Logic Programming Research
Nested Parallel Call Optimization
New Mexico State University, Technical Report.
Author(s)
Gopal Gupta,
Enrico Pontelli
Abstract
We present
a novel optimization called Last Parallel Call
Optimization (LPCO) for parallel systems.
The last parallel call optimization can be regarded as a
parallel extension of last call optimization (which itself is a
generalization of the tail recursion optimization) found in sequential systems.
While the LPCO is fairly general, we use and-parallel
logic programming systems to illustrate it and to report its performance
on multiprocessor systems.
The last parallel call optimization leads to improved time and space performance
for a majority of
and-parallel programs.
We also present a generalization of the Last Parallel Call
Optimization called {\em Nested Parallel Call Optimization} (NPCO).
The NPCO is also illustrated and its performance reported in the
context of and-parallel logic programming systems.
The LPCO and NPCO
can be incorporated in a parallel system through relatively minor
modifications to the runtime machinery; its incorporation in
an existing and-parallel system is illustrated in this paper. A major advantage
of LPCO and NPCO is that parallel systems designed for exploiting
control parallelism can automatically exploit data parallelism efficiently.
The LPCO and NPCO
are motivated by two important principles of system optimization, namely,
the reduced nesting level principle and the memory reuse principle.
The whole paper
can be downloaded from our
server.
Logic Prog. Page Research Page Lab Home Page