Performance modeling and analysis of parallel Gaussian elimination on multi-core computers
Gaussian elimination is used in many applications and in particular in the solution of systems of linear equations. This paper presents mathematical performance models and analysis of four parallel Gaussian Elimination methods (precisely the Original method and the new Meet in the Middle –MiM– algor...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2014-01-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1319157813000086 |
| _version_ | 1811237792512999424 |
|---|---|
| author | Fadi N. Sibai |
| author_facet | Fadi N. Sibai |
| author_sort | Fadi N. Sibai |
| collection | DOAJ |
| description | Gaussian elimination is used in many applications and in particular in the solution of systems of linear equations. This paper presents mathematical performance models and analysis of four parallel Gaussian Elimination methods (precisely the Original method and the new Meet in the Middle –MiM– algorithms and their variants with SIMD vectorization) on multi-core systems. Analytical performance models of the four methods are formulated and presented followed by evaluations of these models with modern multi-core systems’ operation latencies. Our results reveal that the four methods generally exhibit good performance scaling with increasing matrix size and number of cores. SIMD vectorization only makes a large difference in performance for low number of cores. For a large matrix size (n ⩾ 16 K), the performance difference between the MiM and Original methods falls from 16× with four cores to 4× with 16 K cores. The efficiencies of all four methods are low with 1 K cores or more stressing a major problem of multi-core systems where the network-on-chip and memory latencies are too high in relation to basic arithmetic operations. Thus Gaussian Elimination can greatly benefit from the resources of multi-core systems, but higher performance gains can be achieved if multi-core systems can be designed with lower memory operation, synchronization, and interconnect communication latencies, requirements of utmost importance and challenge in the exascale computing age. |
| first_indexed | 2024-04-12T12:30:34Z |
| format | Article |
| id | doaj.art-13cac6e3eba84e45b3ebd4faa5485561 |
| institution | Directory Open Access Journal |
| issn | 1319-1578 |
| language | English |
| last_indexed | 2024-04-12T12:30:34Z |
| publishDate | 2014-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj.art-13cac6e3eba84e45b3ebd4faa54855612022-12-22T03:33:03ZengElsevierJournal of King Saud University: Computer and Information Sciences1319-15782014-01-01261415410.1016/j.jksuci.2013.03.002Performance modeling and analysis of parallel Gaussian elimination on multi-core computersFadi N. SibaiGaussian elimination is used in many applications and in particular in the solution of systems of linear equations. This paper presents mathematical performance models and analysis of four parallel Gaussian Elimination methods (precisely the Original method and the new Meet in the Middle –MiM– algorithms and their variants with SIMD vectorization) on multi-core systems. Analytical performance models of the four methods are formulated and presented followed by evaluations of these models with modern multi-core systems’ operation latencies. Our results reveal that the four methods generally exhibit good performance scaling with increasing matrix size and number of cores. SIMD vectorization only makes a large difference in performance for low number of cores. For a large matrix size (n ⩾ 16 K), the performance difference between the MiM and Original methods falls from 16× with four cores to 4× with 16 K cores. The efficiencies of all four methods are low with 1 K cores or more stressing a major problem of multi-core systems where the network-on-chip and memory latencies are too high in relation to basic arithmetic operations. Thus Gaussian Elimination can greatly benefit from the resources of multi-core systems, but higher performance gains can be achieved if multi-core systems can be designed with lower memory operation, synchronization, and interconnect communication latencies, requirements of utmost importance and challenge in the exascale computing age.http://www.sciencedirect.com/science/article/pii/S1319157813000086Gaussian eliminationMulti-core computingPerformance modeling and analysis |
| spellingShingle | Fadi N. Sibai Performance modeling and analysis of parallel Gaussian elimination on multi-core computers Journal of King Saud University: Computer and Information Sciences Gaussian elimination Multi-core computing Performance modeling and analysis |
| title | Performance modeling and analysis of parallel Gaussian elimination on multi-core computers |
| title_full | Performance modeling and analysis of parallel Gaussian elimination on multi-core computers |
| title_fullStr | Performance modeling and analysis of parallel Gaussian elimination on multi-core computers |
| title_full_unstemmed | Performance modeling and analysis of parallel Gaussian elimination on multi-core computers |
| title_short | Performance modeling and analysis of parallel Gaussian elimination on multi-core computers |
| title_sort | performance modeling and analysis of parallel gaussian elimination on multi core computers |
| topic | Gaussian elimination Multi-core computing Performance modeling and analysis |
| url | http://www.sciencedirect.com/science/article/pii/S1319157813000086 |
| work_keys_str_mv | AT fadinsibai performancemodelingandanalysisofparallelgaussianeliminationonmulticorecomputers |