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.