CONVERSION OF THE SEQUENTIAL INFORMATION GRAPH OF THE THOMAS ALGORITHM INTO A PARALLEL FORM
Abstract
Many computational tasks can be represented in the form of a sequential information graph. In the general case, such an information graph cannot be reduced to a parallel form in order to speed up the execution of its operations. But if the vertices of this graph have the properties of associativity, distributivity, etc., such a graph can be transformed into a parallel-pipeline form. These transformations can be performed not only on graphs containing elementary operations - addition, multiplication, logical AND, etc. - but also over graphs containing macro operations. One example of such graphs is the information graph for solving SLAEs by the sweep method (Thomas's method). The article considers a solution for tridiagonal linear systems. The infor-mation graph of the sweep method consists of two parts: the forward move, in which the transition from the three-diagonal form to the two-diagonal form is performed, and the reverse move, in which the values of the variables are directly calculated. Despite the fact that the operations that make up the basic macro-operation of the sweep method have the property of associativity, a sim-ple transformation of the graph to a pyramidal form will not give the desired result. It is necessary to transform the basic macro operations in a special way and change what data is received on them. After that, it will be possible to bring the graph to a pyramidal form. For the reverse move, a similar transformation of the graph and its constituent base subgraphs is applied. Since in order to start computations in the reverse run, we need to complete the computations of the forward run, we should switch from two specialized types of computational blocks to one universal one, and build a universal computational structure on its basis.
References
1. Ivanov A.I., Konoval'chik P.M. Metody organizatsii parallel'no-konveyernykh vychisleniy dlya resheniya raschetoemkikh zadach [Methods of organization of parallel-pipeline computations for solving computationally intensive tasks], Informatsionnye tekhnologii [Information Tech-nologies], 2004, No. 12, pp. 38-43.
2. Il'in V.P., Kuznetsov Yu.I. Trekhdiagonal'nye matritsy i ikh prilozheniya [Tridiagonal matrices and their applications]. Moscow: Nauka. Glavnaya redaktsiya fiziko-matematicheskoy literatury, 1985, 208 p.
3. Ortega Dzheyms. Vvedenie v parallel'nye i vektornye metody resheniya lineynykh system [Introduc-tion to parallel and vector methods for solving linear systems]. Moscow: Izd-vo Mir, 1991, 367 p.
4. Kasarkin A.V., Levin I.I. Strukturnaya realizatsiya zadachi nakhozhdeniya vsekh maksimal'nykh klik grafa na rekonfiguriruemykh vychislitel'nykh sistemakh [Structural reali-zation of the problem of finding all maximal cliques of a graph on reconfigurable computing systems], Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Bulletin of Computer and Information Technologies], 2018, No. 10 (172), pp. 3-10.
5. Levin I.I., Pelipets A.V. Metodologiya rasparallelivaniya po iteratsiyam pri reshenii zadach lineynoy algebry na rekonfiguriruemykh vychislitel'nykh sistemakh [Methodology of parallel-ization by iterations in solving linear algebra problems on reconfigurable computing systems], Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Bulletin of Computer and Information Technologies], 2016, No. 7 (145), pp. 34-40.
6. Levin I.I., Pelipets A.V., Sorokin D.A. Reshenie zadachi LU-dekompozitsii na rekonfiguriruemykh vychislitel'nykh sistemakh: otsenka i perspektivy [Solving the LU-decomposition problem on recon-figurable computing systems: assessment and prospects], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 7 (168), pp. 62-70.
7. Gulenok A.A. Optimizatsiya blokov perekommutatsii v vychislitel'nykh strukturakh parallel'nykh programm dlya rekonfiguriruemykh vychislitel'nykh sistem [Optimization of recommutation blocks in computing structures of parallel programs for reconfigurable compu-ting systems], Desyataya Vserossiyskaya Mul'tikonferentsiya po problemam upravleniya (MKPU-2017): Mater. 10-y Vserossiyskoy mul'tikonferentsii [The tenth all-Russian multime-dia conference on management (mcpu-2017): proceedings of the 10th all-Russian conference]: in 3 vol. Rostov-on-Don: Izd-vo: YuFU, 2017, pp. 130-131.
8. Kalyaev I.A., Levin I.I. Rekonfiguriruemye mul'tikonveyernye vychislitel'nye sistemy dlya resheniya potokovykh zadach [Reconfigurable multiconveyor computing systems for solving streaming tasks], Informatsionnye tekhnologii i vychislitel'nye sistemy [Information technolo-gies and computing systems], 2011, No. 2, pp. 12-22.
9. Levin I.I. Strukturno-protsedurnaya organizatsiya parallel'nykh vychisleniy [Structural and procedural organization of parallel computing], Mater. Chetvertoy Mezhdunarodnoy nauchnoy molodezhnoy shkoly "Vysokoproizvoditel'nye vychislitel'nye sistemy" [Materials of the Fourth International Scientific Youth School "High-performance computing systems"]. Taganrog: Izd-vo TTI YuFU, 2007, pp. 49-68.
10. Mikhaylov D.V. Preobrazovanie nekotorykh vidov posledovatel'nykh informatsionnykh grafov v parallel'no-konveyernuyu formu [Transformation of some types of sequential information graphs into a parallel-conveyor form], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2020, No. 7 (217), pp. 78-93.
11. Zadacha summirovaniya elementov massiva [The task of summing array elements], Laboratorii Parallel'nykh informatsionnykh tekhnologiy NIVTS MGU [Laboratories of Parallel information technologies of the NIVC MSU]. Available at: https://parallel.ru/fpga/Summ2 (accessed 25 October 2021).
12. Efimov S.S. Obzor metodov rasparallelivaniya algoritmov resheniya nekotorykh zadach vychislitel'noy diskretnoy matematiki [Review of methods for parallelizing algorithms for solving some problems of computational discrete mathematics], Matematicheskie struktury i modelirovanie [Mathematical structures and modeling], 2007, Issue 17, pp. 72-93.
13. Dasgupta S., Papadimitriu Kh., Vazirani U. Algoritmy [Algorithms]: transl. from engl., ed. by A. Shenya. Moscow: MTSNMO, 2014, 320 p.
14. Kharari F. Teoriya grafov [Graph theory]. Moscow: Mir, 1973, 300 p.
15. Kormen T.M. i dr. Chast' VI. Algoritmy dlya raboty s grafami [Part VI. Algorithms for working with graphs], Algoritmy: postroenie i analiz = Introduction to Algorithms [Algorithms: construction and analysis = Introduction to Algorithms]. 2nd ed. Moscow: Vil'yams, 2006, pp. 1296.
16. Edward A. Bender. Lists, Decisions and Graphs. With an Introduction to Probability. S. Gill Williamson, 2010, 251 p.
17. Trudeau, Richard J. Introduction to graph theory. Dover Publications, Inc. New York, 1993, 224 p.
18. Starchenko A.V., Bertsun V.N. Metody parallel'nykh vychisleniy [Methods of parallel compu-ting]. Tomsk: Izd-vo Tom. un-ta, 2013, 223 p.
19. Frich R., Peregud E.E., Matsievskiy S.V. Izbrannye glavy teorii grafov: ucheb. posobie [Se-lected chapters of graph theory: studies. manua]: transl. from german by. E.E. Pereguda, ed. by S.V. Matsievskogo. Kaliningrad: Izd-vo RGU im. I. Kanta, 2008, 204 p.
20. Tatt U. Teoriya grafov [Graph theory]: transl. from the engl. G.P. Gavrilova. Moscow: Mir, 1988, 424 p.
