Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices

被引：1
|
作者：
Sofranac, Boro [1 ,2 ]
Gleixner, Ambros [2 ,3 ]
Pokutta, Sebastian [1 ,2 ]
机构：
[1] Berlin Insitute Technol, Str 17 Juni 135, D-10623 Berlin, Germany
[2] Zuse Inst Berlin, Takustr 7, D-14195 Berlin, Germany
[3] HTW Berlin, Treskowallee 8, D-10318 Berlin, Germany
来源：
PARALLEL COMPUTING | 2022年 / 109卷
关键词：
Mixed integer linear programming; MIP; GPU; Domain propagation; Bound tightening; Parallel algorithms;
D O I：
10.1016/j.parco.2021.102874
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
center dot Currently, domain propagation in state-of-the-art MIP solvers is single thread only. center dot The paper presents a novel, efficient GPU algorithm to perform domain propagation. center dot Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. center dot The algorithm is capable of running entirely on the GPU with no CPU involvement. center dot We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances.
引用
收藏
页数：12
相关论文
共 50 条
  • [1] Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices
    Sofranac, Boro
    Gleixner, Ambros
    Pokutta, Sebastian
    PROCEEDINGS OF IA3 2020: 2020 IEEE/ACM 10TH WORKSHOP ON IRREGULAR APPLICATIONS: ARCHITECTURES AND ALGORITHMS (IA3), 2020, : 1 - 11
  • [2] An efficient GPU-parallel coordinate descent algorithm for sparse precision matrix estimation via scaled lasso
    Seunghwan Lee
    Sang Cheol Kim
    Donghyeon Yu
    Computational Statistics, 2023, 38 : 217 - 242
  • [3] Sparse Partial Correlation Estimation With Scaled Lasso and Its GPU-Parallel Algorithm
    Cho, Younsang
    Lee, Seunghwan
    Kim, Jaeoh
    Yu, Donghyeon
    IEEE ACCESS, 2023, 11 : 65093 - 65104
  • [4] An efficient GPU-parallel coordinate descent algorithm for sparse precision matrix estimation via scaled lasso
    Lee, Seunghwan
    Kim, Sang Cheol
    Yu, Donghyeon
    COMPUTATIONAL STATISTICS, 2023, 38 (01) : 217 - 242
  • [5] A GPU-Parallel Image Coregistration Algorithm for InSar Processing at the Edge
    Romano, Diego
    Lapegna, Marco
    SENSORS, 2021, 21 (17)
  • [6] AN EFFICIENT PARALLEL ALGORITHM FOR EXTREME EIGENVALUES OF SPARSE NONSYMMETRIC MATRICES
    KIM, SK
    CHRONOPOULOS, AT
    INTERNATIONAL JOURNAL OF SUPERCOMPUTER APPLICATIONS AND HIGH PERFORMANCE COMPUTING, 1992, 6 (01): : 98 - 111
  • [7] Designing a GPU-parallel algorithm for raw SAR data compression: A focus on parallel performance estimation
    Romano, Diego
    Lapegna, Marco
    Mele, Valeria
    Laccetti, Giuliano
    FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2020, 112 : 695 - 708
  • [8] A GPU-parallel Algorithm for Fast Hybrid BFS-DFS Graph Traversal
    Maratea, Antonio
    Marcellino, Livia
    Duraccio, Vincenzo
    2017 13TH INTERNATIONAL CONFERENCE ON SIGNAL-IMAGE TECHNOLOGY AND INTERNET-BASED SYSTEMS (SITIS), 2017, : 450 - 457
  • [9] A GPU-parallel algorithm for ECG signal denoising based on the NLM method.
    Cuomo, Salvatore
    De Michele, Pasquale
    Marcellino, Livia
    Galletti, Ardelio
    IEEE 30TH INTERNATIONAL CONFERENCE ON ADVANCED INFORMATION NETWORKING AND APPLICATIONS WORKSHOPS (WAINA 2016), 2016, : 35 - 39
  • [10] Efficient non-uniform grid for GPU-parallel Shallow Water Equations models
    Vacondio, R.
    Ferrari, A.
    Mignosa, P.
    Aureli, E.
    Dal Palu, A.
    RIVER FLOW 2016, 2016, : 281 - 288
12345