An Efficient Approach for Accelerating Bucket Elimination on GPUs

摘要: Bucket elimination (BE) is a framework that encompasses several algorithms, including belief propagation (BP) and variable for constraint optimization problems (COPs). BE has significant computational requirements can be addressed by using graphics processing units (GPUs) to parallelize its fundamental operations, i.e., composition marginalization, which operate on functions represented large tables. We propose novel approach these operations with GPUs, optimizes the table layout so achieve better performance in terms of increased speedup scalability. Our allows us process incomplete tables (i.e., some missing variables assignments), often occur practical applications (such as ones we consider our dataset). Finally, are larger than GPU memory. outperforms state-of-the-art technique BP achieving speedups (up +466% respect such parallel technique). test method publicly available COP dataset, measuring up $696.02\boldsymbol {\times }$ sequential version. The ability crucial this scenario, most instances generate memory, hence they cannot solved previous techniques related BE.