Multi-conflict detection stops at two parallel branches: the merge loop's checks are now precomputed too, averaging 1.21x on two cores
Synopsis
Diagnosis of constraint systems needs several minimal conflicts at once, and MergeXplain returns multiple conflicts from one decomposition, but only its two recursive branches had been run in parallel while the merge loop that eliminates boundary-spanning conflicts stayed sequential. ParallelMergeXplain forks the recursion up to a bounded depth and replaces every GetConflict call in the merge loop with a speculative, QXGen-lookahead parallel version. On a 2-core machine it reached a mean wall-clock speed-up of 1.21x (std. 0.20) across all configurations with non-trivial checks, and 1.531x for par full at p=2 on the real SATLIB uf50-218 instance, returning results identical to sequential MergeXplain.
Interpretation
Parallelism for multi-conflict detection moves from splitting recursive branches into the merge loop itself: each GetConflict call issued to eliminate a boundary-spanning conflict is itself a QuickXplain run, and is now replaced by the speculative ParallelGetConflict. The earlier parallel variant PMXP ran only the two independent recursive calls of FindConflicts in two threads and left the merge loop that repeatedly calls GetConflict strictly sequential. On a 2-core machine, merge-phase speculation alone (par spec, p=2, lmax=4) averaged 1.005x (std. 0.052), essentially breakeven, on the real SATLIB uf50-218 instances, while branch parallelism alone (par branch) reached 1.513x (std. 0.191) and both layers combined (par full, p=2) reached 1.531x (std. 0.134).
Combining both layers was the best or tied-best mean performer in every check-cost regime tested, and the returned conflict sets matched the sequential algorithm case by case. Sequential MergeXplain is the baseline for this comparison; the parallel version changes when and where computation happens, not what it computes. All 75 timed runs (15 instances times 5 variants) returned conflict sets canonically identical to sequential MergeXplain as sets of frozensets, and a further 80 dedicated correctness combinations matched exactly; every conflict returned on the real-world instance was independently verified sound and minimal afterward.
The parallel payoff depends on conflict structure: on the real-world instances sequential MergeXplain issued only 36 to 57 solver calls in total and returned conflicts of sizes 2, 4 and 5 out of 50 candidates, leaving little for merge-phase lookahead to exploit. The synthetic benchmarks could not show this data dependence because their conflict cardinality and position were planted under control. On the same real-world instances, branch parallelism alone reached 1.513x while merge-phase speculation alone reached only 1.005x, showing that the relative payoff of the two layers varies with conflict size.
Perspective
The demonstrated scope is a 2-physical-core Linux sandbox, synthetic and real instances with 18 to 50 requirements, and the conservative conflict-elimination strategy; merge-phase speculation is applied only at the outermost FindConflicts call. The reference implementation and all raw measurements are released under the MIT License so the consistency oracle can be swapped and the runs reproduced.
The authors note that the 2-core hardware is an order of magnitude smaller than the 8-16-core machines used to evaluate ParallelQuickXplain and FastDiagP, so the reported absolute speed-ups should be read as conservative; the from-scratch CDCL consistency oracle matched an independent DPLL solver on 85 instances with zero mismatches but is not a competitively engineered solver such as Sat4j or MiniSat. Real-world validation rests on one externally published formula, SATLIB uf50-218, with three controlled flip-derived scenarios rather than a diverse corpus of real feature models.