Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Formal Techniques for Development and Auto-tuning of Parallel Programs

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

The paper presents formal algebra-algorithmic models for parallel program design and auto-tuning aimed to achieve the highest degree of computation performance. Parallel programs are modeled in terms of high-level schemes represented in Glushkov’s system of algorithmic algebra and a concept of a transition system implemented in the term rewriting technique. The optimization techniques (the methods of asynchronous loop computations and choosing the optimal strategy of indexed data structures traversal) are proposed for auto-tuning. The evaluation of the performance impact of corresponding code transformations is given. The models of parallel program execution and auto-tuning are developed. As the structure and logic of tuned programs can be changed, an approach to verification of correctness of optimization transformations of parallel code performed by an auto-tuner is developed. In some partial cases, this validation can be automated and implemented by checking defined source code characteristics using rewriting rules framework, so correctness verification is reduced to checking equivalence by result property. The developed methods are demonstrated on the examples of optimization of parallel Brownian motion simulation and weather forecasting programs. The multiprocessor speedup for the Brownian motion simulation program was close to the theoretical limit, and the improvement of the overall execution time for the meteorological forecasting program exceeded 13%. The developed formal models and software methods are effective means of achieving the main goal of increasing the multiprocessor speedup of parallel programs as well as of verification of the correctness of the applied code transformations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Data availability

The data are not available.

