Z. M. Kedem
M. O. Rabin
ABSTRACT
In this paper, we address the problem of automatically transforming arbitrary programs written for an ideal parallel machine to run on a completely asynchronous machine. We present a transformation which can be applied to an ideal program such that the resulting program's execution on an asynchronous machine is work and space efficient, relative to the ideal program from which it is derived. Above all, the transformation will guarantee that the ideal program will execute in a continually progressive manner on the asynchronous machine; these instructions are not universal. Furthermore, the individual processors can get delayed for arbitrary amounts of time while executing any instruction. In contrast, previous work relied either on the asynchronous machine having universal read-modify-write instructions as primitives, or on limited asynchrony by restricting the relative speeds of the processors.
- Be83.M. Ben-Or, "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols," Proc. Pnd A CM Symposium on Principles of Distributed Computing, 27-30, 1983. Google Scholar
Digital Library
- AB91.Y. Aumann and M. Ben-Or, "Asymptotically Optimal P RAM Emulation on Faulty Hypereube," Proc. 3#nd IEEE Symp. on Foundations of Computer Science, pp. 440-446, 1991. Google ScholarDigital Library
- AB92.Y. Aumann and M. Ben-Or, "Computing with Faulty Arrays," Proc. Pgth A CM Symposium on Theory of Computing, 1992 (to appear). Google ScholarDigital Library
- BBKTW90.S. Ben-David, A. Borodin, R. Karp, E. Tardos, and A. Wigderson, "On the Power of Randomization in Online Algorithms," Proc. 22nd A CM Symposium on Theory of Computing, 1990. Google ScholarDigital Library
- BHG87.P. Bernstein, V. Hadzilacos, and N. Goodman, Concurrency Control and Recovery in Database Systems, Addison- Wesley, 1987. Google ScholarDigital Library
- C89.F. Christian, "Probabilistic Clock Synchronization," Distributed Computing, 3:146-158, 1989.Google ScholarDigital Library
- CZ89.R. Cole and O. Zajicek, "The APRAM: Incorporating Asynchrony into the PRAM Model," Proc. 1989 A CM Syrup. on Parallel Algorithms and Architectures, 170-178, 1989. Google ScholarDigital Library
- CZ90.R. Cole and O. Zajicek, "The Expected Advantage of Asynchrony," Proc. 2nd A CM Symp. on Parallel Algorithms and Architectures, 85-94, 1990. Google ScholarDigital Library
- DHSS84.D. Dolev, J. Halpern, B. Simons, and R. Strong, "Fault-tolerant Clock Synchronization," Proc. 3rd A CM Symp. on Principles of Distributed Computing, 89-102, 1984. Google ScholarDigital Library
- DSB88.M. Dubois, C. Scheurich, and F. Briggs, "Synchronization, Coherence, and Event Ordering in Multiprocessors," IEEE Computer, 9-21, 1988. Google ScholarDigital Library
- FLP85.M. Fischer, N. Lynch, and M. Paterson, "Impossibility of Distributed Consensus," J. of the A CM, 32(2):374-382, 1985. Google ScholarDigital Library
- FW78.S. Fortune and J. Wyllie, "Parallelism in Random Access Machines," Proc. lOth A CM Syrup. on Theory of Computing, 114-118, 1978. Google ScholarDigital Library
- Gi89.P. Gibbons, "A More Practical PRAM Model," Proc. 1989 A CM Syrup. on Parallel Algorithms and Architectures, 158- 168, 1989. Google ScholarDigital Library
- He88.M. Herlihy, "Impossibility and Universality results for Wait-free Synchronization," Proc. 7th A CM Symp. on Principles of Distributed Computing, 276-290, 1988. Google ScholarDigital Library
- He90.M. I-Ierlihy, "A Methodology for Implementing Highly Concurrent Data Structures," Proc. Pnd A CM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 197-206, 1990. Google ScholarDigital Library
- He91a.M. Herlihy, "Wait-free Synchronization," A CM Trans. on Programming Languages and Systems, 13(1):124-149, 1991. Google ScholarDigital Library
- He91b.M. Herlihy, "Impossibility Results for Asynchronous PRAM," Proc. 3rd A CM Syrup. on Parallel Algorithms and Architectures, 327-336, 1991. Google ScholarDigital Library
- He91c.M. tterlihy, "Randomized Wait-Free Concurrent Objects," Proc. l Oth A CM Syrup. on Principles of Distributed Computing, 11-21, 1991. Google ScholarDigital Library
- KS89.P. Kanellakis and A. Shvartsman, "Efficient Parallel Algorithms Can be Made Robust," Proc. 8th A CM Syrup. on Principles of Distributed Computing, 211-222, 1989. Google ScholarDigital Library
- KS91.P. Kanellakis and A. Shvartsman, "Efficient Parallel Algorithms on Restartable Fail-stop Processors," Proc. l Oth A CM Symp. on Principles of Distribuled Computing, 23-36, 1991. Google ScholarDigital Library
- KPS90.Z. Kedem, K. Palem, and P. Spirakis, "Efficient Robust Parallel Computations," Proc. 22nd A CM Syrup. on Theory of Computing, 138-148, 1990. Google ScholarDigital Library
- KPRS91.Z. Kedem, K. Palem, A. Raghunathan, and P. Spirakis, "Combining Tentative and Definite Algorithms for Very Fast Dependable Parallel Computing," Proc. 23rd A CM Syrup. on Theory of Computing, 381-390, 1991. Google ScholarDigital Library
- La78.L. Lamport, "Time, Clocks and the Ordering of Events in a Distributed System," Comm. of the A CM, 21(7):558-565, 1978. Google ScholarDigital Library
- LL84.J. Lundelius and N. Lynch, "An Upper and Lower Bound for Clock Synchronization," Information and Control, 62:190- 204, 1984.Google ScholarCross Ref
- LS85.L. Lamport and P. Melliar-Smith, "Synchronizing Clocks in the Presence of Faults," J. of the ACM, 32(1):52-78, 1985. Google ScholarDigital Library
- MPS89.C. Martel, A. Park, and R. Subramonian, "Fast Asynchronous Algorithms for Shared Memory Parallel Computers," Tech. Rep. CSE-89-8, Univ. of California-Davis, 1-17, July 25, 1989.Google Scholar
- MS91.C. Martel and 1#. Subramonian, "On the Complexity of Certified Write All Algorithms," Manuscript, 1991.Google Scholar
- MSP90.C. Martel, R. Subramonian, and A. Park, "Asynchronous PRAMs are (Almost) as Good as Synchronous PRAMs," Proc. 32nd IEEE Syrup. on Foundations of Computer Science, 590-599, 1990.Google Scholar
- Ni91.N. Nishimura, "Asynchrony in Shared Memory Parallel Computations," TR- 253/91, University of Toronto, 1991.Google Scholar
- Pl89.S. Plotkin, "Sticky Bits and Universality of Consensus," Proc. 8th A CM Symp. on Principles Distributed Computing, 159- 176, 1989 Google ScholarDigital Library
- Ra82.M. Rabin, "The Choice Coordination Problem," Acta Informatica, 17:121-134, 1982.Google ScholarDigital Library
- Ra83.M. Rabin, "Randomized Byzantine Generals," Proc. 24th IEEE Syrup. on Foundations of Computer Science, 403-409, 1983.Google Scholar
- Ra89.M. Rabin, "Efficient Dispersal of Information for Security, Load Balancing and Fault Tolerance," J. of the A CM, 36(2):335-34S, 1989. Google ScholarDigital Library
- Su91.R. Subramonian, Asynchronous Algo. rithms for Shared-Memory Parallel Computers, Ph.D. Dissertation, University of California, Davis, 1991. Google ScholarDigital Library
- Va90.L. Valiant, "A Bridging Model for Parallel Computation," Comm. of the A CM, 33(8):103-111, 1990. Google ScholarDigital Library
Index Terms
- Efficient program transformations for resilient parallel computation via randomization (preliminary version)
Recommendations
Microprogram Transformations
A descriptive notation is proposed for microprogramming which uses conventional sequential machine notation for the microprogram, and a register transfer language to define microoperations. The combination allows the definition of useful formal ...
Automatic validation of code-improving transformations on low-level program representations
Special issue on program transformationThis paper presents a general approach for automatically validating code-improving transformations on low-level program representations. The approach ensures the correctness of compiler and hand-specified optimizations at the machine instruction level. ...
Comments