A methodology for granularity-based control of parallelism in logic programs (Q2365139)

Several papers have investigated parallel executions of logic programs by defining suitable conditions ensuring correctness, i.e. ensuring that the parallel execution produces the same results as the sequential one. The implicit assumption underlying this approach is that parallel execution allow to obtain a significant speed-up wrt the sequential one. However, in practice this is not always true, since process creation, process scheduling and other overheads appearing in parallel execution can induce a slow-down. This paper introduce a methodology which allows to estimate and to control the granularity of parallel processes, so that parallelism can be limited and the effect of the overheads previously mentioned can be controlled. The approach is based on existing work and consists in the use of complexity functions at compile time to transform the original programs in such a way that the transformed programs automatically controls granularity. This allows to estimate the overhead due to parallel execution and also to obtain several compile-time and run-time optimization techniques.