Advanced Heuristics for Parallel ASP Instantiation
Simona Perri, Francesco Ricca, M. Sirianni · 2009
The evaluation of ASP programs is traditionally carried out in two steps. The first is called instantiation or grounding, and consists on the computation of a ground program equivalent to the input one that, in turn, is evaluated by using a backtracking search algorithm in the second phase. Instantia-tion is important for the efficiency of the whole evaluation, might becomes a bottleneck in common situations, and is particularly crucial when huge in-put data has to be dealt with. Notably, performance improvements can be obtained by developing parallel systems, which exploit modern multi-core multi-processor machines. In this paper, we describe a dynamic heuristics for load balancing and granularity control devised for improving parallel instantiation systems. We implemented the new technique in the parallel instantiator based on the DLV system, and conducted an experimental analysis that confirms its efficacy. 1