Support tools for creation and transformation of functional-dataflow parallel programs

In the article, a novel approach to the development, analysis and transformation of parallel programs is considered. A functional dataflow parallel programming language is used. It supports writing programs independently of any resource limitations. This allows to develop algorithms with maximal level of parallelism. Support tools for translation, execution, debugging, optimization and verification of functional dataflow parallel programs are developed. The translator transforms source code of a program to an intermediate representation, in which each function is defined by its dataflow graph. A dataflow graph describes data dependencies in the function and allows to construct the control graph, which defines the organization of computations by specifying the order of the operators execution. The optimization and verification of the program is carried out on their dataflow and control graphs. In order to execute a program the maximal parallelism is to be «compressed» according to particular computing systems' resource limitations. A computation process is considered as a juxtaposition of the control graph and the dataflow graph. It is possible to employ different control strategies by means of control graphs modification. The developed support tools allow to change computation control strategies adapting them to the peculiarities of a computational environment. The suggested tools provide generation of intermediate representation, which could be used as a basis for the following transformations of a program to the program for existed parallel computing systems architecture.

architecture-independent parallel programming, functional-dataflow parallel programming, transformation of programs, software development tools, dataflow graph, control graph

1. Matloff Norman. Parallel Computing for Data Science With Examples in R, C++ and CUDA. CRC Press. Taylor & Francis Group, 2016.

2. McKenney Paul E. Is Parallel Programming Hard, And, If So, What Can You Do About It? - 2014.

3. Legalov A.I. About computation control in parallel system and programming languages. Nauchiy Vestnik NGTU [Scientific Bulletin of NSTU], № 3 (18), 2004, pp. 63-72 (in Russian).

4. Karpov Y.G. Model Checking. Parallel and distributed program system verification. - SPb., BHV-Petersburg, 2010. - 560 p. (in Russian).

5. Korneev V.D. Parallel Programming in MPI. Novosibirsk, ICMMG SB RAS, 2002, 215 p. (in Russian).

6. Shameem Akhter, Jason Roberts. Multi-Core Programming. Intel Press, 2006.

7. Cheng John, Grossman Max, McKercher Ty. Professional CUDA ® C Programming. John Wiley & Sons, Inc., Indianapolis, Indiana, 2014

8. Tay Raymond. OpenCL Parallel Programming Development Cookbook. Published by Packt Publishing Ltd., 2013

9. Lastovetsky Alexey L. Parallel Computing on Heterogeneous Networks. John Willey & Sons, 2003

10. Grid Computing - Technology and Applications, Widespread Coverage and New Horizons. Edited by Soha Maad. Published by InTech Janeza Trdine 9, 51000 Rijeka, Croatia, 2012.

11. Benedict R. Gaster, Lee Howes, David R. Kaeli, Perhaad Mistry, Dana Schaa. Heterogeneous Computing with OpenCL. Advanced Micro Devices, Inc. Published by Elsevier Inc., 2013

12. Voevodin V.V., Voevodin Vl.V. Parallel computing. SPb., BHV-Petersburg, 2002, 608 p. (in Russian).

13. A.I.Legalov Functional language for architecture-independent programming] Vichislitelnye Technologii [Computing technologies], № 1 (10), 2005, pp. 71-89 (in Russian).

14. Backus J. Can programming be liberated from von Neuman style? A functional stile and its algebra of programs CACM. 1978, Vol. 21, N 8, pp. 613-641.

15. Vasilyev V.S., Ryzhenko I.N., Matkovskii I.V. Parallel list optimization for function dataflow programming language “Pifagor”. Systemy. Methody. Technologii [Systems. Methods. Technologies]. № 3 (23), 2014, pp. 102-107. (in Russian).

16. Hoare, C. A. R. An axiomatic basis for computer programming. Communications of the ACM, 1969, Vol. 10, No. 12, pp. 576-585. DOI: 10.1145/363235.363259

17. Kropacheva M., Legalov A. Formal Verification of Programs in the Pifagor Language. Parallel Computing Technologies, 12th International Confernce PACT September-October, 2013. St. Petersburg, Russia. Lecture Notes in Computer Science 7979, Springer, 2013, pp. 80-89.

18. Ushakova M.S., Legalov A.I. Automation of Formal Verification of Programs in the Pifagor Language. Modeling and Analysis of Information Systems, 2015, 22(4), pp. 578-589. DOI:10.18255/1818-1015-2015-4-578-589