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.
Original language | English (US) |
---|---|
Pages (from-to) | 223-232 |
Number of pages | 10 |
Journal | Information Processing Letters |
Volume | 44 |
Issue number | 4 |
DOIs | |
State | Published - Dec 10 1992 |
Externally published | Yes |
Keywords
- CRCW PRAM
- Parallel algorithms
- fault tolerance
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications