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

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

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

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 1 т.12, 2023 года.

Бесплатный доступ

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

Еще

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

Короткий адрес: https://sciup.org/147240349

IDR: 147240349   |   УДК: 004.421,   |   DOI: 10.14529/cmse230105

Extraction of an explicit level of algorithm implementation for use in the ALGO500 project

The study and description of the algorithm properties is extremely important for their effective implementation on various types of target software and hardware platforms. This topical task is the subject of a project to create an AlgoWiki Open encyclopedia of parallel algorithmic features, launched at Lomonosov Moscow State University in 2014. Within the framework of the project, a unified universal scheme for describing the algorithm properties was proposed, in which special attention to the properties associated with parallelism was paid. The set of algorithms described according to this scheme served as the basis for describing the structure of the subject area within the framework of the “Problem-Method-Algorithm-Implementation” hierarchical scheme. However, for the further development of the AlgoWiki project, it was necessary to separate the implementations of the algorithms that were previously included in the descriptions of the properties of the algorithms. This paper presents a scheme for describing the properties of algorithm implementations, as well as a modification of the original scheme for describing the properties of the algorithms themselves. The transformation of descriptions in the AlgoWiki encyclopedia according to this scheme was performed for all pages of the project, and it allows not only to better describe the properties of algorithm implementations, but also to integrate the AlgoWiki encyclopedia project with the Algo500 project, which implements a scalable digital platform for joint analysis of the properties of algorithms and computer architectures.

Еще

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

  • 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.
  • Воеводин В. Открытая энциклопедия свойств алгоритмов AlgoWiki: от мобильных платформ до экзафлопсных суперкомпьютерных систем // Вычислительные методы и программирование 2015. Т. 16, № 1. С. 99–111. 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 (дата обращения: 01.12.2022).
  • Wikipedia. URL: https://wikipedia.org (дата обращения: 01.12.2022).
  • Открытая энциклопедия свойств алгоритмов. URL: http://algowiki-project.org (дата обращения: 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.
  • Воеводин В., Воеводин Вл. Параллельные вычисления. Санкт-Петербург: БХВ-Петербург, 2002. 608 с.
  • 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 r`esolution num´erique des syst`emes d´equations lin´eaires // La SABIX, Bulletins d´eja publi´es, 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.
  • Воеводин В.В., Швец П.А. Метод покрытий для оценки локальности использования данных в программах // Вестник Уфимского государственного авиационного технического университета. 2014. Т. 18, № 1(62). С. 224–229.
  • 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 (дата обращения: 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 (дата обращения: 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 (дата обращения: 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.
Еще
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp