mireabulletinRussian Technological JournalRussian Technological Journal2782-32102500-316XRTU MIREA10.32362/2500-316X-2022-10-6-7-19mireabulletin-578Research ArticleИНФОРМАЦИОННЫЕ СИСТЕМЫ. ИНФОРМАТИКА. ПРОБЛЕМЫ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИINFORMATION SYSTEMS. COMPUTER SCIENCES. ISSUES OF INFORMATION SECURITYВычислительная сложность построения рациональных планов выполнения программ на заданном поле параллельных вычислителейComputational complexity when constructing rational plans for program execution in a given field of parallel computershttps://orcid.org/0000-0002-1650-038XБакановВ. М.BakanovV. M.

Баканов Валерий Михайлович - д.т.н.,  профессор кафедры КБ-5 «Аппаратное, программное и математическое обеспечение вычислительных систем» Института кибербезопасности и цифровых технологий

119454, Россия, Москва, пр-т Вернадского, д. 78

Scopus Author ID 6505511355, ResearcherID L-1314-2015, SPIN-код РИНЦ 8868-4594

Valery M. Bakanov - Dr. Sci. (Eng.), Professor, Department of Hardware, Software and Mathematical Support of Computing Systems, Institute of Cybersecurity and Digital Technologies

78, Vernadskogo pr., Moscow, 119454

Scopus Author ID 6505511355, ResearcherID L-1314-2015, RSCI SPIN-code 8868-4594

 

 

e881e@mail.ruМИРЭА – Российский технологический университетРоссияMIREA – Russian Technological UniversityRussian Federation202201122022106719Copyright © Баканов В.М., 20222022Баканов В.М.Bakanov V.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.rtj-mirea.ru/jour/article/view/578

Цели. Построение рациональных планов (расписаний) выполнения параллельных программ (ВПП), вследствие неоднозначности, является сложной задачей. Цель работы – создание методик разработки таких планов и специализированного программного обеспечения для реализации этих методик, полагающихся на внутренние свойства алгоритмов, в первую очередь на свойство внутреннего (скрытого) параллелизма.Методы. Основными методами при разработке планов ВПП являются построение, анализ и целенаправленное преобразование ярусно-параллельной формы (ЯПФ) информационных графов алгоритмов (ИГА). Преобразование ЯПФ осуществляется путем переноса операторов с яруса на ярус ЯПФ (именно это событие и принято за элементарный шаг при определении вычислительной сложности выполнения сценария). В качестве инструмента преобразования применен метод разработки сценариев преобразования на скриптовом языке программирования Lua. Сценарии создаются на основе эвристического подхода и используют набор API-функций (API – Application Programming Interface) разработанной программной системы, позволяющих всесторонне изучить параметры ИГА и его ЯПФ-представления для последующего построения плана ВПП на заданном поле параллельных вычислителей.Результаты. Результаты вычислительных экспериментов выявили особенности внутренних свойств алгоритмов, влияющих на эффективность преобразований ЯПФ. Получены сравнительные показатели вычислительной сложности получения планов ВПП и иных параметров (включая плотность кода и др.) при применении различных сценариев преобразования ЯПФ. Итерационный подход к улучшению эвристических методов позволит приблизиться к оптимальным схемам решения целевой задачи.Выводы. В целом разработанный программный комплекс подтвердил эффективность в исследовании параметров скрытого параллелизма в произвольных алгоритмах и рационального его использования при обработке данных. Подход применения скриптового языка для разработки эвристических методов (сценариев) целенаправленного преобразования форм ИГА показал большую гибкость и прозрачность для исследователя. Целевыми потребителями разработанных методов генерации расписаний параллельного выполнения программ в первую очередь являются разработчики трансляторов и виртуальных машин, исследователи свойств алгоритмов (в направлении нахождения и использования потенциала скрытого их параллелизма). Разработанное программное обеспечение и методики несколько лет применяются при обучении студентов в университетах России, что позволило повысить компетенции учащихся в области параллелизации обработки данных.

