Justification of methods for accelerating iterative loops nests

Cover Page

Cite item

Full Text

Abstract

The acceleration of iterative algorithms, found in solving problems of mathematical physics, mathematical modeling, and image processing, is considered. In the software implementation of these algorithms, there are nested loops (sections of the program that consist of nested loops). These loop nests can be accelerated by combination of optimizing transformations, including tiling, hyperplane method, and parallelization on shared memory. The equivalence of this combination of program transformations is substantiated. A method for changing the order of tile traversal is proposed and justified. The method provides acceleration by increasing data readings from registers instead of slower memory. Considering this method, a formula for calculating optimal tile sizes is obtained. The combination of transformations presented in this article results in an acceleration that is 1.4 times greater than the well-known optimization algorithm implemented in PLUTO. In some cases using an 8-core processor, numerical experiments show a significant increase in speed compared to the original sequential algorithms. The findings of this article can be applied to manual and automatic program optimization.

About the authors

Elena Anatol'evna Metelitsa

Southern Federal University

Author for correspondence.
Email: metelica@sfedu.ru
ORCID iD: 0000-0001-6253-150X
junior researcher Institute of Mathematics, Mechanics and Computer Sciences named after. Vorovich, Southern Federal University. Scientific interests in the areas of compiler transformations, optimization and parallelization of programs

References

  1. Wolf M. E., Lam M. S.. “A loop transformation theory and an algorithm to maximize parallelism”, IEEE Transactions on Parallel and Distributed Systems, 2:4 (1991), pp. 452–471.
  2. Wolf M., Banerjee U.. “Data dependence and its application to parallel processing”, International Journal of Parallel Programming, 16:2 (1987), pp. 137–178.
  3. Bondhugula U., Baskaran M., Krishnamoorthy S., Ramanujam J., Rountev A., Sadayappan P.. “Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model”, CC 2008: Compiler Construction, Lecture Notes in Computer Science, vol. 4959, Springer, Berlin–Heidelberg, 2008, ISBN 978-3-540-78791-4, pp. 132–146.
  4. Lamport L.. “The parallel execution of DO loops”, Commun. ACM, 17:2 (1974), pp. 83–93.
  5. Mullapudi R. T., Vasista V., Bondhugula U.. “PolyMage: automatic optimization for image processing pipelines”, ACM SIGPLAN Notices, 50:4 (2015), pp. 429—443.
  6. Maydan D. E., Hennessy J. L., Lam M. S.. “Efficient and exact data dependence analysis”, ACM SIGPLAN Notices, 26:6 (1991), pp. 1–14.
  7. Wolfe M.. “Loop skewing: the wavefront method revisited”, Int. J. Parallel. Program., 15:4 (1986), pp. 279–293.
  8. Irigoin F., Triolet R.. “Supernode partitioning”, POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (San Diego, California, USA, January 10–13, 1988), ACM, New York, 1988, ISBN 978-0-89791-252-5, pp. 319–329.
  9. Allen R., Kennedy K.. “Automatic translation of FORTRAN programs to vector form”, ACM Transactions on Programming Languages and Systems, 9:4 (1987), pp. 491–542.
  10. Vasilenko A., Veselovskiy V., Metelitsa E., Zhivykh N., Steinberg B., Steinberg O.. “Precompiler for the ACELAN-COMPOS package solvers”, PaCT 2021: Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 12942, Springer, Cham, 2021, ISBN 978-3-030-86359-3, pp. 103–116.
  11. Штейнберг Б. Я.. «О взаимосвязи между решетчатым графом программы и графом информационных связей», Известия высших учебных заведений. Северо-Кавказский регион. Серия: Естественные науки, 2011, №5(165), с. 28–30.
  12. Савельев В. А., Штейнберг Б. Я.. Распараллеливание программ, Изд-во Южного федерального университета, Ростов-на-Дону, 2008, ISBN 978-5-9275-0547-0, 192 с.
  13. Christen M., Schenk O., Burkhart H.. “PATUS: a code generation and autotuning framework for parallel iterative stencil computations on modern microarchitectures”, 2011 IEEE International Parallel & Distributed Processing Symposium (Anchorage, AK, USA, 16–20 May 2011), 2011, pp. 676–687.
  14. Bagliy A. P., Metelitsa E. A., Steinberg B. Ya.. “Automatic parallelization of iterative loops nests on distributed memory computing systems”, PaCT 2023: Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 14098, Springer, Cham, 2023, ISBN 978-3-031-41673-6, pp. 18–29.
  15. Воеводин В. В., Воеводин Вл. В.. Параллельные вычисления, БХВ-Петербург, СПб., 2002, ISBN 5-94157-160-7, 608 с.
  16. Баглий А. П., Дубров Д. В., Штейнберг Б. Я., Штейнберг Р. Б.. «43–47», Научный сервис в сети Интернет: труды XIX Всероссийской научной конференции (18–23 сентября 2017 г., г. Новороссийск), ИПМ им. М.В.Келдыша, М., 2017, ISBN 978-5-98354-037-8 URL http://keldysh.ru/abrau/2017/53.pdf.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

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

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».