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

DOI10.1006/JSCO.1996.0038MaRDI QIDQ2365139zbMATH OpenOpenAlexFDO

Authors P. Lopez, Manuel Hermenegildo, Saumya K. Debray

Publication date 22 October 1997

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL http://oa.upm.es/13392/

zbMATH Keywords

overhead controlParallel executionprogram transformation

Mathematics Subject Classification ID

Logic programming (68N17)

Review text

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.

Recommendations

• Automatic compile-time parallelization of logic programs for restricted, goal level, independent and parallelism
• A cost model for the AND-parallel execution of logic programs
• scientific article; zbMATH DE number 1862076
• Strict and nonstrict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions
• scientific article; zbMATH DE number 1420803

Cited in

(12)

• Non-strict independence-based program parallelization using sharing and freeness information
• PAN: A portable, parallel Prolog: Its design, realisation and performance.
• Minimizing the overheads of dependent AND-parallelism
• Lazy tree splitting
• scientific article; zbMATH DE number 516999 (Why is no real title available?)
• Parallel execution of logic programs by load sharing
• scientific article; zbMATH DE number 1760138 (Why is no real title available?)
• scientific article; zbMATH DE number 2086784 (Why is no real title available?)
• scientific article; zbMATH DE number 1420803 (Why is no real title available?)
• Oracle-guided scheduling for controlling granularity in implicitly parallel languages
• A High-Level Implementation of Non-deterministic, Unrestricted, Independent And-Parallelism
• Parallel Logic Programming: A Sequel

This page was built for publication: A methodology for granularity-based control of parallelism in logic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2365139)