A Unified Multi-Dimensional Cost Analysis of Speculative Parallel Conflict Detection and Diagnosis

Vinueza-Morales M.; Tupac-Yupanqui M.; Márquez N.; Vidal-Silva C. · Computers (2026) · DOI: 10.3390/computers15040201

Resumen

Speculative parallelization has been proposed to accelerate computationally intensive reasoning tasks in constraint-based systems, particularly minimal conflict detection and preferred diagnosis computation. Parallel variants of QUICKXPLAIN enable concurrent conflict detection, while parallel FASTDIAG supports speculative diagnosis computation. Existing evaluations of these approaches primarily emphasize runtime reduction and speedup metrics. However, runtime alone does not fully characterize computational efficiency in multi-core environments, where synchronization overhead and speculative execution costs may significantly influence performance. This paper introduces a unified multi-dimensional cost model for analyzing speculative parallel conflict detection and diagnosis algorithms. Rather than proposing new algorithms, we reinterpret previously reported experimental results under a formal cost perspective integrating runtime, speedup, efficiency, parallel overhead, and conflict-normalized cost metrics. Our analysis reveals that speculative parallelization provides substantial benefits in high-cardinality conflict scenarios and complex diagnosis tasks, but scalability is limited by coordination overhead and diminishing efficiency as the number of parallel workers increases. We further identify parallel breakdown points beyond which additional workers degrade performance. The proposed framework offers a systematic basis for cost-aware evaluation of parallel reasoning strategies and provides practical insights into when parallelization is beneficial for conflict detection and diagnosis tasks in large-scale constraint systems.

Instituciones: Universidad Continental