Parallel integer sorting using small operations |
| |
Authors: | Ramachandran Vaidyanathan Carlos R P Hartmann Pramod K Varshney |
| |
Affiliation: | (1) Department of Electrical and Computer Engineering, Lousiana State University, 70803-5901 Baton Rouge, LA, USA;(2) School of Computer and Information Science, Syracuse University, 13244-4100 Syracuse, NY, USA;(3) Department of Electrical and Computer Engineering, Syracuse University, 13244-1240 Syracuse, NY, USA |
| |
Abstract: | We consider the problem of sortingn integers in the range 0,n
c
-1], wherec is a constant. It has been shown by Rajasekaran and Sen 14] that this problem can be solved optimally inO(logn) steps on an EREW PRAM withO(n) n
-bit operations, for any constant >O. Though the number of operations is optimal, each operation is very large. In this paper, we show thatn integers in the range 0,n
c
-1] can be sorted inO(logn) time withO(nlogn)O(1)-bit operations andO(n) O(logn)-bit operations. The model used is a non-standard variant of an EREW PRAMtthat permits processors to have word-sizes ofO(1)-bits and (logn)-bits. Clearly, the speed of the proposed algorithm is optimal. Considering that the input to the problem consists ofO (n logn) bits, the proposed algorithm performs an optimal amount of work, measured at the bit level.This work was partially supported by The Northeast Parallel Architectures Center (NPAC) at Syracuse University, Syracuse, NY 13244 and The Rome Air Development Center, under contract F30602-88-D-0027. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|