Аннотация. 

Рассматривается задача нахождения пространственных и временных отображений программ линейного класса, обеспечивающих локальность использования данных, при распараллеливании гнезд циклов для выполнения на универсальных многоядерных процессорах. Предложена архитектура транслятора текст-в-текст для выполнения распараллеливающих преобразований линейных программ с поддержкой технологии OpenMP. Приведены экспериментальные результаты исследования производительности распараллеленных программ из набора тестов polybench: lu, syr2k, gramschmidt. Произведено сравнение производительности параллельных программ, полученных применением разработанного транслятора ilpy и современного транслятора pluto 0.11.4.

Ключевые слова: 

линейная программа, модель многогранников, пространственные и временные отображения, транслятор.

Стр. 36-47.

DOI: 10.14357/20790279230405 

EDN: WNRRTT

 

 

Литература

1. Banerjee U. Loop transformations for restructuring compilers: the foundations. – Springer Science & Business Media. 2007.

2. Штейнберг Б.Я. и др. Состояние и возможности Открытой распараллеливающей системы (лето 2006 г.) // Новосибирск: Академгородок. 2006. С. 28-29.

3. Griebl M. Automatic parallelization of loop programs for distributed memory architectures. – Passau, Germany : Univ. Passau. 2004.

4. Lengauer C. Loop parallelization in the polytope model // International Conference on Concurrency Theory. – Berlin, Heidelberg : Springer Berlin Heidelberg. 1993. Р. 398-416.

5. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург. 2002. Т. 1. С. 608.

6. Лебедев А.С. Пространственно-временные преобразования при распараллеливании линейных программ //Информационные технологии и вычислительные системы. 2015. №. 1. С. 19-32.

7. Свидетельство о гос. регистрации программы для ЭВМ. Программа для построения аффинных преобразований программ линейного класса [Текст]: 2022667001 Рос. Федерация / А. С. Лебедев, С. В. И. ; Ф. государственное бюджетное учреждение науки Центр информационных технологий в проектировании Российской академии наук. № 2022666032 ; заявл. 29.08.2022 ; опубл. 13.09.2022.

8. Bastoul C. Openscop: A specification and a library for data exchange in polyhedral compilation tools //Paris-Sud University, France, Tech. Rep. 2011. Т.9. Р. 22.

9. Bastoul C. Extracting polyhedral representation from high level languages //Tech. rep. Related to the Clan tool. LRI, Paris-Sud University. 2008.

10. Bastoul C., Pouchet L.N. Candl: the chunky analyzer for dependences in loops. – tech. rep., LRI, Paris-Sud University, France. 2012. С. 2.

11. Bastoul C. Code generation in the polyhedral model is easier than you think //Proceedings. 13th International Conference on Parallel Architecture and Compilation Techniques. 2004. PACT 2004. IEEE. 2004. С. 7-16.

12. Loechner V. PolyLib: A library for manipulating parameterized polyhedra. 1999.

13. Makhorin A. GLPK (GNU linear programming kit). URL: http://www.gnu.org/s/glpk/glpk.html (доступ 18 августа 2023).

14. OpenBLAS: an optimized BLAS library. URL: https://www.openblas.net/ (доступ 18 августа 2023).

15. Yuki T, Pouchet L. PolyBench 4.2. URL: https://sourceforge.net/projects/polybench/ (доступ 18 августа 2023).

16. Лиходед Н.А. Методы распараллеливания гнезд циклов. 2008.

17. Verdoolaege S. isl: An integer set library for the polyhedral model //International Congress on Mathematical Software. – Berlin, Heidelberg : Springer Berlin Heidelberg, 2010. Р. 299-302.

18. Griebl M., Feautrier P., Größlinger A. Forward communication only placements and their use for parallel program construction //Languages and Compilers for Parallel Computing: 15th Workshop, LCPC 2002, College Park, MD, USA, July 25-27, 2002. Revised Papers 15. – Springer Berlin Heidelberg. 2005. Р. 16-30.

19. Bondhugula U., Cohen A. Handling Negative Coefficients in Automatic Transformation Schedules. 2014.

20. Bondhugula U. et al. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model // Compiler Construction: 17th International Conference, CC 2008, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29-April 6, 2008. Proceedings 17. – Springer Berlin Heidelberg. 2008. Р. 132-146.