Search: L773:2169 3536 OR L773:2169 3536
> (2020-2024) >
On the Efficiency o...
On the Efficiency of Supernodal Factorization in Interior-Point Method Using CPU-GPU Collaboration
-
- Ahmad, Muhammad Ovais, Senior Lecturer (author)
- Karlstads universitet,Institutionen för matematik och datavetenskap (from 2013),SQUAD - SOFTWARE QUALITY AND DIGITAL MODERNISATION
-
(creator_code:org_t)
- IEEE Computer Society Digital Library, 2020
- 2020
- English.
-
In: IEEE Access. - : IEEE Computer Society Digital Library. - 2169-3536. ; 8, s. 120892-120904
- Related links:
-
https://doi.org/10.1...
-
show more...
-
https://ieeexplore.i...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- Primal-dual interior-point method (PDIPM) is the most efficient technique for solving sparse linear programming (LP) problems. Despite its efficiency, PDIPM remains a compute-intensive algorithm. Fortunately, graphics processing units (GPUs) have the potential to meet this requirement. However, their peculiar architecture entails a positive relationship between problem density and speedup, conversely implying a limited affinity of GPUs for problem sparsity. To overcome this difficulty, the state-of-the-art hybrid (CPU-GPU) implementation of PDIPM exploits presence of supernodes in sparse matrices during factorization. Supernodes are groups of similar columns that can be treated as dense submatrices. Factorization method used in the state-of-the-art solver performs only selected operations related to large supernodes on GPU. This method is known to underutilize GPU’s computational power while increasing CPU-GPU communication overhead. These shortcomings encouraged us to adapt another factorization method, which processes sets of related supernodes on GPU, and introduce it to the PDIPM implementation of a popular open-source solver. Our adaptation enabled the factorization method to better mitigate the effects of round-off errors accumulated over multiple iterations of PDIPM. To augment performance gains, we also used an efficient CPU-based matrix multiplication method. When tested for a set of well-known sparse problems, the adapted solver showed average speed-ups of approximately 55X, 1.14X and 1.05X over the open-source solver’s original version, the state-of-the-art solver, and a highly optimized proprietary solver known as CPLEX, respectively. These results strongly indicate that our proposed hybrid approach can lead to significant performance gains for solving large sparse problems.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Sparse matrices
- GPU
- GPGPU
- linear programming
- primal-dual interior-point method
- Computer Science
- Datavetenskap
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database