Methods and software tools for automated design and generation of OpenCL programs based on the algebra of algorithms are proposed. OpenCL is a framework for developing parallel software that executes across heterogeneous platforms consisting of general-purpose processors and/or hardware accelerators. The proposed approach consists in using high-level algebra-algorithmic specifications of programs represented in natural linguistic form and rewriting rules. The developed software tools provide the automated design of algorithm schemes based on a superposition of Glushkov algebra constructs that are considered as reusable components. The tools automatically generate code in a target programming language on the basis of the specifications. In most computing problems, a large part of hardware resources is utilized by computations inside loops, therefore the use of automatic parallelization of cyclic operators is most efficient for them. However, the existing automatic code parallelizing tools, such as Par4All, don’t account the limited amount of accelerator’s onboard memory space while real-life problems demand huge amounts of data to be processed. Thus, there is a need for the development of a parallelization technique embracing the cases of massive computational tasks involving big data. In the paper, a method and a software tool for semi-automatic parallelization of cyclic operators based on loop tiling and data serialization are developed. The parallelization technique uses rewriting rules system to transform programs. The framework for parallelization of loops for optimization of computations using graphics processing units allows semi-automatic parallelization of sequential programs. The approach is illustrated on an example of developing a parallel OpenCL image convolution program.

Problems in programming 2020; 2-3: 103-114

OpenCL overview. The open standard for parallel programming of heterogeneous systems. [Online] Available from: https://www.khronos.org/opencl [Accessed: 21 February 2020]

Nvidia CUDA technology. [Online] Available from: http://www.nvidia.com/cuda [Accessed: 21 February 2020]

PIPS: Automatic Parallelizer and Code Transformation Framework. [Online] Available from: http://pips4u.org [Accessed: 21 February 2020]

PPCG: Automatic parallelizing and optimizing compiler. [Online] Available from: http://freecode.com/projects/ppcg [Accessed: 21 February 2020]

Doroshenko, А.Yu., Bondarenko, M.M. & Yatsenko, O.A. (2019) Automated design of OpenCL programs based on algebra-algorithmic approach. Problems in programming. (1). P. 27-36. CrossRef

Andon, P.I., Doroshenko, A.Yu., Zhereb, K.A. & Yatsenko, O.A. (2018) Algebra-algorithmic models and methods of parallel programming. Kyiv: Akademperiodyka. CrossRef

Doroshenko, A., Zhereb, K. & Yatsenko, O. (2013) Developing and optimizing parallel programs with algebra-algorithmic and term rewriting tools. Communications in computer and information science. Information and communication technologies in education, research, and industrial applications. 412. P. 70-92. CrossRef

Doroshenko, A. & Shevchenko, R. (2006) A rewriting framework for rule-based programming dynamic applications. Fundamenta informaticae. 72 (1-3). P. 95-108.

Flener, P. (2002) Achievements and prospects of program synthesis. Computational logic: logic programming and beyond. Essays in honour of Robert A. Kowalski. Part I. London. P. 310-346. CrossRef

Gulwani, S. (2010) Dimensions in program synthesis. Proc. 12th Int. ACM SIGPLAN symposium on principles and practice of declarative programming. Hagenberg, Austria, 26-28 July 2010. New York: ACM. P. 13-24. CrossRef

Fabeiro, J.F., Andrade, D., Fraguela, B.B. & Doallo R. (2015) Automatic generation of optimized OpenCL codes using OCLoptimizer. The computer journal. 58 (11). P. 3057-3073. CrossRef

Sotomayor, R. et al. (2017) Automatic CPU/GPU generation of multi-versioned OpenCL kernels for C++ scientific applications. International journal of parallel programming. 45 (2). P. 262-282. CrossRef

Rodrigues, A., Guyomarc'h, F. & Dekeyser, J.L. (2012) An MDE approach for automatic code generation from UML/MARTE to OpenCL. Computing in science and engineering. 15 (1). P. 46-55. CrossRef

Bernstein, A.J. (1966) Analysis of programs for parallel processing. IEEE transactions on electronic computers. EC-15 (5). P. 757-763. CrossRef

Novak, J., Liktor, G. & Dachsbacher, C. GPU computing: image convolution. [Online] Available from: https://cg.ivd.kit.edu/downloads/ GPUComputing_assignment_3.pdf [Accessed: 21 February 2020]