Выделение явного уровня реализации алгоритмов для использования в проекте Algo500

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

Аннотация


Исследование и описание свойств алгоритмов крайне важно для их эффективной реализации на различных типах целевых программно-аппаратных платформ. Этой актуальной задаче посвящен проект создания Открытой энциклопедии свойств алгоритмов AlgoWiki, начатый в Московском государственном университете имени М.В. Ломоносова в 2014 году. В рамках проекта была предложена единая универсальная схема описания свойств алгоритмов, в которой особое внимание уделялось свойствам, связанным с параллелизмом. Множество описанных по данной схеме алгоритмов послужило основой описания структуры предметной области в рамках иерархической схемы «Задача—Метод—Алгоритм–Реализация». Однако для дальнейшего развития проекта AlgoWiki потребовалось выделить реализации алгоритмов, ранее включенные в описания свойств алгоритмов, в отдельную сущность. В данной статье изложена схема описания свойств реализаций алгоритмов, также как и модификация изначальной схемы описания свойств самих алгоритмов. Преобразование описаний в энциклопедии AlgoWiki по данной схеме было выполнено для всех страниц проекта, и оно позволяет как более качественно описывать свойства реализаций алгоритмов, так и интегрировать проект энциклопедии AlgoWiki с проектом Algo500, реализующим масштабируемую цифровую платформу для совместного анализа свойств алгоритмов и компьютерных архитектур.

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


Algo500; AlgoWiki; задача; метод; алгоритм; реализация; суперкомпьютер; рейтинг

Полный текст:

PDF

Литература


Voevodin V., Antonov A., Dongarra J. AlgoWiki: an Open Encyclopedia of Parallel Algorithmic Features. Supercomput. Front. and Innov. 2015. Vol. 1, no. 2. P. 4–18. DOI: 10.14529/jsfi150101.

Voevodin V. An AlgoWiki open encyclopedia of algorithmic features: from mobile to extreme scale. Numer. methods and program. 2015. Vol. 16, no. 1. P. 99–111. (in Russian) DOI: 10.26089/NumMet.v16r111.

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.

MediaWiki. URL: https://www.mediawiki.org (accessed: 01.12.2022).

Wikipedia. URL: https://wikipedia.org (accessed: 01.12.2022).

Open Encyclopedia of Parallel Algorithmic Features. URL: http://algowiki-project.org/en (accessed: 01.12.2022).

Antonov A., Nikitenko D., Voevodin Vl. Algo500 — a New Approach to the Joint Analysis of Algorithms and Computers. Lobachevskii Journal of Mathematics. 2020. Vol. 41, no. 8. P. 1435–1443. DOI: 10.1134/S1995080220080041.

Antonov A.S., Maier R.V. Development and Implementation of the Algo500 Scalable Digital Platform Architecture. Lobachevskii J Math. 2022. Vol. 43. P. 837–847. DOI: 10.1134/S1995080222070058.

Voevodin V.V., Voevodin Vl.V. Parallel Computing. St. Petersburg, BHV-Petersburg, 2002. 608 p. (in Russian)

Antonov A.S., Volkov N.I. An AlgoView Web-visualization System for the AlgoWiki Project. Communications in Computer and Information Science. 2017. Vol. 753. P. 3–13. DOI: 10.1007/978-3-319-67035-5_1.

Antonov A., Volkov N. Interactive 3D Representation as a Method of Investigating Information Graph Features. Communications in Computer and Information Science. 2018. Vol. 965. P. 587–598. DOI: 10.1007/978-3-030-05807-4_50.

Antonov A.S., Volkov N.I. Information Graph Visualization Using AlgoView Software Tool. Lobachevskii J Math. 2020. Vol. 41, no. 6. P. 1427–1434. DOI: 10.1134/S199508022008003X.

Cholesky, A.-L. Sur la resolution numerique des systemes dequations lineaires. La SABIX, Bulletins deja publies, Sommaire du bulletin. 2005. No. 39. P. 81–95.

Antonov A., Frolov A., Konshin I., Voevodin Vl. Hierarchical Domain Representation in the AlgoWiki Encyclopedia: From Problems to Implementations. Communications in Computer and Information Science. 2018. Vol. 910. P. 3–15. DOI: 10.1007/978-3-319-99673-8_1.

Popov A., Nikitenko D., Antonov A., Voevodin Vl. Formal model of problems, methods, algorithms and implementations in the advancing AlgoWiki open encyclopedia. CEUR Workshop Proc. 2018. Vol. 2281. P. 1–11.

Antonov A.S., Maier R.V. A New Representation of Algorithmic Approaches in the AlgoWiki Encylopedia. Lobachevskii J Math. 2021. Vol. 42, no. 7. P. 1483–1491. DOI: 10.1134/S1995080221070039.

Antonov A., Voevodin Vad., Voevodin Vl., Teplov A. A Study of the Dynamic Characteristics of Software Implementation as an Essential Part for a Universal Description of Algorithm Properties. 24th Euromicro International Conference on Parallel, Distributed, and Network- Based Processing Proceedings, February 17–19, 2016. P. 359–363. DOI: 10.1109/PDP.2016.24.

Voevodin V.V., Shvets P.A. Covering method for assessing the locality of data use in programs. Bulletin of the Ufa State Aviation Technical University. 2014. Vol. 18, no. 1(62). P. 224–229. (in Russian)

Antonov A., Teplov A. Generalized approach to scalability analysis of parallel applications. Lecture Notes in Computer Science. 2016. Vol. 10049. P. 291–304. DOI: 10.1007/978-3-319-49956-7_23.

Antonov A., Dongarra J., Voevodin V. AlgoWiki Project as an Extension of the Top500 Methodology. Supercomputing Frontiers and Innovations. 2018. Vol. 5, no. 1. P. 4–10. DOI: 10.14529/jsfi180101.

Home - | TOP500. URL: https://top500.org (accessed: 01.12.2022).

Dongarra J.J., Bunch J.R., Moler G.B., Stewart G.W. LINPACK Users’ Guide. Society for Industrial and Applied Mathematics, 1979–1993.

Graph 500 | large-scale benchmarks. URL: https://graph500.org (accessed: 01.12.2022).

Murphy R.C., Wheeler K.B., Barrett B.W., Ang J.A. Introducing the Graph 500. Cray User’s Group (CUG). May 5, 2010. Vol. 19. P. 45–74.

HPCG Benchmark. URL: https://www.hpcg-benchmark.org (accessed: 01.12.2022).

Heroux M., Dongarra J. Toward a New Metric for Ranking High Performance Computing Systems. UTK EECS Tech Report and Sandia National Labs Report SAND2013-4744, June 2013.

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.




DOI: http://dx.doi.org/10.14529/cmse230105