Istituto di Scienza e Tecnologie dell'Informazione     
Olariu S., Pinotti M. C., Zheng S. An optimal hardware-algorithm for sorting using a fixed-size parallel sorting device. 2000.
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 N logNp 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, all that is needed is a sorting network of depth Olog2 p such as, for example, Batcher's classic bitonic sorting network.
Subject Special-purpose architectures
sorting networks
C.3 special purpose and application based systems

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional