Eric Hao Philip D. MacKenzie
Quentin F. Stout
EECS Department, University of Michigan
Abstract: Our main result is a Θ(log n) time algorithm for selecting the kth smallest element in a set of n elements stored in a 2-dimensional reconfigurable mesh (rmesh) with n processors. First we show that a good approximation of the median can be found in Θ(log log n) time, which can be used to solve 2-dimensional linear programming over n equations in Θ(log n loglog n). <\p>
We also show an Ω(log log n) lower bound for selection, which is the first non-trivial lower bound on the rmesh which does not rely on the bandwidth constraints of the mesh and does not restrict the processor instruction set.
Keywords: reconfigurable mesh, rmesh, selection, median, linear programming, parallel algorithm, parallel computer
Complete paper A preliminary version of thie paper appeared in Proc. Frontiers `92: 4th Symp. on Frontiers of Massively Parallel Computation (1992), pp. 38-45.
Copyright © 2015-2017 Quentin F. Stout |