Parallel Instantiation of ASP Programs

Most of the Answer Set Programming (ASP) systems are endowed with an instantiation module, which generates a new program equivalent to the input one, but not containing variables. The instantiation process may be computationally expensive, especially for solving real-world problems, where large amounts of data have to be processed: this has been confirmed by recent applications of ASP in different emerging areas, such as knowledge management or information extraction/integration, where also scalability has been recognized as a crucial issue. In this paper we present a new strategy for the parallel instantiation, that allows to improve both performances and scalability of ASP systems by exploiting the power of multiprocessor computers. Indeed, in the last few years, the microprocessors technologies have been moving to multi-core architectures; this makes the real Symmetric MultiProcessing (SMP) finally available even on non-dedicated machines, and paves the way to the development of more scalable softwares. We have implemented such approach into the ASP system DLV, and carried out an experimental analysis which confirms the validity of the proposed strategy, expecially for real-world applications.