Research Initiation Award: Parallel Algorithms for Scalable Multicomputers

本研究在CM-5并行机上设计并实现了几类并行算法，从算法技术、划分方案和容错方案三个方面进行了探讨。这个项目的动机是开发一种设计和实现可伸缩多计算机的快速、高效和健壮的并行算法的方法。在算法技术的上下文中，研究结果使设计者能够在同步和异步算法之间进行选择，并允许设计者在并行算法的不同级别使用不同的技术，例如迭代和分而治之。该研究还确定了特定应用程序的各种分区方案之间的权衡。在容错技术的背景下，该研究展示了如何利用迭代算法所固有的容错能力，并为诸如求解偏微分方程组之类的应用设计合适的容错方案。在CM-5并行机上实现的初步结果表明，异步迭代算法的加速比优于同步迭代算法，并且几种分而治之的算法可以在CM-5并行机上高效地实现。作为该项目的一部分，制定并解决了CM-5系统特有的许多子问题。

This research explores three aspects of algorithmic techniques, partitioning schemes and fault-tolerance schemes of parallel algorithms by designing and implementing several classes of algorithms on the CM-5 parallel machine. The motivation for this project is in developing a methodology for the design and implementation of fast, efficient, and robust parallel algorithms for scalable multicomputers. In the context of algorithmic techniques, the results of the research enable the designer to choose between synchronous and asynchronous algorithms, and allow the designer to use different techniques, such as iterative and divide-and-conquer, at different levels of a parallel algorithm. The research also identifies the tradeoffs among various partitioning schemes for a given application. In the context of fault-tolerance techniques, the research shows how to exploit the fault-tolerance inherent in iterative algorithms, and devise suitable fault-tolerance schemes for applications such as solving partial differential equations. Preliminary results, obtained from implementations on the CM-5 machine, indicate that asynchronous iterative algorithms achieve speedups over their synchronous counterparts, and that several divide-and-conquer algorithms can be implemented efficiently on the CM-5 parallel machine. As part of this project, many subproblems that are specific to the CM-5 system are formulated and solved.