This study presents a new parallel Gaussian elimination approach for symmetric positive definite band systems. For each task, the appropriate start time and adequate processor are determined. Unnecessary dependencies between tasks are eliminated. Simultaneously, all processors perform their associated tasks with precedence constraints under consideration. Our main goal is to obtain a high degree of parallelism by balancing the load of processors and reducing the total idle and parallel execution times. The theoretical lower bounds for parallel execution time and number of processors required to execute the precedence graph at an optimal time are also computed. The validity of our investigation is confirmed by carrying out several experiments on a shared-memory multicore architecture using OpenMP. Practical results prove the efficiency of the proposed method.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2020013
Keywords: Gaussian elimination, symmetric positive definite band systems, parallel execution time, shared-memory multicore architecture, efficiency
@article{RO_2021__55_S1_S905_0,
author = {Marrakchi, Sirine and Jemni, Mohamed},
title = {Parallel gaussian elimination of symmetric positive definite band matrices for shared-memory multicore architectures},
journal = {RAIRO. Operations Research},
pages = {S905--S927},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020013},
mrnumber = {4223122},
zbl = {07375282},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020013/}
}
TY - JOUR AU - Marrakchi, Sirine AU - Jemni, Mohamed TI - Parallel gaussian elimination of symmetric positive definite band matrices for shared-memory multicore architectures JO - RAIRO. Operations Research PY - 2021 SP - S905 EP - S927 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020013/ DO - 10.1051/ro/2020013 LA - en ID - RO_2021__55_S1_S905_0 ER -
%0 Journal Article %A Marrakchi, Sirine %A Jemni, Mohamed %T Parallel gaussian elimination of symmetric positive definite band matrices for shared-memory multicore architectures %J RAIRO. Operations Research %D 2021 %P S905-S927 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020013/ %R 10.1051/ro/2020013 %G en %F RO_2021__55_S1_S905_0
Marrakchi, Sirine; Jemni, Mohamed. Parallel gaussian elimination of symmetric positive definite band matrices for shared-memory multicore architectures. RAIRO. Operations Research, Tome 55 (2021), pp. S905-S927. doi: 10.1051/ro/2020013
, , , and , Editors, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Society for Industrial and Applied Mathematics, Philadelphia, PA (2000). | MR | Zbl
, and , Impact of communications on the complexity of the parallel Gaussian elimination. Parallel Comput. 17 (1991) 55–61. | Zbl | DOI
, Numerical Methods in Matrix Computations. In: Vol. 59 of Texts in Applied Mathematics, edited by: , , , , , , , , , , . Springer, New York, NY (2015). | MR | Zbl | DOI
, Introduction to Numerical Analysis Using MATLAB. Jones and Bartlett Publishers, Burlington, MA (2010).
and , Introduction to Finite Elements in Engineering, 4th edition. Pearson Education, London (2012). | Zbl
, and , Using OpenMP: Portable Shared Memory Parallel Programming. MIT Press, Cambridge, MA (2008).
and , Task Scheduling for Multi-core and Parallel Architectures: Challenges, Solutions and Perspectives. Springer Singapore, Singapore (2017). | MR | Zbl
, and , Gaussian elimination of symmetric, positive definite, banded systems on transputer networks. In: Transputer/Occam Japan 4. Proceedings of the 4th Transputer/Occam International Conference. IOS Press, Amsterdam (1992) 73–84.
and , A Graduate Introduction to Numerical Methods: From the Viewpoint of Backward Error Analysis. Springer, New York, NY (2013). | MR | Zbl | DOI
, Galois Theory. John Wiley & Sons, Hoboken, NJ (2004). | MR | Zbl
, Scheduling for Parallel Processing. Springer, London (2009). | MR | Zbl | DOI
, and , Scientific Computing – An Introduction Using Maple and MATLAB. In: Vol. 11 of Texts in Computational Science and Engineering, edited by: , , , , , . Springer, New York, NY (2014). | MR | Zbl | DOI
and , Matrix Computations, 4th edition. Johns Hopkins University Press, Baltimore, MA (2013). | MR | Zbl
and , Numerical Methods: Design, Analysis, and Computer Implementation of Algorithms. Princeton University Press, Princeton, NJ (2012). | Zbl
Grid5000, https://www.grid5000.fr.
and , Critical path scheduling parallel programs on an unbounded number of processors. Int. J. Found. Comput. Sci. 17 (2006) 287–301. | MR | Zbl | DOI
, Matrix Algebra from a Statistician’s Perspective. Springer, New York, NY (1997). | MR | Zbl | DOI
and , Matrices with banded inverses: inversion algorithms and factorization of Gauss–Markov processes. IEEE Trans. Inf. Theory 46 (2000) 1495–1509. | MR | Zbl | DOI
, Parallel applications performance evaluation using the concept of granularity. In: Vol. 8385 of Lecture Notes in Computer Science. Parallel Processing and Applied Mathematics. Proceedings of the International Conference PPAM 2013, edited by , , , . Springer, New York, NY (2014) 215–224. | DOI
and , Optimal algorithms for Gaussian elimination on an MIMD computer. Parallel Comput. 12 (1989) 183–194. | MR | Zbl | DOI
and , Fine-grained parallel solution for solving sparse triangular systems on multicore platform using OpenMP interface. In: 2017 International Conference on High Performance Computing Simulation (HPCS). IEEE, New York, NY (2017) 659–666. | DOI
and , A parallel scheduling algorithm to solve triangular band systems on multicore machine. In: Vol. 32 of Advances in Parallel Computing. Parallel Computing is Everywhere. Proceedings of the International Conference on Parallel Computing. ParCo 2017, edited by: , , , , . IOS Press, Amsterdam (2018) 127–136. | Zbl
and , Parallel Gaussian elimination using OpenMP and MPI. In: Proceedings 16th Annual International Symposium on High Performance Computing Systems and Applications. IEEE, New York, NY (2002) 169–173. | DOI
, Gaussian elimination for the solution of linear systems of equations. In: Vol. 7 of Handbook of Numerical Analysis. Elsevier, New York, NY (2000) 3–170. | MR | Zbl
, and , An optimal algorithm for Gaussian elimination of band matrices on an MIMD computer. Parallel Comput. 15 (1990) 133–145. | MR | Zbl | DOI
, and , Modeling and Optimization of Parallel and Distributed Embedded Systems. Wiley-IEEE Press, New York, NY (2016). | MR | DOI
and , Optimal scheduling algorithms for parallel Gaussian elimination. Theor. Comput. Sci. 64 (1989) 159–173. | MR | Zbl | DOI
, SPARSKIT: A Basic Tool Kit for Sparse Matrix Computations – Version 2. Technical report (1994).
, An optimal schedule for Gaussian elimination on an MIMD architecture. J. Comput. Appl. Math. 185 (2006) 91–106. | MR | Zbl | DOI
and , Numerical Methods in Electromagnetics. In: Vol. 13 of Handbook of Numerical Analysis, edited by . Elsevier, New York, NY (2005). | MR | Zbl
, Operations Research. Tata McGraw-Hill, New York, NY (2008).
, Analysis of Financial Time Series, 3rd edition. John Wiley & Sons, New York, NY (2010). | MR | Zbl
, and , A DAG task scheduling scheme on heterogeneous cluster systems using discrete IWO algorithm. J. Comput. Sci. 26 (2018) 307–317. | DOI
, , , and , A list scheduling algorithm for heterogeneous systems based on a critical node cost table and pessimistic cost table. Concurr. Comput. Pract. E. 29 (2017) e3944. | DOI
, , and , Computations with symmetric, positive definite and band matrices on a parallel vector processor. Parallel Comput. 8 (1988) 301–312. | Zbl | DOI
Cité par Sources :
