An efficient Write-All algorithm for fail-stop PRAM without initialized memory
- Alex A. Shvartsman(corresponding author)
- Brown University,
- Hewlett-Packard
Abstract
The problem of Write-All-using P processors to write 1's into all locations of an array of size N, where P ≤ N-has been used as the basic building block for constructing efficient and fault-tolerant parallel algorithms. All previous Write-All solutions use Ω(P) auxiliary shared memory and assume that this memory is cleared or initialized to some known value. When Write-All building blocks are used in polylogarithmic parallel time algorithms, auxiliary memory initialization cannot be amortized over the computation. Thus, assuming clear memory is a very strong precondition, and for Write-All itself raises a legitimate "chicken-or-egg" objection. Using a determistic bootstraping and balancing argument, we show how to Write-All when auxiliary memory is contaminated with arbitrary values. For any dynamic pattern of fail-stop, no-restart errors on a CRCW PRAM with at least one surviving processor, our new algorithm writes all 1's using O( N + Plog3N (loglog N)2) work, without any initialization assumption. This technique can be combined with any Write-All algorithm to yield efficient simulations of any PRAM and even optimal simulations given processor slack. It can also be used with restartable fail-stop processor simulations.
Publication Information
Output type
Original language
English (US)Pages from-to (Number of pages)
Pages 223-232 (10 pages)Journal (Volume, Issue Number)
Information Processing Letters (Volume 44, Issue 4)Publication milestones
- Published - 12/10/1992
Publication status
ISSN
0020-0190Publication IDs
- Scopus: 0345777691
- ORCID: /0000-0003-4447-3267/work/97283801
