Optimal scheduling algorithms for parallel Gaussian elimination (Q1823614): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q235410 |
Changed an Item |
||
Property / author | |||
Property / author: Yves Robert / rank | |||
Normal rank |
Revision as of 15:53, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal scheduling algorithms for parallel Gaussian elimination |
scientific article |
Statements
Optimal scheduling algorithms for parallel Gaussian elimination (English)
0 references
1989
0 references
The asymptotic efficiency of a parallel algorithm is defined as the limit of \(T_ 1/(pT_ p)\) for \(n\to \infty\), where n is the order of the matrix, p is the number of processors, and \(T_ 1\) and \(T_ p\) are the execution times for the sequential and parallel algorithms, respectively. For a shared memory machine with \(p=\alpha n\) processors \((\alpha <1)\), and with the assumption that synchronization and communication costs can be neglected, this paper describes a rather complicated, 3-step scheduling algorithm for Gaussian elimination with asymptotic efficiency \((1+\alpha^ 3)^{-1}\). It is also shown that this efficiency is optimal. The paper is mainly of theoretical interest, in particular due to the assumptions and the complicated second step of the algorithm.
0 references
parallel algorithm
0 references
shared memory machine
0 references
3-step scheduling algorithm
0 references
Gaussian elimination
0 references
asymptotic efficiency
0 references