Highly Efficient Asynchronous Execution of Large-Grained Parallel Programs

An n-thread parallel program p is large-grained if in every parallel step the computations on each of the threads are complex procedures requiring numerous processor instructions. This practically relevant style of programs differs from PRAM programs in its large granularity and the possibility that within a parallel step the computations on different threads may considerably vary in size. Let M be an n-processor asynchronous parallel system, with no restriction on the degree of asynchrony and without any specialized synchronization mechanisms. It is a challenging theoretical as well as practically important problem to ensure correct execution of P on such a parallel machine. Let P be a large-grained program requiring total work W for its execution on a synchronous a-processor parallel system. We present a transformation (compilation) of P into a program C(P) which correctly and efficiently effects the computation of P on the asynchronous machine M. Under moderate assumptions on the granularity of threads and the size of the program variables, execution of C(P) requires just O(Wlog* n) expected total work, and the memory space overhead is a small multiplicative constant. >

Authors

• Yonatan Aumann
• Zvi M. Kedem
• Krishna V. Palem
• Michael O. Rabin

Keywords

• Yarn
• Concurrent computing
• Computer science
• Computer aided instruction
• Phase change random access memory
• Parallel machines
• Bridges
• Contracts
• Error correction codes
• Application software
• Parallelization
• Asynchronous Execution
• Control Variables
• Parallel System
• Total Work
• Memory Space
• Parallel Steps
• Asynchronous System
• Multiple Factors
• Hash Function
• Large Grains
• Large Objects
• Factor C
• Start Of Phase
• Probability 2
• Random Number Table
• Synchronous Motor
• Properdin
• Linearizable
• Shared Memory
• Clock Phase
• M Blocks