Proc. of 32nd Euromicro intl. Conference on Parallel, Distributed and Network-based Processing (PDP) — 2024
Benchmarking Parallelization Models through Karmarkar Interior-point method
Marco Edoardo Santimaria, Samuele Fonio, Giulio Malenza, Iacopo Colonnelli, Marco Aldinucci
Abstract
Optimization problems are one of the main focus of scientific research. Their computational-intensive nature makes them prone to be parallelized with consistent improvements in performance. This paper sheds light on different parallel models for accelerating Karmarkar's Interior-point method. To do so, we assess parallelization strategies for individual operations within the aforementioned Karmarkar's algorithm using OpenMP, GPU acceleration with CUDA, and the recent Parallel Standard C++ Linear Algebra library (PSTL) executing both on GPU and CPU. Our different implementations yield interesting benchmark results that show the optimal approach for parallelizing interior point algorithms for general Linear Programming (LP) problems. In addition, we propose a more theoretical perspective of the parallelization of this algorithm, with a detailed study of our OpenMP implementation, showing the limits of optimizing the single operations
@inproceedings{24:pdp:karmarkar,
abstract = {Optimization problems are one of the main focus of scientific research. Their computational-intensive nature makes them prone to be parallelized with consistent improvements in performance. This paper sheds light on different parallel models for accelerating Karmarkar's Interior-point method. To do so, we assess parallelization strategies for individual operations within the aforementioned Karmarkar's algorithm using OpenMP, GPU acceleration with CUDA, and the recent Parallel Standard C++ Linear Algebra library (PSTL) executing both on GPU and CPU. Our different implementations yield interesting benchmark results that show the optimal approach for parallelizing interior point algorithms for general Linear Programming (LP) problems. In addition, we propose a more theoretical perspective of the parallelization of this algorithm, with a detailed study of our OpenMP implementation, showing the limits of optimizing the single operations},
address = {New York City, NYC, USA},
author = {Santimaria, Marco Edoardo and Fonio, Samuele and Malenza, Giulio and Colonnelli, Iacopo and Aldinucci, Marco},
booktitle = {Proc. of 32nd Euromicro intl. Conference on Parallel, Distributed and Network-based Processing (PDP)},
date-modified = {2024-08-18 15:22:13 +0200},
doi = {10.1109/PDP62718.2024.00010},
editor = {Adriana E. Chis, Horacio Gonz{\'a}lez-V{\'e}lez},
isbn = {979-8-3503-6307-4},
issn = {2377-5750},
keywords = {icsc, HPC},
location = {Dublin, Ireland},
month = mar,
pages = {1--8},
publisher = {IEEE},
title = {Benchmarking Parallelization Models through Karmarkar Interior-point method},
url = {https://hdl.handle.net/2318/1964571},
year = {2024},
bdsk-url-1 = {https://hdl.handle.net/2318/1964571},
bdsk-url-2 = {https://doi.org/10.1109/PDP62718.2024.00010}}