Using Parallel Merge Sort to Teach Fundamental Concepts in Distributed Parallelism

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.