Integer Sorting, ISR-PRAM, Model of Computation, PRAM, Parallel Processing, R-PRAM, Sorting
In this report, a fine-grained decomposition approach is used to obtain an optimal parallel solution to the Neighbor Localization Problem, which in turn is œ used to sort n θ(log n)-bit numbers optimally on an EREW model. The model of computation used is the EREW Reconfigurable PRAM (R-PRAM) that permits the use of “very small” processors. The main result of this report is a parallel EREW R-PRAM algorithm that sorts n θ(log n)-bit numbers in θ(log n) time with θ(n log n) “work”. The proposed algorithm is asymptotically optimal in time and efficiency. If a weaker variant of the R-PRAM (called the ISR-PRAM) is used, the efficiency suffers only a slight degradation.
Vaidyanathan, Ramachandran; Hartmann, Carlos R.P.; and Varshney, Pramod K., "Optimal Parallel Solutions to the Neighbor Localization Problem and Integer Sorting: A Fine Grained Approach" (1990). Electrical Engineering and Computer Science Technical Reports. Paper 61.