Research Initiation Award: Parallel Algorithms for Scalable Multicomputers

研究启动奖：可扩展多计算机并行算法

• 批准号: 9308966
• 负责人: Suresh Chalasani
• 金额: $ 9万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-08-01 至 1996-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9308966&HistoricalAwards=false
• 关键词: Research; Initiation; Award; Parallel; Algorithms

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.

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