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.