Computing Stable Models in Parallel

Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning

Volume

Papers from the 2001 AAAI Spring Symposium

Contents

Answer-set programming (ASP) solvers must handle difficult computational problems that are NP-hard. These solvers are in the worst case exponential and their scope of applicability, despite recent impressive gains in performance, remains limited. One way to deal with limitations of answer-set programming is to exploit parallelism. In this paper, we design and implement a parallel program, parstab, that computes stable models of logic programs. We describe preliminary experimental studies ofparstab, running it on seven machines and comparing its performance to a serial execution. Our results are encouraging. For some problems, significant speedups are obtained by runningparstab on multiple machines.