Обоснование методов ускорения гнёзд циклов итерационного типа
Автор: Метелица Е.А.
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 1 (60) т.15, 2024 года.
Бесплатный доступ
Рассматривается ускорение итерационных алгоритмов, которые встречаются при решении задач математической физики, математического моделирования, обработки изображений и других. В программной реализации таких алгоритмов лежат гнёзда циклов (участки программы, состоящие из вложенных циклов). Такие гнёзда циклов ускоряются при помощи комбинации оптимизирующих преобразований, включающих тайлинг, метод гиперплоскостей и распараллеливание на общую память. Обосновывается эквивалентность комбинации используемых преобразований программ. Предлагается и обосновывается метод изменения порядка обхода тайла. Метод даёт ускорение за счёт увеличения количества чтений данных из регистров, вместо чтений из более медленной памяти. С учётом этого метода получена формула вычисления оптимальных размеров тайлов. Представленной в статье цепочкой преобразований достигается ускорение в 1.4 раза большее, чем в известном алгоритме оптимизации, реализованном в системе PLUTO. Приводятся численные эксперименты, которые в некоторых случаях на процессоре с 8 ядрами демонстрируют ускорение относительно исходных последовательных программ более чем на порядок. Результаты статьи могут использоваться для ручной и автоматизированной оптимизации программ.
Тайлинг, метод гиперплоскостей, распараллеливание, общая память, гнёзда циклов итерационного типа
Короткий адрес: https://sciup.org/143182404
IDR: 143182404 | DOI: 10.25209/2079-3316-2024-15-1-63-94
Список литературы Обоснование методов ускорения гнёзд циклов итерационного типа
- 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
