UDC 519.712, 004.4'24
1 Institute of Software Systems, National Academy of Sciences of Ukraine, Kyiv, Ukraine
andon@isofts.kiev.ua
|
2 Institute of Software Systems, National Academy of Sciences of Ukraine, Kyiv, Ukraine; National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine
anatoliy.doroshenko@gmail.com
|
3 Institute of Software Systems, National Academy of Sciences of Ukraine, Kyiv, Ukraine
paiv@ukr.net
|
4 Institute of Software Systems, National Academy of Sciences of Ukraine, Kyiv, Ukraine
oayat@ukr.net
|
GLUSHKOV’S ALGORITHMIC ALGEBRAS AND AUTOMATED
PARALLEL COMPUTING DESIGN
Abstract. An overview of the results obtained within the algebra of algorithms and tools for the automated development of programs for multiprocessor platforms is presented. Algorithmics is based on the theory of algorithm algebras and is focused on solving a wide range of applied problems and developing software tools for automated design and synthesis of classes of algorithms and programs. The generality of algorithms is based on the variety of interpretations of algorithm schemes and provides the possibility of applying algorithms and their tools for solving problems related to various subject domains. The combination of algorithmics and rewriting rules technique made it possible to develop methods and tools aimed at automated design, transformation, synthesis, and tuning of programs for various platforms (multicore processors, graphics processing units, field-programmable gate arrays).
Keywords: algebra of algorithms, parallel computation, program design and synthesis, software auto-tuning.
full text
REFERENCES
- Glushkov V.M. Synthesis of digital automata [in Russian]. Moscow: Fizmatgiz, 1962. 476 p.
- Glushkov V.M. Automata theory and formal transformations of microprograms. Kibernetika. 1965. N 5. P. 1–9.
- Glushkov V.M., Zeitlin G.E., Yushchenko E.L. Symbolic multiprocessing methods [in Russian]. Kyiv: Nauk. Dumka, 1980. 252 p.
- Glushkov V.M., Zeitlin G.E., Yushchenko E.L. Algebra. Languages. Programming [in Russian]. 3rd ed. Kyiv: Nauk. Dumka, 1989. 376 p.
- Yushchenko E.L., Zeitlin G.E., Gritsai V.P., Terzyan T.K. Multilevel structural design of programs: theoretical foundations, tools [in Russian]. Moscow: Finance and Statistics, 1989. 208 p.
- Glushkov V.M., Kapitonova Yu.V., Letichevsky A.A. Computer design automation [in Russian]. Kyiv: Nauk. Dumka, 1975. 228 p.
- Kapitonova Yu.V., Letichevsky A.A. Mathematical theory of computer systems design [in Russian]. Moscow: Nauka, 1988. 296 p.
- Letichevsky A.A., Kapitonova Yu.V., Konozenko S.V. Computations in APS. Theoretical Computer Science. 1993. Vol. 119. P. 145–171.
- I.V. Sergienko, S.L. Kryviy, O.I. Provotar. Algebraic aspects of information technologies [in Ukrainian]. Kyiv: Nauk. Dumka. 2011. 400 p.
- Sergienko I.V. Scientific ideas of V.M. Hlushkova and the development of current trends in informatics .[in Ukrainian] Kyiv: Nauk. Dumka, 2013. 287 p.
- Petryk M.R., Khimich O.M., Boyko I.V. High-performance methods of modeling and identification of complex processes and objects in multicomponent heterogeneous environments . Kyiv: V.M. Glushkov Cybernetics Institute of the National Academy of Sciences of Ukraine, 2020. [in Ukrainian] 204 p.
- Khimich O.M., Mova V.I., Nikolaychuk O.O., Popov O.V., Chistyakova T.V., Tulchynskyi V.G. Intelligent parallel computer on Intel Xeon Phi processors of the new generation. Science and innovation. 2018. Vol. 14, N 6. P. 66–79.
- Golovynskyi A.L., Malenko A.L., Sergienko I.V., Tulchynskyi V.G. Energy-efficient supercomputer SKIT-4. Bulletin of the National Academy of Sciences of Ukraine. 2013. N 2. P. 50–59.
- Andon F.I., Doroshenko A.E., Zeitlin G.E., Yatsenko E.A. Algebroalgorithmic models and methods of parallel programming [in Russian]. Kiev: Akademperiodika, 2007. 634 p.
- Andon P.I., Doroshenko A.Yu., Zhereb K.A., Yatsenko O.A. Algebra-algorithmic models and methods of parallel programming. Kyiv: Akademperiodyka, 2018. 192 p.
- Zeitlin G.E. Introduction to algorithms [in Russian]. Kyiv: Sphere, 1998. 310 p.
- Zakharia L.M. Algebra-algorithmic approaches to the description of subject areas and the synthesis of software environments for them. Bulletin of the Lviv Polytechnic National University. Ser. Information systems and networks. 2015. N 832. P. 376–384.
- Naudin P., QuittБ C. Algorithmique algБbrique avec exercices corrigБs. Paris: Masson, 1992. 469 p.
- Czarnecki K., Eisenecker U. Generative programming: Methods, tools, and applications. Boston: Addison-Wesley, 2000. 864 p.
- Roggenbach M., Cerone A., Schlingloff B.-H., Schneider G., Shaikh S.A. Formal methods for software engineering: Languages, methods, application domains. Cham: Springer, 2022. 524 p.
- Wang J. Formal methods in computer science. New York: Chapman and Hall/CRC, 2019. 350 p.
- Sannella D., Tarlecki A. Foundations of algebraic specification and formal software development. Berlin: Springer, 2012. 584 p.
- Doroshenko A., Ivanenko P., Novak O., Yatsenko O. A mixed method of parallel software auto-tuning using statistical modeling and machine learning. Information and Communication Technologies in Education, Research, and Industrial Applications. ICTERI 2018. Communications in Computer and Information Science. 2019. Vol. 1007. P. 102–123. https://doi.org/10.1007/978-3-030-13929-2_6.
- Sundaramoorthy S. UML diagramming: A case study approach. Boca Raton: Auerbach Publications, 2022. 430 p.
- Boggs W., Boggs M. Mastering UML with Rational Rose. Alameda: Sybex, 2002. 848 p.
- Vasylyuk A., Basyuk T. System of synthesis of formulas of the algebra of algorithms. Information systems and networks. 2021. N 9. P. 11–22. https://doi.org/10.23939/sisn2021.09.011 .
- Lytvyn V.V., Bobyk I.O., Vysotska V.A. Application of the system of algorithmic algebras for the grammatical analysis of symbolic calculations of expressions of the logic of statements. Radio electronics, informatics, control. 2016. N 4. P. 77–89.
- Pohoriliy S.D., Slynko M.S. Creation and research of parallel circuits of the Johnson algorithm in GPGPU technology. Problemy prohramuvannya. 2016. № 2–3. P. 105–112.
- Doroshenko A.Yu., Yatsenko O.A., Ovdii O.M. Ontological and algebra-algorithmic tools for automated design of parallel programs for cloud platforms. Cybernetics and Systems Analysis. 2017. Vol. 53, N 2. P. 323–332. https://doi.org/10.1007/s10559-017-9932-8.
- Doroshenko A.Yu., Yatsenko O.A., Beketov O.G. Algorithm for automated parallelization of cyclic operators for graphics accelerators. Problemy prohramuvannya. 2017. N 4. P. 28–36.
- Doroshenko A., Shymkovych V., Yatsenko O., Mamedov T. Automated software design for FPGAs on an example of developing a genetic algorithm. Proc. 17th Int. Conf. “ICT in Education, Research and Industrial Applications. Integration, Harmonization and Knowledge Transfer”, ICTERI 2021 (28 Sept. – 2 Oct., 2021). CEUR-WS, 2021. P. 74–85.
- Durillo J., Fahringer T. From single- to multi-objective auto-tuning of programs: Advantages and implications. Scientific Programming. 2014. Vol. 22, N 4. P. 285–297. https://doi.org/ 10.3233/SPR-140394 .
- Shevchenko P.C. Counting context terms for rewriting systems. Problemy prohramuvannya. 2018. N 2–3. P. 21–30.
- Godse A.P., Godse D.A. VHDL programming: Concepts, modeling styles and programming. Seattle: Amazon Digital Services LLC, 2020. 206 p.