Трансформация функционально-потоковых параллельных программ в императивные

Функционально-потоковая парадигма параллельного программирования ориентирована на разработку параллельных переносимых программ. Исходный код функционально-потоковых программ транслируется в набор графов, отражающих информационные и управляющие зависимости. Основным способом их исполнения является интерпретация, что не позволяет эффективно выполнять вычисления на реальных параллельных вычислительных системах и ведет к низкой производительности. Для непосредственного выполнения программ на существующих вычислительных системах требуется использование специфических методов оптимизации и трансформации, учитывающих особенности как языка программирования, так и архитектуры исполнителя. В настоящее время наиболее распространенной является архитектура Фон-Неймана, параллельное программирование для которой в большинстве случаев осуществляется с использованием языков, поддерживающих императивный стиль и ориентированных на статическую систему типов. Для различных архитектур параллельных вычислительных систем существуют разнообразные подходы к написанию параллельных программ. Трансформация функционально-потоковых параллельных программ в императивные позволяет сформировать общий каркас из фрагментов императивного кода, непосредственно отображающих последовательные вычисления, который в дальнейшем может быть адаптирован к конкретной параллельной архитектуре. В работе рассматривается подход к выполнению такого типа трансформации, заключающийся в выделении фрагментов функционально-потоковых параллельных программ в качестве шаблонов, заменяемых впоследствии на эквивалентные фрагменты императивных языков. Предлагаемые методы трансформации позволяют порождать программный код, к которому в дальнейшем можно применять различные оптимизирующие преобразования, включая распараллеливание с учетом целевой архитектуры.

трансформация программ, функционально-потоковое параллельное программирование, анализ программ, типизация, промежуточные представления программ

1. K. Vivek, Parallel Computing Architectures and APIs: IoT Big Data Stream Processing. 2019.

2. I. I. Levin, A. I. Dordopulo, and V. A. Gudkov, “Programming of reconfigurable computing nodes in the COLAMO language,” Training manual. Taganrog: Publishing house of TTI SFEDU. In Russian, 2011.

3. A. I. Dordopulo and I. I. Levin, “Resource-independent programming of hybrid reconfigurable computing systems,” in Russian Supercomputing Days. In Russian, 2017, pp. 714-723.

4. V. Kasyanov, “Sisal 3.2: functional language for scientific parallel programming,” Enterprise Information Systems, vol. 7, no. 2, pp. 227-236, 2013.

5. A. I. Legalov, “Functional language for creating architecturally independent parallel programs,” Computing technologies, vol. 10, no. 1, 2005.

6. I. I. Levin, A. I. Dordopulo, I. V. Pisarenko, and A. K. Melnikov, “An approach to architecture-independent programming of computing systems based on the aspect-oriented Set@ language,” Proceedings of the Southern Federal University. Technical sciences. In Russian, vol. 197, no. 3, 2018.

7. A. I. Legalov, V. S. Vasilev, I. V. Matkovskii, and M. S. Ushakova, “A toolkit for the development of data-driven functional parallel programmes,” in International Conference on Parallel Computational Technologies, 2018, pp. 16-30.

8. V. S. Vasilev and A. I. Legalov, “Loop-invariant Optimization in the Pifagor Language,” Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 843-849, 2018.

9. U. V. Udalova, A. I. Legalov, and N. U. Sirotinina, “Methods for debugging and verifying functional-stream parallel programs,” Journal of the Siberian Federal University. Equipment and technologies, vol. 4, no. 2, 2011.

10. M. S. Ushakova and A. I. Legalov, “Verification of Programs with Mutual Recursion in Pifagor Language,” Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 850-866, 2018.

11. S. V. Zykov, Fundamentals of Modern Programming. Development of heterogeneous systems in an Internet-oriented environment. IPR Media, 2017.

12. A. I. Legalov, I. A. Legalov, and I. V. Matkovsky, “Specifics of semantics of a statically typed language of functional and dataflow parallel programming,” in Scientific Conference Scientific Service on the Internet, 2019, pp. 489-500.

13. A. I. Legalov, I. V. Matkovsky, M. S. Ushakova, and D. S. Romanova, “Dynamically Changing Parallelism with the Asynchronous Sequential Data Flows,” Modeling and analysis of information systems, vol. 27, no. 2, pp. 164-179, 2020.

14. O. V. Nepomnyashchiy, I. N. Ryzhenko, and A. I. Legalov, “Method of architecture-independent high-level synthesis of VLSI,” Proceedings of the Southern Federal University. Technical sciences, vol. 202, no. 8, 2018.

15. O. V. Nepomnyashchiy, I. N. Ryzhenko, and A. I. Legalov, “Methods, algorithms, and software tools for architecturally independent high-level synthesis of single-chip digital systems,” in Supercomputing Technologies (SCT-2018), 2018, pp. 104-109.

16. M. S. Ushakova, “Data type semantics of the dataflow parallel programming language Pifagor,” Educational resources and technologies, vol. 14, no. 2, 2016.

17. I. V. Matkovsky and A. I. Legalov, “Instrumental support for the translation and execution of functional-stream parallel programs,” Polzunovsky vestnik, no. 2, pp. 49-52, 2013.

18. J. Ferrante, K. J. Ottenstein, and J. D. Warren, “The program dependence graph and its use in optimization,” ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 9, no. 3, pp. 319-349, 1987.

19. V. M. Bakanov, “Software tools for analyzing the information structure of algorithms based on their information graphs,” in Parallel Computing Technologies (PaVT ' 2016), 2016, pp. 432-441.