×

On the complexity of min-max sorting networks. (English) Zbl 1248.68179

Summary: This paper extends previous work on sorting networks (SNs) based on min/max circuits. In particular, we have identified the complexity of both min/max-based sorting and merging networks showing that, depending on design choice, the time complexity of this kind of SN ranges from \(O(1)\) to \(O(\log (n))\) and spatial complexity from \(O(n2^{n})\) to \(O(n^{2})\), respectively. Moreover, we show that both \(AT\) and \(AT^{2}\) metrics of the proposed SN are better than those of Batcher’s SNs also for SNs with several hundreds of inputs.
In addition to these results we show how to design a fast digital, serial, pipelined sorting network using FPGA technology. As expected, FPGA synthesis results confirm our theoretical analysis.

MSC:

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions, with Formulas, Graphs and Mathematical Tables (1974), Dover: Dover New York) · Zbl 0171.38503
[2] Akl, S. G., Parallel Sorting Algorithms (1985), Academic Press · Zbl 0526.68062
[3] K.E. Batcher, Sorting networks and their applications, in: AFIPS Spring Joint Computer Conference, 32, 1968.; K.E. Batcher, Sorting networks and their applications, in: AFIPS Spring Joint Computer Conference, 32, 1968.
[4] Borwein, P.; Erdelyi, T., Polynomials and Polynomial Inequalities (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0840.26002
[5] T. Chen, S. Liu, ATM switching. Wiley Encyclopedia of Telecommunications, December 2002.; T. Chen, S. Liu, ATM switching. Wiley Encyclopedia of Telecommunications, December 2002.
[6] V. Chvátal. Lecture Notes On The New AKS Sorting Network, 1992. Tech. Rep., Rutgers University, 1992.; V. Chvátal. Lecture Notes On The New AKS Sorting Network, 1992. Tech. Rep., Rutgers University, 1992.
[7] Colavita, A.; Mumolo, E.; Capello, G., A novel sorting algorithm and its application to a gamma-ray telescope asynchronous data acquisition system, Nuclear Instruments and Methods in Physics Research, Section A, 394, 374-380 (1997)
[8] Colavita, A. A.; Cicuttin, A.; Fratnik, F.; Capello, G., SORTCHIP: A VLSI implementation of hardware algorithm for continuous data sorting, IEEE Journal of Solid-State Circuits, 38, 6 (2003)
[9] Rahayu, J. W.; Taniar, D., Parallel database sorting, Information Sciences, 146, 171-219 (2002) · Zbl 1033.68559
[10] Proietti, G.; Nardelli, E., Efficient unbalanced merge sort, Information Sciences, 176, 1321-1337 (2006) · Zbl 1156.68369
[11] Prasad, D., Sorting networks on FPGA, (Proceedings of the 10th WSEAS International Conference on Telecommunications and Informatics and Microelectronics, Nanoelectronics, Optoelectronics, and WSEAS International Conference on Signal Processing, TELE-INFO’11/MINO’11/SIP’11 (2011), World Scientific and Engineering Academy and Society (WSEAS)), 29-31
[12] Nakamura, M., Time-slot interchanger for self-routing event building, Nuclear Instruments and Methods in Physics Research, Section A, 441, 510-516 (2000)
[13] Govindaraju, N., Gputerasort: high performance graphics co-processor sorting for large database management, (Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, SIGMOD ’06 (2006), ACM), 325-336
[14] Jun, Y., E-health networking, Digital Ecosystems and Technologies (EDT), 1, 77-80 (2010)
[15] Russo, M.; Campobello, G., A scalable VLSI speed/area tunable sorting network, Journal of Systems Architecture, 52, 589-602 (2006)
[16] Levi, T.; Even, G.; Litman, A., Optimal conclusive sets for comparator networks, Lecture Notes in Computer Science, 4474, 304-317 (2007) · Zbl 1201.68046
[17] Hennessy, J.; Patterson, D., Computer Architecture: A Quantitative Approach (1995), Morgan Kaufman · Zbl 0752.68014
[18] Lee, J.; Batcher, K. E., Minimizing communication in the bitonic sort, IEEE Transactions on Parallel and Distributed Systems, 11, 5, 459-474 (2000)
[19] N. Kahale and et al., Lower bounds for sorting networks, in: ACM Symposium on Theory of Computing, 1995, pp. 437-446.; N. Kahale and et al., Lower bounds for sorting networks, in: ACM Symposium on Theory of Computing, 1995, pp. 437-446. · Zbl 0968.68508
[20] Knuth, D., The Art of Computer Programming (1973), Addison-Wesley, vol. III
[21] T. Leighton, Tight bounds on the complexity of parallel sorting, in: ACM Symposium on Theory of Computing, 1984, pp. 71-80.; T. Leighton, Tight bounds on the complexity of parallel sorting, in: ACM Symposium on Theory of Computing, 1984, pp. 71-80.
[22] Levi, T.; Litman, A., Accelerating certain outputs of merging and sorting networks, Theoretical Computer Science, 410, 38-40, 3725-3732 (2009) · Zbl 1171.68007
[23] Levi, T.; Litman, A., The strongest model of computation obeying 0-1-principles, Theory of Computing Systems, 48, 374-388 (2011) · Zbl 1209.68252
[24] Lin, R.; Olariu, S., An efficient VLSI architecture for columnsort, IEEE Transactions on VLSI, 7, 1, 135-139 (1999)
[25] B.M. Maggs, B. Vocking, Improved routing and sorting on multibutterlies, in: ACM Symposium on Theory of Computing, May 1997, pp. 517-530.; B.M. Maggs, B. Vocking, Improved routing and sorting on multibutterlies, in: ACM Symposium on Theory of Computing, May 1997, pp. 517-530. · Zbl 0963.68005
[26] Ajtai, M.; Komlós, J.; Szemerédi, E., An O(nlog(n)) sorting network, Combinatorica, 3, 1-19 (1983) · Zbl 0523.68048
[27] Mavronicolas, M., Balancing networks: state of the art, Information Sciences, 97, 1-2, 125-157 (1997)
[28] Nakase, Y., A BiCMOS wired-OR logic, IEEE Journal of Solid-State Circuits, 30, 6 (1996)
[29] B. Pascal, Traite du Triangle Arithmetic, 1665.; B. Pascal, Traite du Triangle Arithmetic, 1665.
[30] Paterson, M. S., Improved sorting network with O(log n) depth, Algorithmica, 5, 75-92 (1990) · Zbl 0689.68066
[31] Rabaey, J. M., Digital Integrated Circuits (1996), Prentice Hall
[32] Russo, G. V.; Russo, M., A novel class of sorting networks, IEEE Transactions on Circuits and Systems-I, 43, 7, 544-552 (1996)
[33] Olariu, S.; Pinott, M. C.; Zheng, S. Q., How to sort N items using a sorting network of fixed I/O size, IEEE Transactions on Parallel and Distributed Systems, 10, 5, 487-499 (1999)
[34] Seiferas, J., Sorting-networks-of-logarithmic depth, further-simplified, Algorithmica, 53, 374-384 (2009) · Zbl 1172.68016
[35] Smith, M. J.S., Application-Specific Integrated Circuits (1997), Addison Wesley
[36] Sutherland, I.; Sproull, B.; Harris, D., Logical Effort: Designing Fast CMOS Circuits (1999), Morgan Kaufman
[37] Wegener, I., The Complexity of Boolean Functions (1987), John Wiley & Sons · Zbl 0623.94018
[38] Weste, N. H.E.; Eshraghan, K., Principles of CMOS VLSI Design: A System Perspective (1993), Addison Wesley
[39] Yun, K. Y.; James, K. W.; Farlie-Cuningham, R. H.; Chakraborty, S.; Cruz, R. L., A self-timed real-time sorting network, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 8, 3 (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.