Abstract
The further development of software tools based on algebra-algorithmic approach and term rewriting technique in the direction of automated design of programs for heterogeneous platforms using OpenCL is proposed. The method for semi-automatic parallelization of loop operators is developed. The particular feature of the approach consists in using high-level algebra-algorithmic program specifications. The tools automate design of parallel programs starting with construction of an algorithm scheme by superposition of operations of Glushkov’s system of algorithmic algebra and then synthesize corresponding source code in a target programming language on the basis of the scheme. The parallelization technique is based on loop tiling and data serialization and uses rewriting rules to transform programs. The application of the approach is illustrated by an example of developing an OpenCL interpolation program used in numerical weather forecasting. The results of the experiment consisting in executing the generated OpenCL program on a graphics processing unit are given.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
OpenCL Overview. The open standard for parallel programming of heterogeneous systems. https://www.khronos.org/opencl. Accessed 26 Sept 2019
Nvidia CUDA technology. http://www.nvidia.com/cuda. Accessed 26 Sept 2019
PIPS: Automatic Parallelizer and Code Transformation Framework. http://pips4u.org. Accessed 26 Sept 2019
PPCG: Automatic parallelizing and optimizing compiler. http://freecode.com/projects/ppcg. Accessed 26 Sept 2019
Andon, P.I., Doroshenko, A.Y., Zhereb, K.A., Yatsenko, O.A.: Algebra-algorithmic models and methods of parallel programming. Akademperiodyka, Kyiv (2018)
Doroshenko, A., Zhereb, K., Yatsenko, O.: Developing and Optimizing Parallel Programs with Algebra-Algorithmic and Term Rewriting Tools. In: Ermolayev, V., Mayr, Heinrich C., Nikitchenko, M., Spivakovsky, A., Zholtkevych, G. (eds.) ICTERI 2013. CCIS, vol. 412, pp. 70–92. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03998-5_5
Doroshenko, A., Shevchenko, R.: A rewriting framework for rule-based programming dynamic applications. Fundamenta Informaticae 72(1–3), 95–108 (2006)
Doroshenko, A., Beketov, O., Bondarenko, M., Yatsenko, O.: Automated generation of OpenCL programs based on algebra-algorithmic approach. In: Ermolayev, V., Mallet, F., Yakovyna, V., Mayr, H.C., Spivakovsky, A. (eds.) 15th International Conference “ICT in Education, Research and Industrial Applications. Integration, Harmonization and Knowledge Transfer” (ICTERI 2019), vol. 1, pp. 215–222 (2019)
Doroshenko, A., Beketov, O.: Large-scale loops parallelization for GPU accelerators. In: Ermolayev, V., Mallet, F., Yakovyna, V., Mayr, H.C., Spivakovsky, A. (eds.) 15th International Conference “ICT in Education, Research and Industrial Applications. Integration, Harmonization and Knowledge Transfer” (ICTERI 2019), vol. 1, pp. 82–89 (2019)
Prusov, V., Doroshenko, A.: Computational techniques for modeling atmospheric processes. IGI Global, Hershey (2018). https://doi.org/10.4018/978-1-5225-2636-0
Wolfe, M.: More iteration space tiling. In: 1989 ACM/IEEE Conference on Supercomputing, ser. Supercomputing 1989, pp. 655–664. ACM, New York (1989)
Bernstein, A.J.: Analysis of programs for parallel processing. IEEE Trans. Electron. Comput. EC 15(5), 757–763 (1966)
Doroshenko, AYu., Yatsenko, O.A., Beketov, O.G.: Algorithm for automatic loop parallelization for graphics processing units. Probl. Program. 4, 28–36 (2017). (in Ukrainian)
Flener, P.: Achievements and Prospects of Program Synthesis. In: Kakas, Antonis C., Sadri, F. (eds.) Computational Logic: Logic Programming and Beyond. LNCS (LNAI), vol. 2407, pp. 310–346. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45628-7_13
Gulwani, S.: Dimensions in program synthesis. In: 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming, pp. 13–24. ACM, New York (2010)
Kalms, L., Hebbeler, T., Göhringer, D.: Automatic OpenCL code generation from LLVM–IR using polyhedral optimization. In: 9th Workshop and 7th Workshop on Parallel Programming and RunTime Management Techniques for Manycore Architectures and Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA–DITAM 2018), pp. 45–50. ACM, New York (2018). https://doi.org/10.1145/3183767.3183779
Rodrigues, A., Guyomarc’h, F., Dekeyser, J.L.: An MDE approach for automatic code generation from UML/MARTE to OpenCL. Comput. Sci. Eng. 15(1), 46–55 (2012)
Li, P., Brunet, E., Trahay, F., Parrot, C., Thomas, G., Namyst, R.: Automatic OpenCL code generation for multi-device heterogeneous architectures. In: 44th International Conference on Parallel Processing (ICPP’ 2015), pp. 959–968. IEEE, Piscataway (2015)
Tillet, P., Rupp, K., Selberherr, S.: An automatic OpenCL compute kernel generator for basic linear algebra operations. In: 2012 Symposium on High Performance Computing (HPC 2012), pp. 4:1–4:2. Society for Computer Simulation International, San Diego (2012)
Steuwer, M., Fensch, C., Lindley, S., Dubach, C.: Generating performance portable code using rewrite rules: from high-level functional expressions to high-performance OpenCL code. 20th ACM SIGPLAN International Conference on Functional Programming (ICFP 2015). ACM SIGPLAN Notices, vol. 50, pp. 205–217. ACM, New York (2015)
Fabeiro, J.F., Andrade, D., Fraguela, B.B., Doallo, R.: Automatic generation of optimized OpenCL codes using OCLoptimizer. Comput. J. 58(11), 3057–3073 (2015)
Sotomayor, R., Sanchez, L.M., Garcia Blas, J., Fernandez, J., Garcia, J.D.: Automatic CPU/GPU generation of multi-versioned OpenCL kernels for C++ scientific applications. Int. J. Parallel Prog. 45(2), 262–282 (2017). https://doi.org/10.1007/s10766-016-0425-6
Supercomputer of IC. http://icybcluster.org.ua/index.php?lang_id=3&menu_id=1. Accessed 26 Sept 2019
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Doroshenko, A., Beketov, O., Bondarenko, M., Yatsenko, O. (2020). Automated Design of Parallel Programs for Heterogeneous Platforms Using Algebra-Algorithmic Tools. In: Ermolayev, V., Mallet, F., Yakovyna, V., Mayr, H., Spivakovsky, A. (eds) Information and Communication Technologies in Education, Research, and Industrial Applications. ICTERI 2019. Communications in Computer and Information Science, vol 1175. Springer, Cham. https://doi.org/10.1007/978-3-030-39459-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-39459-2_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-39458-5
Online ISBN: 978-3-030-39459-2
eBook Packages: Computer ScienceComputer Science (R0)