A Message Ordering Problem in Parallel Programs

Bora Uçar and Cevdet Aykanat

Abstract. We consider a certain class of parallel program segments in which the order of messages sent affects the completion time. We give characterization of these parallel program segments and propose a solution to minimize the completion time. With a sample parallel program, we experimentally evaluate the effect of the solution on a PC cluster.

Key words. fine grain computation, message latency, message ordering