Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices

  • Fast domain propagation of linear constraints has become a crucial component of today's best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the-art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Boro Sofranac, Ambros Gleixner, Sebastian Pokutta
Document Type:In Proceedings
Parent Title (English):2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)
First Page:1
Last Page:11
Year of first publication:2020
ArXiv Id:http://arxiv.org/abs/2009.07785
Note:
URL of the Slides: https://app.box.com/s/qy0pjmhtbm7shk2ypxjxlh2sj4nudvyu
Note:
URL of the Abstract: http://www.pokutta.com/blog/research/2020/09/20/gpu-prob.html
DOI:https://doi.org/10.1109/IA351965.2020.00007