FAILURE-SENSITIVE ANALYSIS OF PARALLEL ALGORITHMS WITH CONTROLLED MEMORY ACCESS CONCURRENCY
Abstract
The abstract problem of using P failure-prone processors to cooperatively update all locations of an N-element shared array is called Write-All. Solutions to Write-All can be used iteratively to construct efficient simulations of PRAM algorithms on failure-prone PRAMS. Such use of Write-All in simulations is abstracted in terms of the iterative Write-All problem. The efficiency of the algorithmic solutions for Write-All and iterative Write-All is measured in terms of work complexity where all processing steps taken by the processors are counted. This paper considers determinitic solutions for the Write-All and iterative Write-All problems in the fail-stop synchronous CRCW PRAM model where memory access concurrency needs to be controlled. A deterministic algorithm of Kanellakis, Michailidis, and Shvartsman [16] efficiently solves the Write-All problem in this model, while controlling read and write memory access concurrency. However it was not shown how the number of processor failures f affects the work efficiency of the algorithm. The results herein give a new analysis of the algorithm [16] that obtain failure-sensitive work bounds, while retaining the known memory access concurrency bounds. Specifically, the new result expresses the work bound as a function of N, Pandf. Another contribution in this paper is the new failure-sensitive analysis for iterative Write-All with controlled memory access concurrency. This result yields tighter bounds on work (vs. [16]) for simulations of PRAM algorithms on fail-stop PRAMS.
This research is supported by the NSF Grants 9988304 and 0311368, and NSF ITR Grant 0121277. The work of the second author is supported in part by the NSF CAREER Award 0093065. The work of the third author is supported in part by the NSF CAREER Award 9984774. The work of the first author was performed in part, while at the University of Connecticut.
References
- Computer Journal 36(8), 756 (1993), DOI: 10.1093/comjnl/36.8.756. Crossref, ISI, Google Scholar
Y. Aumann and M. O. Rabin , Clock construction in fully asynchronous parallel systems and PRAM simulation, Proc. of 33rd IEEE Symposium on Foundations of Computer Science (1992) pp. 147–156, DOI: 10.1109/SFCS.1992.267777. Google Scholar- SIAM Journal of Computing 26(5), 1277 (1997), DOI: 10.1137/S0097539794319126. Crossref, ISI, Google Scholar
- Journal of Algorithms 20(1), 45 (1996), DOI: 10.1006/jagm.1996.0003. Crossref, ISI, Google Scholar
B. Chlebus , Towards practical deterministic Write-All algorithms, Proc. of 13th ACM Symposium on Parallel Algorithms and Architectures (2001) pp. 271–280. Google ScholarD. Culler , LogP: Torwards a realistic model of parallel computation, Proc. of 4th Symp. on Principles and Practice of Parallel Programming (1993) pp. 1–12, DOI: 10.1145/155332.155333. Google ScholarP. Dasgupta , Z. Kedem and M. Rabin , Parallel processing on networks of workstation: A fault-tolerant, high performance approach, Proc. of the 15th IEEE International Conference on Distributed Computer Systems (1995) pp. 467–474, DOI: 10.1109/ICDCS.1995.500052. Google Scholar- Annual Reviews in Computer Science 3, 233 (1988), DOI: 10.1146/annurev.cs.03.060188.001313. Crossref, ISI, Google Scholar
- Distributed Computing 14(2), 75 (2001), DOI: 10.1007/PL00008930. Crossref, ISI, Google Scholar
P. B. Gibbons , A more practical PRAM model, Proc. of 1st ACM Symposium on Parallel Algorithms and Architectures (1989) pp. 158–168, DOI: 10.1145/72935.72953. Google Scholar- Theoretical Computer Science 196(1–2), 3 (1998), DOI: 10.1016/S0304-3975(97)00193-X. Crossref, ISI, Google Scholar
Ch. Georgiou , A. Russell and A. A. Shvartsman , The complexity of distributed cooperation in the presence of failures, Proc. of the 4th International Conference on Principles of Distributed Systems (2000) pp. 245–264. Google Scholar- Distributed Computing 17(1), 47 (2004), DOI: 10.1007/s00446-003-0099-3. Crossref, ISI, Google Scholar
Ch. Georgiou , A. Russell and A. A. Shvartsman , Failure-Sensitive Analysis of Parallel Algorithms with Controlled Memory Access Concurrency, Proc. of the 6th International Conference on Principles of Distributed Systems (2002) pp. 127–138. Google Scholar-
A. M. Gibbons and P. Spirakis (eds.) , Lectures on Parallel Computation ,Cambridge International Series on Parallel Computation ( Cambridge University Press , 1993 ) . Google Scholar - Nordic Journal of Computing 2(2), 146 (1995). Google Scholar
- Distributed Computing 5(4), 201 (1992), DOI: 10.1007/BF02277667. Crossref, ISI, Google Scholar
-
P. C. Kanellakis and A. A. Shvartsman , Fault-Tolerant Parallel Computation ( Kluwer Academic Publishers , 1997 ) . Crossref, Google Scholar R. M. Karp and V. Ramachandran , Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (1990) pp. 869–941. Google ScholarZ. M. Kedem , Efficient program transformations for resilient parallel computation via randomization, Proc. of 24th ACM Symposium on Theory of Computing (1992) pp. 306–318, DOI: 10.1145/129712.129742. Google ScholarZ. M. Kedem , Combining tentative and definite executions for dependable parallel computing, Proc. of 23rd ACM Symposium on Theory of Computing (1991) pp. 381–390, DOI: 10.1145/103418.103459. Google ScholarZ. M. Kedem , K. V. Palem and P. Spirakis , Efficient robust parallel computations, Proc. of 22nd ACM Symposium on Theory of Computing (1990) pp. 138–148, DOI: 10.1145/100216.100231. Google Scholar- Theory of Computing Systems 33(5/6), 427 (2000), DOI: 10.1007/s002240010009. Crossref, ISI, Google Scholar
- SIAM J. on Computing 21(6), 1070 (1992), DOI: 10.1137/0221063. Crossref, ISI, Google Scholar
C. Martel , R. Subramonian and A. Park , Asynchronous PRAMs are (almost) as good as synchronous PRAMs, Proc. of 31st IEEE Symposium on Foundations of Computer Science (1990) pp. 590–599, DOI: 10.1109/FSCS.1990.89580. Google Scholar- Information Processing Letters 39(2), 59 (1991), DOI: 10.1016/0020-0190(91)90156-C. Crossref, ISI, Google Scholar
- Communications of the ACM 33(8), 103 (1990), DOI: 10.1145/79173.79181. Crossref, ISI, Google Scholar
-
U. Vishkin , Explicit multi-threading (XMT) bridging models for instruction parallelism , Proc. of 10th ACM Symposium on Parallel Algorithms and Architectures ( 1998 ) , DOI: 10.1145/277651.277680 . Google Scholar


