Вычислительная сложность построения рациональных планов выполнения программ на заданном поле параллельных вычислителей

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

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург; 2004. 608 c.

2. 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_22

3. Федотов И.Е. Параллельное программирование. Модели и приемы. М.: СОЛОН-Пресс; 2018. 390 с. ISBN 978-5-91359-222-4

4. Баканов В.М. Управление динамикой вычислений в процессорах потоковой архитектуры для различ- ных типов алгоритмов. Программная инженерия. 2015;9:20–24.

5. 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-0019

6. Padua D. (Ed.). Encyclopedia of parallel computing. NY: Springer; 2012. 2195 p. https://doi.org/10.1007/978-0-387-09766-4

7. Dennis 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.642111

8. Kukunas J. Power and performance: Software analysis and optimization. Morgan Kaufman, Elsevier Inc.; 2015. 300 p.

9. McNairy C., Soltis D. Itanium 2 processor microarchitecture. IEEE Micro. 2003;23(2):44–55. https://doi.org/10.1109/MM.2003.1196114

10. Таненбаум Э., Остин Т. Архитектура компьютера: пер с англ. СПб.: Питер; 2019. 816 c. ISBN 978-5-4461- 1103-9

11. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to algorithms. 3rd ed. London: MIT Press; 2009. 1292 p.

12. McConnell J.J. Analysis of algorithms: An active learning approach. Jones & Bartlett Publishers; 2008. 451 p.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: пер. с англ. М.: Книга по требованию; 2012. 420 с. ISBN 978-5-458-26100-5

14. Ierusalimschy R. Programming in Lua. 3rd ed. PUC-Rio, Brasil, Rio de Janeiro; 2013. 348 p.

15. 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.801649

16. Babb R.I. Parallel processing with large-grain data flow techniques. Computer. 1984;17(7):55–61. https://doi.org/10.1109/MC.1984.1659186