A Portable Low-Level Multi-GPU Branch-and-Bound: A Comparison Against Chapel | ChapelCon '25

Описание: Presentation by Ivan Tagliaferro de Oliveira Tezoto at ChapelCon '25.

Slides for this talk are available at: https://chapel-lang.org/ChapelCon/202...

Modern high-performance computing systems increasingly rely on heterogeneous architectures combining CPUs and GPUs from multiple vendors, such as Nvidia and AMD. Ensuring both performance and portability in this context remains a key challenge. This work investigates two distinct programming approaches for parallel tree-based exact optimization, focusing on the Branch-and-Bound algorithm. The first is a low-level, performance-oriented implementation in C, combining OpenMP with CUDA and HIP for multi-GPU acceleration within a single compute node. The second leverages the PGAS-based Chapel language, which offers a unified and portable high-level framework for threaded and GPU programming. We revisit the design of a portable multi-GPU Chapel implementation and propose an optimized low-level counterpart featuring a collegial multi-pool data structure, dynamic load balancing through Work Stealing, and GPU thread-indexing optimizations. Both implementations are evaluated on the Permutation Flowshop Scheduling Problem using up to eight GPUs on Nvidia A100 and AMD MI250x architectures. Experimental results demonstrate that while CUDA and HIP versions consistently outperform Chapel in terms of raw performance, Chapel achieves comparable or superior scalability when considering absolute speedups. These findings suggest that Chapel represents a promising option for prototyping GPU-accelerated parallel applications, allowing developers to evaluate feasibility and design choices before transitioning to performance-tuned, low-level implementations.