Abstract
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 NC 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. Performance and correctness through cooperative axiomatic reasoning and temporal reasoning provide an additional basis for understanding parallel algorithm design and specification. Finally, the realities of algorithm design are presented through partitioning and mapping issues and models.
Recommended Citation
McMillin, Bruce M.; Lutfiyya, Hanan; Tsai, Grace; and Liu, Jun-Lin, "Parallel Algorithm Fundamentals and Analysis" (1993). Computer Science Technical Reports. 27.
https://scholarsmine.mst.edu/comsci_techreports/27
Meeting Name
International Summer Institute on Parallel Computer Architectures, Languages, and Algorithms (1993: Jul. 5-10, Prague, Czech Republic)
Department(s)
Computer Science
Keywords and Phrases
Algorithm Design; Embeddings; Speedup; Class NC; Reasoning
Report Number
CSC-93-05
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1993 University of Missouri--Rolla, All rights reserved.
Publication Date
10 Jul 1993
