Sample Sort on Meshes
Jop F. Sibeyn · MPG.PuRe (Max Planck Society) · 1995
In this paper various algorithms for sorting on processor networks are considered. We focus on meshes, but the results can be generalized easily to other decomposable architectures. We consider the k-k sorting problem in which every PU initially holds k packets. We present well-known randomized and deterministic splitter-based sorting algorithms. We come with a new deterministic sorting algorithm which performs much better than previous ones. The number of routing steps is reduced by a refined deterministic splitter selection. Hereby deterministic sorting might become competitive with randomized sorting in practice. 1 Introduction 1.1 Problem and Machine Meshes. One of the most thoroughly investigated interconnection schemes for parallel computation is the n \\Theta n mesh, in which n 2 processing units, PUs, are connected by a twodimensional grid of communication links. Its immediate generalizations are d-dimensional n \\Theta \\Delta \\Delta \\Delta \\Theta n meshes. While meshes have ...