An optimal hardware-algorithm for sorting using a fixed-size parallel sorting device

Olariu, S

doi:10.1109/12.895849

Return

An optimal hardware-algorithm for sorting using a fixed-size parallel sorting device

2000-01-01

PRE

Olariu, S *

Cristina M. Pinotti

Zheng, SQ

DOI：10.1109/12.895849

Original

Original request for help

Save

Abstract

En 中文

We present a hardware-algorithm for sorting N elements using either a p-sorter or a sorting network of fixed I/O size p while strictly enforcing conflict-free memory accesses. To the best of our knowledge, this is the first realistic design that achieves optimal time performance, running in Theta (N log N/p log p) time for all ranges of N. Our result completely resolves the problem of designing an implementable, time-optimal algorithm for sorting N elements using a p-sorter. More importantly, however, our result shows that, in order to achieve optimal time performance, ail that is needed is a sorting network of depth O(log(2) p) such as, for example, Batcher's classic bitonic sorting network.

Keywords:

special-purpose architectures

hardware-algorithms

sorting networks

columnsort

VLSI