References

  1. Naono K, Teranishi K, Cavazos J, Suda R. Software automatic tuning: from concepts to state-of-the-art results. Berlin: Springer; 2010.

    Book  Google Scholar 

  2. Durillo J, Fahringer T. From single- to multi-objective auto-tuning of programs: advantages and implications. Sci Program. 2014;22(4):285–97.

    Google Scholar 

  3. Doroshenko A, Yatsenko O. Formal and adaptive methods for automation of parallel programs construction: emerging research and opportunities. Hershey: IGI Global; 2021.

    Book  Google Scholar 

  4. Andon PI, Doroshenko AY, Zhereb KA, Yatsenko OA. Algebra-algorithmic models and methods of parallel programming. Kyiv: Akademperiodyka; 2018.

    Book  Google Scholar 

  5. Doroshenko A, Ivanenko P, Novak O, Yatsenko O. A mixed method of parallel software auto-tuning using statistical modeling and machine learning. In: Ermolayev V, Suárez-Figueroa MC, Ławrynowicz A, Palma R, Yakovyna V, Mayr HC, Nikitchenko M, Spivakovsky A, editors. ICTERI 2018. Communications in computer and information science. Cham: Springer; 2019. p. 102–23.

    Google Scholar 

  6. Ivanenko P, Doroshenko A, Zhereb K. TuningGenie: auto-tuning framework based on rewriting rules. In: Ermolayev V, Mayr H, Nikitchenko M, Spivakovsky A, Zholtkevych G, editors. ICTERI 2014. Communications in computer and information science. Cham: Springer; 2014. p. 139–58.

    Google Scholar 

  7. Doroshenko A, Zhereb K, Yatsenko O. Developing and optimizing parallel programs with algebra-algorithmic and term rewriting tools. In: Ermolayev V, Mayr HC, Nikitchenko M, Spivakovsky A, Zholtkevych G, editors. ICTERI 2013. Communications in computer and information science. Cham: Springer; 2013. p. 70–92.

    Google Scholar 

  8. Doroshenko A, Shevchenko R. A rewriting framework for rule-based programming dynamic applications. Fund Inform. 2006;72(1–3):95–108.

    MATH  Google Scholar 

  9. Keller RM. A fundamental theorem of asynchronous parallel computation. LNCS. 1975;24:102–12.

    MathSciNet  MATH  Google Scholar 

  10. Akhter S, Roberts J. Multi-core programming: Increasing performance through software multi-threading. Santa Clara: Intel Press; 2006.

    Google Scholar 

  11. Mazurkiewicz A. Introduction to trace theory. In: Diekert V, Rozenberg G, editors. The book of traces. Singapore: World Scientific; 1995. p. 3–41.

    Chapter  Google Scholar 

  12. Mamedov T, Doroshenko A. A method of autotuning .NET programs on target platforms with rewriting rules. In: 24th ITHEA International Conference on Software Engineering (SoftEngine 2019). Kyiv: National Aviation University; 2019. pp. 49–52. http://www.ithea.org/softengine/2019_SE_Proceedings.pdf. Accessed 24 Jul 2022.

  13. Petryk M, Doroshenko A, Mykhalyk D, Ivanenko P, Yatsenko O. Automated parallelization of software for identifying parameters of intraparticle diffusion and adsorption in heterogeneous nanoporous media. In: Mathematical Modeling and Simulation of Systems 2022 (MODS’2022). Chernihiv: Chernihiv Polytechnic National University; 2022. (forthcoming paper)

  14. Prusov VA, Doroshenko AY, Chernysh RI, Guk LN. Theoretical study of a numerical method to solve a diffusion-convection problem. Cybern Syst Anal. 2008;44(2):283–91.

    Article  MATH  Google Scholar 

  15. Prusov VA, Doroshenko AY, Chernysh R. A method for numerical solution of a multidimensional convection-diffusion problem. Cybern Syst Anal. 2009;45(1):89–95.

    Article  MathSciNet  MATH  Google Scholar 

  16. Wetter und Klima – Deutscher Wetterdienst. http://www.dwd.de. Accessed 24 Jul 2022.

  17. Sannella D, Tarlecki A. Foundations of algebraic specification and formal software development. Berlin: Springer; 2012.

    Book  MATH  Google Scholar 

  18. Kapitonova YV, Letichevsky AA. Algebraic programming: methods and tools. Cybern Syst Anal. 1993;29(3):307–12.

    Article  Google Scholar 

  19. Kessler C, Keller J. Models for parallel computing: review and perspectives Mitteilungen – Gesellschaft für Informatik e.V. Parallel-Algorithmen und Rechnerstrukturen. 2007;24:13–29.

    Google Scholar 

  20. Chandy KM, Misra J. Parallel program design: a foundation. New York: Addison Wesley; 1988.

    MATH  Google Scholar 

  21. Kordic V. Petri net: theory and applications. Vienna: I-Tech Education and Publishing; 2008.

    Book  Google Scholar 

  22. Whaley R, Petitet A, Dongarra JJ. Automated empirical optimizations of software and the ATLAS Project. Parallel Comput. 2001;27(1–2):3–35.

    Article  MATH  Google Scholar 

  23. Frigo M, Johnson S. FFTW: an adaptive software architecture for the FF. Acoustics Speech Signal Process. 1998;3:1381–4.

    Google Scholar 

  24. Schaefer CA, Pankratius V, Tichy WF. Atune-IL: an instrumentation language for auto-tuning parallel applications. In: Sips H, Epema D, Lin HX, editors. Euro-Par’2009. Berlin: Springer; 2009. p. 9–20.

    Google Scholar 

  25. Tapus C, Chung IH, Hollingsworth JK. Active Harmony: towards automated performance tuning. In: Giles RC, Reed DA, Kelley K, editors. 2002 ACM/IEEE conference on Supercomputing (SC’02). Los Alamitos, CA: IEEE Computer Society; 2002. p. 1–11.

  26. Yi Q, Seymour K, You H, Vuduc R, Quinla D. POET: parameterized optimizations for empirical tuning. In: Parallel and Distributed Processing Symposium 2007 (IPDPS 2007). Piscataway, NJ: IEEE Computer Society; 2007. p. 447.

  27. Katagiri T, Kise K, Honda H, Yuba T. FIBER: a generalized framework for auto-tuning software. In: Veidenbaum A, Joe K, Amano H, Aiso H, editors. International Symposium on High Performance Computing 2003 (ISHPC 2003). Berlin: Springer; 2003. p. 146–59.

  28. Fursin G, Kashnikov Y, Memon AW, Chamski Z, Temam O, Namolaru M, Yom-Tov E, Mendelson B, Zaks A, Courtois E, Bodin F, Barnard P, Ashton E, Bonilla E, Thomson J, Williams CKI, O’Boyle M. Milepost GCC: machine learning enabled self-tuning compiler. Int J Parallel Prog. 2011;39(3):296–327.

    Article  Google Scholar 

  29. Plotnikov D, Melnik D, Vardanyan M, Buchatskiy R, Zhuykov R, Lee JH. Automatic tuning of compiler optimizations and analysis of their impact. In: Alexandrov VN, Lees M, Krzhizhanovskaya VV, Dongarra JJ, Sloot PMA, editors. 8th International Workshop on Automatic Performance Tuning (iWAPT2013). Amsterdam: Elsevier; 2013. p. 1312–21.

  30. Ansel J, Kamil S, Veeramachaneni K, Ragan-Kelley J, Bosboom J, O’Reilly U-M, Amarasinghe S. OpenTuner: an extensible framework for program autotuning. In: Amaral JN, Torrellas J, editors. 23rd international conference on Parallel architectures and compilation (PACT’14). New York: ACM; 2014. p. 303–16.

  31. Rasch A, Haidl M, Gorlatch S. ATF: a generic auto-tuning framework. In: 2017 IEEE 19th International Conference on High Performance Computing and Communications. Piscataway: IEEE Computer Society; 2017. p. 64–71.

  32. Videau B, Pouget K, Genovese L, Deutsch T, Komatitsch D, Desprez F, Méhaut J-F. BOAST: a metaprogramming framework to produce portable and efficient computing kernels for HPC applications. Int J High Perform Comput Appl. 2017;32(1):28–44.

    Article  Google Scholar 

  33. Roy RB, Patel T, Gadepally V, Tiwari D. Bliss: auto-tuning complex applications using a pool of diverse lightweight learning models. In: Freund SN, Yahav E, editors. 42nd ACM SIGPLAN international conference on programming language design and implementation (PLDI 2021). New York: ACM; 2021. p. 1280–95.

  34. Oracle Developer Studio. https://www.oracle.com/application-development/technologies/developerstudio.html. Accessed 24 Jul 2022.

  35. Intel C++ and Fortran Compilers Redistributable Libraries by Version. https://www.intel.com/content/www/us/en/developer/articles/tool/compilers-redistributable-libraries-by-version.html. Accessed 24 Jul 2022.

  36. GCC, the GNU Compiler Collection. https://gcc.gnu.org. Accessed 24 Jul 2022.

Download references

Author information

Authors and Affiliations

  1. Institute of Software Systems, National Academy of Sciences of Ukraine, Glushkov Prosp. 40, Kyiv, 03187, Ukraine

    Anatoliy Doroshenko, Pavlo Ivanenko & Olena Yatsenko

Authors
  1. Anatoliy Doroshenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pavlo Ivanenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Olena Yatsenko
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Olena Yatsenko.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Models and Methods in ICT for Research and Applications” guest edited by Vadim Ermolayev, Stephen W. Liddle, Heinrich C. Mayr, Elisabeth Métais and Jolita Ralyté.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Doroshenko, A., Ivanenko, P. & Yatsenko, O. Formal Techniques for Development and Auto-tuning of Parallel Programs. SN COMPUT. SCI. 4, 162 (2023). https://doi.org/10.1007/s42979-022-01559-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-022-01559-2

Keywords

Search

Navigation