<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">ellibs</journal-id><journal-title-group><journal-title xml:lang="ru">Электронные библиотеки</journal-title><trans-title-group xml:lang="en"><trans-title>Russian Digital Libraries Journal</trans-title></trans-title-group></journal-title-group><issn pub-type="epub">1562-5419</issn><publisher><publisher-name>Казанский (Приволжский) федеральный университет</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.26907/1562-5419-2020-23-4-770-787</article-id><article-id custom-type="elpub" pub-id-type="custom">ellibs-228</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Статьи</subject></subj-group></article-categories><title-group><article-title>Восстановление многомерной формы обращений к линеаризованным массивам в системе SAPFOR</article-title><trans-title-group xml:lang="en"><trans-title>Reconstruction of Multi-Dimensional Form of Linearized Accesses to Arrays in SAPFOR</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Катаев</surname><given-names>Н. А.</given-names></name><name name-style="western" xml:lang="en"><surname>Kataev</surname><given-names>N. A.</given-names></name></name-alternatives><email xlink:type="simple">kataev_nik@mail.ru</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Василькин</surname><given-names>В. Н.</given-names></name><name name-style="western" xml:lang="en"><surname>Vasilkin</surname><given-names>V. N.</given-names></name></name-alternatives><email xlink:type="simple">volandtymim@gmail.com</email><xref ref-type="aff" rid="aff-2"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Институт прикладной математики им. М.В. Келдыша РАН</institution></aff><aff xml:lang="en"><institution>Keldysh Institute of Applied Mathematic RAS</institution></aff></aff-alternatives><aff-alternatives id="aff-2"><aff xml:lang="ru"><institution>Московский государственный университет им. М.В. Ломоносова</institution></aff><aff xml:lang="en"><institution>Lomonosov Moscow State University</institution></aff></aff-alternatives><pub-date pub-type="collection"><year>2020</year></pub-date><pub-date pub-type="epub"><day>28</day><month>08</month><year>2020</year></pub-date><volume>23</volume><issue>4</issue><fpage>770</fpage><lpage>787</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Катаев Н.А., Василькин В.Н., 2020</copyright-statement><copyright-year>2020</copyright-year><copyright-holder xml:lang="ru">Катаев Н.А., Василькин В.Н.</copyright-holder><copyright-holder xml:lang="en">Kataev N.A., Vasilkin V.N.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://ellibs.elpub.ru/jour/article/view/228">https://ellibs.elpub.ru/jour/article/view/228</self-uri><abstract><p>Система автоматизированного распараллеливания SAPFOR (System FOR Automated Parallelization) включает инструменты для анализа и преобразования программ, основной ее целью является снижение сложности распараллеливания программ. Система SAPFOR ориентирована на исследования многоязыковых вычислительных комплексов, разрабатываемых на языках программирования Фортран и Си. Для анализа программ в этой системе используется низкоуровневое их представление в виде LLVM IR, которое позволяет проводить различные оптимизации с целью повышения качества анализа программ. При этом оно теряет некоторые особенности программы, отражаемые ее представлением на языке высокого уровня. Одной из таких особенностей является многомерная структура используемых массивов. Анализ зависимостей по данным является одним из ключевых при исследовании возможности параллельного выполнения программ. При этом такой анализ относится к классу NP-трудных задач. Знание многомерной структуры массивов позволяет во многих случаях учесть структуру индексных выражений в обращениях к массивам и снизить сложность проводимого анализа. Кроме того, использование многомерных массивов позволяет повысить уровень параллелизма в программе за счет использования многомерных решеток процессоров и распараллеливания гнезд циклов, а не отдельных циклов в гнезде. Данная возможность естественным образом поддерживается в DVM-системе. В настоящей работе рассмотрен подход, применяемый в системе SAPFOR для восстановления формы многомерных массивов и обращений к ним по их линеаризованному представлению в LLVM IR. Предложенный подход был успешно протестирован на различных приложениях, включая тесты производительности из набора NAS Parallel Benchmarks.</p></abstract><trans-abstract xml:lang="en"><p>The system for automated parallelization SAPFOR (System FOR Automated Parallelization) includes tools for program analysis and transformation. The main goal of the system is to reduce the complexity of program parallelization. SAPFOR system is focused on the investigation of multilingual applications in Fortran and C programming languages. The low-level LLVM IR representation is used in SAPFOR for program analysis. This representation allows us to perform various IR-level optimizations to improve the quality of program analysis. At the same time, it loses some features of the program, which are available in its higher level representation.  One of these features is the multi-dimensional structure of the arrays. Data dependence analysis is one of the main problems which should be solved to automate program parallelization. Moreover, such an analysis belongs to the class of NP-hard problems. Knowledge of the multidimensional structure of arrays allows in many cases to take into account the structure of index expressions in calls to arrays and reduce the complexity of the analysis. In addition, the use of multi-dimensional arrays allows us to use multi-dimensional processor matrix and to parallelize a whole loop nests, rather than a single loop in the nest. So, parallelism of a program is going to be increased. These opportunities are natively supported in the DVM system. This paper discusses the approach used in the SAPFOR system to recover the form of multi-dimensional arrays by their linearized representation in LLVM IR. The proposed approach has been successfully evaluated on various applications including performance tests from the NAS Parallel Benchmarks suite.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>анализ программ</kwd><kwd>автоматизация распараллеливания</kwd></kwd-group><kwd-group xml:lang="en"><kwd>SAPFOR</kwd><kwd>DVM</kwd><kwd>LLVM</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">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&amp;ndash;38.</mixed-citation><mixed-citation xml:lang="en">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&amp;ndash;38.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Бахтин В.А., Клинов М.С., Крюков В.А., Поддерюгина Н.В., Притула М.Н., Сазанов Ю.Л. Расширение DVM-модели параллельного программирования для кластеров с гетерогенными узлами // Вестник Южно-Уральского государственного университета, серия &amp;laquo;Математическое моделирование и программирование&amp;raquo;. 2012. №18 (277), выпуск 12. Челябинск: Издательский центр ЮУрГУ. C. 82&amp;ndash;92.</mixed-citation><mixed-citation xml:lang="en">Бахтин В.А., Клинов М.С., Крюков В.А., Поддерюгина Н.В., Притула М.Н., Сазанов Ю.Л. Расширение DVM-модели параллельного программирования для кластеров с гетерогенными узлами // Вестник Южно-Уральского государственного университета, серия &amp;laquo;Математическое моделирование и программирование&amp;raquo;. 2012. №18 (277), выпуск 12. Челябинск: Издательский центр ЮУрГУ. C. 82&amp;ndash;92.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Клинов М.С., Крюков В.А. Автоматическое распараллеливание Фортран-программ. Отображение на кластер // Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. № 2. С. 128&amp;ndash;134.</mixed-citation><mixed-citation xml:lang="en">Клинов М.С., Крюков В.А. Автоматическое распараллеливание Фортран-программ. Отображение на кластер // Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. № 2. С. 128&amp;ndash;134.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Бахтин В.А., Жукова О.Ф., Катаев Н.А., Колганов А.С., Крюков В.А., Поддерюгина Н.В., Притула М.Н., Савицкая О.А., Смирнов А.А. Автоматизация распараллеливания программных комплексов // Труды XVIII Всероссийской научной конференции &amp;laquo;Научный сервис в сети Интернет&amp;raquo;, Новороссийск, Россия, 19&amp;ndash;24 сентября 2016 г. М.: ИПМ им. М.В. Келдыша, 2016. С. 76&amp;ndash;85. doi:10.20948/ abrau-2016-31</mixed-citation><mixed-citation xml:lang="en">Бахтин В.А., Жукова О.Ф., Катаев Н.А., Колганов А.С., Крюков В.А., Поддерюгина Н.В., Притула М.Н., Савицкая О.А., Смирнов А.А. Автоматизация распараллеливания программных комплексов // Труды XVIII Всероссийской научной конференции &amp;laquo;Научный сервис в сети Интернет&amp;raquo;, Новороссийск, Россия, 19&amp;ndash;24 сентября 2016 г. М.: ИПМ им. М.В. Келдыша, 2016. С. 76&amp;ndash;85. doi:10.20948/ abrau-2016-31</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Goff G., Kennedy K., Tseng C.W. Practical Dependence Testing // Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation (PLDI &amp;rsquo;91), 1991. ACM, New York, NY, USA, 1991. P. 15&amp;ndash;29.</mixed-citation><mixed-citation xml:lang="en">Goff G., Kennedy K., Tseng C.W. Practical Dependence Testing // Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation (PLDI &amp;rsquo;91), 1991. ACM, New York, NY, USA, 1991. P. 15&amp;ndash;29.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Lattner C., Adve V. LLVM: A Compilation Framework for Lifelong Program Analysis &amp;amp; Transformation // Proc. of the 2004 International Symposium on Code Generation and Optimization (CGO&amp;rsquo;04), 2004. Palo Alto, California.</mixed-citation><mixed-citation xml:lang="en">Lattner C., Adve V. LLVM: A Compilation Framework for Lifelong Program Analysis &amp;amp; Transformation // Proc. of the 2004 International Symposium on Code Generation and Optimization (CGO&amp;rsquo;04), 2004. Palo Alto, California.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Бахтин В.А., Жукова О.Ф., Катаев Н.А., Колганов А.С., Крюков В.А., Кузнецов&amp;nbsp;М.Ю., Поддерюгина Н.В., Притула М.Н., Савицкая О.А., Смирнов А.А. Распараллеливание программных комплексов. Проблемы и перспективы // Труды XX Всероссийской научной конференции &amp;laquo;Научный сервис в сети Интернет&amp;raquo;, Новороссийск, Россия, 17&amp;ndash;22 сентября 2018&amp;nbsp;г. М.: ИПМ им.&amp;nbsp;М.В.&amp;nbsp;Келдыша, 2018. С.&amp;nbsp;63&amp;ndash;72. doi:10.20948/abrau-2018-33</mixed-citation><mixed-citation xml:lang="en">Бахтин В.А., Жукова О.Ф., Катаев Н.А., Колганов А.С., Крюков В.А., Кузнецов&amp;nbsp;М.Ю., Поддерюгина Н.В., Притула М.Н., Савицкая О.А., Смирнов А.А. Распараллеливание программных комплексов. Проблемы и перспективы // Труды XX Всероссийской научной конференции &amp;laquo;Научный сервис в сети Интернет&amp;raquo;, Новороссийск, Россия, 17&amp;ndash;22 сентября 2018&amp;nbsp;г. М.: ИПМ им.&amp;nbsp;М.В.&amp;nbsp;Келдыша, 2018. С.&amp;nbsp;63&amp;ndash;72. doi:10.20948/abrau-2018-33</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">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</mixed-citation><mixed-citation xml:lang="en">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</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Катаев Н.А., Козырев В.И. Преобразование программ на высокоуровневом языке программирования на основе результатов анализа низкоуровневого представления программ в системе SAPFOR // Труды XIII международной конференции &amp;laquo;Параллельные вычислительные технологии, ПаВТ'2019&amp;raquo;, Калининград, Россия, 2&amp;ndash;4 апреля 2019 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2019. C. 251&amp;ndash;262.</mixed-citation><mixed-citation xml:lang="en">Катаев Н.А., Козырев В.И. Преобразование программ на высокоуровневом языке программирования на основе результатов анализа низкоуровневого представления программ в системе SAPFOR // Труды XIII международной конференции &amp;laquo;Параллельные вычислительные технологии, ПаВТ'2019&amp;raquo;, Калининград, Россия, 2&amp;ndash;4 апреля 2019 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2019. C. 251&amp;ndash;262.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Dwarf 3 Standard. URL: http://eagercon.com/dwarf/dwarf3std.htm</mixed-citation><mixed-citation xml:lang="en">Dwarf 3 Standard. URL: http://eagercon.com/dwarf/dwarf3std.htm</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">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&amp;ndash;9.</mixed-citation><mixed-citation xml:lang="en">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&amp;ndash;9.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Polly &amp;ndash; Polyhedral optimizations for LLVM. URL: https://polly.llvm.org/</mixed-citation><mixed-citation xml:lang="en">Polly &amp;ndash; Polyhedral optimizations for LLVM. URL: https://polly.llvm.org/</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Ctestgen. URL: https://github.com/VolandTymim/ctestgen</mixed-citation><mixed-citation xml:lang="en">Ctestgen. URL: https://github.com/VolandTymim/ctestgen</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">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&amp;ndash;148.</mixed-citation><mixed-citation xml:lang="en">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&amp;ndash;148.</mixed-citation></citation-alternatives></ref><ref id="cit15"><label>15</label><citation-alternatives><mixed-citation xml:lang="ru">PolyBench/C the Polyhedral Benchmark suite. URL: http://web.cse.ohio-state.edu/~pouchet.2/software/polybench/polybench.html</mixed-citation><mixed-citation xml:lang="en">PolyBench/C the Polyhedral Benchmark suite. URL: http://web.cse.ohio-state.edu/~pouchet.2/software/polybench/polybench.html</mixed-citation></citation-alternatives></ref><ref id="cit16"><label>16</label><citation-alternatives><mixed-citation xml:lang="ru">SAPFOR. URL: https://github.com/dvm-system</mixed-citation><mixed-citation xml:lang="en">SAPFOR. URL: https://github.com/dvm-system</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
