The goal of this research project is to better understand how to efficiently use the present generation of parallel computers and to influence the design of the next generation. The bulk of the research will be in the design of processor efficient parallel algorithms for abstract machines that possess a message passing architecture such as the Parallel Random Access Machine. The problems under investigation include the breadth first search of an undirected graph. Special attention will be given to architectures where the individual processors contain a relatively large amount of local memory. Message passing schemes which efficiently simulate the local memory model will be considered.
