Back to Search
Start Over
Classifying Matrices Separating Rows and Columns.
- Source :
-
IEEE Transactions on Parallel & Distributed Systems . Jul2004, Vol. 15 Issue 7, p654-665. 12p. - Publication Year :
- 2004
-
Abstract
- 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. This paper shows how the well-known Leighton's Columnsort algorithm can be modified to solve the classification problem of N = rs numbers, with 1 ≤ s ≤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 + log r) time and uses an O(r log r(s + log r)) work. The implementation shows that, when N = r log r, there is a classifier network solving the classification problem on N numbers in the same O(log r) time and using the same O(r log r) comparators as an r-classifier, thus saving a log r factor in the number of comparators over an (r log r)-classifier. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10459219
- Volume :
- 15
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Parallel & Distributed Systems
- Publication Type :
- Academic Journal
- Accession number :
- 13705516
- Full Text :
- https://doi.org/10.1109/TPDS.2004.16