Обоснование методов ускорения гнёзд циклов итерационного типа

Обложка

Цитировать

Полный текст

Аннотация

Рассматривается ускорение итерационных алгоритмов, которые встречаются при решении задач математической физики, математического моделирования, обработки изображений и других. В программной реализации таких алгоритмов лежат гнёзда циклов (участки программы, состоящие из вложенных циклов). Такие гнёзда циклов ускоряются при помощи комбинации оптимизирующих преобразований, включающих тайлинг, метод гиперплоскостей и распараллеливание на общую память. Обосновывается эквивалентность комбинации используемых преобразований программ. Предлагается и обосновывается метод изменения порядка обхода тайла. Метод даёт ускорение за счёт увеличения количества чтений данных из регистров, вместо чтений из более медленной памяти. С учётом этого метода получена формула вычисления оптимальных размеров тайлов. Представленной в статье цепочкой преобразований достигается ускорение в 1.4 раза большее, чем в известном алгоритме оптимизации, реализованном в системе PLUTO. Приводятся численные эксперименты, которые в некоторых случаях на процессоре с 8 ядрами демонстрируют ускорение относительно исходных последовательных программ более чем на порядок. Результаты статьи могут использоваться для ручной и автоматизированной оптимизации программ.

Об авторах

Елена Анатольевна Метелица

Южный Федеральный Университет

Автор, ответственный за переписку.
Email: metelica@sfedu.ru
ORCID iD: 0000-0001-6253-150X
м.н.с. Института математики механики и компьютерных наук им. Воровича, Южный федеральный университет. Научные интересы в областях компиляторных преобразований, оптимизации и распараллеливания программ

Список литературы

  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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать


Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных

 

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