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.
