Определение зависимостей по данным средствами динамического анализа системы SAPFOR

Main Article Content

Никита Андреевич Катаев
Александр Андреевич Смирнов
Андрей Дмитриевич Жуков

Аннотация

Использование указателей и косвенной адресации в программе, а также сложная структура графа потока управления являются одними из основных препятствий при выполнении статического анализа программ. Обнаруженные в результате такого анализа свойства программы слишком консервативно описывают ее поведение и часто оказываются недостаточными для принятия решений о возможности ее параллельного выполнения. Использование динамического анализа программ позволяет расширить возможности средств автоматизации распараллеливания. В системе SAPFOR (System FOR Automated Parallelization) реализован инструмент динамического анализа, опирающийся на инструментацию программ в представлении LLVM, что позволяет исследовать программы на языках C и Fortran. Чтобы снизить накладные расходы на время выполнения инструментированной программы, сохранив при этом полноту проводимого анализа, используются возможности статического анализа, реализованного в SAPFOR. В процессе динамического анализа часть обращений к памяти, информация о которых была получена в процессе статического анализа, может быть проигнорирована. Разработанный инструмент был протестирован на тестах производительности из пакета NAS Parallel Benchmarks для языков C и Fortran. В процессе динамического анализа кроме традиционных видов зависимостей (flow, anit, output) также определяются переменные, зависимость по которым может быть устранена за счет приватизации или конвейерного выполнения циклов. Совместно с возможностями DVM и OpenMP это существенно облегчает, в том числе, и ручное распараллеливание, облегчая задание соответствующих директив компилятора.

Article Details

Как цитировать
Катаев, Н. А., Смирнов, А. А., & Жуков, А. Д. (2020). Определение зависимостей по данным средствами динамического анализа системы SAPFOR. Электронные библиотеки, 23(3), 473-493. https://doi.org/10.26907/1562-5419-2020-23-3-473-493
Биографии авторов

Никита Андреевич Катаев

Научный сотрудник ИПМ им. М.В. Келдыша, специалист в области системного программирования. Сфера научных интересов – компиляторные технологии, автоматизация распараллеливания программ.

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

Научный сотрудник ИПМ им. М.В. Келдыша, специалист в области системного программирования. Сфера научных интересов – компиляторные технологии, автоматизация распараллеливания программ.

Андрей Дмитриевич Жуков

Студент 2 курса магистратуры факультета ВМиК МГУ им М.В. Ломоносова.

Библиографические ссылки

Клинов М.С., Крюков В.А. Автоматическое распараллеливание Фортран-программ. Отображение на кластер // Вестник Нижегородского университета им. Н.И. Лобачевского, 2009. № 2. С. 128–134.

Бахтин В.А., Жукова О.Ф., Катаев Н.А., Колганов А.С., Крюков В.А., Поддерюгина Н.В., Притула М.Н., Савицкая О.А., Смирнов А.А. Автоматизация распараллеливания программных комплексов // Труды XVIII Всероссийской научной конференции «Научный сервис в сети Интернет», Новороссийск, Россия, 19–24 сентября 2016 г. М.: ИПМ им. М.В. Келдыша, 2016. С. 76–85. doi:10.20948/abrau-2016-31

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.

Бахтин В.А., Клинов М.С., Крюков В.А., Поддерюгина Н.В., Притула М.Н., Сазанов Ю.Л. Расширение DVM-модели параллельного программирования для кластеров с гетерогенными узлами // Вестник Южно-Уральского государственного университета, серия «Математическое моделирование и программирование», 2012. №18 (277), выпуск 12. Челябинск: Издательский центр ЮУрГУ. C. 82–92.

Kim M., Kim H., Luk C.K. Prospector: A dynamic data-dependence profiler to help parallel programming // HotPar’10: Proceedings of the USENIX workshop on Hot Topics in parallelism, 2010.

Dorta A.J., Rodríguez C., de Sande F., Gonzalez-Escribano A. The OpenMP Source Code Repository // Parallel, Distributed, and Network-Based Processing, Euromicro Conference, 2005.

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

NAS Parallel Benchmarks. UFL: https://www.nas.nasa.gov/publications/ npb.html

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.

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). Palo Alto, California, 2004.

Intel Parallel Studio. URL: https://software.intel.com/en-us/parallel-studio-xe

Kim M., Kim H., Luk C.K. SD3: A Scalable Approach to Dynamic Data-Dependence Profiling // 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture. IEEE, 2011. doi:10.1109/MICRO.2010.49

SAPFOR. URL: https://github.com/dvm-system.