Parallel Sorting Pattern

A large number of parallel applications contain a compu-tationally intensive phase in which a large list of elements must be ordered based on some common attribute of the elements. How do we sort a sequence of elements on multi-ple processing units so as to minimize redistribution of keys while allowing processing units to do independent sorting work? 2. CONTEXT Sorting is the process of reordering a sequence taken as input and producing one that is ordered according to an attribute. Parallel sorting is the process of using multiple processing units to collectively sort an unordered sequence. The un-sorted sequence is composed of disjoint sub-sequences, each of which is associated with a unique processing unit. Par-allel sorting produces a fully sorted sequence composed of ordered sub-sequences, each of which is associated with a unique processing unit. The produced sequences are typi-cally ordered according to the given processor ordering and are of roughly equal length. It is important to realize that parallelization of sorting algo-rithms (particularly under the distributed memory model which we focus on) is a fundamentally different problem from acceleration or hardware performance tuning of a sort-ing algorithm. Indeed, such acceleration and tuning is of-ten implemented using techniques similar to parallel sort-ing algorithms implemented within a distributed memory model [1] [2]. However, the semantics and goals of such ac-celeration and tuning of sorting is often different than that of parallel sorting under the distributed memory model and deserves separate analysis that will not be provided here. In particular, we focus on sorting a sequence composed of a set of sequences, each associated with a logical memory. Parallel sorting under the distributed memory model is a fundamentally different problem from sorting under a se-quential or shared memory programming model. Sequentia