Performance and Portability in Multi-GPU Branch-and-Bound: Chapel Versus CUDA and HIP for Tree-Based Optimization

Tree search algorithms, such as the Branch-and-Bound (B&B) method, are essential tools in exact combinatorial optimization. Parallel B&B presents significant challenges in achieving scalability arising due to irregular and fine-grained workload associated and the hardware heterogeneity of modern supercomputers. This work focuses on leveraging GPU heterogeneity in the HPC environment within exact tree search optimization algorithms, through a comparison between a proposed CUDA-based low-level implementation and a high-level PGAS-based one. We revisit the design and implementation of a pool-based GPU-accelerated parallel B&B algorithm tailored for heterogeneous CPU / GPU systems originally developed in Chapel. A low-level counterpart implementation, suited for Nvidia and AMD GPU architectures, is proposed for performance gain, appeasing some of the portability issues usually related to low-level implementations. This comparison provides insights into the trade-offs between different programming paradigms in large-scale, heterogeneous computing environments.