A Methodology for Granularity
Based Control of Parallelism in Logic Programs
Pedro López-García Manuel
Hermenegildo Saumya Debray
Abstract
Several types of parallelism can be exploited in logic
programs while preserving correctness and efficiency, i.e.\ ensuring
that the parallel execution obtains the same results as the sequential
one and the amount of work performed is not greater. However, such
results do not take into account a number of overheads which appear in
practice, such as process creation and scheduling, which can induce a
slow-down, or, at least, limit speedup, if they are not controlled in
some way. This paper describes a methodology whereby the granularity
of parallel tasks, i.e.\ the work available under them, is efficiently
estimated and used to limit parallelism so that the effect of such
overheads is controlled. The run-time overhead associated with the
approach is usually quite small, since as much work is done at compile
time as possible. Also, a number of run-time optimizations are
proposed. Moreover, a static analysis of the overhead associated with
the granularity control process is performed in order to decide its
convenience. The performance improvements resulting from the
incorporation of grain size control are shown to be quite good,
specially for systems with medium to large parallel execution
overheads.