Восстановление многомерной формы обращений к линеаризованным массивам в системе SAPFOR

Article Sidebar

PDF
Опубликован: 28.05.2020
УДК 004.432
DOI: https://doi.org/10.26907/1562-5419-2020-23-4-770-787
Выпуск
Том 23 № 4 (2020): Тематический выпуск «Научный сервис в сети Интернет». Часть 2

Main Article Content

Никита Андреевич Катаев
Институт прикладной математики им. М.В. Келдыша РАН, г. Москва
Владислав Николаевич Василькин
Московский государственный университет им. М.В. Ломоносова, г. Москва

Аннотация

Система автоматизированного распараллеливания SAPFOR (System FOR Automated Parallelization) включает инструменты для анализа и преобразования программ, основной ее целью является снижение сложности распараллеливания программ. Система SAPFOR ориентирована на исследования многоязыковых вычислительных комплексов, разрабатываемых на языках программирования Фортран и Си. Для анализа программ в этой системе используется низкоуровневое их представление в виде LLVM IR, которое позволяет проводить различные оптимизации с целью повышения качества анализа программ. При этом оно теряет некоторые особенности программы, отражаемые ее представлением на языке высокого уровня. Одной из таких особенностей является многомерная структура используемых массивов. Анализ зависимостей по данным является одним из ключевых при исследовании возможности параллельного выполнения программ. При этом такой анализ относится к классу NP-трудных задач. Знание многомерной структуры массивов позволяет во многих случаях учесть структуру индексных выражений в обращениях к массивам и снизить сложность проводимого анализа. Кроме того, использование многомерных массивов позволяет повысить уровень параллелизма в программе за счет использования многомерных решеток процессоров и распараллеливания гнезд циклов, а не отдельных циклов в гнезде. Данная возможность естественным образом поддерживается в DVM-системе. В настоящей работе рассмотрен подход, применяемый в системе SAPFOR для восстановления формы многомерных массивов и обращений к ним по их линеаризованному представлению в LLVM IR. Предложенный подход был успешно протестирован на различных приложениях, включая тесты производительности из набора NAS Parallel Benchmarks.

Article Details

Биографии авторов

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

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

Владислав Николаевич Василькин

Студент 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.

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

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

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

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.

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.

Бахтин В.А., Жукова О.Ф., Катаев Н.А., Колганов А.С., Крюков В.А., Кузнецов М.Ю., Поддерюгина Н.В., Притула М.Н., Савицкая О.А., Смирнов А.А. Распараллеливание программных комплексов. Проблемы и перспективы // Труды XX Всероссийской научной конференции «Научный сервис в сети Интернет», Новороссийск, Россия, 17–22 сентября 2018 г. М.: ИПМ им. М.В. Келдыша, 2018. С. 63–72. doi:10.20948/abrau-2018-33

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

Катаев Н.А., Козырев В.И. Преобразование программ на высокоуровневом языке программирования на основе результатов анализа низкоуровневого представления программ в системе SAPFOR // Труды XIII международной конференции «Параллельные вычислительные технологии, ПаВТ'2019», Калининград, Россия, 2–4 апреля 2019 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2019. C. 251–262.

Dwarf 3 Standard. URL: http://eagercon.com/dwarf/dwarf3std.htm

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.

Polly – Polyhedral optimizations for LLVM. URL: https://polly.llvm.org/

Ctestgen. URL: https://github.com/VolandTymim/ctestgen

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.

PolyBench/C the Polyhedral Benchmark suite. URL: http://web.cse.ohio-state.edu/~pouchet.2/software/polybench/polybench.html

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



Представляя статьи для публикации в журнале «Электронные библиотеки», авторы автоматически дают согласие предоставить ограниченную лицензию на использование материалов Казанскому (Приволжскому) федеральному университету (КФУ) (разумеется, лишь в том случае, если статья будет принята к публикации). Это означает, что КФУ имеет право опубликовать статью в ближайшем выпуске журнала (на веб-сайте или в печатной форме), а также переиздавать эту статью на архивных компакт-дисках журнала или включить в ту или иную информационную систему или базу данных, производимую КФУ.

Все авторские материалы размещены в журнале «Электронные библиотеки» с ведома авторов. В случае, если у кого-либо из авторов есть возражения против публикации его материалов на данном сайте, материал может быть снят при условии уведомления редакции журнала в письменной форме.

Документы, изданные в журнале «Электронные библиотеки», защищены законодательством об авторских правах, и все авторские права сохраняются за авторами. Авторы самостоятельно следят за соблюдением своих прав на воспроизводство или перевод их работ, опубликованных в журнале. Если материал, опубликованный в журнале «Электронные библиотеки», с разрешения автора переиздается другим издателем или переводится на другой язык, то ссылка на оригинальную публикацию обязательна.

Передавая статьи для опубликования в журнале «Электронные библиотеки», авторы должны принимать в расчет, что публикации в интернете, с одной стороны, предоставляют уникальные возможности доступа к их материалам, но, с другой, являются новой формой обмена информацией в глобальном информационном обществе, где авторы и издатели пока не всегда обеспечены защитой от неправомочного копирования или иного использования материалов, защищенных авторским правом.

При использовании материалов из журнала обязательна ссылка на URL: http://rdl-journal.ru. Любые изменения, дополнения или редактирования авторского текста недопустимы. Копирование отдельных фрагментов статей из журнала разрешается для научных исследований, персонального использования, коммерческого использования до тех пор, пока есть ссылка на оригинальную статью.

Запросы на право переиздания или использования любых материалов, опубликованных в журнале «Электронные библиотеки», следует направлять главному редактору Елизарову А.М. по адресу: amelizarov@gmail.com

Издатели журнала «Электронные библиотеки» не несут ответственности за точки зрения, излагаемые в публикуемых авторских статьях.

Предлагаем авторам статей загрузить с этой страницы, подписать и выслать в адрес издателя журнала по электронной почте скан Авторского договора о передаче неисключительных прав на использование произведения.