Describing and Analyzing Properties, Features and Characteristics of Algorithms in the AlgoWiki Open Encyclopedia of Parallel Algorithmic Features
DOI:
https://doi.org/10.14529/cmse260201Keywords:
algorithm, parallelism, supercomputer, co-design, computational complexity, parallel complexity, parallelism resource, speedup, information dependency graph, AlgoWikiAbstract
Investigating the properties of algorithms is a crucial step in their effective implementation on high-performance computing systems. This paper examines the properties, features, and characteristics of algorithms that can be useful for such analysis. It also discusses the necessary preliminary steps to transform algorithms into a form suitable for analysis and comparison. Analytical characteristics of algorithms – that is, those properties that can be described numerically or formulaically – are highlighted, with an emphasis on properties related to parallelism. Many of the properties discussed are proposed for algorithms for the first time, while at the same time being similar to those commonly considered for software implementations. All of the properties discussed are illustrated with several examples for well-known algorithms, such as summation of vector elements, the scalar product of two vectors, the multiplication of two dense square matrices, and the Givens (rotation) method of the QR factorization of a square matrix. In the future, based on the study of the considered properties, it is proposed to solve problems of supercomputer co-design for the joint analysis of the properties of algorithms, software implementations and supercomputer systems.
References
Antonov A. Review of methods for describing the structure of algorithms. Numerical Methods and Programming. 2025. Vol. 26, no. 4. P. 548–568. (in Russian) DOI: 10.26089/NumMet.v26r436.
Voevodin V., Antonov A., Dongarra J. Why is it hard to describe properties of algorithms? Procedia Computer Science. 2016. Vol. 101. P. 4–7. DOI: 10.1016/j.procs.2016.11.002.
Voevodin V., Voevodin V. Parallel computing. BHV-Peterburg, 2002. 608 p. (in Russian).
Antonov A., Volkov N. Information Graph Visualization Using AlgoView Software Tool. Lobachevskii J. Math. 2020. Vol. 41, no. 6. P. 1427–1434. DOI: 10.1134/S199508022008003X.
Skryabin G., Gadieva T., Antonov A. A New Version of the AlgoView System for 3D Visualization and Interactive Analysis of Information Graphs of Algorithms. Parallel Computational Technologies. Vol. 2241 / ed. by L. Sokolinsky, M. Zymbler, V. Voevodin, J. Dongarra. Cham: Springer, 2024. P. 19–33. Communications in Computer and Information Science. DOI: 10.1007/978-3-031-73372-7_2.
Antonov A., Volkov N. Study of the Algorithms Information Structure as the Basis of a Training Workshop. Supercomputing. Vol. 1510 / ed. by V. Voevodin, S. Sobolev. Cham: Springer, 2021. P. 404–414. Communications in Computer and Information Science. DOI: 10.1007/978-3-030-92864-3_31.
Open Encyclopedia of Parallel Algorithmic Features – Algowiki. URL: https://algowikiproject.org/en (accessed: 23.01.2026).
Description of algorithm properties and structure – Algowiki. URL: https://algowikiproject.org/en/Description_of_algorithm_properties_and_structure (accessed: 23.01.2026).
Antonov A. Wiki Representation and Analysis of Knowledge About Algorithms. Supercomputing. Vol. 13708 / ed. by V. Voevodin, S. Sobolev, M. Yakobovskiy, R. Shagaliev. Cham: Springer, 2022. P. 604–616. Lecture Notes in Computer Science. DOI: 10.1007/978-3-031-22941-1_44.
MediaWiki. URL: https://www.mediawiki.org (accessed: 23.01.2026).
Algorithm classification – Algowiki. URL: https://algowiki-project.org/en/Algorithm_classification (accessed: 23.01.2026).
Antonov A., Frolov A., Konshin I., Voevodin V. Hierarchical Domain Representation in the AlgoWiki Encyclopedia: From Problems to Implementations. Parallel Computational Technologies. Vol. 910 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2018. P. 3–15. Communications in Computer and Information Science. DOI: 10.1007/978-3-319-99673-8_1.
Popov A., Nikitenko D., Antonov A., Voevodin V. Formal Model of Problems, Methods, Algorithms and Implementations in the Advancing AlgoWiki Open Encyclopedia. CEUR Workshop Proc. Vol. 2281. 2018. P. 1–11. URL: http://ceur-ws.org/Vol-2281/#paper-01.
Givens method – Algowiki. URL: https://algowiki-project.org/en/Givens_method (accessed: 23.01.2026).
Help:Templates – MediaWiki. URL: https://www.mediawiki.org/wiki/Help:Templates/en (accessed: 23.01.2026).
Knuth D. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd Edition. 2001. 672 p.
Akl S. The Design and Analysis of Parallel Algorithms. Prentice Hall, 1989. 412 p.
Skiena S. The Algorithm Design Manual Second Edition. Springer, 2011. 739 p.
Lobanova V., Voronina O., Lobanova N. Theory of Algorithms: A Tutorial. Orel: Orel State University named after I.S. Turgenev, 2017. 95 p. (in Russian).
Mehlhorn K., Sanders P. Algorithms and Data Structures: The Basic Toolbox. Springer Science & Business Media, 2008. 305 p. DOI: 10.1007/978-3-540-77978-0.
Cormen T., Leiserson C.E., Rivest R.L., Stein C. Introduction To Algorithms, 3rd Edition. Milton, Qld., Jacaranda Wiley, 2009. 1292 p.
Sedgewick R. Algorithms in C, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching. Addison-Wesley Professional, 1997. 702 p.
Reingold E. Basic Techniques for Design and Analysis of Algorithms. Chapman, Hall/CRC, 2004. 3–1 p. DOI: 10.1201/9780429171529-4.
JaJa J. An Introduction to Parallel Algorithms. Addison Wesley Longman Publishing Co., Inc., United States, 1992. 566 p.
Alsuwaiyel M. Parallel algorithms. World Scientific Publishers, 2022. 400 p. DOI: 10.1142/12744.
Blelloch G., Maggs B. Parallel Algorithms. Computer science handbook / editor-in-chief, Allen B. Tucker–2nd ed. 2004. 10-10–41 p.
Selivanova I., Blinov V. Fundamental Algorithms in C++. Construction and Analysis of Data Processing Algorithms: A Tutorial. Ekaterinburg: Ural University Publishing House, 2015. 108 p. (in Russian).
McConnell J. Analysis of Algorithms. Jones & Bartlett Learning, 2008. 451 p.
Stone doubling algorithm for solving bidiagonal SLAEs. URL: https://algowiki-project.org/en/Stone_doubling_algorithm_for_solving_bidiagonal_SLAEs (accessed: 23.01.2026) (in Russian).
Aho A., Hopcroft J., Ullman J. The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., 1974. 480 p.
Antonov A., Maier R., Nikitenko D., Voevodin V. An Approach to Solving the Problem of Supercomputer Co-design. Lobachevskii J Math. 2024. Vol. 45, no. 7. P. 2965–2973. DOI: 10.1134/S1995080224603680.
Deterministic algorithm. URL: https://xlinux.nist.gov/dads/HTML/deterministicAlgorithm.html (accessed: 23.01.2026).
Smith J. The Design and Analysis of Parallel Algorithms. Oxford University Press, 1993. 470 p.
Casanova H., Legrand A., Robert Y. Parallel Algorithms. CRC PRESS, 2020. 335 p.
Patterson D., Hennessy J. Computer Organization and Design. 4th Edition. Elsevier, 2012. 919 p.
Voevodin V., Antonov A., Nikitenko D., et al. Supercomputer Lomonosov-2: Large Scale, Deep Monitoring and Fine Analytics for the User Community. Supercomputing Frontiers and Innovations. 2019. Vol. 6, no. 2. P. 4–11. DOI: 10.14529/jsfi190201.
