Skip to main content
Top
Published in:

2020 | OriginalPaper | Chapter

Automated Design of Parallel Programs for Heterogeneous Platforms Using Algebra-Algorithmic Tools

Authors : Anatoliy Doroshenko, Oleksii Beketov, Mykola Bondarenko, Olena Yatsenko

Published in: Information and Communication Technologies in Education, Research, and Industrial Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
5.
go back to reference Andon, P.I., Doroshenko, A.Y., Zhereb, K.A., Yatsenko, O.A.: Algebra-algorithmic models and methods of parallel programming. Akademperiodyka, Kyiv (2018)CrossRef Andon, P.I., Doroshenko, A.Y., Zhereb, K.A., Yatsenko, O.A.: Algebra-algorithmic models and methods of parallel programming. Akademperiodyka, Kyiv (2018)CrossRef
6.
go back to reference 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_5CrossRef 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_​5CrossRef
7.
go back to reference Doroshenko, A., Shevchenko, R.: A rewriting framework for rule-based programming dynamic applications. Fundamenta Informaticae 72(1–3), 95–108 (2006)MATH Doroshenko, A., Shevchenko, R.: A rewriting framework for rule-based programming dynamic applications. Fundamenta Informaticae 72(1–3), 95–108 (2006)MATH
8.
go back to reference 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., 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)
9.
go back to reference 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) 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)
11.
go back to reference Wolfe, M.: More iteration space tiling. In: 1989 ACM/IEEE Conference on Supercomputing, ser. Supercomputing 1989, pp. 655–664. ACM, New York (1989) Wolfe, M.: More iteration space tiling. In: 1989 ACM/IEEE Conference on Supercomputing, ser. Supercomputing 1989, pp. 655–664. ACM, New York (1989)
12.
go back to reference Bernstein, A.J.: Analysis of programs for parallel processing. IEEE Trans. Electron. Comput. EC 15(5), 757–763 (1966)CrossRef Bernstein, A.J.: Analysis of programs for parallel processing. IEEE Trans. Electron. Comput. EC 15(5), 757–763 (1966)CrossRef
13.
go back to reference 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)CrossRef 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)CrossRef
15.
go back to reference 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) 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)
16.
go back to reference 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 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
17.
go back to reference 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)CrossRef 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)CrossRef
18.
go back to reference 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) 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)
19.
go back to reference 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) 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)
20.
go back to reference 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)CrossRef 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)CrossRef
21.
go back to reference 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)CrossRef 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)CrossRef
Metadata
Title
Automated Design of Parallel Programs for Heterogeneous Platforms Using Algebra-Algorithmic Tools
Authors
Anatoliy Doroshenko
Oleksii Beketov
Mykola Bondarenko
Olena Yatsenko
Copyright Year
2020
DOI
https://doi.org/10.1007/978-3-030-39459-2_1

Premium Partner