Восстановление многомерной формы обращений к линеаризованным массивам в системе SAPFOR
https://doi.org/10.26907/1562-5419-2020-23-4-770-787
Аннотация
Система автоматизированного распараллеливания SAPFOR (System FOR Automated Parallelization) включает инструменты для анализа и преобразования программ, основной ее целью является снижение сложности распараллеливания программ. Система SAPFOR ориентирована на исследования многоязыковых вычислительных комплексов, разрабатываемых на языках программирования Фортран и Си. Для анализа программ в этой системе используется низкоуровневое их представление в виде LLVM IR, которое позволяет проводить различные оптимизации с целью повышения качества анализа программ. При этом оно теряет некоторые особенности программы, отражаемые ее представлением на языке высокого уровня. Одной из таких особенностей является многомерная структура используемых массивов. Анализ зависимостей по данным является одним из ключевых при исследовании возможности параллельного выполнения программ. При этом такой анализ относится к классу NP-трудных задач. Знание многомерной структуры массивов позволяет во многих случаях учесть структуру индексных выражений в обращениях к массивам и снизить сложность проводимого анализа. Кроме того, использование многомерных массивов позволяет повысить уровень параллелизма в программе за счет использования многомерных решеток процессоров и распараллеливания гнезд циклов, а не отдельных циклов в гнезде. Данная возможность естественным образом поддерживается в DVM-системе. В настоящей работе рассмотрен подход, применяемый в системе SAPFOR для восстановления формы многомерных массивов и обращений к ним по их линеаризованному представлению в LLVM IR. Предложенный подход был успешно протестирован на различных приложениях, включая тесты производительности из набора NAS Parallel Benchmarks.
Об авторах
Н. А. Катаев
Институт прикладной математики им. М.В. Келдыша РАН
Россия
Россия
В. Н. Василькин
Московский государственный университет им. М.В. Ломоносова
Россия
Россия
Список литературы
1. Konovalov N.A., Krukov V.A, Mikhajlov S.N., Pogrebtsov A.A. Fortan DVM: a Language for Portable Parallel Program Development // Programming and Computer Software, 1995. V. 21. No 1. P. 35–38.
2. Бахтин В.А., Клинов М.С., Крюков В.А., Поддерюгина Н.В., Притула М.Н., Сазанов Ю.Л. Расширение DVM-модели параллельного программирования для кластеров с гетерогенными узлами // Вестник Южно-Уральского государственного университета, серия «Математическое моделирование и программирование». 2012. №18 (277), выпуск 12. Челябинск: Издательский центр ЮУрГУ. C. 82–92.
3. Клинов М.С., Крюков В.А. Автоматическое распараллеливание Фортран-программ. Отображение на кластер // Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. № 2. С. 128–134.
4. Бахтин В.А., Жукова О.Ф., Катаев Н.А., Колганов А.С., Крюков В.А., Поддерюгина Н.В., Притула М.Н., Савицкая О.А., Смирнов А.А. Автоматизация распараллеливания программных комплексов // Труды XVIII Всероссийской научной конференции «Научный сервис в сети Интернет», Новороссийск, Россия, 19–24 сентября 2016 г. М.: ИПМ им. М.В. Келдыша, 2016. С. 76–85. doi:10.20948/ abrau-2016-31
5. Goff G., Kennedy K., Tseng C.W. Practical Dependence Testing // Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation (PLDI ’91), 1991. ACM, New York, NY, USA, 1991. P. 15–29.
6. Lattner C., Adve V. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation // Proc. of the 2004 International Symposium on Code Generation and Optimization (CGO’04), 2004. Palo Alto, California.
7. Бахтин В.А., Жукова О.Ф., Катаев Н.А., Колганов А.С., Крюков В.А., Кузнецов М.Ю., Поддерюгина Н.В., Притула М.Н., Савицкая О.А., Смирнов А.А. Распараллеливание программных комплексов. Проблемы и перспективы // Труды XX Всероссийской научной конференции «Научный сервис в сети Интернет», Новороссийск, Россия, 17–22 сентября 2018 г. М.: ИПМ им. М.В. Келдыша, 2018. С. 63–72. doi:10.20948/abrau-2018-33
8. Kataev N.A. Application of the LLVM Compiler Infrastructure to the Program Analysis in SAPFOR // Voevodin V., Sobolev S. (eds) Supercomputing. RuSCDays 2018. Communications in Computer and Information Science, 2018. Vol 965. Springer, Cham. P. 487-499. doi:10.1007/978-3-030-05807-4_41
9. Катаев Н.А., Козырев В.И. Преобразование программ на высокоуровневом языке программирования на основе результатов анализа низкоуровневого представления программ в системе SAPFOR // Труды XIII международной конференции «Параллельные вычислительные технологии, ПаВТ'2019», Калининград, Россия, 2–4 апреля 2019 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2019. C. 251–262.
10. Dwarf 3 Standard. URL: http://eagercon.com/dwarf/dwarf3std.htm
11. Grosser T., Pop S., Ramanujam J., Sadayappan P. On recovering multi-dimensional arrays in Polly // 5th International Workshop on Polyhedral Compilation Techniques, IMPACT 2015. P. 1–9.
12. Polly – Polyhedral optimizations for LLVM. URL: https://polly.llvm.org/
13. Ctestgen. URL: https://github.com/VolandTymim/ctestgen
14. Seo S., Jo G., Lee J. Performance Characterization of the NAS Parallel Benchmarks in OpenCL // 2011 IEEE International Symposium on. Workload Characterization (IISWC), 2011. P. 137–148.
15. PolyBench/C the Polyhedral Benchmark suite. URL: http://web.cse.ohio-state.edu/~pouchet.2/software/polybench/polybench.html
16. SAPFOR. URL: https://github.com/dvm-system
Рецензия
Для цитирования:
Катаев Н.А., Василькин В.Н. Восстановление многомерной формы обращений к линеаризованным массивам в системе SAPFOR. Электронные библиотеки. 2020;23(4):770-787. https://doi.org/10.26907/1562-5419-2020-23-4-770-787
For citation:
Kataev N.A., Vasilkin V.N. Reconstruction of Multi-Dimensional Form of Linearized Accesses to Arrays in SAPFOR. Russian Digital Libraries Journal. 2020;23(4):770-787. (In Russ.) https://doi.org/10.26907/1562-5419-2020-23-4-770-787
Просмотров:
16
Послать статью по эл. почте 