FAST PARALLEL SORTING UNDER LOGP - EXPERIENCE WITH THE CM-5

In this paper, we analyze four parallel sorting algorithms (bitonic, c olumn, radix, and sample sort) with the LogP model. LogP characterizes the performance of modern parallel machines with a small set of param eters: the communication latency (L), overhead (o), bandwidth (g), and the number of processors (P). We develop implementations of these alg orithms in Split-C, a parallel extension to C, and compare the perform ance predicted by LogP to actual performance on a CM-5 of 32 to 512 pr ocessors for a range of problem sizes. We evaluate the robustness of t he algorithms by varying the distribution and ordering of the key valu es. We also briefly examine the sensitivity of the algorithms to the c ommunication parameters. We show that the LogP model is a valuable gui de in the development of parallel algorithms and a good predictor of i mplementation performance. The model encourages the use of data layout s which minimize communication and balanced communication schedules wh ich avoid contention. With an empirical model of local processor perfo rmance, LogP predictions closely match observed execution times on uni formly distributed keys across a broad range of problem and machine si zes. We find that communication performance is oblivious to the distri bution of the key values, whereas the local processor performance is n ot; some communication phases are sensitive to the ordering of keys du e to contention. Finally, our analysis shows that overhead is the most critical communication parameter in the sorting algorithms.