А.С. Лебедев1

1 Центр информационных технологий в проектировании РАН (г. Одинцово, Россия)
1 tementy@gmail.com

Постановка проблемы. Значительная часть времени выполнения программ для научных и инженерных расчетов затрачивается на исполнение циклических конструкций, которые удовлетворяют критериям линейности программ и могут быть проанализированы и оптимизированы с применением модели многогранников. Рассматривается задача нахождения пространственных отображений программ линейного класса, обеспечивающих локальность использования данных, при распараллеливании гнезд циклов для выполнения на системах с распределенной памятью. Применяется метод, сокращающий расстояние использования данных для доступов к массивам, не требующий дублирования данных во всех вычислительных процессах.

Цель. Повышение быстродействия программ линейного класса при выполнении на системах с распределенной памятью.

Результаты. Предложена архитектура транслятора текст-в-текст для выполнения распараллеливающих преобразований линейных программ с поддержкой технологии MPI. Разработаны макросы для работы с информационными пакетами, оборачивающими строки матриц, линеаризованных по строкам и распределенных в вычислительных процессах согласно блочной схеме распределения. Произведено сравнение производительности параллельных программ, полученных применением разработанного транслятора ilpy и современного транслятора pluto 0.11.4 к последовательному варианту LU-разложения квадратной матрицы. Все параллельные решения позволили получить ускорение вычислений. Параллельный вариант ilpy показывает лучшую производительность в запусках на 1, 4, 6, 8 машинах. Проигрыш в производительности при запуске на двух машинах составил от 2 до 8% в зависимости от количества процессов. Наибольшее преимущество перед pluto достигается при запуске в восьми процессах и составляет 27% для запуска на одной машине и 18% для запуска на восьми машинах. Решения pluto во всех параллельных запусках демонстрируют лучшую загруженность процессоров, однако преимущество перед ilpy достигается только при запуске на двух машинах.

Практическая значимость. Разработанное программное обеспечение (транслятор) может быть использовано для анализа потока данных в программах линейного класса, улучшения локальности использования данных при вычислениях, а также распараллеливания таких программ для кластерных систем благодаря поддержке MPI в качестве технологии распараллеливания. Разработанные макросы информационного обмена могут быть включены в параллельную программу с синхронным параллелизмом для реализации операций удаленного чтения.

Лебедев А.С. Трансляция программ линейного класса для параллельного выполнения на системах с распределенной памятью // Системы высокой доступности. 2023. Т. 19. № 3. С. 35−47. DOI: https:// doi.org/10.18127/j20729472-202303-03

1. Lim A. W., Cheong G. I., Lam M. S. An affine partitioning algorithm to maximize parallelism and minimize communication. Proceedings of the 13th international conference on Supercomputing. 1999. P. 228–237.
2. Feautrier P. Automatic distribution of data and computations. TSI-Technique et Science Informatiques-RAIRO. 1996. V. 15. № 5. P. 529–558.
3. Griebl M. Automatic parallelization of loop programs for distributed memory architectures. Passau, Germany: Univ. Passau, 2004.
4. Лебедев А.С. Размещение данных при автоматическом распараллеливании линейных программ для систем с распределенной памятью // Вестник Рыбинской государственной авиационной технологической академии им. П.А. Соловьева. 2015. № 3. С. 92–99.
5. Dathathri R. et al. Generating efficient data movement code for heterogeneous architectures with distributed-memory. Proceedings of the 22nd international conference on Parallel architectures and compilation techniques. IEEE. 2013. P. 375–386.
6. Лебедев А.С. Организация информационного обмена между параллельными процессами при автоматическом распараллеливании линейных программ для кластерных систем с применением модели многогранников // Программные системы: теория и приложения. 2017. Т. 8. № 4 (35). С. 3–20.
7. Saà-Garriga A., Castells-Rufas D., Carrabina J. OMP2MPI: Automatic MPI code generation from OpenMP programs. arXiv preprint arXiv:1502.02921. 2015.
8. Millot D. et al. From OpenMP to MPI: first experiments of the STEP source-to-source transformation tool. ParCO 2009: International Conference on Parallel Computing: Mini-Symposium" Parallel Programming Tools for Multi-core Architectures". IOS Press, 2009. P. 669–676.
9. Loechner V. PolyLib: A library for manipulating parameterized polyhedra. 1999.
10. Bastoul C. Openscop: A specification and a library for data exchange in polyhedral compilation tools. Paris-Sud University, France, Tech. Rep. 2011. V. 9. P. 22.
11. Makhorin A. GLPK (GNU linear programming kit). URL: http://www.gnu.org/s/glpk/glpk.html. 2008 (дата обращения 18 августа 2023).
12. 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. P. 7–16.