  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 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. It is well-known that
instantiation is important for the efficiency of the whole evaluation, might
become a bottleneck in common situations, is crucial in several realworld
applications, and is particularly relevant when huge input data has to be dealt
with. At the time of this writing, the available instantiator modules are not
able to exploit satisfactorily the latest hardware, featuring
multi-core/multi-processor SMP (Symmetric MultiProcessing) technologies. This
paper presents some parallel instantiation techniques, including load-balancing
and granularity control heuristics, which allow for the effective exploitation
of the processing power offered by modern SMP machines. This is confirmed by an
extensive experimental analysis herein reported.
  To appear in Theory and Practice of Logic Programming (TPLP).
  KEYWORDS: Answer Set Programming, Instantiation, Parallelism, Heuristics
