A Parallelized Variant of Junker’s QUICKXPLAIN Algorithm

Preprint - please cite: C. Vidal Silva, A. Felfernig, J. Galindo, M. Atas, and D. Benavides, A Parallelized Variant of Junker’s QuickXPlain Algorithm, 25th International Symposium on Methodologies for Intelligent Systems, Graz, Austria, pp. 457–468, LNAI, 12117, 2020. A Parallelized Variant of Junker’s QUICKXPLAIN Algorithm Cristian Vidal Silva1, Alexander Felfernig2, Jos´ e A. Galindo1, M¨ usl¨ um Atas2, and David Benavides1 1Catholic University of the North [email protected] 2University of Sevilla {benavides,jagalindo}@us.es 3Graz University of Technology {afelfernig,muatas}@ist.tugraz.at Abstract. Conflict detection is used in many scenarios ranging from interactive decision making to the diagnosis of potentially faulty hardware components or models. In these scenarios, the efficient identification of conflicts is crucial. Junker’s QUICKXPLAIN is a divide-and-conquer based algorithm for the determination of preferred minimal conflicts. Motivated by the increasing size and complexity of knowledge bases, we propose a parallelization of the original algorithm that helps to significantly improve runtime performance especially in complex knowledge bases. In this paper, we introduce a parallelized version of QUICKXPLAIN that is based on the idea of predicting and executing parallel consistency checks needed by QUICKXPLAIN. 1 Introduction Conflict detection is used in many applications of constraint-based representations (and beyond). Examples thereof are knowledge-based configuration [13] where users define requirements and conflict detection is in charge of figuring out minimal sets of potential changes to the given requirements in order to restore consistency (if the configurator is not able to identify a solution), recommender systems [3,10], and many other applications of model-based diagnosis [9]. Especially in interactive settings, there is often a need of identifying preferred conflicts [7,11], for example, users of a car configurator or a camera recommender who have strict preferences regarding the upper price limit, are more interested in relaxations related to technical features (e.g., related to the availability of a skibag in a car or a wide-aperture lens in a pocket camera). Conflict detection helps to find combinations of constraints in the knowledge base that are responsible for an inconsistency. QUICKXPLAIN is such a conflict detection algorithm which is frequently used and works for constraint-based representations, description logics, and SAT solvers [7]. The algorithm is based on a divide-and-conquer approach where consistency analysis operations are based on the division of a constraint set C={c1..cm}into two subsets Ca={c1..ck}and Cb={ck+1..cm}assuming, for example, k=bm 2c. If Cbis inconsistent, the consideration set Ccan be reduced by half since Camust not be analyzed anymore (at least one conflict exists in Cb). Depending on the QUICKXPLAIN variant, either Caor Cbis checked for consistency. Conflict detection is typically applied in combination with conflict resolution which helps to resolve all existing conflicts. In this context, the minimality (irreducability) of conflict sets is important since this allows to resolve each conflict by simply deleting one of the elements in the conflict set. The elements to be deleted to restore global consistency are denoted as hitting set and can, for example, be determined on the basis of a hitting set directed acyclic graph [9]. Due to the increasing size and complexity of knowledge bases, there is an increasing need to further improve the performance of solution search and conflict detection / hitting set calculation [2,4,5,8]. Parallelizations of algorithms in these scenarios have been implemented in different contexts. Approaches to parallelization have, for example, been proposed on the reasoning level [2] where the determination of a solution is based on the idea of identifying subproblems which can be solved to some degree independently by the available cores. Due to today’s multicore CPU architectures, such parallelization techniques become increasingly popular in order to be able to better exploit the offered computing resources. A similar motivation led to the development of parallelization techniques in modelbased diagnosis [9]. J. Marques-Silva. et al [6] propose a parallelization approach for hitting set determination where Reiter’s approach to model-based diagnosis is parallelized by a level-wise expansion of a breadth-first search tree with the goal of computing minimal (cardinality) diagnoses. On each level, (minimal) conflict sets are determined in parallel, however, the determination of individual conflict sets is still a sequential process (based on QUICKXPLAIN [7]). In diagnosis search, the efficient determination of minimal conflicts is a core requirement [6]. Especially in constraint-based reasoning scenarios, the identification of minimal conflict sets is frequently based on QUICKXPLAIN [7]. Compared to iterative approaches of removing elements from inconsistent constraint sets [1], QUICKXPLAIN follows a divide-and-conquer strategy that helps to reduce the number of needed consistency checks. Although the algorithm is often used in interactive settings with challenging runtime requirements, up-to-now no parallelized version has been proposed. In this paper, we propose an algorithm that enables efficient parallelized minimal conflict detection and thus helps a.o. to significantly improve the runtime performance of conflict detection in interactive applications. The contributions of this paper are the following. First, we show how to parallelize conflict detection with look-ahead strategies that scale with the number of available computing cores. Second, we show how to integrate our approach with the QUICKXPLAIN algorithm that is often used in constraint-based applications. Third, we show the applicability and improvements of our approach on the basis of performance evaluations. Finally, we point out in which way the proposed approach can help to improve the performance of existing diagnosis approaches. The remainder of the paper is organized as follows. In Section 2, we introduce the basic idea of Junker’s QUICKXPLAIN using a working example. Thereafter, in Section 3 we introduce a parallelized variant of the algorithm. In Section 4, we analyze the proposed approach and report the results of a performance evaluation which shows significant improvements compared to standard QUICKXPLAIN. The paper is concluded with Section 5. 2 Calculating Minimal Conflicts In the remainder of this paper, we introduce our approach to parallelized conflict detection on the basis of constraint-based knowledge representations [14]. A conflict set can be defined as a minimal set of constraints that is responsible for an inconsistency, i.e., a situation in which no solution can be found for a given constraint satisfaction problem (CSP) (see Definitions 1–2). Definition 1. AConstraint Satisfaction Problem (CSP) is a triple (V,D,C) with a set of variables V={v1..vn}, a set of domain definitions D={dom(v1)..dom(vn)}, and a set of constraints C={c1..cm}. Definition 2. Assuming the inconsistency of C, a conflict set can be defined as a subset CS ⊆C:CS is inconsistent. CS minimal if ¬∃CS0:CS0⊂CS. Examples of a CSP and a conflict set are the following (see Examples 1–2). Example 1. An example of a CSP for car configuration is the following: V= {cartype, fuel, pdc, color, skibag},D={dom(cartype) = [s, c], dom(fuel) = [p, d], dom(pdc) = [y, n], dom(color) = [b, r, g], dom(skibag) = [y, n]}, and C= {c1:fuel =d, c2:skibag =y, c3:color =b, c4:cartype =c, c5:pdc =y, c6: skibag =y→cartype =s, c7:cartype =c→color =b}. Note that PCD refers to the Park Distance Control implemented in recent vehicles It is convenient to distinguish between a consistent background knowledge Bof constraints that cannot be relaxed (in our case, B={c6, c7}) and a consideration set Cof relaxable constraints (in our case, requirements C={c1..c5}). Example 2. In Example 1, there is one minimal conflict which is CS ={c2, c4}, since {c2, c4} ⊆ Cand inconsistent (CS). Furthermore, CS is minimal since there does not exist a CS0s.t. CS0⊂CS. The execution trace of QUICKXPLAIN for this working example is depicted in Figure 1. [1] C={c1..c5}, B ={c6, c7}, Bδ =∅,C1={c1..c2}, C2={c3..c5}. return({c2, c4}). [2] C={c1..c2}, B ={c3..c5, c6, c7}, Bδ ={c3..c5},C1={c1}, C2={c2}. return({c2}). [3] C={c1}, B={c2..c5, c6, c7}, Bδ ={c2}. return({}). [4] C={c2}, B={c3..c5..c7}, Bδ =∅. return({c2}). [5] C={c3..c5}, B ={c2, c6, c7}, Bδ ={c2},C1={c3}, C2={c4..c5}. return({c4}). [6] C={c3}, B={c2, c4..c7}, Bδ ={c4, c5}. return({}). [7] C={c4..c5}, B={c2, c6, c7},Bδ =∅ C1={c4},C2={c5}. return({c4}). [8] C={c4}, B={c2, c5..c7},Bδ ={c5}. return({c4}). [9] C={c5}, B={c2, c4, c6, c7},Bδ ={c4}. return({}). Fig. 1: QX execution trace for C={c1..c5}and B={c6, c7}assuming a minimal conflict set CS ={c2, c4}. Underlined Bs denote QX consistency checks. For example, in the incarnation [2] of the QX function, the consistency check activated is {c3..c5, c6, c7}. QUICKXPLAIN [7] (a variant is shown in Algorithms 1 and 2) supports the determination of minimal (irreducible) conflicts in a given set of constraints (C). QUICKXPLAIN is activated if the background knowledge B(often assumed to be empty or a consistent set of constraints) is inconsistent with the set of constraints C(we assume this consistency check to be performed by a direct solver call). The core algorithm is implemented in the function QX (Algorithm 2) that determines a minimal conflict which is a minimal subset of the constraints in Cwith the conflict set property. The function QX (Algorithm 2) focuses on isolating those constraints that are part of a minimal conflict. If Cincludes only one element (C={cα}), this element can be considered as element of the conflict - this is due to the invariant property inconsistent(C∪B). If the Bis consistent and Chas more than one element, Cis divided into two separate sets, where (in our QX variant) the second part (Cb) is added to Bin order to analyse further elements of the conflict. The function QX activates a consistency check (INCONSISTENT) to figure out whether the considered background knowledge is inconsistent, i.e., no solution exists. Bδ indicates constraints added to B. Algorithm 1 QUICKXPLAIN(C, B) : CS 1: if CONSISTENT(B∪C)then 2: return(’no conflict’) 3: else if C=∅then 4: return(∅) 5: else 6: return(QX(C, B, ∅)) 7: end if Algorithm 2 QX(C={c1..cm}, B, Bδ) : CS 1: if Bδ 6=∅and INCONSISTENT(B)then 2: return(∅) 3: end if 4: if C={cα}then 5: return({cα}) 6: end if 7: k=bm 2c 8: Ca←c1...ck;Cb←ck+1...cm; 9: ∆2←QX(Ca, B ∪Cb, Cb);∆1←QX(Cb, B ∪∆2, ∆2); 10: return(∆1∪∆2) In many of the mentioned application scenarios, there exists an exponential number of conflicts and ways to resolve a conflict [7]. Especially in interactive scenarios, it is extremely important to identify preferred conflicts, i.e., conflicts with a high probability of being the basis of a relaxation acceptable for the user. For example, if a user is strongly interested in low-priced digital cameras, a conflict set that includes a price limit might be of low relevance for the user (since the user is not willing to change the price limit). QUICKXPLAIN [7] supports the determination of preferred conflicts. Although our discussions focus on constraint-based representations, the approach can be applied to any kind of satisfiability problem such as propositional satisfiability (SAT) and description logics (DL). We assume monotonic satisfiability (see Proposition 1). Proposition 1. If a solution for a CSP satisfies all constraints ci∈Cthen it also satisfies every proper subset C0⊂C. QUICKXPLAIN determines one minimal preferred conflict at a time which includes constraints one might be willing to relax. In the line with [7], an explanation Xis preferred over an explanation Yunder the following condition (see Definition 3). Definition 3. We define a total order <on the constraints in C={c1..cm}which is represented as [c1< c2< .. < cm]. If ci< cj, i.e., the importance of ciis higher than cj, then i < j. If Xand Yare two lexicographical constraint orderings of c1..cn, Yis preferred over X(Y >lex X)iff ∃k:ck∈X−Yand X∩ {ck−1..c1}= Y∩ {ck−1..c1}. Example 3. Given the constraint ordering [c3< c4< c5< c6]and two binary conflict sets X={c3, c4}and Y={c4, c5},Yis preferred over Xsince c3∈X−Ywith X∩ {c2, c1}=Y∩ {c2, c1}. 3 Parallelizing QUICKXPLAIN Our approach to parallelize the consistency checks in QX substitutes the direct solver call INCONSISTENT(B) in QX with the activation of a lookahead function (QXGEN) in which consistency checks are not only triggered to directly provide feedback to QX requests, but also to be able to provide fast answers for consistency checks potentially relevant in upcoming states of a QX instance. In the parallelized variant of QUICKXPLAIN, consistency checking is activated by QX with INCONSISTENT(C, B, Bδ) (see Algorithm 3). This also activates the QXGEN function (see Algorithm 4) that starts to generate and trigger (in a parallelized fashion) further consistency checks that might be of relevance in upcoming QX phases. For the description of QXGEN, we employ a two-level ordered set notation which requires, for example, to embed the QX Binto {B}, etc. In QXGEN,C,Bδ, and Bare interpreted as ordered sets. Algorithm 3 INCONSISTENT(C, B, Bδ):Boolean 1: if ¬EXISTSCONSISTENCYCHECK(B)then 2: QXGEN({C},{Bδ},{B−Bδ},{Bδ},0) 3: end if 4: return(¬LOOKUP(B)) QXGEN-generated consistency checking tasks are stored in a LOOKUPtable (see, e.g., Table 1). Thus, in the parallelized variant, QX has to activate the consistency check with INCONSISTENT(C, B, Bδ). In contrast to the original QUICKXPLAIN approach, Cand Bδ are needed as additional parameters to conduct inferences about needed future consistency checks. While in the standard QX version Bδ ⊆B, we assume Bδ and Bto be separate units in QXGEN. node-id constraint set inconsistent 1{c3, c4, c5, c6, c7}true 1.1{c2, c3, c4, c5, c6, c7}false 1.1.1{c1, c6, c7}true 1.2.1{c4, c5, c6, c7}- Table 1: LOOKUPtable indicating the consistency of individual constraint sets. The consistency checking tasks have been generated by ADDCC in the QXGEN function (see Figure 2) and are executed in parallel. The ’-’ entry for the constraint set {c4, c5, c6, c7}indicates that the corresponding consistency check is still ongoing or has not been started up to now. Algorithm 3 uses the LOOKUPfunction to test the consistency of a constraint set. The QXGEN function (see Algorithm 4) predicts future potentially relevant consistency checks needed by QX and activates individual consistency checking tasks in an asynchronous fashion using the ADDCC (add consistency check) function. The ADDCC function triggers an asynchronous service that is in charge of adding consistency checks (parameter of ADDCC) to a LOOKUPtable and issuing the corresponding solver calls. The global parameter lmax is used define the maximum search depth of one activation of QXGEN. In QXGEN,|f(X)|denotes the number of constraints ciin X(it is introduced due to the subset structure in C). Furthermore, SPLIT(C, Ca, Cb) splits Cat position b|C| 2c if |C|>1or C1(the first element of C) at position b|C1| 2cif |C|= 1 and |C1|>1into Caand Cb. Otherwise, no split is needed (C1is a singleton). The first inner condition of QXGEN (|f(δ)|>0) generates a consistency check if this is needed. A consistency check is needed, if Bδ gets extended from Cor a singleton Chas been identified which then extends B. The function ADDCC is used to add consistency check tasks which can then be executed asynchronously in a parallelized fashion. Thus, a consistency check in the LOOKUPtable can be easily identified by an ordered constraint set that has also been used as parameter of ADDCC, for example, ADDCC({{c4, c5},{c6, c7}}) results in the LOOKUPtable enty {c4, c5, c6, c7}which is internally represented with 4567. Algorithm 4 QXGEN(C, Bδ, B, δ, l) C={C1..Cr}... consideration set (subsets Cα) Bδ={Bδ1..Bδn}... added knowledge (subsets Bδβ) B = {B1..Bo}... background (subsets Bγ) δ={D1..Dp}... to be checked (subsets Dπ) l ... current lookahead depth 1: if l < lmax then 2: if |f(δ)|>0then 3: ADDCC(Bδ ∪B) 4: end if 5: {Bδ ∪Bassumed consistent} 6: if |f(C)|= 1 ∧ |f(Bδ)|>0then 7: QXGEN(Bδ, ∅, B ∪ {C1},{C1}, l + 1) 8: else if |f(C)|>1then 9: SPLIT(C, Ca, Cb) 10: QXGEN(Ca, Cb∪Bδ, B, Cb, l + 1) 11: end if 12: {Bδ ∪Bassumed inconsistent} 13: if |f(Bδ)|>0∧ |f(δ)|>0then 14: QXGEN({Bδ1}, Bδ − {Bδ1}, B, ∅, l + 1) 15: end if 16: end if If Bδ ∪Bis assumed to be consistent, additional elements from Chave to be included such that an inconsistent state can be generated (which is needed for identifying a minimal conflict). This extension of Bδ can be achieved by dividing C(if |f(C)|>1, i.e., more than one constraint is contained in C) into two separate sets Caand Cband to add Cbto Bδ. If |f(C)|= 1, this singleton can be added to Bwhich is responsible of collecting constraints that have been identified as being part of the minimal conflict. This is the case due to the already mentioned invariant property, i.e., C∪Bδ ∪Bis inconsistent. If Ccontains only one constraint, i.e., C1is a singleton, it is part of the conflict set. If Bδ ∪Bis assumed to be inconsistent, it can be reduced and at least one conflict element will be identified in the previously added Bδ1. If δdoes not contain an element, no further recursive calls are needed since Bδ−Bδ1has already been checked. The QXGEN function (Algorithm 4) is based on the idea of issuing recursive calls and adapting the parameters of the calls depending on the two possible situations 1) consistent(Bδ ∪B) and 2) inconsistent(Bδ ∪B). In Table 2, the different parameter settings are shown in terms of FOLLOW sets representing the settings of C, Bδ,B, and δin the next activation of QXGEN. Optimizations. To further improve the performance of QX, we have included mechanisms that help to identify irrelevant executions of consistency checks (see Table 3). FOLLOW SETS COND.C Bδ B δ |f(C)|= 1 Bδ ∅B∪ {C1} {C1} |f(C)|>1CaCb∪Bδ B Cb |f(Bδ)|>0{Bδ1}Bδ − {Bδ1}B∅ Table 2: FOLLOW sets of the QXGEN function. Depending on the assumption about the consistency of Bδ ∪B, the follow-up activations of QXGEN have to be parameterized differently. If a consistency check has been completed, we are able to immediately decide whether some of the still ongoing or even not started ones can be canceled since they are not relevant anymore. For example, if the result of a consistency check is {c3..c7}is true (see Figure 2), the check {c4..c7}does not have to be executed anymore (see also Proposition 1) or has to be canceled since QUICKXPLAIN will not need this check (see Figure 2). The deletion criteria for ongoing or even not started consistency checks can be pregenerated for lmax. An example for lmax = 3 is provided in Table 3. RESULT OF CONSISTENCY CHECK NODE-IDtrue false 1del(1.2.x)del(1.1.x) 1.1del(1.1.2.x)del(1.1.1.x) 1.2del(1.2.2.x)del(1.2.1.x) Table 3: Optimizing the execution of consistency checks by detecting irrelevant ones. If the result of a specific check is known, LOOKUP(Algorithm 3) triggers the corresponding delete (del) operation. Nodes without associated consistency check are ignored. In Table 3, the used node-ids are related to QXGEN instances, for example, in Figure 2 the consistency check {c3..c7=true}has the node-id 1. QXGEN [1] C={{c1, c2}},Bδ ={{c3, c4, c5}}, B={{c6, c7}},δ={{c3, c4, c5}} ADDCC({{c3, c4, c5},{c6, c7}}) Ca={{c1}}, Cb={{c2}} QXGEN [1.1] C={{c1}},Bδ ={{c2}{c3, c4, c5}}, B={{c6, c7}},δ={{c2}} ADDCC({{c2},{c3, c4, c5},{c6, c7}}) QXGEN [1.1.1] C={{c2}},Bδ ={{c3, c4, c5}}, B={{c1},{c6, c7}},δ={{c1}} ADDCC({{c1}{c3, c4, c5}{c6, c7}}) QXGEN [1.1.2] C={{c2}}, Bδ ={{c3, c4, c5}}, B={{c6, c7}},δ=∅ QXGEN [1.2] C={{c3, c4, c5}},Bδ =∅, B={{c6, c7}},δ=∅, Ca={{c3}}, Cb={{c4, c5}} QXGEN [1.2.1] C={{c3}},Bδ ={{c4, c5}}, B={{c6, c7}},δ={{c4, c5}} ADDCC({{c4, c5},{c6, c7}}) Fig. 2: QXGEN execution trace for C={{c1..c5}},Bδ =∅,B={{c6, c7}},δ=∅, and lmax = 3. The consistency checks {c3, c4, c5, c6, c7}and {c2, c3, c4, c5c6, c7}(flattened list generated by ADDCC) can be used by the QUICKXPLAIN instance of Figure 1. The QXGEN nodes {[1],[1.1],[1.1.2]}represent the first part of the QUICKXPLAIN search path in Figure 1. 4 Analysis QX complexity. Assuming a splitting k=bm 2cof C={c1..cm}, the worst case time complexity of QUICKXPLAIN in terms of the number of consistency checks needed for calculating one minimal conflict is 2k×log2(m k)+2kwhere kis the minimal conflict set size and mrepresents the underlying number of constraints [7]. Since consistency checks are the most time-consuming part of conflict detection, the runtime performance of the underlying algorithms must be optimized as much as possible. QXGEN complexity. The number (nc) of different possible minimal conflict sets that could be identified with QXGEN for an inconsistent constraint set Cconsisting of m constraints is represented by Formula 1. nc(C) = m 1!+ m 2!+... + m m!(1) The upper bound of the space complexity in terms of recursive QXGEN calls for lmax =nis in the worst case 2n−1−1. Due to the combinatiorial explosion, only those solutions make sense that scale lmax depending on the available computing cores (see the reported evaluation results). If the non-parallelized version of QUICKXPLAIN is applied, only sequential consistency checks can be performed. The approach presented in this paper is more flexible since #processors consistency checks can be performed in parallel. Assuming a maximum QXGEN search depth of lmax = 4, the maximum number of generated consistency checks is 2lmax−1 2due to the binary structure of the search tree, i.e., 4in our example. Out of these 4 checks, a maximum of 3 will be relevant to QX, the remaining ones are irrelevant for identifying the conflict in the current QX session. Thus, the upper bound of relevant consistency checks generated by QXGEN is lmax, i.e., one per QXGEN search level (see the outer left search path in Figure 2), the minimum number of relevant consistency checks is dlmax 2e, i.e., 2in our example. Assuming #processors = 16, our approach can theoretically achieve a performance boost of factor 3 since max. 3 relevant consistency checks can be performed in parallel. It is important to mention, that within the scope of these upper and lower bounds, a performance improvement due to the integration of QXGEN can be guaranteed independent of the underlying knowledge base. Termination of QXGEN. If the parameter lmax =n, recursive calls of QXGen stop at level n−1. In every recursive step, based on the inconsistency invariant between C∪Bδ ∪B,either 1) Cis reduced to Caand Bδ gets extended with Cb(if Bδ ∪B is consistent) or to B∪Cif Cis a singleton, or 2) Bδ is further reduced (if Bδ ∪B is inconsistent). Obviously, in the second case, the constraints in Care not relevant anymore, since a conflict can already be found in Bδ (which is inconsistent with B). QX-conformance of QXGEN. QXGEN correctly predicts QX consistency checks. It follows exactly the criteria of QX. If |f(C)|= 1, i.e., Cincludes only one constraint cα,Bδ ∪Bis consistent and - as a consequence of the inconsistency invariant - cαis a conflict element and therefore has to be added to B. The issued consistency check is B∪C- if inconsistent, a conflict has already been identified. If |f(C)|>1,Cb∪Bδ∪B has to be checked, since Bδ ∪Bis consistent and by adding Cbwe follow the goal of restoring the inconsistency of Bδ ∪B. Finally, if Bδ ∪Bis inconsistent, no check has to be issued since Bδ − {Bδ1} ∪ Bhas already been checked in the previous QXGen call and obviously was considered consistent. Thus, QXGEN takes into account all QX states that can occur in the next step and exactly one of the generated consistency checks (if needed) will be relevant for QX. Finally, the generated consistency checks are irredundant since each check is only generated if new constraints from Care added to Bδ or a new constraint (singleton C) is added to B.