ПРЕОБРАЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНОГО ИНФОРМАЦИОННОГО ГРАФА МЕТОДА ПРОГОНКИ В ПАРАЛЛЕЛЬНУЮ ФОРМУ

  • Д. В. Михайлов ООО «НИЦ СЭ и НК»
Ключевые слова: Метод прогонки, СЛАУ, последовательный информационный граф

Аннотация

Множество вычислительных задач может быть представлено в виде последова-
тельного информационного графа. В общем случае такой информационный граф не может
быть приведён к параллельному виду с целью ускорения выполнения его операций. Но в слу-
чае если вершины этого графа обладают свойствами ассоциативности, дистрибутивно-
сти и т.д., такой граф можно преобразовать в параллельно-конвейерную форму. Эти пре-
образования могут быть произведены не только над графами, содержащими элементар-
ные операции – сложение, умножение, логическое И и т.д. – но и над графами, содержа-
щими макрооперации. Одним из примеров таких графов является информационный граф
решения СЛАУ методом прогонки (методом Томаса). В статье рассмотрено решение для
трёхдиагональных СЛАУ. Информационный граф метода прогонки состоит из двух час-
тей: прямого хода, в котором выполняется переход от трёхдиагональной формы к двух-
диагональной, и обратного хода, в котором непосредственно вычисляются значения неиз-
вестных. Несмотря на то, что операции, составляющие базовую макрооперацию метода
прогонки, обладают свойством ассоциативности, простое преобразование графа к пира-
мидальному виду не даст необходимого результата. Необходимо преобразовать базовые
макрооперации особым образом и изменить то, какие данные на них поступают. После
этого возможно будет привести граф к пирамидальному виду. Для обратного хода приме-
няется аналогичное преобразование графа и составляющих его базовых подграфов. По-
скольку для того, чтобы начать вычисления в обратном ходе, нам необходимо полное за-
вершение вычислений прямого хода, следует перейти от двух специализированных типов
вычислительных блоков к одному универсальному, и построить на его основе универсаль-
ную вычислительную структуру.

Литература

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 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.
Опубликован
2022-03-02
Выпуск
Раздел
РАЗДЕЛ III. ОБРАБОТКА ИНФОРМАЦИИ В РАСПРЕДЕЛЕННЫХ, РЕКОНФИГУРИРУЕМЫХ И НЕЙРОСЕТЕ