| Abstract: | This paper describes how the algorithm called parallel merge sort can be used to teach fundamental concepts in the design of parallel algorithms for a network of workstations (NOW). First, the basic algorithm is introduced and its performance studied. Then, through a series of improvements based on a close examination of the algorithm and the underlying communication network, students are shown how performance can be significantly enhanced. This incremental approach lets students observe, first-hand, the critical importance of communication overhead, granularity, latency, and load balancing in designing efficient distributed parallel algorithms for a NOW environment. |
