Описание и анализ свойств, особенностей и характеристик алгоритмов в Открытой энциклопедии свойств алгоритмов AlgoWiki

Александр Сергеевич Антонов

doi:10.14529/cmse260201

Авторы

Александр Сергеевич Антонов Московский государственный университет имени М.В. Ломоносова, Научно-исследовательский вычислительный центр https://orcid.org/0000-0003-2820-7196

DOI:

https://doi.org/10.14529/cmse260201

Ключевые слова:

алгоритм, параллелизм, суперкомпьютер, кодизайн, вычислительная сложность, параллельная сложность, ресурс параллелизма, ускорение, граф информационных зависимостей, AlgoWiki

Аннотация

Исследование свойств алгоритмов является важнейшим этапом в процессе их эффективной реализации на высокопроизводительных вычислительных системах. В данной статье рассматриваются свойства, особенности и характеристики алгоритмов, которые могут быть полезны для проведения такого анализа. Рассмотрены необходимые предварительные шаги, которые нужно выполнить для приведения алгоритмов к виду, в котором их можно анализировать и сравнивать между собой. Выделяются аналитические характеристики алгоритмов, то есть те свойства, которые могут быть описаны в числовом или формульном виде, при этом акцент делается на свойствах, связанных с параллелизмом. Многие из рассматриваемых свойств именно для алгоритмов предлагаются впервые, в то же время являясь аналогичными свойствам, которые принято рассматривать для программных реализаций. Все рассматриваемые свойства иллюстрируются несколькими примерами для хорошо известных алгоритмов, таких как суммирование элементов вектора, скалярное произведение двух векторов, перемножение двух плотных квадратных матриц и метод Гивенса (вращений) QR-разложения квадратной матрицы. В дальнейшем на базе исследования рассмотренных свойств предполагается решать задачи суперкомпьютерного кодизайна по совместному анализу свойств алгоритмов, программных реализаций и суперкомпьютерных систем.

Библиографические ссылки

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.