Система автоматического распараллеливания линейных программ для машин с общей и распределенной памятью
Аннотация
Эффективное программирование параллельных архитектур всегда было сложной задачей и особенно усложняется при их современном разнообразии. Задача автоматического распараллеливания программного кода была сформулирована с момента появления первых параллельных отечественных вычислителей (например, ПС2000). К настоящему времени разработаны языки и технологии программирования, которые упрощают работу программиста (Т-Система, MC#, Erlang, Go, OpenCL), но не делают распараллеливание автоматическим. Сложившаяся ситуация требует разработки и развития эффективных инструментов программирования вычислительных систем. Такие инструменты должны поддерживать разработку параллельных программ для систем с общей и распределенной памятью. В работе рассматривается задача автоматического распараллеливания линейных программ для таких систем. Обсуждаются разработанные методы вычисления пространственно-временных преобразований, оптимизирующих локальность программы. Рассматривается реализация методов на языке Haskell в рамках source-to-source транслятора, осуществляющего автоматическое распараллеливание. Осуществляется сравнение быстродействия параллельных программ lu, atax, syr2k, полученных с помощью разработанной системы и современного инструмента Pluto. Эксперименты проводились на двух машинах архитектуры x86_64, объединенных сетью InfiniBand. В качестве технологий распараллеливания использовались OpenMP и MPI. Быстродействие результирующей параллельной программы свидетельствует о практической применимости разработанной системы распараллеливания линейных программ.
Об авторах
Ш. Г. Магомедов
МИРЭА - Российский технологический университет
Россия
Россия
кандидат технических наук, доцент кафедры КБ-4 «Автоматизированные системы управления» Института комплексной безопасности и специального приборостроения,
119454, Москва, пр-т Вернадского, д. 78
А. С. Лебедев
МИРЭА - Российский технологический университет
Россия
Россия
преподаватель кафедры КБ-4 «Автоматизированные системы управления» Института комплексной безопасности и специального приборостроения,
119454, Москва, пр-т Вернадского, д. 78
Список литературы
1. Griebl M., Lengauer C. On the space-time mapping of WHILE-loops. Parallel Processing Lett. 1994; 4(3):221-232. https://doi.org/10.1142/S0129626494000223
2. Griebl M., Lengauer C. The loop parallelizer LooPo – announcement. Int. Workshop on Languages and Compilers for Parallel Computing. Springer, Berlin, Heidelberg, 1996. P. 603-604. https://doi.org/10.1007/BFb0017283
3. Irigoin F., Jouvelot P., Triolet R. Semantical interprocedural parallelization: An overview of the PIPS project. Proceed. of the 5th Int. Conf. on Supercomputing, ACM, New York, ICS ’91. 1991. P. 244-251. https://doi.org/10.1145/109025.109086
4. Bondhugula U., Hartono A., Ramanujam J., Sadayappan P. A practical automatic polyhedral parallelizer and locality optimizer. ACM SIGPLAN Notices. 2008;43(6):101-113. https://doi.org/10.1145/1379022.1375595
5. Bondhugula U. Compiling affine loop nests for distributed-memory parallel architectures. SC'13: Proceed. of the Int. Conf. on High Performance Computing, Networking, Storage and Analysis. IEEE, 2013. P. 1-12. https://doi.org/10.1145/2503210.2503289
6. Bondhugula U., Bandishti V., Pananilath I. Diamond tiling: Tiling techniques to maximize parallelism for stencil computations. IEEE Trans. on Parallel and Distributed Systems. 2016;28(5):1285- 1298. https://doi.org/10.1109/TPDS.2016.2615094
7. Malas T.M., Hager G., Ltaief H., Keyes D. Multidimensional intratile parallelization for memory-starved stencil computations. ACM Trans. on Parallel Computing (TOPC). 2018;4(3):12. https://doi.org/10.1145/3155290
8. Park E., Cavazos J., Pouchet L.-N., Bastoul C., Cohen A., Sadayappan P. Predictive modeling in a polyhedral optimization space. Int. J. Parallel Program. 2013;41(5):704-750. https://doi.org/10.1007/s10766-013-0241-1
9. Baghdadi R., Beaugnon U., Cohen A., Grosser T., Kruse M., Reddy C., Verdoolaege S., Betts A., Donaldson A.F., Ketema J., Absar J., Van Haastregt S., Kravets A., Lokhmotov A., David R., Hajiyev E. Pencil: A platform-neutral compute intermediate language for accelerator programming. 2015 Int. Conf. on Parallel Architecture and Compilation (PACT). IEEE, 2015. P. 138-149. https://doi.org/10.1109/pact.2015.17
10. Lee S., Vetter J. S. OpenARC: Extensible OpenACC compiler framework for directive-based accelerator programming study. Proceed. of the First Workshop on Accelerator Programming using Directives. IEEE Press, 2014. P. 1-11. http://dx.doi.org/10.1109/WACCPD.2014.7
11. Grosser T., Zheng H., Aloor R., Simbürger A., Größlinger A., Pouchet L.-N. Polly-polyhedral optimization in LLVM. In: Alias C., Bastoul C. (eds.) Proceed. of the First Int. Workshop on Polyhedral Compilation Techniques (IMPACT). INRIA Grenoble Rhône-Alpes, 2011. P. 1.
12. Intel® C++ Compiler 19.0 Developer Guide and Reference. Submitted March 7, 2019. URL: https:// software.intel.com/en-us/cpp-compiler-developer-guide-and-reference-enabling-auto-parallelization
13. PGI 2019 Version Information and New Features. URL: https://www.pgroup.com/support/release-2019.htm
14. Bastoul C. Code generation in the polyhedral model is easier than you think. Proceed. of the 13th Int. Conf. on Parallel Architectures and Compilation Techniques. IEEE Computer Society, 2004. P. 7-16. https://doi.org/10.1109/PACT.2004.1342537
15. Лебедев А.С. Пространственно-временные преобразования при распараллеливании линейных программ. Информационные технологии и вычислительные системы. 2015;(1):19-32.
16. Лебедев А.С. Размещение данных при автоматическом распараллеливании линейных программ для систем с распределенной памятью. Вестник Рыбинского государственного авиационного технического университета имени П.А. Соловьева. 2015;(3):92-99.
17. Лебедев А.С. Организация информационного обмена между параллельными процессами при автоматическом распараллеливании линейных программ для кластерных систем с применением модели многогранников. Программные системы: теория и приложения. 2017;(4):3-20. https://doi.org/10.25209/2079-3316-2017-8-4-3-20
18. Griebl M., Feautrier P., Größlinger A. Forward communication only placements and their use for parallel program construction. Int. Workshop on Languages and Compilers for Parallel Computing. Springer, Berlin, Heidelberg, 2002. P. 16-30. https://doi.org/10.1007/11596110_2
19. Feautrier P. Toward automatic distribution. Parallel Processing Lett. 1994;4(3):233-244. https://doi.org/10.1142/S0129626494000235
20. Griebl M. Automatic parallelization of loop programs for distributed memory architectures. Univ. Passau, 2004. 207 p. URL: http://www.infosun.fim.uni-passau.de/cl/publications/docs/Gri04.pdf
21. Reddy C., Bondhugula U. Effective automatic computation placement and data allocation for parallelization of regular programs. Proceed. of the 28th ACM Int. Conf. on Supercomputing. ACM, 2014. P. 13-22. https://doi.org/10.1145/2597652.2597673
22. Bastoul C., Cohen A., Girbal S., Sharma S., Temam O. Putting polyhedral loop transformations to work. Int. Workshop on Languages and Compilers for Parallel Computing. Springer, Berlin, Heidelberg, 2003. P. 209-225. https://doi.org/10.1007/978-3-540-24644-2_14
23. Bastoul C. Openscop: A specification and a library for data exchange in polyhedral compilation tools. Tech. Rep. Paris-Sud University, France, 2011. V. 9. URL: http://icps.u-strasbg.fr/~bastoul/development/openscop/docs/openscop.pdf
24. Bastoul C., Pouchet L.N. Candl: The chunky analyzer for dependences in loops. Tech. Rep. LRI, ParisSud University, France, 2012. URL: http://icps.u-strasbg.fr/~bastoul/development/candl/#DOC
Дополнительные файлы
|
|
1. Таблица 2. Результаты распараллеливания программ | |
| Тема | ||
| Тип | Исследовательские инструменты | |
Посмотреть
(20KB)
|
Метаданные | |
Рецензия
При поддержке: Данные исследования проведены при поддержке РТУ МИРЭА в рамках инициативной научно-исследовательской работы ИЦМР-5 «Разработка автоматизированной системы управления закупками».
Для цитирования:
Магомедов Ш.Г., Лебедев А.С. Система автоматического распараллеливания линейных программ для машин с общей и распределенной памятью. Russian Technological Journal. 2019;7(5):7-19. https://doi.org/10.32362/2500-316X-2019-7-5-7-19
For citation:
Magomedov S.G., Lebedev A.S. A tool for automatic parallelization of affine programs for systems with shared and distributed memory. Russian Technological Journal. 2019;7(5):7-19. (In Russ.) https://doi.org/10.32362/2500-316X-2019-7-5-7-19
Просмотров: 584
Послать статью по эл. почте 