Objectives. The construction of rational plans (schedules) for parallel program execution (PPE) represents a challenging problem due to its ambiguity. The aim of this work is to create methods for developing such plans and specialized software for implementing these methods, which are based on the internal properties of algorithms, primarily on the property of internal (hidden) parallelism.Methods. The main method for developing PPE plans was the construction, analysis, and purposeful transformation of the stacked-parallel form (SPF) of information graphs of algorithms (IGA). The SPF was transformed by transferring operators from tier to tier of the SPF (this event was taken as an elementary step in determining the computational complexity of scenario execution). As a transformation tool, a method for developing transformation scenarios in the scripting programming language Lua was used. Scenarios were created by a heuristic approach using a set of Application Programming Interface (API) functions of the developed software system. These functions formed the basis for a comprehensive study of the parameters of the IGA and its SPF representation for the subsequent construction of a PPE plan applying to a given field of parallel computers.Results. Features of the internal properties of the algorithms that affect the efficiency of SPF transformations were identified during the course of computational experiments. Comparative indices of the computational complexity of obtaining PPE plans and other parameters (including code density, etc.) were obtained for various SPF transformation scenarios. An iterative approach to improving heuristic methods favors developing optimal schemes for solving the objective problem.Conclusions. The developed software system confirmed its efficiency for studying the parameters of hidden parallelism in arbitrary algorithms and rational use in data processing. The approach of using a scripting language to develop heuristic methods (scenarios) for the purposeful transformation of IGA forms showed great flexibility and transparency for the researcher. The target consumers of the developed methods for generating schedules for parallel execution of programs are, first of all, developers of translators and virtual machines, and researchers of the properties of algorithms (for identifying and exploiting the potential of their hidden parallelism). The developed software and methods have been successfully used for a number of years for increasing student competence in data processing parallelization at Russian universities.

граф алгоритматонкая информационная структура программыярусно-параллельная форма графарациональные параметры выполнения параллельной программыплан выполнения параллельной программыalgorithm graphfine information structure of programstacked-parallel form of graphrational execution parameters of parallel programexecution plan of parallel programReferencesВоеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург; 2004. 608 c.Voevodin V.V., Voevodin Vl.V. Parallel’nye vychisleniya (Parallel computing). St. Petersburg: BHV-Petersburg; 2004. 608 p. (in Russ.).Bakanov V. Research and selection of rational methods for obtaining framework of schedules for the parallel programs execution. In: Silhavy R., Silhavy P., Prokopova Z. (Eds.). Data Science and Intelligent Systems. CoMeSySo 2021. Lecture Notes in Networks and Systems. V. 231. Springer, Cham. https://doi.org/10.1007/978-3-030-90321-3_22Bakanov V. Research and selection of rational methods for obtaining framework of schedules for the parallel programs execution. In: Silhavy R., Silhavy P., Prokopova Z. (Eds.). Data Science and Intelligent Systems. CoMeSySo 2021. Lecture Notes in Networks and Systems. V. 231. Springer, Cham. https://doi.org/10.1007/978-3-030-90321-3_22Федотов И.Е. Параллельное программирование. Модели и приемы. М.: СОЛОН-Пресс; 2018. 390 с. ISBN 978-5-91359-222-4Fedotov I.E. Parallel’noe programmirovanie. Modeli i priemy (Parallel programming. Models and techniques). Moscow: SOLON-Press; 2018. 390 p. (in Russ.). ISBN 978-5-91359-222-4Баканов В.М. Управление динамикой вычислений в процессорах потоковой архитектуры для различ- ных типов алгоритмов. Программная инженерия. 2015;9:20–24.Bakanov V.M. Dynamics control computing in the processors data flow architecture for different types of algorithms. Programmnaya inzheneriya = Software Engineering. 2015;9:20–24 (in Russ.).Bakanov V.M. Software complex for modeling and optimization of program implementation on parallel calculation systems. Open Comput. Sci. 2018;8(1): 228–234. https://doi.org/10.1515/comp-2018-0019Bakanov V.M. Software complex for modeling and optimization of program implementation on parallel calculation systems. Open Comput. Sci. 2018;8(1): 228–234. https://doi.org/10.1515/comp-2018-0019Padua D. (Ed.). Encyclopedia of parallel computing. NY: Springer; 2012. 2195 p. https://doi.org/10.1007/978-0-387-09766-4Padua D. (Ed.). Encyclopedia of parallel computing. NY: Springer; 2012. 2195 p. https://doi.org/10.1007/978-0-387-09766-4Dennis J.B., Misunas D.P. A preliminary architecture for a basic data-flow processor. In: Proc. Second Annual Symp. Computer Architecture (ISCA ́75). 1975. P. 126–132. https://doi.org/10.1145/642089.642111Dennis J.B., Misunas D.P. A preliminary architecture for a basic data-flow processor. In: Proc. Second Annual Symp. Computer Architecture (ISCA ́75). 1975. P. 126–132. https://doi.org/10.1145/642089.642111Kukunas J. Power and performance: Software analysis and optimization. Morgan Kaufman, Elsevier Inc.; 2015. 300 p.Kukunas J. Power and performance: Software analysis and optimization. Morgan Kaufman, Elsevier Inc.; 2015. 300 p.McNairy C., Soltis D. Itanium 2 processor microarchitecture. IEEE Micro. 2003;23(2):44–55. https://doi.org/10.1109/MM.2003.1196114McNairy C., Soltis D. Itanium 2 processor microarchitecture. IEEE Micro. 2003;23(2):44–55. https://doi.org/10.1109/MM.2003.1196114Таненбаум Э., Остин Т. Архитектура компьютера: пер с англ. СПб.: Питер; 2019. 816 c. ISBN 978-5-4461- 1103-9Tanenbaum E., Ostin T. Arkhitektura komp’yutera (Computer architecture). Transl. from Eng. St. Petersburg: Piter; 2019. 816 p. (in Russ.). ISBN 978-5-4461-1103-9Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to algorithms. 3rd ed. London: MIT Press; 2009. 1292 p.Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to algorithms. 3rd ed. London: MIT Press; 2009. 1292 p.McConnell J.J. Analysis of algorithms: An active learning approach. Jones & Bartlett Publishers; 2008. 451 p.McConnell J.J. Analysis of algorithms: An active learning approach. Jones & Bartlett Publishers; 2008. 451 p.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: пер. с англ. М.: Книга по требованию; 2012. 420 с. ISBN 978-5-458-26100-5Garey M., Johnson D. Vychislitel’nye mashiny i trudnoreshaemye zadachi ( Computing machines and difficult tasks). Transl. from Eng. Moscow: Kniga po trebovaniyu; 2012. 420 р. (in Russ.). ISBN 978-5-458- 26100-5 [Garey M., Johnson D. Computers and intractability. San Francisco; 1979. 338 p.]Ierusalimschy R. Programming in Lua. 3rd ed. PUC-Rio, Brasil, Rio de Janeiro; 2013. 348 p.Ierusalimschy R. Programming in Lua. 3rd ed. PUC-Rio, Brasil, Rio de Janeiro; 2013. 348 p.Fisher J.A. Very long instruction word architectures and the ELI-512. In: Proceedings of the 10th Annual International Symposium on Computer Architecture (ISCA ’83). 1983. P. 140–150. https://doi.org/10.1145/800046.801649Fisher J.A. Very long instruction word architectures and the ELI-512. In: Proceedings of the 10th Annual International Symposium on Computer Architecture (ISCA ’83). 1983. P. 140–150. https://doi.org/10.1145/800046.801649Babb R.I. Parallel processing with large-grain data flow techniques. Computer. 1984;17(7):55–61. https://doi.org/10.1109/MC.1984.1659186Babb R.I. Parallel processing with large-grain data flow techniques. Computer. 1984;17(7):55–61. https://doi.org/10.1109/MC.1984.1659186

The authors declare that there are no conflicts of interest present.