Adventures in Parallel Logic Programming

Enrico Pontelli
Laboratory for Logic, Databases, and Advanced Programming
New Mexico State University

Still under construction...

Abstract:

This document contains an overview of the current state-of-the-art in the implementation of Logic Programming Languages, with particular focus on exploitation of parallelism.

The presentation is divided in two parts. The first part gives an overview of the most relevant implementation techniques currently used in parallel logic programming, along with a brief description of the most effective sequential and parallel systems available. The second part deals with the issue of efficiency of the implementation models: the major sources of inefficiency in the current systems are identified and possible solutions to improve them are considered.

Keywords: Logic Programming, Parallelism, Optimizations, Prolog

• Contents
• Introduction
  • The Parallel Wave
  • Paradigms for Parallel Processing
    • Explicit Parallelism:
    • Implicit Parallelism:
    • Ideal System:
  • Parallel Logic Programming
    • Logic Programming and Prolog
    • Parallelism in Logic Programming
    • Limits and Perspectives
• Parallel Logic Programming
  • Sequential Implementation of Logic Programming
    • Beating the Interpretation Blues
      • Hardware Solution:
      • Native Code Compilation:
    • Other Intermediate Languages
  • Classification of Parallelism
  • An Example
  • Single Parallelism Systems
    • Or-parallelism
      • Independent Or-Parallelism:
      • Restricted Or-Parallelism:
      • Dependent Or-Parallelism:
    • And-parallelism
      • Independent And-parallelism
      • Restricted And-parallelism:
      • Dependent And-parallelism:
  • Multiple Parallel Systems
    • And- Under Or-parallelism
    • Problems in Combining And- and Or-Parallelism
    • Existing Approaches to And/Or-Parallelism
    • The Ideal System
  • Parallelism vs. Efficiency
• Sequential Efficiency
  • Compile-time Analysis
  • New Models
• Parallelism Efficiency
  • Overheads in Or-Parallelism
    • Stack Copying:
    • Binding Arrays:
  • Overheads in And-Parallelism
  • Overheads in And/Or-Parallelism
  • Memory Management
    • Memory Management in And-Parallelism
    • Memory Management in Or-parallelism
    • Memory Management in And/Or-Parallel Systems
  • Control Management
    • Scheduling
    • Order-sensitive Executions
  • Compile Time Analysis
    • Compile-time Analysis for Parallelism
      • Or-parallelism:
      • And-parallelism:
      • And/Or-parallelism:
    • Granularity Control
• Further Issues
• Conclusion
• Acknowledgements
• References
• About this document ...