Обоснование методов ускорения гнёзд циклов итерационного типа
Автор: Метелица Е.А.
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 1 (60) т.15, 2024 года.
Бесплатный доступ
Рассматривается ускорение итерационных алгоритмов, которые встречаются при решении задач математической физики, математического моделирования, обработки изображений и других. В программной реализации таких алгоритмов лежат гнёзда циклов (участки программы, состоящие из вложенных циклов). Такие гнёзда циклов ускоряются при помощи комбинации оптимизирующих преобразований, включающих тайлинг, метод гиперплоскостей и распараллеливание на общую память. Обосновывается эквивалентность комбинации используемых преобразований программ. Предлагается и обосновывается метод изменения порядка обхода тайла. Метод даёт ускорение за счёт увеличения количества чтений данных из регистров, вместо чтений из более медленной памяти. С учётом этого метода получена формула вычисления оптимальных размеров тайлов. Представленной в статье цепочкой преобразований достигается ускорение в 1.4 раза большее, чем в известном алгоритме оптимизации, реализованном в системе PLUTO. Приводятся численные эксперименты, которые в некоторых случаях на процессоре с 8 ядрами демонстрируют ускорение относительно исходных последовательных программ более чем на порядок. Результаты статьи могут использоваться для ручной и автоматизированной оптимизации программ.
Тайлинг, метод гиперплоскостей, распараллеливание, общая память, гнёзда циклов итерационного типа
Короткий адрес: https://sciup.org/143182404
IDR: 143182404 | УДК: 004.424.22, | DOI: 10.25209/2079-3316-2024-15-1-63-94
Justification of methods for accelerating iterative loops nests
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.
Список литературы Обоснование методов ускорения гнёзд циклов итерационного типа
- Wolf M. E., Lam M. S. A loop transformation theory and an algorithm to maximize parallelism // IEEE Transactions on Parallel and Distributed Systems.– 1991.– Vol. 2.– No. 4.– Pp. 452–471. https://doi.org/10.1109/71.97902 ↑64, 71, 72, 73
- Wolf M., Banerjee U. Data dependence and its application to parallel processing // International Journal of Parallel Programming.– 1987.– Vol. 16.– No. 2.– Pp. 137–178. https://doi.org/10.1007/BF01379099 ↑64, 72, 77, 82
- 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, Berlin–Heidelberg: Springer.– 2008.– ISBN 978-3-540-78791-4.– Pp. 132–146. https://doi.org/10.1007/978-3-540-78791-4_9 ↑64
- Lamport L. The parallel execution of DO loops // Commun. ACM.– 1974.– Vol. 17.– No. 2.– Pp. 83–93. https://doi.org/10.1145/360827.360844 ↑64, 71
- Mullapudi R. T., Vasista V., Bondhugula U. PolyMage: automatic optimization for image processing pipelines // ACM SIGPLAN Notices.– 2015.– Vol. 50.– No. 4.– Pp. 429—443. https://doi.org/10.1145/2775054.2694364 ↑64
- Maydan D. E., Hennessy J. L., Lam M. S. Efficient and exact data dependence analysis // ACM SIGPLAN Notices.– 1991.– Vol. 26.– No. 6.– Pp. 1–14. https://doi.org/10.1145/113446.113447 ↑69
- Wolfe M. Loop skewing: the wavefront method revisited // Int. J. Parallel. Program..– 1986.– Vol. 15.– No. 4.– Pp. 279–293. https://doi.org/10.1007/BF01407876 ↑69
- 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), New York: ACM.– 1988.– ISBN 978-0-89791-252-5.– Pp. 319–329. https://doi.org/10.1145/73560.73588 ↑72
- Allen R., Kennedy K. Automatic translation of FORTRAN programs to vector form // ACM Transactions on Programming Languages and Systems.– 1987.– Vol. 9.– No. 4.– Pp. 491–542. https://doi.org/10.1145/29873.29875 ↑82
- 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, Cham: Springer.– 2021.– ISBN 978-3-030-86359-3.– Pp. 103–116. https://doi.org/10.1007/978-3-030-86359-3_8 ↑64, 88
- Штейнберг Б. Я. О взаимосвязи между решетчатым графом программы и графом информационных связей // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Естественные науки.– 2011.– №5(165).– С. 28–30. [РИНЦ] ↑66, 67
- Савельев В. А., Штейнберг Б. Я. Распараллеливание программ, учебник.– Ростов-на-Дону: Изд-во Южного федерального университета.– 2008.– ISBN 978-5-9275-0547-0.– 192 с. ↑65, 74
- 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. https://doi.org/10.1109/IPDPS.2011.70 ↑70
- 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, Cham: Springer.– 2023.– ISBN 978-3-031-41673-6.– Pp. 18–29. https://doi.org/10.1007/978-3-031-41673-6_2 ↑64
- Воеводин В.В., Воеводин Вл. В. Параллельные вычисления.– СПб.: БХВ-Петербург.– 2002.– ISBN 5-94157-160-7.– 608 с. ↑66
- Баглий А. П., Дубров Д. В., Штейнберг Б. Я., Штейнберг Р. Б. 43–47 //
- Научный сервис в сети Интернет: труды XIX Всероссийской научной конференции (18–23 сентября 2017 г., г. Новороссийск), М.: ИПМ им. М.В.Келдыша.– 2017.– ISBN 978-5-98354-037-8. hUtRtpL://keldysh.ru/abrauh/t2tp0s1:7///5d3o.ip.odrfg/10.20948/abrau-2017-53 ↑64, 88
