2.1 Logic programming

A logic programming language is built on a signature composed of a set of function symbols $\cal F$ , a set of variables $\cal X$ , and a set of predicate symbols $\cal P$ . An arity function ar(p) is associated to each function symbol and predicate symbol p. A term is either a variable $x \in {\cal X}$ or a formula of the form $f(t_1,\dots, t_n)$ , where $t_1,\dots,t_n$ are themselves terms, $f\in {\cal F}$ , and $ar(f) = n \geq 0$ . A constant is a symbol $f \in {\cal F}$ such that $ar(f)=0$ .

An atomic formula (or simply atom) is a formula of the form $p(t_1,\dots,t_n)$ , where $p \in {\cal P}$ , $t_1,\dots,t_n$ are terms, and $ar(p)=n$ . A literal is either an atom or an entity of the form $\textit{not }A$ , where A is an atom. A clause is a formula of the form

\begin{equation*} H \leftarrow B_1, \dots, B_n, \textit{not } C_1, \dots, \textit{not } C_m,\end{equation*}

where $H, B_1, \dots, B_n, C_1, \dots, C_m$ are atoms. If $m=0$ (i.e. there are no negated literals), the clause is said to be definite, if $m=n=0$ , then the clause is said to be a fact.

Given a clause r, we define $head(r)=H$ , $pos(r) = \{B_1,\dots,B_n\}$ and $neg(r)=\{C_1,\dots, C_m\}$ , while $B_1, \dots, B_n, \textit{not } C_1, \dots, \textit{not } C_m$ is called the body of r. The symbol “ $\leftarrow$ " can be read as “if"; in the rest of this paper we will use $\leftarrow$ and its programming language syntactic notation :- interchangeably. Intuitively, if the body of the clause is true, then the head will be true as a consequence. Variables are universally quantified. For instance, the clause

\begin{align*}grandparent(X,Y) \leftarrow parent(X,Z), parent(Z,Y)\end{align*}

can be read as: “for every X,Y,Z, if X is parent of Z and Z is parent of Y then X is a grandparent of Y." A program is a collection of clauses. A program is definite if all of its clauses are definite. Negated literals are here written at the end of the body, for simplicity, but they can appear interleaved with positive literals in actual programs.

Important information concerning the semantics of a program P can be obtained by the analysis of its dependency graph $\mathcal{G}(P)$ (Baral Reference Baral2003; Gelfond and Kahl Reference Gelfond and Kahl2014). $\mathcal{G}(P)$ is a graph where nodes correspond to atoms in P; an edge $p \leftarrow q$ is added in $\mathcal{G}(P)$ if there is a clause in P with p as head and q in the body. The edge is labeled differently if q occurs as an atom or a negated atom in the body of the clause.

A term (atom, clause, program) is ground if it contains no variables. A substitution $\theta$ is a mapping from a set of variables to terms. If r is a term (literal, clause) and $\theta$ a substitution, $r\theta$ denotes the term (literal, clause) obtained by replacing each variable X in r with the term $\theta(X)$ . Given two terms/atoms s,t, we say that s is subsumed by t (or s is an instance of t) if there is a substitution $\theta$ such that $s = t\theta$ . Two terms/atoms s and t are said to be variants if s is subsumed by t and t is subsumed by s. In this case, s and t are identical modulo a variable renaming. An instance $t\theta$ of t is a ground instance if $t\theta$ contains no variables. Given a clause r, ground(r) denotes the set of all ground instances of r; analogously, given a program P, $ground(P) = \bigcup_{r \in P} ground(r)$ .

Given two substitutions $\sigma$ and $\theta$ , $\sigma$ is more general than $\theta$ if there is a substitution $\gamma$ such that for every term t we have that $(t \sigma) \gamma = t \theta$ . $\theta$ is a unifier of two terms/atoms s and t if $s\theta = t\theta$ , namely the two terms/atoms become syntactically equal after the substitution is applied. If two terms/atoms admit a unifier, they will also admit a most general unifier (mgu) – that is, the most general substitution which is also a unifier; the mgu is unique modulo variable renaming.

Let us denote with $B_P$ the set of all possible ground atoms that can be built with the function and predicate symbols occurring in a program P, also known as the Herbrand Base of P. An interpretation $I\subseteq B_P$ is a set of ground atoms – intuitively representing which atoms are true; all atoms in $B_P\setminus I$ are assumed to be false.

An interpretation I is a model of a ground clause r if either $head(r)\in I$ , or $pos(r)\not\subseteq I$ , or $neg(r)\cap I \neq \emptyset$ (namely, if the head is true or if the body is false). An interpretation I is a model of a clause if it is a model of all its ground instances. An interpretation I is a model of a program P if it is a model of each clause in P.

The semantics of definite programs, which is used as the foundation of Datalog and Prolog, is defined in terms of the set of logical consequences, namely by the set of atoms that are true in every model. For a definite logic program P the existence of a unique minimum model, denoted by $M_P$ , is guaranteed. $M_P$ can be defined as the intersection of all I such that I is a model of P; it can be shown that $M_P$ corresponds to the set of all ground logical consequences of P.

The minimal model $M_P$ of a definite logic program has a constructive characterization through the use of the immediate consequence operator $T_P$ . The operator maps interpretations to interpretations, and it is defined as:

${T_P}(I) = \{ head(r)\>|\>{\rm{ }}r\,{\rm{ground}}\,{\rm{instance}}\,{\rm{of}}\,{\rm{aclause}}\,{\rm{in}}\,P,{\mkern 1mu} pos(r) \subseteq I\} $

$T_P$ is a monotone and continuous operator; in addition, $M_P$ is the least fixpoint of $T_P$ , that is, $M_P = T_P(M_P)$ , and $M_P = T_P \uparrow\omega$ , where $T_P\uparrow 0=\emptyset$ , $T_P \uparrow n = T_P (T_P \uparrow (n-1))$ for a successor ordinal n, and $T_P \uparrow \alpha = lub \{T_P\uparrow n \:|\: n < \alpha\}$ for a limit ordinal $\alpha$ . Computing $M_P$ as $T_P \uparrow\omega =T_P(T_P( \cdots (T_P(\emptyset))\cdots ))$ is called the bottom-up approach to the semantics of P.

In the context of Prolog, computation is expressed in terms of reasoning about the minimal model $M_P$ . Given a program P and a conjunction of possibly non-ground atoms $\bigwedge_{i=1}^n p_i$ , the objective is to determine substitutions $\theta$ for the variables in $p_1, \dots,p_n$ such that $M_P \models \bigwedge_{i=1}^n p_i\theta$ ; these are referred to as correct answers. The conjunction $\bigwedge_{i=1}^n p_i$ is referred to as a goal and subsets of $\{p_1,\dots,p_n\}$ are called subgoals (let us observe that a subgoal can contain more than one atom).

SLD resolution is a strategy used to derive correct answers. It can be described as the process of constructing a tree, the SLD-resolution tree, whose nodes are pairs composed of a goal and a substitution. Given a goal $\vec{p}=\bigwedge_{i=1}^n p_i$ and a program P, the root of the resolution tree is $\langle \vec{p}, \epsilon\rangle$ , where $\epsilon$ is the identity substitution. If $\langle \bigwedge_{i=1}^m q_i, \theta \rangle$ is a node in the resolution tree, then such node will have as many children as there are rules $r\in P$ such that there is a substitution $\gamma$ such that $head(r')\gamma = q_1\theta\gamma$ , where r’ is a renaming of the rule r with fresh new variables. In this case a most general unifier of head(r’) and $q_1\theta$ is chosen. Each child is of the form $\langle pos(r') \circ [q_2,\dots,q_n], \theta\gamma\rangle$ , where $\theta\gamma$ is the composition of the two substitutions and $\circ$ is the list concatenation operator. If $m=0$ , then the node will be labeled as a success node and $\theta$ is a correct answer. If $m>0$ but no child can be constructed, then the node will be labeled as a failed node. Prolog typically implements SLD resolution by building the resolution tree in a depth-first manner, where the children of each node are sorted according to the ordering of the clauses in the program P. The SLD resolution provides a top-down approach to reason about the semantics of P.

The top-down approach is extended in the case of negated literals in goals (general programs). The goal $\textit{not } p$ succeeds or fails as a consequence of the result of the goal p. If there is an answer substitution $\theta$ for p then the goal $\textit{not } p$ fails, otherwise it succeeds. This is referred to as negation as failure.

However, for programs with general clauses, the existence and uniqueness of a minimum model is no longer guaranteed. The well-founded model of a logic program is a unique 3-valued model (Van Gelder et al. Reference Van Gelder, Ross and Schlipf1991) or 4-valued model (Truszczynski Reference Truszczynski2018). We briefly report the procedure presented by Brass et al. (Reference Brass, Dix, Freitag and Zukowski2001), based on the following variant of the $T_P$ operator, for computing the 3-valued well-founded semantics. Given a ground program P and two sets of ground atoms I,J, we define the extended immediate consequence operator

\begin{equation*}T_{P,J}(I) = \{head(r) \:|\: r \in P, pos(r) \subseteq I,neg(r)\cap J=\emptyset\}.\end{equation*}

Let us denote by $P^+$ the set of definite clauses in P, the alternating fixpoint procedure is defined as follows

\begin{equation*}\begin{array}{lcl} K(0) = \mathit{lfp}(T_{P^+}) & & U(0) = \mathit{lfp}(T_{P,K(0)})\\[4pt] K(i+1) = \mathit{lfp}(T_{P,U(i)}) && U(i+1) = \mathit{lfp}(T_{P,K(i+1)}).\end{array}\end{equation*}

Let $(K^*,U^*)$ be the minimum fixpoint of the computation; that is, if i is the smallest value such that $K(i)=K(i-1)$ and $U(i)=U(i-1)$ , then $K^*=K(i)$ and $U^*=U(i)$ .

The well-founded model of the program P is a 3-valued model $W^*$ defined as $W^* = (K^*, U^*)$ – where all atoms in $K^*$ are true, all atoms in $U^*$ are false, and all atoms in $H \setminus (K^*\cup U^*)$ are unknown.

The most successful approach for the two-valued semantics is the one based on the notion of answer sets. Given a program P (for simplicity let us assume P to be ground) and given an interpretation I, we define the reduct of P with respect to I, denoted by $P^I$ as the set of definite clauses $P^I = \{head(r)\leftarrow pos(r)\:|\: r\in P, neg(r)\cap I=\emptyset\}$ . A model M of P is an answer set of P if M is the minimum model of the definite program $P^M$ . It should be noted that a program may have no answer sets, one answer set (for example, each definite program has exactly one answer set, corresponding to its minimal model), or multiple answer sets.

2.2 Parallelism and speedups

When talking about parallelism, it is a naive belief that if a program runs in time T on a computing platform, then it should be possible to execute the program N times faster using N processors. ^{Footnote 1} Namely, that the running time could decrease to $\frac{T}{N}$ .

A definitive theoretical limit to this kind of reasoning was set by Amdahl (Reference Amdahl1967). The crucial point is that the program we are considering is composed of parts that are intrinsically sequential and other parts that can be parallelized. Let S (sequential) and P (parallel) be the running times of the two fractions of the program, scaled to guarantee that $S+P=1$ . With N processors one can expect an ideal running time of $T\left(S + \frac{P}{N}\right)$ , with a speedup of $\frac{1}{S + \frac{P}{N}}$ . Observe that with a “very large" N this leads to a maximum speedup of $\frac{1}{S}$ . Even if S is “small" with respect to the program, for example, $S=0.1$ , this means that the maximum speedup is 10, no matter how many processors are used. The naive reasoning mentioned at the beginning of the paragraph assumes implicitly that $S=0$ , which is often not a realistic assumption.

Gustafson (Reference Gustafson1988) approached the problem from another perspective, giving new hopes of high impact for parallel systems. The key observation of Gustafson is that Amdahl’s law assumes that the problem size (the data size) is fixed. However, Gustafson argues that, in practice, it makes more sense to scale the size of the problem (e.g. the amount of data) in parallel with the addition of processors. Given the running time T as discussed earlier, let us assume that the parallel part of the program P has “to do with data," and that the architecture allows parallel processors to concurrently access independent portions of the data. Then in the same time T, in principle, the program could process N times more data, leading to a speedup of $\frac{PN+S}{P+S}$ . If $S=0.1$ , with one thousand of processors we can, in principle, aim at reaching a speedup of $\approx 900$ .

3.1 Explicit parallelism

Parallel execution of the different operations in a logic program results in implicit exploitation of parallelism, that is, no input is required from the user to identify and exploit parallelism; rather, parallelism is automatically exploited by the inference system. Nevertheless, the literature has presented several approaches that explore extensions of a logic programming language with explicit constructs for the description of concurrency and parallelism. While these approaches are not the focus of this survey, we will briefly mention some of them in this section.

The approaches for the explicit description of parallelism in logic programming can be largely classified into three categories: (1) message passing; (2) shared memory; and 3) dataflow.

Methods based on message passing extend a logic programming language, typically rooted in Prolog, to enable the creation of concurrent computations and the communication among them through the explicit exchange of messages. Several systems have been described over the years with similar capabilities, such as Delta Prolog (Pereira et al. Reference Pereira, Monteiro, Cunha and Aparcio1986) and CS-Prolog (Futó Reference Futó1993). A more recent example is the April system (Fonseca et al. Reference Fonseca, Silva and Camacho2006), where the high-level modeling capabilities of logic programming are used to explicitly parallelize Machine Learning procedures into independent tasks, in the various stages of data analysis, search, and evaluation (Fonseca et al. Reference Fonseca, Srinivasan, Silva and Camacho2009).

