Theory and System Building for Asynchronous Parallel Computing

这项计划的目的，是扩展八达通系统的基本理论，加强、完善、测试和编写八达通系统的应用程序。八达通系统是由PI在1994-96年开发的。 Octopus是一个独特的新型软件层，它将集群工作站或PC板的计算能力结合在一起，产生一个容错的、可扩展的系统，为大型并行计算提供高吞吐量和快速周转。 Octopus基于并实现了以前和当前的基础工作，是将理论转化为实际系统的最好例子。 该项目继续与系统建设工作并行的基础工作，以双方的共同利益，并调查随机化的进一步应用。在过去的四年里，PI与其他人合作，创新了异步并行计算的理论。 异步并行系统（APS）由许多处理器组成，这些处理器以可能不同的速率执行，并在逻辑上（但不一定是物理上）寻址共享内存。 该理论展示了如何有效地模拟为同步并行计算机编写的并行程序的执行，而不会在处理器也可能失败的实际异步并行系统上出现故障。 最有效的模拟开发的大粒度的n线程并行程序。 在这样的程序中，大多数线程在每个并行步骤中执行大量的指令块，并且程序变量包括大量的存储器字（例如：大型矩阵的一行，或并行合并排序中的键串）。 由高带宽交换机连接的一组工作站或PC板是APS模型的一种实现。 这种不稳定性是由于没有共同的驱动时钟以及每个节点可能被多重编程的事实造成的。 Octopus系统由Octopus层管理的这样一个集群组成。 该系统已投入运行，实现了Octopus的控制、负荷分配和容错功能。

The thrust of this project is to extend the underlying theory, enhance, perfect, test, and write applications for the Octopus System which was developed by the PI during 1994-96. Octopus is a uniquely novel software layer that harnesses together the computing power of clustered workstations or PC boards to produce a fault-tolerant, scalable system which provides high throughput and fast turnaround for large parallel computations. Octopus is based on and realizes previous and current fundamental work and is a prime example for theory translated into an actual system. The project continues the fundamental work side by side with the system building work, to the mutual benefit of both, and investigates further applications of randomization. Over the past four years the PI has innovated, in collaboration with others, a theory of asynchronous parallel computations. The Asynchronous Parallel System (APS), consists of a number of processors executing at possibly different rates and addressing a logically (but not necessarily physically) shared memory. The theory showed how to efficiently simulate the execution of parallel programs written for synchronous parallel computers without faults on realistic asynchronous parallel systems in which processors may also fail. The most efficient simulations were developed for large-grained n-thread parallel programs. In such a program most threads execute a substantial block of instructions within each parallel step, and the program variables comprise a large number of memory words (examples are: a row of a large matrix, or a string of keys in a parallel merge-sort). A cluster of workstations or PC boards connected by a high bandwidth switch is one realization of the APS model. The asynchrony arises from the absence of a common driving clock and the fact that each node may be multi-programmed. The Octopus System consists of such a cluster managed by the Octopus layer. The system is up and running and realizes the control, loa d distribution, and fault-tolerance properties of Octopus.