Optimal scheduling algorithms for parallel Gaussian elimination (Q1823614): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(89)90059-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3002895390 / rank | |||
Normal rank |
Revision as of 22:40, 19 March 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