An investigation in parallel execution of answer set programs on distributed memory platforms: Task sharing and dynamic scheduling

Answer Set Programming (ASP) is a novel logic programming paradigm, that has already had a profound impact in several application domains, especially in the areas of knowledge representation and reasoning.In spite of the development of excellent inference engines for ASP, efficiency and scalability remain challenging aspects that prevent the use of ASP in various real-world domains. Parallelism has been identified as a natural avenue to address these problems.This paper describes the design of a complete ASP parallel engine, derived from the basic design of the Smodels architecture. The paper places emphasis on addressing the problem of the irregular structure of the search trees generated by typical ASP computations (in a Smodels-like computation), which requires the use of dynamic load balancing mechanisms. The paper provides a systematic investigation of alternative strategies for dynamic scheduling and task sharing. These are the two components that more directly affect the efficiency of a parallel engine.