An Efficient Approach for Accelerating Bucket Elimination on GPUs.

Area of Science:

• Computer Science
• Artificial Intelligence
• Computational Mathematics

Background:

• Bucket elimination (BE) is a core framework for solving constraint optimization problems (COPs).
• Standard BE algorithms face significant computational demands, particularly with large datasets.
• Parallelizing BE operations on graphics processing units (GPUs) offers a potential solution for performance enhancement.

Purpose of the Study:

• To develop a novel GPU-based approach for parallelizing fundamental BE operations (composition and marginalization).
• To optimize table layout for improved speedup and scalability in BE computations.
• To enable processing of incomplete tables and tables exceeding GPU memory capacity.

Main Methods:

• A novel table layout optimization strategy for parallel BE operations on GPUs.
• Implementation of parallel composition and marginalization functions tailored for GPU architecture.
• Testing on a publicly available COP dataset, including instances with tables larger than GPU memory.

Main Results:

• Achieved significant speedups compared to sequential BE execution.
• Outperformed state-of-the-art GPU-based belief propagation (BP) parallelization techniques, with speedups up to +466%.
• Demonstrated capability to process tables larger than GPU memory, a limitation of previous methods.

Conclusions:

• The proposed GPU-based BE approach offers substantial performance improvements for COPs.
• Optimized table layouts and memory handling are critical for efficient GPU parallelization of BE.
• This method expands the applicability of GPU acceleration to complex COPs with large-scale data.