Asynchronous Parallel Computing, Fault Tolerance, and Randomization

一类重要的实用并行计算机是由由许多大粒度处理器组成的机器组成的。这些处理器异步执行，并且假定内存是分布式的。试图在这样一个并行系统上执行一个通用的n线程并行程序P提出了理论和实践上的挑战。必须提供实现同步屏障、处理器之间的负载共享和平衡以及尊重内存局部性的程序执行的机制。本研究中使用的方法是定义算法和程序转换（编译）T，以便T(P)在任何P上正确有效地执行。这种模拟执行不需要目标机器中任何专门的硬件或操作系统机制。特别有趣的是并行程序是大粒度的情况，即在每个并行步骤中，在一些或大多数并行线程上执行大量指令块。假设并行程序已经优化，使得并行步内的代码块相当大。本项目研究大粒度并行程序的最一般情况，特别注意内存局域性和内存容错性，采用随机化。进一步的目标是实现拉斯维加斯风格的结果，即较小的预期运行时间和无错误。

An important class of practical parallel computers consists of machines comprising many large grained processors. These processors execute asynchronously and memory is assumed to be distributed. Trying to execute a general n-thread parallel program P on such a parallel system poses theoretical and practical challenges. One must provide mechanisms for implementing the synchronization barriers, for load sharing and balancing amongst the processors, and for program executing that respects memory locality. The approach used in this research is to define algorithms and a program transformation (compilation) T so that T(P) executes correctly and efficiently on any P. This simulated execution does not require any specialized hardware or operating system mechanisms in the target machine. Of particular interest is the case that the parallel program is large-grained, i.e. that in each parallel step a substantial block of instructions is executed on some or most of the parallel threads. It is assumed that the parallel program is already optimized so as to make the blocks of code within the parallel step quite large. This project studies the most general case of large grained parallel programs, paying particular attention to memory locality and to memory fault-tolerance, employing randomization. A further goal is to achieve Las Vegas style results, i.e. small expected running time and no errors.