Annotation of logic programs for independent AND-parallelism by partial evaluation

DOI10.1017/S1471068412000191MaRDI QIDQ4911136zbMATH OpenOpenAlexFDO

Authors Germán Vidal

Publication date 13 March 2013

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.1665

zbMATH Keywords

partial evaluationprogram analysisautomatic parallelization

Mathematics Subject Classification ID

Logic programming (68N17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Abstract: Traditional approaches to automatic AND-parallelization of logic programs rely on some static analysis to identify independent goals that can be safely and efficiently run in parallel in any possible execution. In this paper, we present a novel technique for generating annotations for independent AND-parallelism that is based on partial evaluation. Basically, we augment a simple partial evaluation procedure with (run-time) groundness and variable sharing information so that parallel conjunctions are added to the residual clauses when the conditions for independence are met. In contrast to previous approaches, our partial evaluator is able to transform the source program in order to expose more opportunities for parallelism. To the best of our knowledge, we present the first approach to a parallelizing partial evaluator.

Recommendations

• Annotation Algorithms for Unrestricted Independent And-Parallelism in Logic Programs
• Automatic compile-time parallelization of logic programs for restricted, goal level, independent and parallelism
• Static analysis of logic programs for independent and parallelism
• Independent and-parallelization of logic programs using static slicing
• Strict and nonstrict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions

Cites work

• A hybrid approach to conjunctive partial evaluation of logic programs
• Automatic compile-time parallelization of logic programs for restricted, goal level, independent and parallelism
• Conjunctive partial deduction: foundations, control, algorithms, and experiments
• Fast Offline Partial Evaluation of Large Logic Programs
• Non-strict independence-based program parallelization using sharing and freeness information
• Partial evaluation in logic programming
• Transformation by interpreter specialisation

Cited in

(7)

• A framework for computing finite SLD trees
• Independent and-parallelization of logic programs using static slicing
• Parallel Logic Programming: A Sequel
• Annotation Algorithms for Unrestricted Independent And-Parallelism in Logic Programs
• Non-strict independence-based program parallelization using sharing and freeness information
• Program specialization as a tool for solving word equations
• Abstract conjunctive partial deduction for the analysis and compilation of coroutines

This page was built for publication: Annotation of logic programs for independent AND-parallelism by partial evaluation

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