Document Type
Report
Date
10-1990
Keywords
Integer Sorting, ISR-PRAM, Model of Computation, PRAM, Parallel Processing, R-PRAM, Sorting
Language
English
Disciplines
Computer Sciences
Description/Abstract
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.
Recommended Citation
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. 61.
https://surface.syr.edu/eecs_techreports/61
Source
local
Additional Information
School of Computer and information Science, Syracuse University, SU-CIS-89-11