PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Zheng S., Olariu S., Pinotti M. C. A systolic architecture for sorting and arbitrary number of elements. In: Proceedings of 3rd International Conference on Algorithms and Architectures for Parallel Processing (Melbourne, Australia, 1997). Proceedings, pp. 113 - 126. IEEE, 1997.
 
 
Abstract
(English)
We propose a simple systolic VLSI sorting architecture whose main feature is the pipelined use of a sorting network of fixed I/O size p to sort an arbitrarily large data set of N elements. Our architecture is feasible for VLSI implementation and its time performance is virtually independent of the cost and depth of the underlying sorting network. Specifically, we show that by using our design N elements can be sorted in T(N/p log N/p) time without memory access conflicts. We also show how to use an AT2-optimal sorting network of fixed I/O size p to construct a similar systolic architecture that sorts N elements in T(N/p log N/plogp) time.
Subject Systolic architecture


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