Colloquium: Parallel Instantiation of ASP Program

Colloquium:  Parallel Instantiation of ASP Program

by Francesco Ricca

Dipartimento di Matematica
Università della Calabria

Davis Marksbury Theater, 4-5 PM, Monday, August 27th




Answer Set Programming (ASP) is a powerful logic-based programming language, which is enjoying increasing interest within the scientific community and (very recently) in industry. The language of ASP is very expressive, and thus the development of efficient and fast ASP systems is a still challenging task.


The evaluation of ASP programs is traditionally carried out in two steps. At the first step an input program P undergoes the so-called instantiation (or grounding) process, which produces a program P' semantically equivalent to P, but not containing any variable; in turn, P' is evaluated by using a backtracking search algorithm in the second step.


Instantiation is a computationally expensive task, and it is widely recognized that having an efficient instantiation procedure is crucial for the performance of an ASP system. In particular, instantiation is fundamental for real world applications where huge amounts of input data have to be handled, and might become a bottleneck in other common cases.


As a matter of fact, traditional instantiator modules are not able to exploit satisfactorily multi-core/multi-processor SMP (Symmetric MultiProcessing) technologies, despite the fact that parallel hardware is nowadays common and particularly suitable for dealing with large amount of data.


We describe some techniques for parallel instantiation of ASP programs, including parallel evaluation algorithms that are based on structural properties of programs, and load-balancing and granularity control heuristics, which allow for the effective exploitation of the processing power offered by modern SMP machines.