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 algorithmic 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 rule rewriting 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, and field-programmable gate arrays).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
V. M. Glushkov, Synthesis of Digital Automata [in Russian], Fizmatgiz, Moscow (1962).
V. M. Glushkov, “Automata theory and formal microprogram transformations,” Cybern. Syst. Analysis, Vol. 1, No. 5, 1–8 (1965). https://doi.org/10.1007/BF01071417.
V. M. Glushkov, G. E. Tseitlin, and E. L. Yushchenko, Symbolic Multiprocessing Methods [in Russian], Naukova Dumka, Kyiv (1980).
V. M. Glushkov, G. E. Tseitlin, and E. L. Yushchenko, Algebra, Languages, and Programming, 3rd ed. [in Russian], Naukova Dumka, Kyiv (1989).
E. L. Yushchenko, G. E. Tseitlin, V. P. Gritsai, and T. K. Terzyan, Multilevel Structured Program Design: Theoretical Foundations and Tools [in Russian], Finansy i Statistika, Moscow (1989).
V. M. Glushkov, Yu. V. Kapitonova, and A. A. Letichevsky, Computer-Aided Design of Computers [in Russian], Naukova Dumka, Kyiv (1975).
Yu. V. Kapitonova and A. A. Letichevsky, Mathematical Theory of Computer System Design [in Russian], Nauka, Moscow (1988).
A. A. Letichevsky, J. V. Kapitonova, and S. V. Konozenko, “Computations in APS,” Theor. Computer Sci., Vol. 119, 145–171 (1993).
I. V. Sergienko, S. L. Kryvyi, and O. I. Provotar, Algebraic Aspects of Information Technologies [in Ukrainian], Naukova Dumka, Kyiv (2011).
I. V. Sergienko, Topical Directions of Informatics, In Memory of V. M. Glushkov, Springer Optimization and Its Applications, Vol. 78, Springer, New York (2014). https://doi.org/10.1007/978-1-4939-0476-1.
M. R. Petryk, O. M. Khimich, and I. V. Boyko, High-Performance Methods of Modeling and Identification of Complex Processes and Objects in Multicomponent Heterogeneous Environments [in Ukrainian], V. M. Glushkov Institute of Cybernetics, NAS of Ukraine, Kyiv (2020).
O. M. Khimich, V. 2. Mova, Î. O. Nikolaichuk, O. V. Popov, Ò. V. Chistjakova, and V. G. Tulchinsky, “Intelligent parallel computer with Intel Xeon Phi processors of new generation,” Nauka Innov., Vol. 14, No. 6, 66–79 (2018). https://doi.org/10.15407/scin14.06.066.
A. L. Golovynskyi, A. L. Malenko, I. V. Sergienko, and V. G. Tulchinsky, “Power efficient supercomputer SCIT-4,” Visn. Nac. Akad. Nauk Ukr., No. 2, 50–59 (2013).
F. I. Andon, A. E. Doroshenko, G. E. Tseitlin, and E. A. Yatsenko, Algebra-Algorithmic Models and Parallel Programming Methods [in Russian], Akademperiodyka, Kyiv (2007).
P. I. Andon, A. Yu. Doroshenko, K. A. Zhereb, and O. A. Yatsenko, Algebra-Algorithmic Models and Methods of Parallel Programming, Akademperiodyka, Kyiv (2018). https://doi.org/10.15407/akademperiodyka.367.192.
G. E. Tseitlin, Introduction to Algorithmics [in Russian], Sfera, Kyiv (1998).
L. Zakhariya, “Algebra-algorithmic approaches in the subject areas and synthesis description of software environments for them,” Bulletin of Lviv Polytechnic National University, Ser. Information Systems and Networks, Iss. 832, 376–384 (2015).
P. Naudin and C. Quitté, Algorithmique Algébrique: Avec Exercices Corrigés, Masson, Paris (1992).
K. Czarnecki and U. Eisenecker, Generative Programming: Methods, Tools, and Applications, Addison-Wesley, Boston (2000).
M. Roggenbach, A. Cerone, B.-H. Schlingloff, G. Schneider, and S. A. Shaikh, Formal Methods for Software Engineering: Languages, Methods, Application Domains (Texts in Theoretical Computer Science, An EATCS Series), Springer, Cham (2022). https://doi.org/10.1007/978-3-030-38800-3.
J. Wang and W. Tepfenhart, Formal Methods in Computer Science, Chapman and Hall/CRC, New York (2019). https://doi.org/10.1201/9780429184185.
D. Sannella and A. Tarlecki, Foundations of Algebraic Specification and Formal Software Development, Springer Berlin–Heidelberg (2012). https://doi.org/10.1007/978-3-642-17336-3.
A. Doroshenko, P. Ivanenko, O. Novak, and O. Yatsenko, “A mixed method of parallel software auto-tuning using statistical modeling and machine learning,” in: V. Ermolayev, M. Suárez-Figueroa, V. Yakovyna, H. Mayr, M. Nikitchenko, and A. Spivakovsky (eds.), Information and Communication Technologies in Education, Research, and Industrial Applications, ICTERI 2018, Communications in Computer and Information Science, Vol. 1007, Springer, Cham (2019), pp. 102–123. https://doi.org/10.1007/978-3-030-13929-2_6/.
S. Sundaramoorthy, UML Diagramming: A Case Study Approach, Auerbach Publications, Boca Raton (2022). https://doi.org/10.1201/9781003287124.
W. Boggs and M. Boggs, Mastering UML with Rational Rose, Sybex, Alameda, CA (2002).
A. Vasyluk and T. Basyuk, “ Synthesis system îf algebra algorithms formulas,” Bulletin of Lviv Polytechnic National University, Ser. Information Systems and Networks, Iss. 9, 11–22 (2021). https://doi.org/10.23939/sisn2021.09.011.
V. V. Lytvyn, I. O. Bobyk, and V. A. Vysotska, “Application of algorithmic algebra system for grammatical analysis of symbolic computation expressions of propositional logic,” Radio Electronics, Computer Science, Control, No. 4, 77–89 (2016). https://doi.org/10.15588/1607-3274-2016-4-10.
S. D. Pogorilyy and M. S. Slynko, “Research and development of Johnson’s algorithm parallel schemes in GPGPU technology,” Problems in Programming, No. 2–3, 105–112 (2016).
A. Yu. Doroshenko, O. A. Yatsenko, and O. M. Ovdii, “Ontological and algebra-algorithmic tools for automated design of parallel programs for cloud platforms,” Cybern. Syst. Analysis, Vol. 53, No. 2, 323–332 (2017). https://doi.org/10.1007/s10559-017-9932-8.
A. Yu. Doroshenko, O. A. Yatsenko, and O. G. Beketov, “Algorithm for automatic loop parallelization for graphics processing units,” Problems in Programming, No. 4, 28–36 (2017).
A. Doroshenko, V. Shymkovych, O. Yatsenko, and T. Mamedov, “Automated software design for FPGAs on an example of developing a genetic algorithm,” in: Proc. 17th Intern. Conf. “ICT in Education, Research and Industrial Applications. Integration, Harmonization and Knowledge Transfer,” ICTERI 2021 (Kherson, Ukraine, 28 Sept – 2 Oct, 2021), Vol. 1: Main Conference, PhD Symposium, Posters and Demonstrations, CEUR-WS (2021), pp. 74–85.
J. Durillo and T. Fahringer, “From single- to multi-objective auto-tuning of programs: Advantages and implications,” Sci. Program., Vol. 22, No. 4, 285–297 (2014). https://doi.org/10.3233/SPR-140394.
R. Shevchenko, “Context term calculus for rewriting systems,” Problems in Programming, No. 2–3, 21–30 (2018).
A. P. Godse and Dr. D. A. Godse, VHDL Programming: Concepts, Modeling Styles and Programming, Amazon Digital Services LLC, Seattle (2020).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetyka ta Systemnyi Analiz, No. 5, September–October, 2023, pp. 3–15.
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.
About this article
Cite this article
Andon, P.I., Doroshenko, A.Y., Ivanenko, P.A. et al. Glushkov’s Algorithmic Algebras and Automated Parallel Computing Design. Cybern Syst Anal 59, 687–697 (2023). https://doi.org/10.1007/s10559-023-00604-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-023-00604-z