Theory and System Building for Asynchronous Parallel Computing

异步并行计算的理论与系统构建

• 批准号: 9700365
• 负责人: Michael Rabin
• 金额: $ 21.16万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-06-15 至 1999-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9700365&HistoricalAwards=false
• 关键词: Theory; System; Building; Asynchronous; Parallel

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.

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