Document Type

Report

Date

10-1990

Embargo Period

4-30-2012

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.

Additional Information

School of Computer and information Science, Syracuse University, SU-CIS-89-11

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.