PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Bertossi A. A., Olariu S., Pinotti M. C., Zheng S. Classifying matrices separating rows and columns. In: Ieee Transactions on Parallel and Distributed Systems, vol. Vol. 15 (No. 7) pp. 654 - 665. IEEE Computer Society, 2004.
 
 
Abstract
(English)
The classification problem transforms a set of N numbers in such a way that none of the first N/2 numbers exceeds any of the last N/2 numbers. A comparator network that solves the classification problem on a set of r numbers is commonly called an r-classifier. We show how the well-known Leighton's Columnsort algorithm can be modified to solve the classification problem of N=rs numbers, with 1 /spl les/ s /spl les/ r, using an r-classifier instead of an r-sorting network. Overall, the r-classifier is used O(s) times, namely, the same number of times that Columnsort applies an r-sorter. A hardware implementation is proposed that runs in optimal O(s+logr) time and uses an O(rlogr(s + logr)) work. The implementation shows that, when N= rlogr, there is a classifier network solving the classification problem on N numbers in the same O(logr) time and using the same O(rlogr) comparators as an r-classifier, thus saying a logr factor in the number of comparators over an (rlogr)-classifier.
URL: http://ieeexplore.ieee.org/xpl/abs_free.jsp?isNumber=28930&prod=JNL&arnumber=13
Subject Comparator network
Classifier
Classification problem
Hardware algorithm
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