This session explores, through the use of formal methods, the “intuition” used in creating a parallel algorithm design and realizing this design on distributed memory hardware. The algorithm class NG and the LSTM machine are used to show why some algorithms realize their promise of speedup better than others and the algorithm class NP is used to show why other algorithms will never be good for parallelization. The realities of algorithm design are presented through partitioning and mapping issues and models. Finally, correctness through cooperative axiomatic reasoning provides an additional basis for understanding parallel algorithm design and specification and is used for run-time assurance of distributed computing systems through operational evaluation.
McMillin, Bruce M.; Lutfiyya, Hanan; Tsai, Grace; and Liu, Jun-Lin, "Parallel Algorithm Fundamentals and Analysis" (1993). Computer Science Technical Reports. 39.
International Summer Institute on Parallel Computer Architectures, Languages, and Algorithms (1993: Jul. 5-10, Prague, Czech Republic)
Keywords and Phrases
Algorithm Design; Embeddings; Speedup; Class NG; Reasoning; Operational Evaluation
© 1993 University of Missouri--Rolla, All rights reserved.
10 Jul 1993