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

Olariu, S

doi:10.1109/12.895849

2000-01-01

PRE

Olariu, S *

Cristina M. Pinotti

Zheng, SQ

DOI：10.1109/12.895849

原文链接

原文求助

摘要

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.

Keyword:

special-purpose architectures

hardware-algorithms

sorting networks

columnsort

VLSI