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.