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

DOI10.1017/S1471068412000191zbMATH Open1260.68068arXiv1210.1665OpenAlexW3106424691MaRDI QIDQ4911136FDOQ4911136

Authors: Germán Vidal 

Publication date: 13 March 2013

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

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.

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

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

zbMATH Keywords

partial evaluationprogram analysisautomatic parallelization

Mathematics Subject Classification ID

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

Cites Work

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

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)