Selection and Multiselection on Multi-Dimensional Meshes

摘要

This paper addresses the problem of selection and multiselection in multi-dimensional mesh-connected computers. For selecting the kth smallest element from a set S of n elements on a d dimensional mesh of p ≤ n processors, we present an efficient algorithm that runs in time O(d~2p~(1/d) + (n/p) log p log(kp)), where T_R = O(dp~(1/d)) is the routing cost and T_C = O((n/p) log p log(kp)) is the computation cost. Next, we present an efficient algorithm for selecting r elements at specified ranks from S on the mesh, where r < p ≤ n, which runs in time O(dT_R +log pT_C). Running on d dimensional mesh with processors operating in the SIMD mode under unshuffled row-major indexing, both algorithms are close to time optimal as d is usually small.