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 information
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 simple
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
resheniya raschetoemkikh zadach [Methods of organization of parallel-pipeline computations
for solving computationally intensive tasks], Informatsionnye tekhnologii [Information Technologies],
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 [Introduction
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 realization
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 parallelization
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 reconfigurable
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 computing
systems], Desyataya Vserossiyskaya Mul'tikonferentsiya po problemam upravleniya
(MKPU-2017): Mater. 10-y Vserossiyskoy mul'tikonferentsii [The tenth all-Russian multimedia
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 technologies
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 computing].
Tomsk: Izd-vo Tom. un-ta, 2013, 223 p.
19. Frich R., Peregud E.E., Matsievskiy S.V. Izbrannye glavy teorii grafov: ucheb. posobie [Selected
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.
