Abstract
In this paper a new method for checking the subsumption relation for the optimal-size sorting network problem is described. The new approach is based on creating a bipartite graph and modelling the subsumption test as the problem of enumerating all perfect matchings in this graph. Experiments showed significant improvements over the previous approaches when considering the number of subsumption checks and the time needed to find optimal-size sorting networks. We were able to generate all the complete sets of filters for comparator networks with 9 channels, confirming that the 25-comparators sorting network is optimal. The running time was reduced more than 10 times, compared to the state-of-the-art result described in [6].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ajtai, M., Komlós, J., Szemerédi, E.: An 0(n log n) sorting network. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC 1983, pp. 1–9. ACM, New York (1983)
Baddar, S.W.A.H., Batcher, K.E.: Designing Sorting Networks: A New Paradigm. Springer, New York (2012). https://doi.org/10.1007/978-1-4614-1851-1
Batcher, K.E.: Sorting networks and their applications. In: Proceedings of the 30 April–2 May 1968, Spring Joint Computer Conference, pp. 307–314. ACM, New York (1968)
Bundala, D., Závodný, J.: Optimal sorting networks. In: Dediu, A.-H., Martín-Vide, C., Sierra-Rodríguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 236–247. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04921-2_19
Codish, M., Cruz-Filipe, L., Ehlers, T., Müller, M., Schneider-Kamp, P.: Sorting networks: to the end and back again. J. Comput. Syst. Sci. (2016)
Codish, M., Cruz-Filipe, L., Frank, M., Schneider-Kamp, P.: Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten). In: 2014 IEEE 26th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 186–193. IEEE (2014)
Codish, M., Cruz-Filipe, L., Schneider-Kamp, P.: The quest for optimal sorting networks: Efficient generation of two-layer prefixes. In: 2014 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), pp. 359–366. IEEE (2014)
Ehlers, T., Müller, M.: New bounds on optimal sorting networks. In: Beckmann, A., Mitrana, V., Soskova, M. (eds.) CiE 2015. LNCS, vol. 9136, pp. 167–176. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20028-6_17
Kipfer, P., Westermann, R.: Improved GPU sorting. GPU Gems 2, 733–746 (2005)
Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol. 3, 2nd edn. Addison Wesley Longman Publishing Co. Inc., Redwood City (1998)
Morgenstern, A., Schneider, K.: Synthesis of parallel sorting networks using SAT solvers. In: MBMV, pp. 71–80 (2011)
Parberry, I.: A computer-assisted optimal depth lower bound for nine-inputsorting networks. Math. Syst. Theory 24(1), 101–116 (1991). https://doi.org/10.1007/BF02090393
Parberry, I.: On the computational complexity of optimal sorting network verification. In: Aarts, E.H.L., van Leeuwen, J., Rem, M. (eds.) Parle’ 91 Parallel Architectures and Languages Europe. LNCS, pp. 252–269. Springer, Heidelberg (1991). https://doi.org/10.1007/978-3-662-25209-3_18
Uno, T.: Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In: Leong, H.W., Imai, H., Jain, S. (eds.) ISAAC 1997. LNCS, vol. 1350, pp. 92–101. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63890-3_11
Valsalam, V.K., Miikkulainen, R.: Using symmetry and evolutionary search to minimize sorting networks. J. Mach. Learn. Res. 14, 303–331 (2013)
Acknowledgments
We would like to thank Michael Codish for introducing us to this research topic and Cornelius Croitoru for his valuable comments. Furthermore, we thank Mihai Rotaru for providing us with the computational resources to run our experiments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Frăsinaru, C., Răschip, M. (2019). An Improved Subsumption Testing Algorithm for the Optimal-Size Sorting Network Problem. In: Rousseau, LM., Stergiou, K. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019. Lecture Notes in Computer Science(), vol 11494. Springer, Cham. https://doi.org/10.1007/978-3-030-19212-9_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-19212-9_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-19211-2
Online ISBN: 978-3-030-19212-9
eBook Packages: Computer ScienceComputer Science (R0)