Tech Report CS-92-09

How to Write-All Efficiently Even with Contaminated Memory

Alex A. Shvartsman

February 1992

Abstract:

The problem of {\em Write-All} ---using $P$ processors, write 1's into all locations of an array of size $N$, where $P \leq N$--- has been used as the basic building block for constructing efficient and fault-tolerant parallel algorithms. All previous {\em Write-All} solutions use $\Omega(P)$ auxiliary shared memory and assume that this memory is cleared or initialized to some known value. When {\em Write-All} building blocks are used in polylogarithmic parallel-time algorithms (e.g., to compute prefix sums or list ranking), auxiliary memory initialization cannot be amortized over the computation. Thus, assuming clear memory is a very strong precondition and for {\em Write-All} itself raises a legitimate ``chicken-or-egg'' objection.

In this note, using a deterministic bootstrapping and balancing argument, we show how to {\em 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 + P\log^3 N / (\log\log^2 N))$ work, {\em without any initialization assumption}. This technique can be combined with any {\em 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. In addition, we show that for the parallel prefix computation it is possible to improve on the best deterministic simulations to date: by a factor of $\log N$ when the memory is clear, and by a factor of $\log\log N$ when the memory is contaminated.

(complete text in pdf)