Message passing features have become common in many implementations of Prolog – for example, Ciao Prolog (Hermenegildo et al. Reference Hermenegildo, Bueno, Carro, Lopez-Garcia, Mera, Morales and Puebla2012), SICStus Prolog (Carlsson and Mildner Reference Carlsson and Mildner2012), SWI-Prolog (Wielemaker et al. Reference Wielemaker, Schrijvers, Triska and Lager2012), tuProlog (Calegari et al. Reference Calegari, Denti, Mariani and Omicini2018), XSB (Swift and Warren Reference Swift and Warren2012), and YAP Prolog (Santos Costa et al. Reference Santos Costa, Rocha and Damas2012).

Most Prolog implementations provide comprehensive multi-threading libraries, allowing the creation of separate threads and enabling message passing communication between them so (see also the paper by Körner et al. Reference Körner, Leuschel, Barbosa, Santos Costa, Dahl, Hermenegildo, Morales, Wielemaker, Diaz, Abreu and Ciatto2022). The design of these libraries has also been guided by a 2007 ISO technical document which provides recommendations on how multi-threading predicates may be introduced in Prolog.

For example, in YAP Prolog threads are created as follows:

and the communication between them can be achieved through message queues, for example,

The roots of message-passing Prolog systems date back to the early 80s. The Delta Prolog system (Pereira and Nasr Reference Pereira and Nasr1984) draws inspiration from communicating sequential processes to provide the ability of creating processes capable of synchronizing and exchanging messages; for example, the following code snippet describes a simple producer-consumer structure:

A more extensive design is proposed in the CS-Prolog system (Futó and Kacsuk Reference Futó and Kacsuk1989), which provides communicating process designed to execute on Transputer architectures.

The second class of methods is based on the use of shared memory to enable communication between concurrent processes. The most notable approaches rely on the use of blackboards, as exemplified in the Shared Prolog system (Ciancarini Reference Ciancarini1990) and in the various Linda libraries available in several Prolog implementations (e.g. SICStus). An interesting alternative is provided by Ciao Prolog, where the communication is done using concurrent facts in the Prolog database (Carro and Hermenegildo Reference Carro and Hermenegildo1999). This approach is designed to provide a clear transactional behavior, elegantly interacting with backtracking and preserving, under well-defined conditions, the declarative semantics of logic programming.

Finally, a more extensive literature has been developed around the concept of concurrent logic programming (see for example the works by Shapiro Reference Shapiro1987; Shapiro Reference Shapiro1989; Clark and Gregory Reference Clark and Gregory1986, and Tick Reference Tick1995) and implemented in systems like Parlog and GHC. These languages offer a syntax similar to traditional logic programming, but they view all goals in the program clauses as concurrent processes, capable of interacting through shared variables and synchronizing through dataflow constraints. For example, a goal of the type ?- generate(Z), proc(Z) creates two concurrent processes, the first generating values in a list (used as a stream in concurrent logic programming) and the second process consuming values from the stream, for example,

The second process suspends until a value is available in the stream; the clause whose guard (i.e. the goal preceding the “ $|$ ") is satisfied will be activated and executed. One important aspect to observe is that, due to the complications of combining search with this type of concurrency, these systems do not support the classical non-determinism of logic programs. They instead implement only the deterministic part – a form of computation referred to as “committed choice." The fact that all goals are concurrent processes may also lead to complex and unintended interactions, making programs harder to understand.

The idea of synchronization through shared variables is very appealing. This concept has generated several research efforts focused on supporting variable binding-based communication in conjunction with explicit concurrency in Prolog systems, for example, in several proposals for dependent And-parallelism (Gupta and Pontelli Reference Gupta and Pontelli1997; Hermenegildo et al. Reference Hermenegildo, Cabeza and Carro1995; Shen Reference Shen1996). More information about these directions of work can be found later in this section and in Section 4.2.

3.2 Implicit parallelism

The fundamental idea underlying the implicit exploitation of parallelism is to make the exploitation of parallelism transparent to the programmer, by automatically performing in parallel some of the steps belonging to the operational semantics of the language.

As mentioned earlier, most of the pre-2000 literature on implicit exploitation of parallelism focused on the parallelization of the execution model of Prolog. In very general terms, the traditional SLD-resolution process adopted by Prolog can be visualized as a search procedure (see Algorithm 1). There are three major steps in Algorithm 1: Atom Selection, Clause Selection, and Unification. Atom Selection (also known as literal selection in literature) is used to identify the next atom to resolve (line 3 of Algorithm 1). Clause Selection is used to identify which clause to use to conduct resolution (line 5). Unification determines the most general unifier to be used to unify the selected literal with the head of the selected clause (line 6).

Extensive research has been performed to improve efficiency of these steps, especially, for atom selection and clause selection. Techniques such as constraint programming (Gent et al. Reference Gent, Miguel, Nightingale, McCreesh, Prosser, Moore and Unsworth2018) and the Andorra principle (Santos Costa et al. Reference Santos Costa, Warren, Yang, Press and Cambridge1991b) attempt to select subgoals in an order that will lead to early pruning of the search space. The parallelization of the atom selection step leads to independent and dependent And-parallelism (Hermenegildo Reference Hermenegildo1986b; Shen Reference Shen1996; Gupta and Pontelli Reference Gupta and Pontelli1997), which allow multiple subgoals to be selected and solved in parallel. The distinction between the two forms of And-parallelism derives from whether shared unbound variables are allowed (dependent And-parallelism) or not (independent And-parallelism) between concurrently resolved subgoals. The parallelization of the Clause Selection step, which allows resolution of the selected subgoal using multiple clauses in parallel, leads to Or-parallelism (Zhang Reference Zhang1993; Lusk et al. Reference Lusk, Butler, Disz, Olson, Stevens, Warren, Calderwood, Szeredi, Brand, Carlsson, Ciepielewski, Hausman and Haridi1990; Ali and Karlsson Reference Ali and Karlsson1990b).

Algorithm 1:

High–level view of SLD Resolution.

Unification parallelism arises when arguments of a goal are concurrently unified with those of a clause head with the same name and arity. This can be visualized in Algorithm 1 as the parallel execution of the steps present in the unify operation. The different argument terms can be unified in parallel as can the different subterms in a term (Barklund Reference Barklund1990). Unification parallelism is very fine-grained, it requires dealing with dependencies caused by multiple occurrences of the same variables, and is best exploited by building specialized processors with multiple unification units (Singhal and Patt Reference Singhal and Patt1989). Unification parallelism has not been the major focus of research in parallel logic programming, so we will not consider it any further.

3.2.1 Or-parallelism

Or-parallelism arises when multiple clauses have the same predicate in the head and the selected subgoal unifies with more than one clause head – the corresponding clause bodies can be explored in parallel, giving rise to Or-parallelism. This can be illustrated in Algorithm 1 as the parallelization of the choices present in the select $_\textit{clause}$ operation. Or-parallelism is thus a way of efficiently searching for solutions to the goal, by exploring alternative solutions in parallel: it corresponds to the parallel exploration of the search tree originating from the choices performed when selecting different clauses for solving the selected subgoals (often referred to as the or-tree).

Let us consider a very simple example, composed of the Prolog clauses that define the concatenation of two lists:

append([], X, X). append([H|X], Y, [H|Z]) :- append(X, Y, Z).

and the goal:

?- append(X, Y, [1,2,3]).

The append literal in the goal (and all append subgoals that arise recursively during resolution) will match both clauses, and therefore the bodies of these clauses can be executed in parallel to find the four solutions to this goal (see Figure 1). ^{Footnote 2}

Fig. 1.

Example of Or-parallelism.

Or-parallelism should be, in principle, easy to achieve, since the various branches of the or-tree are independent of each other, as they each explore an alternative sequence of resolution steps. As such, their construction should require little communication between parallel computations. ^{Footnote 3} However, in practice, implementation of Or-parallelism is difficult because of the sharing of nodes in the or-tree. Given two nodes in two different branches of the or-tree, all nodes above (and including) their least common ancestor node are shared between the two branches. A variable created in one of these ancestor nodes might be bound differently in the two branches. The environments of the two branches have to be organized in such a way that, in spite of the ancestor nodes being shared, the correct bindings applicable to each of the two branches are easily discernible.

If a binding for a variable, created in one of the common ancestor nodes, is generated above (or at) the least common ancestor node, then this binding will be the same for both branches, and hence can be used as such. Such binding is known as an unconditional binding and such a variable is referred to as an unconditional variable. However, if a binding to such a variable is generated by a node below the least common ancestor node, then that binding shall be visible only in the branch to which the binding node belongs. Such a binding is known as a conditional binding and such a variable is referred to as a conditional variable. The main problem in implementing Or-parallelism is the efficient representation of multiple environments that co-exist simultaneously in the or-tree – commonly known as the environment representation problem. Note that the main problem in the management of multiple environments is how to efficiently represent and access the conditional bindings; the unconditional bindings can be treated as in normal sequential execution of logic programs. The environment representation problem has to be solved by devising a mechanism where each branch has some private areas where it stores the conditional bindings applicable to such branch. Several approaches have been explored to address this problem. For example:

• By storing the conditional bindings created by a branch in an array or a hash table private to that branch, from where the bindings are accessed whenever they are needed. This approach has been adopted, for example, in the binding array model, successfully used in the Aurora system (Warren Reference Warren1984; Lusk et al. Reference Lusk, Butler, Disz, Olson, Stevens, Warren, Calderwood, Szeredi, Brand, Carlsson, Ciepielewski, Hausman and Haridi1990).

• Keeping a separate copy of the environment for each branch of the tree, so that every time branching occurs at a node the environment of the old branch is copied to each new branch. This approach has been adopted, for example, in the stack copying model, successfully used in the Muse and the ACE systems (Ali and Karlsson Reference Ali and Karlsson1990a; Pontelli and Gupta Reference Pontelli and Gupta1997).

• Recording all the conditional bindings in a global data structure and attaching a unique identifier with each binding which identifies the branch a binding belongs to. This approach has been explored, for example, in the version vectors model (Hausman et al. Reference Hausman, Ciepielewski and Haridi1987).

3.2.2 And-parallelism

And-parallelism arises when more than one subgoal is present in the goal or in the body of a clause, and multiple subgoals are selected and resolved concurrently. This can be visualized in Algorithm 1 as generating parallelism from the operation select $_\textit{atom}$ . The literature has traditionally distinguished between independent And-parallelism and dependent And-parallelism.

In the case of independent And-parallelism, subgoals selected for parallel execution are guaranteed to be independent of each other with respect to bindings of variables. In other words, two subgoals solved in parallel are guaranteed to not compete in the binding of unbound variables. A sufficient condition for this (called strict independence) is that any two subgoals solved in parallel do not have any unbound variables in common. Independent And-parallelism is, for example, a way of speeding up a divide-and-conquer algorithm by executing the independent subproblems in parallel. The advantage of independence is that the parallel execution can be carried out without interaction through shared variables. Communication is still needed for returning values and synchronization (including during backtracking).

The main systems proposed to support independent And-parallelism, for example, &-Prolog (Hermenegildo Reference Hermenegildo1986b) and &ACE (Pontelli et al. Reference Pontelli, Gupta and Hermenegildo1995), adopted initially a fork-join organization of the computation, inspired by the original proposal on restricted And-parallelism by DeGroot (Reference DeGroot1984). In this fork-join model independent goals selected to be run in parallel (identified, e.g. using a different conjunction operator &) are made available simultaneously for parallel execution, and the continuation of the computation waits for completion of these parallel goals before proceeding (e.g. see Figure 2). These And-parallel structures can be arbitrarily nested.

Fig. 2.

Intuition behind independent And-parallelism.

The major challenges in the development of independent And-parallel systems are:

• The implementation of distributed backtracking – the goal of maintaining the same visible behavior as a sequential Prolog system implies the need of allowing a processor to backtrack over computations performed by other processors, with requirements of communication and synchronization; these issues have been extensively explored by Hermenegildo (Reference Hermenegildo1986a), Hermenegildo and Nasr (Reference Hermenegildo, Nasr and Notes1986), Shen and Hermenegildo (Reference Shen and Hermenegildo1996), Pontelli and Gupta (Reference Pontelli and Gupta2001), Chico de Guzmán et al. (Reference Chico de Guzmán, Casas, Carro and Hermenegildo2011), Chico de Guzmán et al. (Reference Chico de Guzmán, Casas, Carro and Hermenegildo2012).

• The identification of subgoals that will be independent at runtime – this problem has been addressed by Hermenegildo (Reference Hermenegildo1986a), Hermenegildo (Reference Hermenegildo1986b) through manual program annotations and by Muthukumar et al. (Reference Muthukumar, Bueno, García de la Banda and Hermenegildo1999) using static analysis techniques.

• The need to allow more relaxed notions of independence, that is, the conditions that guarantee that subgoals can be solved in parallel without communication. These include:

  1. — the classical notion of independence (called strict independence by Hermenegildo and Rossi (Reference Hermenegildo and Rossi1995), that is, goals should not share variables at runtime;

  2. — non-strict independence, characterized by the fact that only one goal can bind each shared variable (Hermenegildo and Rossi Reference Hermenegildo and Rossi1995);

  3. — search independence, that is, bindings are compatible (García de la Banda 1994);

  4. — constraint independence (García de la Banda et al. 2000).

Deterministic behavior is also a form of independence (Hermenegildo and Rossi Reference Hermenegildo and Rossi1995).

Dependent And-parallelism arises when two or more subgoals that are executed in parallel have variables in common and the bindings made by one subgoal affect the execution of other subgoals. Dependent And-parallelism can be exploited in two ways (let us consider the simple case of two subgoals):

1. 1. The two subgoals can be executed independently until one of them accesses/binds the common variable. It is possible to continue executing the two subgoals independently in parallel, separately maintaining the bindings generated by each subgoal. In such a case, at the end of the execution of the two subgoals, the bindings produced by each will have to be checked for compatibility (this compatibility check at the end is referred to as back unification).

2. 2. Once the common variable is accessed by one of the subgoals, it is bound to a structure, or stream (the goal generating this binding is called the producer), and the structure is read as an input argument by the other goal (called the consumer).

Case (1) is very similar to independent And-parallelism and can be seen as exploiting independence at a different granularity level. Case (2) is sometimes also referred to as stream-parallelism and is useful for speeding up producer-consumer interactions, by allowing the consumer goal to compute with one element of the stream while the producer goal is computing the next element. Note that stream-parallelism introduces a form of coroutining. Stream-parallelism forms the basis of the Committed Choice Languages mentioned earlier (e.g. Parlog Clark and Gregory Reference Clark and Gregory1986, GHC Ueda Reference Ueda1986, and Concurrent Prolog Shapiro Reference Shapiro1987; Shapiro Reference Shapiro1989).

The main challenge in implementing dependent And-parallelism is controlling the parallel execution of the consumer subgoal. Given two subgoals that share a variable X, one a producer of X and another a consumer, the execution of both can be initiated in parallel. However, one must make sure that the consumer subgoal computes only as far as it does not instantiate the dependent variable X to a non-variable binding. If it attempts to do so, it must suspend. It will be woken up only after a non-variable binding has been produced for X by the producer subgoal – or, alternatively, after the producer has completed its execution without binding X. Thus, in addition to the concerns mentioned in the context of independent And-parallelism, the two additional main concerns in implementing dependent And-parallelism are: In Prolog execution, subgoals in the current goal are resolved in a left-to-right order. Thus, when a subgoal is resolved, it will never have an unexecuted subgoal to its left in the goal. This rule, however, can be relaxed, and considerable advantage can be gained by processing goals in a different order. In particular, this can be applied to subgoals that have at most one matching clause, known as determinate subgoals. This has been realized in the Andorra principle (Santos Costa et al. Reference Santos Costa, Warren and Yang1991a). The Andorra principle states that all determinate subgoals in the current goal should be executed first, irrespective of their position in the goal. Once all determinate subgoals have finished execution, the leftmost non-determinate subgoal is selected and its various alternatives tried in the standard Prolog order. Along each alternative, the same principle is applied. Under the Andorra principle, all deterministic decisions are taken as soon as possible and this facilitates coroutining and leads to a significant narrowing of the search space.

The Andorra principle has been realized in the Andorra-I system (Santos Costa et al. Reference Santos Costa, Warren, Yang, Press and Cambridge1991b). The Andorra-I system also has a determinacy analyzer which generates conditions for each subgoal at compile-time (Santos Costa et al. Reference Santos Costa, Warren, Yang, Press and Cambridge1991c). These simple conditions are checked at runtime and their success indicates that the corresponding subgoal is determinate. The Andorra-I system is a goal stacking implementation of Prolog rather than the traditional environment stacking, due to the need to reorder subgoals during execution. The Andorra principle is in fact useful even beyond parallelism, as a control rule for Prolog, and can also be implemented using delay primitives (Bueno et al. Reference Bueno, Debray, García de la Banda and Hermenegildo1994). This is supported for example by the Ciao Prolog system.

The Andorra principle has been generalized to the Extended Andorra Model (EAM) (Haridi and Brand Reference Haridi and Brand1988) to exploit both And- and Or-parallelism. In EAM, arbitrary subgoals can execute in And-parallel and clauses can be tried in Or-parallel. Computations that do not impact the environment external to a subgoal are freely executed, giving rise to parallelism. However, computations that may bind a variable occurring in argument terms of a subgoal are suspended, unless the binding is deterministic (in which case the binding is said to be promoted). If the binding is non-deterministic, then the subgoal is replicated for each binding (non-determinate promotion). These replicated subgoals are executed in Or-parallel. At any moment, constraints and bindings generated outside of a subgoal are immediately percolated down to that subgoal (propagation).

The Extended Andorra Model seeks to optimally exploit And-/Or-parallelism. It provides a generic model for the exploitation of coroutining and parallelism in logic programming and has motivated two main lines of research. The first path resulted in the Andorra Kernel Language (Haridi and Janson Reference Haridi, Janson, Warren and Szeredi1990) that can be thought of as a new paradigm that subsumes both Prolog and concurrent logic languages (Haridi and Brand Reference Haridi and Brand1988). The second focused on the EAM with Implicit Control (Warren Reference Warren1990; Lopes et al. Reference Lopes, Santos Costa and Silva2012), where the goal is to achieve efficient (parallel) execution of logic programs with minimal programmer control. An interpreter (in Prolog) was developed to better understand EAM with implicit control (Gupta and Warren Reference Gupta and Warren1992) and new concepts, such as lazy copying and eager producers, that give finer control over search and improve parallelism have been investigated. Gupta and Pontelli later experimented with an extension of dependent And-parallelism that provides some of the functionality of the EAM through parallelism (Gupta and Pontelli Reference Gupta and Pontelli1997). The first prototype parallel implementation of the EAM (called BEAM), based on the WAM, has been presented by Lopes et al. (Reference Lopes, Santos Costa and Silva2003), Lopes et al. (Reference Lopes, Santos Costa and Silva2004). The BEAM system is promising, though the fine-grain And-/Or-parallelism that EAM supports results in significant overhead and thus extracting good performance requires taking into account additional factors such as granularity control.

The state-of-the-art in the exploitation of dependent And-parallelism at the beginning of 2000 is represented by systems like ACE (Gupta and Pontelli Reference Gupta and Pontelli1997), BEAM (Lopes et al. Reference Lopes, Santos Costa and Silva2012) and DDAS (Shen Reference Shen1996), which are effective but complex. There are also some early attempts at simpler approaches to parallel implementations (Hermenegildo et al. Reference Hermenegildo, Cabeza and Carro1995).

4.1 Or-parallelism

4.1.2 Recent solutions to the environment representation problem

As introduced in Section 3, before 2000, the state-of-the-art in Or-parallel Prolog systems was achieved using one of two approaches: stack copying (as used in the Muse system and in ACE Ali and Karlsson Reference Ali and Karlsson1990b; Pontelli and Gupta Reference Pontelli and Gupta1997), and binding arrays (as used in the Aurora system Lusk et al. Reference Lusk, Butler, Disz, Olson, Stevens, Warren, Calderwood, Szeredi, Brand, Carlsson, Ciepielewski, Hausman and Haridi1990). These techniques provided comparable benefits and fostered a wealth of additional research (e.g. in the area of scheduling de Castro Dutra Reference de Castro Dutra1994; Beaumont and Warren Reference Beaumont, Warren, Press and Cambridge1993; Ali and Karlsson Reference Ali and Karlsson1992). The advent of distributed computing architectures, especially Beowulf clusters, led researchers to investigate the development of Or-parallel Prolog systems in absence of shared memory. The two approaches above are not immediately suitable for distributed memory architectures, as they require some level of data sharing between workers ^{Footnote 5} during the execution. For example, in the case of stack copying, shared frames need to be created to coordinate workers’ access to unexplored choice point alternatives.

The PALS system (Villaverde et al. Reference Villaverde, Pontelli, Guo and Gupta2001b; Pontelli et al. Reference Pontelli, Villaverde, Guo and Gupta2007; Gupta and Pontelli Reference Gupta and Pontelli1999) introduced the concept of stack splitting as a new environment representation methodology suitable for distributed memory systems. Stack splitting replaces the dynamic synchronization among workers, for example, as in the access to shared choice points during backtracking in the binding arrays method, with a “static" partitioning of the unexplored alternatives between workers. Such partitioning is performed each time two workers collaborate to share unexplored branches of the resolution tree. Thus, stack splitting allows us to remove synchronization requirements by preemptively partitioning the remaining unexplored alternatives at the moment of sharing. The splitting allows both workers to proceed, each executing its branch of the computation, without any need for further synchronization when accessing parts of the resolution tree which are common among the workers.he original definition of stack splitting (Villaverde et al. Reference Villaverde, Pontelli, Guo and Gupta2001a; Pontelli et al. Reference Pontelli, Villaverde, Guo and Gupta2006) explored two strategies of splitting. Vertical stack splitting (Figure 3–top) is suitable for computations where branches of the resolution tree are highly unbalanced and where choice points tend to have a small number of alternatives (e.g. binary trees). In this case, the available choice points are alternated between the two sharing workers – for example, the first worker keeps the first, third, fifth, etc. choice point with unexplored alternatives, while the second worker keeps the second, fourth, sixth, etc. In the end, each worker ends up with approximately half of the choice points with unexplored alternatives. The alternation between choice points kept and choice points given away is meant to improve the chance of a balanced distribution of work between the two workers. Horizontal stack splitting has been, instead, designed to support sharing in the case of computations with few choice points, each with a large number of unexplored alternatives. In this case, the two workers partition the unexplored alternatives within each available choice point (Figure 3–middle).

Fig. 3.

From top to bottom: Vertical Splitting, Horizontal Splitting, Middle Splitting. Workers visit the resolution tree in depth-first order; CP stands for choice point; CP1 is the “root" of the tree. P and Q denote different workers. A black node means that the choice point has no alternatives available. A connection between P/Q and a node indicates that the worker is executing the given alternative of the choice point. The arrow denotes immediate backtracking for the worker stealing work.

Follow-up research has explored additional variations of stack splitting. Diagonal stack splitting (Rocha et al. Reference Rocha, Silva and Martins2003) provides a combination of horizontal and vertical stack splitting. Middle stack splitting, also known as Half stack splitting (Villaverde et al. Reference Villaverde, Pontelli, Guo and Gupta2003), is similar to vertical stack splitting, but with the difference that one worker keeps the top half of the choice points while the second worker keeps the bottom half. The advantage of this methodology is its efficient implementation and the ability to know the respective position of the two workers in the resolution tree immediately after the sharing operation – a useful property in order to manage side-effects and other order-sensitive predicates (Figure 3–bottom).

Even though stack splitting has been originally designed to sustain Or-parallelism on distributed memory architectures, this methodology provides advantages also on shared memory platforms. The ACE system (Gupta and Pontelli Reference Gupta and Pontelli1999) demonstrated that stack-splitting outperforms stack copying in a variety of benchmarks. A microprocessor-level simulation, using the Simics simulator, identified an improved cache behavior as the reason for the superior performance in shared memory platforms (Pontelli and Gupta Reference Pontelli and Gupta1999).

4.2 And-parallelism

4.3 Static analysis for parallelism

Static analysis, generally based on Cousots’ theory of abstract interpretation (Cousot and Cousot Reference Cousot and Cousot1977), is a supporting technology in a number of areas related to parallelism in logic programming, and especially in the process of automatic parallelization of logic programs to exploit And-parallelism. In fact, logic programming pioneered the development of abstract interpretation-based analyzers – such as MA3 and Ms (Warren et al. Reference Warren, Hermenegildo and Debray1988), PLAI (Muthukumar and Hermenegildo Reference Muthukumar and Hermenegildo1990; Muthukumar and Hermenegildo Reference Muthukumar and Hermenegildo1992; García de la Banda et al. 1996), or GAIA (Le Charlier and Van Hentenryck Reference Le Charlier and Van Hentenryck1994), and the extension of this style of analysis to CLP/CHCs (García de la Banda and Hermenegildo 1993; García de la Banda et al. 1996; Kelly et al. Reference Kelly, Marriott, Søndergaard and Stuckey1998). Arguably, the MA3 and PLAI parallelizers for independent And-parallelism were the first complete, practical applications of abstract interpretation in a working compiler (see, e.g. Van Roy Reference Van Roy1994).

Static analysis is an area that has seen significant progress in this period. In this section we briefly focus on the advances made in static analysis for parallelism in logic programs since the survey paper by Gupta et al. (Reference Gupta, Pontelli, Ali, Carlsson and Hermenegildo2001), with a quick view on main older results.

Sharing analyses. One of the main instrumental properties for automatic (And-)parallelization is the safe approximation of the sharing (aliasing) patterns between variables. Apart from being necessary for obtaining analyses that are at the same time precise and correct, variable sharing is a basic component of essentially all notions of independence (Hermenegildo and Rossi Reference Hermenegildo and Rossi1995; Bueno et al. Reference Bueno, García de la Banda and Hermenegildo1999; Muthukumar et al. Reference Muthukumar, Bueno, García de la Banda and Hermenegildo1999; Marriott et al. Reference Marriott, García de la Banda and Hermenegildo1994; García de la Banda et al. 1995; García de la Banda et al. 2000). The main abstract domains developed for detecting independence typically seek to capture either set-sharing (Muthukumar and Hermenegildo Reference Muthukumar, Hermenegildo, Lusk and Overbeek1989; Muthukumar and Hermenegildo Reference Muthukumar, Hermenegildo, Press and Cambridge1991; Muthukumar and Hermenegildo Reference Muthukumar and Hermenegildo1992; Jacobs and Langen Reference Jacobs and Langen1989; Codish et al. Reference Codish, Lagoon and Bueno2000; Hill et al. Reference Hill, Bagnara and Zaffanella2002) or pair-sharing (SØ ndergaard 1986; Lagoon and Stuckey Reference Lagoon and Stuckey2002; Bueno and García de la Banda 2004). Results in this area implied the development of widenings (Cousot and Cousot Reference Cousot and Cousot1977) and/or alternative more efficient representations and abstract domain operations for sharing domains. Widenings are used in abstract interpretation-based analyses to support infinite abstract domains and also to reduce the cost of complex domains, such as sharing. In both cases the essence of the technique is to lose precision in return for reduced analysis time (at the limit, termination) by generalizing at some point in the analysis to a larger abstract value. This implies arriving at fixpoints that are less precise than the minimal fixpoint, but still safe approximations of the concrete values.

In this line, widenings of sharing have been proposed for example by Zaffanella et al. (Reference Zaffanella, Bagnara and Hill1999), by performing a widening switch to a modification of Fecht’s domain (Fecht Reference Fecht1996) and incorporating other techniques such as combining with the Pos domain. Navas et al. (Reference Navas, Bueno and Hermenegildo2006) proposed an encoding of sharing that represents sets of variables that have total sharing (which gives rise to large sharing sets) in a compact way and also widens abstract values to this representation when they are close to total sharing. Li et al. (Reference Li, King and Lu2006) developed a lazy technique that postpones computations of sharing sets until they are really needed. Trias et al. (Reference Trias, Navas, Ackley, Forrest and Hermenegildo2008) proposed an encoding that uses negative information representation techniques to switch to a dual representation for certain variables when there is a high degree of sharing among them. Also, Méndez-Lojo et al. (Reference Méndez-Lojo, Lhoták and Hermenegildo2008) proposes and studies a representation using ZBDDs.

Determinism and non-failure analyses. Inference of determinacy (Lopez-Garcia et al. Reference Lopez-Garcia, Bueno and Hermenegildo2010) and non-failure (Bueno et al. Reference Bueno, Lopez-Garcia and Hermenegildo2004), including multivariant (i.e. context/path-sensitive) analyses, based on the PLAI framework have been investigated. These analyses are instrumental in And-parallelism, since if goals can be determined to not fail and/or be deterministic, significant simplifications can be performed in the handling of their parallel execution. This is due to the inherent complexity in handling backtracking across parallel goals (Section 4.2), significant parts of which can be avoided if such information is available.

Cost analysis and granularity control. The advances in determinism and non-failure analyses are also useful for improving the precision of cost analysis (Debray et al. Reference Debray, Lin and Hermenegildo1990; Debray et al. Reference Debray, Lopez-Garcia, Hermenegildo and Lin1994; Debray et al. Reference Debray, Lopez-Garcia, Hermenegildo and Lin1997), which is instrumental in parallelism for performing task granularity control (Debray et al. Reference Debray, Lin and Hermenegildo1990; Lopez-Garcia et al. Reference Lopez-Garcia, Hermenegildo and Debray1996; Lopez-Garcia Reference Lopez-Garcia2000). Such analyses have been extended to estimate actual execution time (Mera et al. Reference Mera, Lopez-Garcia, Carro and Hermenegildo2008), rather than steps, as in previous work, which is arguably more relevant to automatic parallelization and granularity control. Techniques have also been developed for fuzzy granularity control (Trigo de la Vega et al. Reference Trigo de la Vega, Lopez-García and Muñoz-Hernández2010). Another important related line of work has been the static inference of the cost of parallelized programs (Klemen et al. Reference Klemen, Lopez-Garcia, Gallagher, Morales and Hermenegildo2020). The base cost analyses have also been extended to be parametric (Navas et al. Reference Navas, Mera, Lopez-Garcia and Hermenegildo2007) (where the analysis can track user-defined resources and compound resources) and multivariant, formulated as an abstract domain (Serrano et al. Reference Serrano, Lopez-Garcia and Hermenegildo2014).

Static analysis for parallelization algorithms. There has also been progress in the development of improved, static analysis-based parallelization algorithms that allow automatic parallelization for non-restricted And-parallelism (Casas et al. Reference Casas, Carro and Hermenegildo2007; Casas Reference Casas2008) (i.e. not limited to fork-join structures, as supported by Casas et al. Reference Casas, Carro and Hermenegildo2008a, see Section 4.2.2). Also, improved parallelization algorithms for non-strict independence (Hermenegildo and Rossi Reference Hermenegildo and Rossi1995) using sharing and freeness information have been proposed (Cabeza and Hermenegildo Reference Cabeza and Hermenegildo2009).

In another line of work, by Vidal (Reference Vidal2012), a novel technique has been presented for generating annotations for independent And-parallelism based on partial evaluation. A partial evaluation procedure is augmented with (runtime) groundness and variable sharing information so that parallel conjunctions are added to the residual clauses when the conditions for independence are met. The results are parallel annotated programs which are shown to be capable of achieving interesting speedups.

Improvements in static analysis related to scalability are directly relevant to improving the practicality of automatic parallelization techniques. In this context, much work has been done in improving these aspects for LP and CLP analyses, including combined modular and incremental analysis, assertion-guided multivariant analysis, and analysis of programs with assertions and open predicates (Garcia-Contreras et al. Reference Garcia-Contreras, Morales and Hermenegildo2018; Garcia-Contreras et al. Reference Garcia-Contreras, Morales and Hermenegildo2019; Garcia-Contreras et al. Reference Garcia-Contreras, Morales and Hermenegildo2020).

Runtime checking overhead. The reduction of the overhead implied by runtime tests (through caching techniques (Stulova et al. Reference Stulova, Morales and Hermenegildo2015; Stulova Reference Stulova2018) and also static analysis (Stulova et al. Reference Stulova, Morales and Hermenegildo2018), similarly to what done in the works by Bueno et al. (Reference Bueno, García de la Banda and Hermenegildo1999) and Puebla and Hermenegildo (Reference Puebla and Hermenegildo1999), as well as in generating static performance guarantees for programs with runtime checks (Klemen et al. Reference Klemen, Stulova, Lopez-Garcia, Morales and Hermenegildo2018), have been subject of active research. This work was done in the context of runtime tests for assertions but it is directly relevant to runtime checking for conditional And-parallelism.

Applications to other paradigms and areas. The techniques developed for LP/CLP parallelization have been used to support the parallelization of other paradigms (Hermenegildo Reference Hermenegildo2000). This is a large topic that goes beyond the scope of this survey, but examples include the application of pair-sharing (Secci and Spoto Reference Secci and Spoto2005) and set-sharing (Méndez-Lojo and Hermenegildo Reference Méndez-Lojo and Hermenegildo2008) to object-oriented programs, sharing analysis of arrays, collections, and recursive structures (Marron et al. Reference Marron, Méndez-Lojo, Hermenegildo, Stefanovic and Kapur2008b), identifying logically related heap regions (Marron et al. Reference Marron, Kapur and Hermenegildo2009), identification of heap-carried dependencies (Marron et al. Reference Marron, Kapur, Stefanovic and Hermenegildo2008a), or context-sensitive shape analysis (Marron et al. Reference Marron, Kapur, Stefanovic and Hermenegildo2006; Marron et al. Reference Marron, Hermenegildo, Kapur, Stefanovic and Notes2008).

As stated before, the demand for precise global analysis and transformation stemming from automatic parallelization spurred the development of the first abstract interpretation-based “production" analyzers. Having these systems readily available led to the early realization that analysis and transformation are very useful also in program verification and static debugging, as illustrated by the pioneering Ciao Prolog system (Bueno et al. Reference Bueno, Deransart, Drabent, Ferrand, Hermenegildo, Maluszynski and Puebla1997; Hermenegildo et al. Reference Hermenegildo, Puebla and Bueno1999; Hermenegildo et al. Reference Hermenegildo, Puebla, Bueno and Garcia2005; Hermenegildo et al. Reference Hermenegildo, Bueno, Carro, Lopez-Garcia, Mera, Morales and Puebla2012). During the past two decades, the analysis and verification of a large variety of other programming paradigms – including imperative, functional, object-oriented, and concurrent ones – using LP/CLP-related analysis techniques, has received significant interest, and many verification approaches and tools have recently been implemented which are based in one way or another in a translation into LP/CLP (referred to in this context as Constrained Horn Clauses – CHCs) (Peralta et al. Reference Peralta, Gallagher, SaĞlam and Notes1998; Henriksen and Gallagher Reference Henriksen and Gallagher2006; Méndez-Lojo et al. Reference Méndez-Lojo, Navas and Hermenegildo2007; Navas et al. Reference Navas, Méndez-Lojo and Hermenegildo2008; Navas et al. Reference Navas, Méndez-Lojo and Hermenegildo2009; Albert et al. Reference Albert, Arenas, Genaim, Puebla, Zanardini and Notes2007; GÓmez-Zamalloa et al. Reference GÓmez-Zamalloa, Albert and Puebla2009; Grebenshchikov et al. Reference Grebenshchikov, Lopes, Popeea and Rybalchenko2012; Gurfinkel et al. Reference Gurfinkel, Kahsai, Komuravelli and Navas2015; De Angelis et al. Reference De Angelis, Fioravanti, Pettorossi and Proietti2015; Kahsai et al. Reference Kahsai, Rümmer, Sanchez, Schäf, Chaudhuri and Farzan2016; Lopez-Garcia et al. Reference Lopez-Garcia, Darmawan, Klemen, Liqat, Bueno and Hermenegildo2018; Liqat et al. Reference Liqat, Kerrison, Serrano, Georgiou, Lopez-Garcia, Grech, Hermenegildo, Eder, Gupta and Peña2014; Liqat et al. Reference Liqat, Georgiou, Kerrison, Lopez-Garcia, Hermenegildo, Gallagher and Eder2016; Gallagher et al. Reference Gallagher, Hermenegildo, Kafle, Klemen, Lopez-Garcia and Morales2020). The main reason is that LP and CLP are effective as languages for specifying program semantics and program properties. De Angelis et al. (Reference De Angelis, Fioravanti, Gallagher, Hermenegildo, Pettorossi and Proietti2022) offers an up-to-date, comprehensive survey of this approach.

4.4 Parallelism and tabling

Tabling, introduced by Chen and Warren (Reference Chen and Warren1996), is a powerful implementation technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant sub-computations. Tabling has become a popular and successful technique thanks to the ground-breaking work in the XSB Prolog system and in the SLG-WAM engine (Sagonas and Swift Reference Sagonas and Swift1998). The success of SLG-WAM led to several alternative implementations that differ in the execution rule, in the data structures used to implement tabling, and in the changes to the underlying Prolog engine (Swift and Warren Reference Swift and Warren2012; Santos Costa et al. Reference Santos Costa, Rocha and Damas2012; Zhou Reference Zhou2012; Guo and Gupta Reference Guo and Gupta2001; Somogyi and Sagonas Reference Somogyi and Sagonas2006; Chico de Guzmán et al. Reference Chico de Guzmán, Carro, Hermenegildo, Silva and Rocha2008; Desouter et al. Reference Desouter, van Dooren and Schrijvers2015; Zhou et al. Reference Zhou, Kjellerstrand and Fruhman2015).

Tabling is a refinement of SLD resolution that stems from one simple idea: programs are evaluated by saving intermediate answers for tabled subgoals so that they can be reused when a similar call appears during the resolution process. First calls to tabled subgoals are considered generators and are evaluated as usual, using SLD resolution, but their answers are stored in a global data space, called the table space. Similar calls are called consumers and are resolved by consuming the answers already stored for the corresponding generator, instead of re-evaluating them against the program clauses. During this process, as further new answers are found, they are stored in their table entries and later returned to all similar calls. Call similarity thus determines if a subgoal will produce their own answers or if it will consume answers from a generator call.

A key procedure in tabled evaluation is the completion procedure, which determines whether a subgoal is completely evaluated. A subgoal is said to be completely evaluated when all its possible resolutions have been performed, that is, when no more answers can be generated and all consumers have consumed all the available answers. A number of subgoals may be mutually dependent, forming a strongly connected component (SCC), and therefore can only be completed together. In this case, completion is performed by the leader of the SCC, which is the oldest generator subgoal in the SCC, when all possible resolutions have been made for all subgoals in the SCC (Sagonas and Swift Reference Sagonas and Swift1998).

4.4.2 YAP Prolog

We focus here on the already cited YAP Prolog system that provides the ground technology for both implicit and explicit concurrent tabled evaluation, but separately. From the user’s point of view, tabling can be enabled through the use of single directives of the form “:- table p/n," meaning that common sub-computations for p/n will be synchronized and shared between workers at the engine level, that is, at the level of the tables where the results for such sub-computations are stored. Implicit concurrent tabled evaluation can be triggered if using the OPTYap design (Rocha et al. Reference Rocha, Silva and Santos Costa2005), which exploits implicit Or-parallelism using shared memory processes. Explicit concurrent tabled evaluation can be triggered if using the thread-based implementation (Areias and Rocha Reference Areias and Rocha2012); in this case, the user still needs to implement the thread management and scheduler policy for task distribution.

Implicit Or-Parallel Tabled Evaluation

The OPTYap system builds on the YapOr (Rocha et al. Reference Rocha, Silva and Santos Costa1999b) and YapTab (Rocha et al. Reference Rocha, Silva and Santos Costa2000) engines. YapOr extends YAP’s sequential engine to support implicit Or-parallelism based on the environment copying model. YapTab extends YAP’s execution model to support (sequential) tabled evaluation. In the OPTYap design, tabling is the base component of the system as, most of the time, each worker behaves as a full sequential tabling engine. The Or-parallel component of the system is triggered to allow synchronized access to the shared region of the search space or to schedule work. Work sharing is implemented through stack copying with incremental copying of the stacks (Ali and Karlsson Reference Ali and Karlsson1990a).

Workers exploiting the public (shared) region of the search space must synchronize to ensure the correctness of the tabling operations. Synchronization is required: (i) when backtracking to public generator or interior (non-tabled) nodes to take the next available alternative; (ii) when backtracking to public consumer nodes to take the next unconsumed answer; or, (iii) when inserting new answers into the table space. Moreover, since Or-parallel systems can execute alternatives early, the relative positions of generator and consumer nodes are not as clear as for sequential tabling. As a result, it is possible that generators will execute earlier, and in a different branch than in sequential execution. Or that different workers may execute the generator and the consumer calls. Or, in the worst case, workers may have consumer nodes while not having the corresponding generators in their branches. This induces complex dependencies between workers, hence requiring a more elaborated and specific public completion operation (Rocha et al. Reference Rocha, Silva and Santos Costa2001).

Figure 4 illustrates this kind of dependencies. Starting from a common public node, worker W1 takes the leftmost alternative while worker W2 takes the rightmost. While exploiting their alternatives, W1 calls a tabled subgoal a and W2 calls a tabled subgoal b. As this is the first call to both subgoals, a generator node is stored for each one. Next, each worker calls the tabled subgoal firstly called by the other, and consumer nodes are therefore allocated. At that point, we may question at which (leader) node should we check for completion? In OPTYap, public completion is performed at the least common ancestor node (node L in Figure 4). But that leader node can be any type of node and not necessarily a generator node as in the case of sequential tabling.

Fig. 4.

Public completion scheme. Black nodes are public nodes, rectangle nodes are generators, rhombus nodes are consumers. $W_1$ and $W_2$ are the workers.

Consider now the case where W1 has explored all its private work and backtracks to the public leader node L common to W2. Since work is going on below L, W1 cannot complete its current SCC (which includes L, the generator node for a and the consumer node for b). The reason for this is that W2 can still influence W1’s branch, for instance, by finding new answers for subgoal b. On the other hand, we would like to move W1 in the tree, say to node N, where there is available work and, for that, we may need to reset the stacks to the values in N. As a result, in order to allow W1 to continue execution, it becomes necessary to suspend the SCC at hand. This is the only case where Or-parallelism and tabling conflict in OPTYap (a worker needs to move in the tree above an uncompleted leader node). OPTYap’s solution is to save the SCC’s stacks to a proper space, leaving in L a reference to where the stacks were saved. These suspended computations are considered again when the remaining workers check for completion at L. To resume a suspended SCC a worker needs to copy the saved stacks to the correct position in its own stacks, and thus, it has to suspend its current SCC first. To minimize that, OPTYap adopts the strategy of resuming suspended SCCs only when the worker finds itself at a leader node, since this is a decision point where the worker either completes or suspends its current SCC. OPTYap’s public completion algorithm and associated data structures is one of the major contributions of OPTYap’s design.

Explicit Concurrent Tabled Evaluation

In YAP, threads run independently within their own execution stacks. For tabling, this means that each thread evaluation depends only on the computations being performed by itself, that is, from the thread point of view, each thread has its own private tables but, at the engine level, YAP uses a common table space shared among all threads.

Figure 5 shows the general table space organization for a tabled predicate in YAP. At the entry level is the table entry data structure where the common information for the predicate is stored. This structure is allocated when a tabled predicate is being compiled, so that a pointer to the table entry can be included in the compiled code. This guarantees that further calls to the predicate will access the table space starting from the same point. Below the table entry, is the subgoal trie structure. Each different tabled subgoal call to the predicate at hand corresponds to a unique path through the subgoal trie structure, always starting from the table entry, passing by several subgoal trie data units, the subgoal trie nodes, and reaching a leaf data structure, the subgoal frame. The subgoal frame stores additional information about the subgoal and acts like an entry point to the answer trie structure. Each unique path through the answer trie data units, the answer trie nodes, corresponds to a different answer to the entry subgoal. To deal with multi-threading tabling, YAP implements several designs with different degrees of sharing of the table space data structures.

Fig. 5.

YAP’s table space organization.

We report here the main features of three sharing designs proposed in Areias and Rocha (Reference Areias and Rocha2012): No-Sharing (NS), Subgoal-Sharing (SS), and Full-Sharing (FS).

NS was the starting design for multi-threading tabling support in YAP: each thread allocates fully private tables and the table entry is extended with a thread array, where each thread has its own entry, which then points to the private subgoal tries, subgoal frames and answer tries for the thread.

In the SS design, the threads share part of the table space, namely, the subgoal trie structures are now shared among the threads and the leaf data structure in each subgoal trie path, instead of referring a subgoal frame, it now points to a thread array. Each entry in this array then points to private subgoal frames and answer trie structures. In this design, concurrency among threads is restricted to the allocation of trie nodes on the subgoal trie structures. Tabled answers are still stored in the private answer trie structures of each thread. The Partial Answer Sharing (PAS) design (Areias and Rocha Reference Areias and Rocha2017) extends the SS design to allow threads to share answers. The idea is as follows: whenever a thread calls a new tabled subgoal, first it searches the table space to lookup if any other thread has already computed the full set of answers for that subgoal. If so, then the thread reuses the available answers, thus avoiding recomputing the subgoal call from scratch. Otherwise, it computes the subgoal itself. The first thread completing a subgoal call, shares the results by making them available (public) to the other threads. The PAS design avoids the usage of the thread array and instead it uses a list of private subgoal frames corresponding to the threads evaluating the subgoal call. In order to find the subgoal frame corresponding to a thread, we may have to pay an extra cost for navigating in the list but, once a subgoal frame is completed and made public, its access is immediate since it is moved to the beginning of the list.

Finally, the FS design tries to maximize the amount of data structures being shared. In this design, the answer tries and part of the subgoal frame information are also shared among threads. A new subgoal entry data structure stores the shared information for the subgoal, which includes access to the shared answer trie and to the thread array that keeps pointing to the subgoal frames, where the remaining private information is kept. In this design, concurrency among threads includes the access to the new subgoal entries and the allocation of tries nodes on the answer trie structures. Memory usage is reduced to a minimum and, since threads share the answer tries, answers inserted by a thread for a particular subgoal call are automatically made available to all other threads when they call the same subgoal. However, since different threads can be inserting answers in the same answer trie, when an answer already exists, it is not possible to determine if the answer is new or repeated for a particular thread without further support. This can be a problem if the tabling engine implements a batched scheduling strategy (Freire et al. Reference Freire, Swift and Warren1996). To mitigate this problem, the Private Answer Chaining (PAC) design (Areias and Rocha Reference Areias and Rocha2015) extends the FS design to keep track of the answers that were already found and propagated per thread and subgoal call.

5.1 Parallelism and Datalog

Research on parallelization of Datalog inherited results and techniques developed in the field of relational DBMS, such as parallelization of relational operations and of SQL query evaluation. Particularly relevant are the approaches to parallelization of natural join operations, as they are at the core of the naive and semi-naive bottom-up computation in Datalog, and query optimization; the literature has explored such issues in the context of a variety of computing architectures (Wang et al. Reference Wang, Xiong, Li, Shi, Li and Gao2018; Diamos et al. Reference Diamos, Wu, Wang, Lele and Yalamanchili2013; Zeuch Reference Zeuch2018; Zinn et al. Reference Zinn, Wu, Wang, Aref and Yalamanchili2016; Shehab et al. Reference Shehab, Algergawy and Sarhan2017).

Initial attempts towards the parallelization of Datalog appeared early in literature. Among many, we mention the works by Wolfson and Silberschatz (Reference Wolfson and Silberschatz1988), Ganguly et al. (Reference Ganguly, Silberschatz and Tsur1992), and Zhang et al. (Reference Zhang, Wang and Chau1995) which explore the execution of Datalog on distributed memory architectures. These approaches are mainly restricted to definite programs or, in the case of programs with negation, to stratified programs. The core idea consists in parallelizing the computation of the minimum model of a Datalog program, computed using the semi-naive bottom-up technique. Program rules are partitioned and assigned to the distributed workers. Communication between workers is implemented through explicit message passing. The different early proposals differ on the techniques used to distribute sets of rules different workers and management of the communication, used to exchange components of the minimal model as it is computed.

Similar approaches have been developed to operate on multi-core shared memory machines – by exploring hash functions to partition computation of relations that guarantee the avoidance of locks (Yang et al. Reference Yang, Shkapsky and Zaniolo2015). Significant speedups can be obtained by using as little synchronization as possible during the program evaluation. An example is the work by Martinez-Angeles et al. (Reference Martinez-Angeles, de Castro Dutra, Santos Costa and Buenabad-Chávez2014), where the load of computing the model is distributed among the various GPU threads that can access and modify the data in the GPU shared memory.

In more recent years, various tools and systems have been developed to evaluate Datalog programs in parallel or distributed settings. Some of such parallel/distributed engines have been mainly designed to support declarative reasoning in application domains like declarative networking, program analysis, distributed social networking, security, and graph/data analytic. These approaches often extend plain Datalog with some form of aggregation and negation to meet the needs of the specific application domain.

Moustafa et al. (Reference Moustafa, Papavasileiou, Yocum and Deutsch2016) propose Datalography, a bottom-up evaluation engine for Datalog tailored to graph analytics. The system enables the distributed evaluation of Datalog queries, also involving aggregates; the target architecture for this implementation is a BSP-style graph processing engine. Queries are compiled into sets of rules that can be executed locally by the distributed workers. Optimizations are applied to partition the work and to minimize communication between workers. A different approach to large-scale Datalog applications is adopted in the Soufflé system (Jordan et al. Reference Jordan, Scholz and Subotic2016; Nappa et al. Reference Nappa, Zhao, Subotic and Scholz2019; Zhao et al. Reference Zhao, Subotic and Scholz2020). Efficient Datalog evaluation is obtained by compiling declarative specifications into C++ programs involving openMP directives that enable parallel execution on shared memory multi-core architectures.

The BigDatalog system (Condie et al. Reference Condie, Das, Interlandi, Shkapsky, Yang and Zaniolo2018; Das and Zaniolo Reference Das and Zaniolo2019; Shkapsky et al. Reference Shkapsky, Yang, Interlandi, Chiu, Condie and Zaniolo2016) supports scalable analytics and can be executed on distributed and multi-core architectures. The notion of “pre-mappability" (Zaniolo et al. Reference Zaniolo, Yang, Das, Shkapsky, Condie and Interlandi2017) is exploited to extend Datalog’s fixpoint semantics in order to enable aggregates in recursion.

Seo et al. (Reference Seo, Park, Shin and Lam2013) describe Distributed SociaLite, an extension of the SociaLite system for parallel and distributed large-scale graph analysis. In this case, users can specify how data should be partitioned and shared across workers in a cluster of multi-cores. The system optimizes the communication needed between workers.

In the Myria system (Wang et al. Reference Wang, Balazinska and Halperin2015) for large-scale data analytics, Datalog queries, possibly involving aggregates and recursion, are translated into parallel query plans to be executed in a shared-nothing multi-core cluster. Both synchronous and asynchronous evaluation schemes are possible.

Concerning the exploitation of parallelism in Datalog-based approaches to data analysis, we also mention RecStep (Fan et al. Reference Fan, Zhu, Zhang, Albarghouthi, Koutris and Patel2019), an implementation of a general-purpose Datalog engine built on top of a parallel RDBMS. The target architecture is a single-node multi-core system and the language extension of plain Datalog offers aggregates and stratified negation. Yedalog (Chin et al. Reference Chin, von Dincklage, Ercegovac, Hawkins, Miller, Och, Olston and Pereira2015) extends Datalog to enable computations and analysis on large collections of semi-structured data. The DeALS system (see the paper by Shkapsky Reference Shkapsky2016 and the references therein) which supports standard SQL-like aggregates as well as user-defined aggregates, combined with (stratified) negation, has been ported to both multi-core platforms and distributed memory systems (using the Spark library).

In Sections 6 and 7 we will also show other approaches to Datalog parallelism.

5.2 Search (Or-) parallelism in ASP

The most popular ASP solvers proposed in the literature implement search processes that explore the search space of possible truth value assignments to the atoms of the ground program – directly or indirectly (e.g. through activation of program rules). This has prompted the study of parallelization of the search process, by supporting the concurrent exploration of different parts of the search space. This form of parallelization resembles the exploitation of Or-Parallelism in Prolog, as discussed earlier.

5.2.1 General design

The concept of Or-parallelism (or Search parallelism) in ASP emerged early on in the history of the paradigm – the first popular ASP solvers appeared around 1997 (e.g. Smodels Niemela and Simons Reference Niemela and Simons1997, DLV Citrigno et al. Reference Citrigno, Eiter, Faber, Gottlob, Koch, Leone, Mateis, Pfeifer and Scarcello1997) and the first reports of parallel ASP solvers were presented in 2001 (El-Khatib and Pontelli Reference El-Khatib and Pontelli2000; Finkel et al. Reference Finkel, Marek, Moore, Truszczyński, Provetti and Tran2001; Pontelli Reference Pontelli2001). These first Or-parallel ASP implementations originated from modifications of the Smodels inference engine. The intuitive structure of the algorithm underlying Smodels is illustrated in Algorithm 2. The procedure incrementally constructs a partial interpretation by identifying atoms as being true (added to $S^+$ ) or false (added to $S^-$ ). If all atoms of the Herbrand base of the program P ( $B_P$ ) are assigned, the solution is returned. The Expand procedure is used to deterministically expand the partial interpretation constructed so far, using the clauses of the program to infer the truth value of other atoms. Intuitively, if $\langle S^+,S^-\rangle$ is the current partial interpretation, the Expand procedure determines a subset of

\begin{equation*}\langle \{A\:|\: P \cup S^+ \cup \{\neg B\:|\: B\in S^-\} \models A\}, \{A\:|\: P \cup S^+ \cup \{\neg B\:|\: B\in S^-\} \models \neg A\}\rangle\end{equation*}

The implementation of Expand in Smodels uses inference rules which are equivalent to the computation of the well-founded model of the program $P\cup S^+\cup \{\leftarrow p\:|\:p\in S^-\}$ (similar to the program transformations proposed by Brass et al. Reference Brass, Dix, Freitag and Zukowski2001). The Select_Atom function heuristically selects an unassigned atom to assign next, while the Choose function creates a non-deterministic choice between the two following alternatives. Or-parallelism arises from the concurrent exploration of the alternatives generated by Choose – see also Figure 6.

Fig. 6.

Intuition of Or-Parallelism in ASP.

Algorithm 2:

Intuition of Smodels.

The model proposed by Finkel et al. (Reference Finkel, Marek, Moore, Truszczyński, Provetti and Tran2001) relies on a centralized scheduling structure, with a single central master and a collection of slave workers. The master is responsible for coordinating the distribution of unexplored parts of the search tree among workers. Paths in the search tree are described as binary strings (i.e. a 0 represent a left child while a 1 represents a right child). Initially, each worker receives the complete ASP program and a binary string which is used to deterministically choose its position in the search tree (Figure 7). A similar model has been adapted for execution on distributed memory architectures in the claspar system (Ellguth et al. Reference Ellguth, Gebser, Gusowski, Kaufmann, Kaminski, Liske, Schaub, Schneidenbach and Schnor2009; Schneidenbach et al. Reference Schneidenbach, Schnor, Gebser, Kaminski, Kaufmann and Schaub2009). The claspar system adds the ability of organizing workers in a deeper hierarchical structure and the ability to exchange learned nogoods across parallel computations.

Fig. 7.

Examples of initial distribution in ParStab: 0 left child, 1 right child.

The binary search tree created by the execution of Smodels is irregular – thus leading to an unbalanced distribution of work among workers. When a worker has exhausted its assigned search tree, it requests a new branch to the master; in turn, the master requests work from a randomly chosen worker. The selected worker will transfer the highest (i.e. closest to the root) choice point with open alternatives to the master for redistribution, marking it as fully explored. This approach avoids the risk of different workers exploring the same branch of the search tree. Selecting unexplored choices closer to the root is a known heuristic aimed at increasing the chance of assigning to a worker a potentially large task.

The system initially proposed by El-Khatib and Pontelli (Reference El-Khatib and Pontelli2000) and Pontelli (Reference Pontelli2001), and later fully developed by Balduccini et al. (Reference Balduccini, Pontelli, El-Khatib and Le2005) and Pontelli et al. (Reference Pontelli, Le and Son2010), represents a fully Or-parallel implementation of Smodels with symmetric workers – without the presence of a master serving as broker for distribution of unexplored tasks. Each worker explores parts of the search tree as well as participates in the distribution of unexplored parts of the search tree to other, idle, workers. Thus, each worker alternates (1) computation steps (corresponding to the execution of Smodels), and (2) load balancing steps to relocate workers to branches of the search tree with unexplored alternatives. The design has been developed on both shared memory systems (Pontelli Reference Pontelli2001; Balduccini et al. Reference Balduccini, Pontelli, El-Khatib and Le2005) as well as on Beowulf clusters (Pontelli et al. Reference Pontelli, Le and Son2010). The two implementations have a similar design, where branches of the search tree are represented locally within the data structures of each worker (i.e. a complete Smodels solver).

5.2.2 Scheduling and heuristics

The process of load balancing is essential to allow workers to remain busy and increase the degree of parallelism exploited. Load balancing is composed of two activities: (1) scheduling, which is used to identify the location in the search tree where an idle worker should be moved, and (2) task sharing, which is the actual process of moving the worker to the new location.

Several dimensions have been explored for both scheduling and task sharing, and experimental comparisons have been presented by Le and Pontelli (Reference Le and Pontelli2005), Le and Pontelli (Reference Le and Pontelli2007), Pontelli et al. (Reference Pontelli, Le and Son2010). While significant performance differences can be observed, thus making it hard to identify a clear winning strategy, on average the most effective methodology for scheduling and task sharing is the Recomputation with Reset strategy (Figure 8). Intuitively, scheduling is based on selecting the highest node in the tree with unexplored alternatives. The process of task sharing is realized by restoring the state of the worker to the root of the tree (Figure 8 top left) and repeating the computation from the root to the selected node of the tree (Figure 8 top right). The latter operation can be performed efficiently using a single Expand operation. The idle worker is then able to restart the computation with an unexplored alternative from the selected node (Figure 8 bottom). The idea of recomputation in Or-parallelism is not novel – it has been explored in the context of Or-parallelism in Prolog by several systems, such as the Delphi model (Clocksin and Alshawi Reference Clocksin and Alshawi1988) and the Randomized Parallel Backtracking model (Janakiram et al. Reference Janakiram, Agrawal and Mehrotra1988; Lin Reference Lin1989).

Fig. 8.

Recomputation with reset.

5.3 Parallel grounding

In this section we focus on the parallelization of the grounding stage that transforms the first order logic program P into an equivalent propositional program ground(P). P uses a finite set of constant symbols $\mathcal{C}$ . A rule using n different variables should, in principle, be replaced by $|\mathcal{C}|^n$ ground clauses where variables are replaced by elements of $\mathcal{C}$ in all possible ways. This simple idea can be easily parallelized; however it might lead to a ground program of unacceptable size. Since the first grounder Lparse (Simons et al. Reference Simons, Niemelä and Soininen2002) this problem has been addressed by splitting program-defined predicates into two classes: domain and non-domain predicates. The precise definition of domain predicates has been changed in the evolution of grounders, but the idea is that they are those predicates that can be extensionally computed deterministically using a bottom-up procedure. In particular, all predicates extensionally defined by ground facts are domain predicates. Every variable occurring in a rule should occur in the argument of a positive atom in the body as well to help grounding (domain/range restriction). This introduces a partial ordering between parts of the program. This ordering has been exploited by parallel grounders, as well. Precisely, parallelism for grounding can be implemented at three different levels:

1. 1. Components Level parallelism is based on the analysis of the strongly connected components (SCC) of the dependency graph $\mathcal{G}(P)$ . The program is split in modules and the grounding follows the topological ordering of the SCC. Independent modules can be managed in parallel and synchronization points are used to control the overall process.

2. 2. Rules Level parallelism. Each rule can be, in principle, grounded in parallel. Non-recursive rules are grounded first. Grounding of rules involved in recursion are delayed. Their grounding follows the bottom-up fixpoint procedure (precisely, the semi-naive evaluation procedure developed for Datalog) that ends when no new ground clauses are generated.

3. 3. Single Rule Level parallelism takes care of parallelizing into different threads the grounding of a single rule. Assume a rule contains n different variables $X_1,\dots,X_n$ . Each variable $X_i$ , $i \in \{1,\dots,n\}$ , occurs in an atom based on a domain predicate and we know that $X_i$ ranges in the set of constant symbols $\mathcal{C}_i \subseteq \mathcal{C}$ . The grounding of the rule produces $\Pi_{i=1}^n |\mathcal{C}_i|$ ground instances. It is expected that $|\mathcal{C}_i| \ll |\mathcal{C}|$ but, in any case, the number of instances grows exponentially with n. Thus, implementing this form of parallelism is crucial for rules containing several variables.

The research in parallel grounding can be traced back to the work of Balduccini et al. (Reference Balduccini, Pontelli, El-Khatib and Le2005), where authors exploited the property of range restrictedness of Lparse programs and implemented single rule parallelization following a static partition of rules. Let us observe that each parallel processor is assumed to be aware of the domain predicates used in the rule. The group of University of Calabria has deeply investigated the multilevel parallelism hierarchy described above (see, for instance, the work by Calimeri et al. Reference Calimeri, Perri and Ricca2008 and by Perri et al. Reference Perri, Ricca and Sirianni2013) with outstanding performance improvements. An interesting observation of these works is the evidence that, in the majority of the explored benchmarks, single rule level parallelism represents the dominating component for performance improvement.

5.4 Other forms of parallelism

Alternative forms of parallelism have also been explored in the context of ASP.

Lookahead parallelism has been considered as a technique to improve performance of the deterministic steps of the ASP computation. Lookahead is an optimization technique introduced in the Smodels system. Lookahead is part of the Select_Atom operation. Before selecting a chosen atom, the lookahead operation performs a quick set of Expand operations (which are typically very efficient) on undefined atoms: given a partial answer set $\langle S^+, S^-\rangle$ and a set of atoms A such that $A \cap (S^+\cup S^-)=\emptyset$ , for each $x\in A$ the system executes both Expand $(P,\langle S^+\cup\{x\},S^-\rangle)$ and Expand $(P, \langle S^+, S^-\cup\{x\}\rangle)$ . If both of them leads to failure, then backtracking should be initiated; if only one of them leads to failure, then x can be added to the partial answer set and the process continue; if both operations succeed without failure, then the element can be considered as an option for the non-deterministic choice. The intuition of parallel lookahead is to perform such tests concurrently to eliminate unsuitable options for choice. Balduccini et al. (Reference Balduccini, Pontelli, El-Khatib and Le2005) demonstrate speedups in the range from 5 to 24 using 50 processors on a variety of benchmarks.

5.5 Portfolio parallelism

ASP solvers, constraint solvers (used in CLP), and SAT solvers (used as auxiliary solvers in logic programming languages such as Picat Zhou and Kjellerstrand Reference Zhou and Kjellerstrand2016) are composed of many distinguished parts, but they share a common scheme: (1) choice of a not yet instantiated variable/literal, (2) choice of the value (e.g. true/false for ASP and SAT solvers, a domain element in many constraint solvers), (3) deterministic propagation of the value chosen that allows us to reduce the remaining part of the search space. When the assignments made so far cause a conflict (e.g. a rule/clause/constraint unsatisfied), a (4) backtracking/backjumping activity starts, possibly after a (deterministic) analysis of the conflict that might lead to (5) learning new clauses/constraints. These clauses are implied by the problem and therefore from a logic point of view they are redundant, but their explicit addition can speed up the remaining part of the search, thanks to the new inference power they support. Moreover, the search can be sometimes restarted (6) from the beginning but new parts of the search tree are visited thanks to the new constraints.

This general scheme supports many variants, especially for the choices (1), (2), and (6). Thus, one could use different solvers (a portfolio of algorithms Gomes and Selman Reference Gomes and Selman2001) or a solver with many parameters that can, in principle, be tuned to the particular instance of the problem to provide the best possible performance (algorithm configuration). A solver has a set of parameters with values in discrete or continuous domains. Even if continuous domains are discretized, the number of possible tuples of parameter values would make a manual optimization infeasible. The algorithm configuration approach applies statistical techniques to automatically find an “optimal" configuration for a family of problem instances that follow a certain distribution. This is usually implemented by iterating a local search routine starting from an initial solution and verifying it in a set of training instances.

An easy way of exploiting parallelism in this context could be simply that of using a set of (fixed) algorithms and run them in parallel, and taking the first solution generated by one of the parallel threads. In the case of algorithm configuration, local search techniques can be run in parallel (with different random choices) and the best solution in a finite amount of time is retrieved. Thus, algorithm portfolio and configuration activities will benefit from a parallel architecture.

The research in the area has been rather active in the last years showing excellent performances. The heuristics that drive to the choices (1) and (2) can be static (computed only at the beginning of the search) or dynamic (updated during the search) and based on the analysis of some features. Typical features are of the following types (as described by Maratea et al. Reference Maratea, Pulina and Ricca2014):

Problem size features number of rules r, number of atoms a, ratios $r/a$ and ratios reciprocal $a/r$ of the ground program.

Balance features ratio of positive and negative atoms in each rule body, ratio of positive and negative occurrences of each variable, fraction of unary, binary, and ternary rules, etc

Proximity to Horn features fraction of Horn rules and number of atoms occurrences in Horn rules.

ASP peculiar features number of true and disjunctive facts, fraction of normal rules and constraints, head sizes, occurrences of each atom in heads, bodies and rules, occurrences of true negated atoms in heads, bodies and rules, sizes of the SCCs of $\mathcal{G}(P)$ , number of Head-Cycle Free (HCF) and non-HCF, etc

Moreover, dynamic features can consider the ratio of the variables currently assigned by propagation vs those assigned non-deterministically, the number of restarts, the number of rules learned since the last restart, and so on. Modern solvers offer a number of built-in sets of parameter configurations. For instance, the heuristics frumpy of the ASP-solver clasp (Gebser et al. Reference Gebser, Kaufmann, Kaminski, Ostrowski, Schaub and Schneider2011b) sets the following parameters

In particular, it uses the variable selection rule developed for the SAT solver Berkmin (Goldberg and Novikov Reference Goldberg and Novikov2007). Furthermore, clasp allows the user to choose the auto option that select the most promising configuration based on the features of the current instance or to input a precise configuration from a file.

The selection of the algorithm is implemented using supervised and unsupervised machine learning techniques. In the case of algorithm configuration, instead, parameters are often tuned using local search technique. We give a brief summary here of the approaches in the area of SAT, ASP, and Constraint Programming (a complete and up-to-date survey can be found in the paper by Tarzariol Reference Tarzariol2019).

SATzilla (Xu et al. Reference Xu, Hutter, Hoos and Leyton-Brown2008) is the first algorithm selection implementation in the area of SAT solving. Several versions follow its first prototype adding new statistical techniques and obtaining much more performances. CLASPfolio (Gebser et al. Reference Gebser, Kaminski, Kaufmann, Schaub, Schneider and Ziller2011a) executes algorithm selection among a set of twelve configurations of the clasp solver with “complementary strengths" using support vector regression techniques. A static approach is made by ME–ASP (Maratea et al. Reference Maratea, Pulina and Ricca2014) analyzing a set of parameters as explained above.

A common experience in problem-solving is that (often) a solver either solves a problem in few seconds or does not solve it in days. Then, the idea is to use the algorithm portfolio with a limited time and analyze the output for selecting the best algorithm and repeat this several times during the search. This technique is called algorithm scheduling. In this case, it is crucial that the portfolio selection is made in parallel. This technique has been implemented and applied with success in Constraint Programming by SUNNY – SUbset of portfolio solvers by using k-Nearest Neighbor technique to define a lazY learning model – (Amadini et al. Reference Amadini, Gabbrielli and Mauro2014), in ASP by aspeed (Hoos et al. Reference Hoos, Kaminski, Lindauer and Schaub2015) that is based on the clasp solver, and in SAT by Malitsky et al. (Reference Malitsky, Sabharwal, Samulowitz and Sellmann2012). All the three proposals exploit multi-core architectures and parallelism.

Portfolio parallelism has been considered in the second revision of claspar (Schneidenbach et al. Reference Schneidenbach, Schnor, Gebser, Kaminski, Kaufmann and Schaub2009). Portfolio parallelism is realized by instructing a pool of workers to attempt to solve the same problem but with different configurations of the solver – for example, different heuristics and different parameters to guide search. This allows the workers to “compete" in the resolution of a problem by creating different organizations of the search space and exploring them in parallel. Schneidenbach et al. (Reference Schneidenbach, Schnor, Gebser, Kaminski, Kaufmann and Schaub2009) provided speedups of the order of 2 using this technique.

Some systems combine algorithm portfolio and configuration. CLASPfolio 2 (Hoos et al. Reference Hoos, Lindauer and Schaub2014) improves the selection technique of CLASPfolio by defining a static pre-solving scheduling that may intervene if the learned selection model performs poorly. AutoFolio (Lindauer et al. Reference Lindauer, Hoos, Hutter and Schaub2015) executes Algorithm Configuration over CLASPfolio 2, choosing the optimal learning techniques with its optimal parameters configuration.

As a final observation, the use of portfolio techniques may have an impact on the “observable semantics" of a system in some situations. In the context of solving optimization problems or in determining all models of a program, portfolio techniques will not modify the behavior of the system; on the other hand, if the system is used to determine one answer set, then portfolio techniques may lead to a different answer set than the one found by a sequential system.

6.1 Introduction to large-scale data paradigms

The literature has offered access to popular infrastructures and paradigms to facilitate the development of applications on distributed platforms, taking advantage of both the parallelism and the ability to distribute data over the memory hierarchies of multiple machines. In this section, we will briefly review some of the fundamentals of such distributed programming infrastructures (see, e.g. Hadoop and Spark documentation White Reference White2015; Karau et al. Reference Karau, Konwinski, Wendell and Zaharia2015 for further insights).

Distributed File Systems (DFS)

are designed to provide a scalable and highly fault-tolerant file system, which can be deployed on a collection of machines using possibly low-cost hardware. The Hadoop Distributed File System (HDFS) represents a popular implementation of a DFS (Apache 2020a). It adopts a master-slave architecture. NameNodes (masters) regulate access to files, track data files, and store metadata. File content is partitioned into small chunks (blocks) of data distributed across the network. Chunks may range in size (typically, from 16 to 64 MB) and replicated to provide redundancy and seamless recovery in case of hardware failures. An HDFS instance may consist of thousands of server machines and provides hardware failure detection, a write-once-read-many access model, and streaming data access.

Map-Reduce

is a distributed programming paradigm designed to analyze and process large data sets. The foundations of the concept of Map-Reduce can be traced back to fundamental list operations in functional programming. However, the concept gained popularity as a rigid paradigm for distributed programming, piloted by Google and popularized in implementations as in the Apache Hadoop framework (Ullman Reference Ullman2010; Apache 2020a). The Map-Reduce paradigm provides a basic interface consisting of two methods (see Figure 9–left):

• map() that maps a function over a collection of objects. It outputs a collection of “key-value" tuples;

• reduce() that takes as input a collection of key-value pairs and merges the values of all entries with the same key.

Fig. 9.

Map-Reduce paradigm.

The map method is usually performed in order to transform and filter a collection, while the reduce method usually performs a summary (e.g. counting the elements of a collection, or the word frequencies in a text).

Extended implementations of Map-Reduce have been devised to allow the iterative execution (Figure 9–right) of Map-Reduce cycles optimizing communication (Bu et al. Reference Bu, Howe, Balazinska and Ernst2010; Ekanayake et al. Reference Ekanayake, Li, Zhang, Gunarathne, Bae, Qiu and Fox2010).

Graphs Primitives

are made available for HDFS within the framework Apache Spark (Karau et al. Reference Karau, Konwinski, Wendell and Zaharia2015). Spark is an in-memory data processing engine that allows for streaming, data processing, machine learning and SQL functionalities; it relies on the concept of Resilient Distributed Dataset (RDD). A RDD is an immutable, fault-tolerant distributed collection of objects, a read-only, partitioned collection of records, organized into logical partitions, that may be located and processed on different nodes of the HDFS. Among the libraries built on top of Spark Core, GraphX (Apache 2020b) has been developed for graphs modeling and graph-parallel computation. GraphX takes full advantage of the RDD data structure and extends it providing a distributed property multigraph abstraction. Property graphs are directed multigraphs with user-defined objects associated to vertices and edges. They are encoded by pairs of RDDs containing the properties for vertices and edges, and, therefore, inherit RDDs features, such as map, filter, and reduce.

GraphX also gives access to a complete interface for dealing with graphs, as well to an implementation of the Pregel API (Malewicz et al. Reference Malewicz, Austern, Bik, Dehnert, Horn, Leiser and Czajkowski2010). Pregel is a programming model for large-scale graph problems and for fixpoint computations over graphs. A typical Pregel computation consists of a sequence of super-steps. Within each super-step, vertices may interact with their neighbors by sending messages. Each vertex analyzes the set of messages received in the previous super-step (if any) and alters its content according to a user-defined function. In turn, each node can generate new messages to the neighboring nodes. A Pregel computation stops when a super-step does not generate any messages or when other halting conditions are encountered (e.g. a maximum number of iterations).

6.2 Large-scale computing in Datalog

Computing Natural Joins Using Map-Reduce. The underlying core component of most implementations of logic programming using Map-Reduce is the ability to scale the computation of natural join operations over large datasets, as originally studied by Afrati and Ullman (Reference Afrati and Ullman2010), Afrati et al. (Reference Afrati, Borkar, Carey, Polyzotis and Ullman2011).

Let us start considering the basic case of a 2-way join between two relations R and S, denoted by . Let us assume, for the sake of simplicity, that R and S are binary and that the second attribute name of the former is also the first attribute name of the latter (briefly, it can be denoted as ). A Map-Reduce computation can be achieved as follows:

• Each Map task receives tuples drawn from the two relations R and S and produces key-values pairs where the key is the value of the common argument B and the values are the remaining component of the tuple. Namely, $(a,b) \in R$ is mapped to the pair $\langle b, (a,R)\rangle$ , and $(b,c) \in S$ is mapped to $\langle b, (c,S)\rangle$ (R and S are here the names of the two relations).

• Each Reduce task receives a pair with one value of the common argument and a list of all tuples containing such value, for example, $\langle b,L\rangle$ , with $L= [(a,R),(a',R),(c,S),(c',S),\dots]$ and outputs a resulting (ternary) relation RS with tuples $(x,b,y) \in RS$ for each (x,R),(y,S) in the list L.

Thus, the Reduce task exploits data parallelism, using one worker for every single element of the common domain.

This can be extended to the case of multi-way joins, for example, , without the need of cascading two-way joins (which could lead to very large intermediate relations). The model explored relies on the use of hashing. Let us adopt a hash function h for the attribute B, partitioned in $\beta$ buckets, and a hash function g for the common attribute C, partitioned in $\gamma$ buckets.

• Each Map task performs the following hash operations: (1) each tuple $(x,y) \in R$ is mapped to $\langle (h(y),c), (R,x,y)\rangle$ for each $1 \leq c \leq \gamma$ ; (2) each tuple $(y,z) \in S$ is mapped to $\langle (h(y),g(z)), (S,y,z) \rangle$ ; (3) each tuple $(z,w) \in T$ is mapped to $\langle (b,g(z)), (T,z,w)\rangle$ for each $1\leq b \leq \beta$ .

• For each pair $(b,c) \in \{1,\dots,\beta\} \times \{1,\dots,\gamma\}$ there is a Reduce task taking care of pairs of the form $\langle (b,c), L\rangle$ . It outputs the relation RST with tuples (x,y,z,w) for every triple of triples (R,x,y), (S,y,z), (T,z,w) in L.

In this case the distribution of the work is split in $\beta \gamma$ workers, and $\beta$ and $\gamma$ can be defined arbitrarily, thus determining the amount of parallelism we would like to exploit.

Distributed Computation in Datalog. Distributing the computing of the join is the basis for the general computation of bottom-up semantics. In particular, the WebPIE system (Urbani et al. Reference Urbani, Kotoulas, Maassen, van Harmelen and Bal2012) has been designed to support reasoning over RDF stores. The proposed system is capable of determining inferences according to RDFS semantics and the OWL ter Horst fragment (ter Horst 2005). The approach adopted consists of encoding the inference rules capturing these semantics as Datalog rules. The computation of the least fixpoint of the set of rules given a collection of RDF triples is achieved as an iterated Map-Reduce computation, which captures the bottom-up application of the inference rules. The WebPIE system takes advantage of the specific format of the resulting Datalog rules. In the case of RDFS, the system takes advantage of the following factors:

• Each rule has at most two subgoals in the body – thus allowing the use of the Map-Reduce method to compute 2-way natural joins to capture the bottom-up application of each rule;

• In most rules, one of the two subgoals is one of the triples from the RDF store – allowing to optimize the computation by keeping the original triples in memory and matching them with generated ones;

• In most cases, it is possible to order the application of the rules to perform the computation using only three phases of Map-Reduce.

The generalization to arbitrary Datalog programs has been investigated in a variety of works (e.g. those by Afrati et al. Reference Afrati, Borkar, Carey, Polyzotis and Ullman2011 and by Afrati and Ullman Reference Afrati and Ullman2012). While different approaches have provided a variety of optimizations, based on special types of rules (e.g. transitive closures) and size of the definitions of different predicates in the extensional database, they all build on the principles of iterated execution of Map-Reduce workflows, using approaches like HaLoop (Bu et al. Reference Bu, Howe, Balazinska and Ernst2010).

This work direction has been expanded to consider Datalog with a stratified use of negation, as a natural iteration of the approaches described earlier (Tachmazidis and Antoniou Reference Tachmazidis and Antoniou2013). Following the lexicographical sort of the $\mathcal{G}(P)$ , the computation can proceed by iterating the standard Datalog computation (implementing the $T_P$ using joins and exploiting Map-Reduce). The extra ingredient here is handling of negated literals where anti-join needs to be implemented.

For example, given a rule of the type

\begin{equation*}h(A,B) \texttt{:-} p(A,C), q(C,B), \texttt{not } r(B).\end{equation*}

the inference is realized using two Map-Reduce processes:

1. 1. The first implements a natural join to derive the consequences of p(A,C),q(C,B), as discussed earlier (e.g. producing a temporary relation pq(A,C,B));

2. 2. The second Map-Reduce phase performs an anti-join – with analogous structure as the natural join, with the exception that the Reduce step is used to filter out those tuples with matching values in the pq relation and the r relation.

Strong performance results have been presented, thanks also to a broad range of optimizations based on special cases present in the program clauses, such as lack of common arguments in the body of a rule (Tachmazidis and Antoniou Reference Tachmazidis and Antoniou2013).

The approach can be extended to support the computation of the well-founded semantics of logic programs with negation (c.f. Section 2.1), as demonstrated by Tachmazidis et al. (Reference Tachmazidis, Antoniou and Faber2014).

Recent approaches for increasing the speedup of Datalog distributed computation introduce new data structures (Jordan et al. Reference Jordan, Subotic, Zhao and Scholz2019) and exploit network topology (Blanas et al. Reference Blanas, Koutris and Sidiropoulos2020) for increasing the speedup of Datalog distributed computation.

A similar methodology was also used to support inferences in stratified Datalog with defeasible reasoning (Tachmazidis et al. Reference Tachmazidis, Antoniou, Flouris, Kotoulas and McCluskey2012). In simplified terms, a theory is composed of a Datalog program with two types of rules:

\begin{equation*}\begin{array}{lcr}\underset{\textit{non-defeasible}}{\textit{head} \leftarrow \textit{body}} &\phantom{aaaaaaa}& \underset{\textit{defeasible}}{\textit{head} \Leftarrow \textit{body}} \end{array}\end{equation*}

along with an ordering among defeasible rules. The work by Tachmazidis et al. (Reference Tachmazidis, Antoniou, Flouris, Kotoulas and McCluskey2012) explores the use of Map-Reduce in the case of stratified defeasible theories – that is, theories where the dependency graph is acyclic – and thus organized in strata (e.g. the top stratum includes predicates with no outgoing edges, the preceding one contains the predicates with links to the top stratum, etc.). The computation requires two Map-Reduce phases for each stratum, starting with the lowest one. The first Map-Reduce is used to identify applicable rules, using multi-way joins as discussed earlier, recording for each derivable element the producing rule and the defeasible nature of the derivation. The second phase, which is primarily composed of a Reduce step, compares derived rules based on the ordering of defeasible rules to identify undefeated conclusions.

6.3 Large-scale computing and ASP

The use of Map-Reduce and related paradigms to support the execution of ASP has been only recently considered and with only very preliminary results. The extension of the previously mentioned approaches to the case of ASP is not trivial, due to the switch from a bottom-up computation leading to a single minimal model, as in Datalog, to the case of a non-deterministic computation leading to possibly multiple models.

The foundation of the methodology considered for the distributed computation of ASP lies in the ability of modeling the computation of the semantics of logic programming in terms of operations of graphs (Konczak et al. Reference Konczak, Linke and Schaub2006), and taking advantage of existing models for large-scale distributed computations over graphs. This idea was piloted by Maiterth (Reference Maiterth2012).

Basically, from a ground logic program P, a graph akin to the rule dependency graph $\mathcal{G}(P)$ is computed. The idea is of looking for a coloring of the nodes with two colors; colors encode the fact that the body of a rule is activated (by the tentative model) and therefore its head should be in the model, as well, or not. A correspondence between these colorings and answer sets has been established and therefore the computation is delegated to graph operations that can be parallelized exploiting the library GraphX of Apache.

These concepts have been used to develop a preliminary ASP-solver, using the Pregel support of Apache Spark (Igne et al. Reference Igne, Dovier and Pontelli2018; De Bortoli et al. Reference De Bortoli, Igne, Tardivo, Totis, Dovier and Pontelli2019). The approach allows dealing with programs with huge grounding that could not be stored in a single memory. However, answer set computation based on coloring cannot exploit the many heuristics and the conflict-driven clause learning techniques commonly implemented in ASP solvers and the running time is not comparable. Map-Reduce has been experimented with as a general parallel approach for distributed computation of the minimal model and of the well-founded semantics, using an approach based on distributed graph computation (De Bortoli et al. Reference De Bortoli, Igne, Tardivo, Totis, Dovier and Pontelli2019). However, the algorithms proposed are general, architecture-independent and do not exploit any possible optimization. Thus, even if running time scales with the number of processors the performances are not comparable to those of traditional methods in a single processor.

7.1 GPU-based parallelism

GPUs are designed to execute a very large number of concurrent threads on multiple data. The underlying conceptual parallel model is defined as Single-Instruction Multiple-Thread (SIMT). In the CUDA framework, threads are organized and executed in groups of 32 threads called warps. Cores are grouped in a collection of Streaming MultiProcessors (SMs) of the same size and warps are scheduled and executed on the SMs. Threads in the same warp are expected (but not forced) to follow the same program address. Whenever two (or more) groups of threads belonging to the same warp fetch/execute different instructions, thread divergence occurs. In this case the execution of the different groups is serialized and the overall performance decreases.

From the programmer’s perspective, threads are logically grouped in 3D blocks and blocks are organized in 3D grids. Each thread in a grid executes an instance of the same kernel (namely, a C/C++ or Fortran procedure). A typical CUDA program includes parts meant for execution on the CPU (the host) and parts meant for parallel execution on the GPU (the device). The host program contains instructions for device data initialization, grids/blocks/threads configuration, kernel launch, and retrieval of results. GPUs also exhibit a hierarchical memory organization. The threads in the same block share data using high-throughput on-chip shared memory organized in banks of equal dimension. Threads of different blocks can only share data through the off-chip global memory.

To take full advantage of GPU architecture, one has to:

• proficiently distribute the workload among the cores to maximize GPU occupancy (exploit all available device resources, such as SMs, registers, shared memory,…) and minimize thread divergence;

• achieve the highest possible throughput in memory accesses – namely, (1) adopt strided access pattern to shared memory to minimize bank conflicts (i.e. accesses to locations in the same bank by threads of the same block. In this case accesses are serialized); (2) employ coalesced accesses to global memory (see Figure 9), as this minimizes the number of memory transactions.

Fig. 10.

Memory-access patterns on an array data structure by a group of four threads $t_0-t_3$ . Coalesced access pattern (left) and strided access pattern (right).

These requirements make the model of parallelization used on GPUs deeply different from those employed in more “conventional" parallel architectures. Existing serial or parallel solutions need substantial re-engineering to become profitably applicable in the context of GPUs.

The design of parallel engines for logic programming taking full advantage of computational power of modern massively parallel graphic accelerators, posed a number of challenges typically found in irregular applications. Briefly, applications are considered irregular when the exploitation of parallelism changes while the execution proceeds. Irregularity appears both in data accesses and in control flow. It is mainly due to the intrinsic nature of the data, often represented through pointer-based data structures such as lists and graphs, and to the concurrency patterns of the related algorithms. Because of data-dependencies these applications frequently produce concurrent activity per data element, require unpredictable fine-grain communications, and exhibit peculiar load imbalances (Lumsdaine et al. Reference Lumsdaine, Gregor, Hendrickson and Berry2007). Needless to say, the presence of irregularity makes it hard to maximize GPU occupancy and memory throughput, while minimizing thread divergence and bank conflicts. This makes the development of solutions to irregular applications a difficult task, where high performance and scalability are not an obvious outcome. This is especially true when porting to GPUs serial algorithms or even solutions originally targeted at more traditional parallel/distributed architectures, such as cluster and multi-core systems. Parallel graph algorithms constitute significant examples, that, like SAT/ASP solving, are characterized by the need to process large, sparse, and unstructured data, and exhibit irregular and low-arithmetic intensity combined with data-dependent control flow and memory access patterns (Dal Palù et al. Reference Dal Palù, Dovier, Formisano and Pontelli2015; Formisano et al. Reference Formisano, Gentilini and Vella2017; Dovier et al. Reference Dovier, Formisano and Vella2019; Formisano et al. Reference Formisano, Gentilini and Vella2021).

7.2 GPU-based Datalog

Datalog engines can be obtained by exploiting (parallel) implementations of relational algebra operations select, join, and projection. This approach is, in principle, viable also for GPU-based parallelism or, more generally, for the case of parallel/distributed heterogeneous architectures (i.e. systems encompassing different devices, such as multi-cores, GPUs, FPGAs, etc). Several proposals appeared in literature enabling the mechanization on (multi-)GPUs systems and heterogeneous architectures, of relational operators and SQL, also including aggregate operators (Huang and Chen Reference Huang and Chen2015; Wang et al. Reference Wang, Xiong, Li, Shi, Li and Gao2018; Rui and Tu Reference Rui and Tu2017; Diamos et al. Reference Diamos, Wu, Wang, Lele and Yalamanchili2013; Saeed et al. Reference Saeed, Young and Yalamanchili2015).

Concerning Datalog, Martinez-Angeles et al. (Reference Martinez-Angeles, de Castro Dutra, Santos Costa and Buenabad-Chávez2014), Martinez-Angeles et al. (Reference Martinez-Angeles, Wu, de Castro Dutra, Santos Costa and Buenabad-Chávez2016) design a GPU-based engine by exploiting GPU-accelerated relational algebra operators. The computation order is driven by the dependency graph of the Datalog program and fixpoint procedures are employed in case of recursive predicates. The host preprocesses the program, converting each rule into an internal numerical representation; the host decides which relational algebra operators are needed for each rule, while their executions are delegated to the device. In particular, select is implemented using three different device function executions. The first one marks the rows of a matrix that satisfy the selection predicate, the second one performs a prefix sum on the marks to determine the size of the results buffer and the location where each GPU thread must write the results, and the last device function writes the results. The projection operator simply moves the elements of each required column to a different location. Concerning join, the authors adopted a standard Indexed Nested Loop Join algorithm. We refer the reader to the mentioned works by Martinez-Angeles et al. for the details on the CUDA implementation and a report on experimental evaluations showing significant speedups of the GPU-based engine with respect to engines running on single and multi-core CPUs. The experiments demonstrate scalability in presence of extensional databases with several million of tuples.

The Datalog-like language LogiQL is used as front-end in the Red Fox system (Wu et al. Reference Wu, Diamos, Sheard, Aref, Baxter, Garland and Yalamanchili2014). LogiQL is a variant of Datalog including aggregations, arithmetic, integrity constraints and active rules. Red Fox provides an environment enabling relational query processing on GPUs, through compilation of LogiQL queries into optimized GPU-based relational operations. Then, an optimized query plan is generated and executed on the device. The approach is demonstrated to be faster than the corresponding (commercial) CPU-oriented implementation of LogiQL.

Nguyen et al. (Reference Nguyen, Sakama, Sato, Inoue, Kaenampornpan, Malaka, Nguyen and Schwind2018) propose a different approach to Datalog parallelization, not directly relying on parallelization of relational algebra. In this work, the computation of the least model of a definite program is obtained by first translating the program into a linear algebra problem. Then, the multi-linear problem is solved on GPU by using standard CUDA libraries for matrix computations. The solution of the multi-linear problem identifies the model of the program. A similar approach is also viable to compute stable models of disjunctive logic programs. The approach demonstrates encouraging performance results for randomly generated programs with over 20,000 rules.

7.3 GPU-based ASP

The first attempt in exploiting GPU parallelism for ASP solving has been described by Dovier et al. (Reference Dovier, Formisano, Pontelli and Vella2015), Dovier et al. (Reference Dovier, Formisano, Pontelli and Vella2016), Dovier et al. (Reference Dovier, Formisano and Vella2019), proposing the solver yasmin. The authors design a conflict-driven ASP-solver reminiscent of the conventional structure of sequential conflict-driven ASP solvers (Gebser et al. Reference Gebser, Kaminski, Kaufmann and Schaub2012). However, substantial differences lay in both the implemented algorithms and in the specific solutions adopted to optimize GPU occupancy, minimize thread divergence, and maximizing memory throughput. To this aim, difficult to parallelize and intrinsically sequential components of serial solvers have been replaced by parallel counterparts. More specifically, (1) the notion of ASP computations (Liu et al. Reference Liu, Pontelli, Son and Truszczyński2010) is exploited to avoid the introduction of loop formulas and the need of performing unfounded set checks (Gebser et al. Reference Gebser, Kaminski, Kaufmann and Schaub2012); (2) a parallel conflict analysis procedure is used as an alternative to the sequential resolution-based technique used in clasp. Memory accesses have been regularized by suitably sorting input data with respect to size of rules, by storing them using Compressed Sparse Row (CSR) format, and by designing specific device functions, each one tailored to process groups of rules of homogeneous size. All this enables efficient balanced mapping of data to threads. Moreover, to maximize device performance, the authors exploited specific features supported by CUDA framework, such as shuffling (a high efficient intra-warp communication mechanism) and stream-based parallelism (a support to concurrent kernels asynchronous execution available in the CUDA programming framework).

Algorithm 3:

Host code of the main procedure pthreaded yasmin of the pthreaded ASP-solver yasmin (simplified).

GPU-based parallelism can be combined with host-parallelism by exploiting host POSIX pthreads and CUDA streams. In particular, Algorithm 3 (simplified form of the ASP-solver designed by Dovier et al. Reference Dovier, Formisano and Vella2019) shows the main part of the host code of the multi-pthread procedure pthreaded_yasmin which first splits (line 1) the given problem into a number $\mathit{Npb}$ of subproblems by applying some heuristics/criteria. The simplest possibility would be to apply Or-parallelism and split the search space by assigning in different ways the truth values of a subset of the input atoms. Then, the procedure (lines 2–3) spawns a pool of $\mathit{N}$ host POSIX threads. Note that these pthreads share host variables (such as P, $\mathit{Parts}$ ,…), but each pthread issues device commands in a different CUDA stream. Each pthread created in line 3 runs an instance of the host procedure yasmin_launcher (described in Algorithm 4). After the termination of all issued device commands (lines 4–6) results are collected and output (line 7).

Algorithm 4:

Host code of yasmin launcher, called in Algorithm 3 (simplified).

Algorithm 4 describes the procedure yasmin_launcher executed by each concurrent pthread. Such procedure iterates by extracting (in mutual exclusion) one of the unsolved subproblems (line 2) and by running an instance of the CUDA solver in a dedicated CUDA stream (line 3). Notice that, since each pthread runs an instance of the solver in a private CUDA stream, each of them proceeds by issuing commands (memory transfers, kernel launches, etc) in such stream, independently and concurrently with the other solver instances. This helps in maximizing GPU occupancy, because it permits overlapping between computation and memory transfers and allows scheduling of warps on all available SMs.

The combination of host-parallelism and device-parallelism opens up further refinements, such as the introduction of techniques like parallel lookahead (Dovier et al. Reference Dovier, Formisano and Pontelli2018), the development of more powerful multiple learning schemes (Formisano and Vella Reference Formisano and Vella2014), and paves the way to the exploitation of multi-GPU and heterogeneous architectures in ASP solving.