Article

Article title MULTIGRID METHOD TO SOLVE SPARSE LARGE AND EXTRA-LARGE SLAE BY RECONFIGURABLE COMPUTING SYSTEM
Authors A. V. Podoprigora, M. D. Chekina
Section SECTION IV. RECONFIGURABLE AND NEURAL NETWORK COMPUTING SYSTEMS
Month, Year 08, 2018 @en
Index UDC 004.273
DOI 10.23683/2311-3103-2018-8-212-221
Abstract This paper presents the possibility of solving large and extra-large sparse systems of linear algebraic equations having used multigrid method by reconfigurable computing systems (RCS). At the present moment, computer modeling is becoming topical. Replacing prototype models, it is being used in many areas of science of technology, and makes it possible to predict natural process and phenomena, as well as enable us to predict natural processes and phenomena. This mode of modeling is based on Physics and Mathematics models in occurrence of systems of linear equations and the main matrix operator is provided with sparse structure. To attack large and extra-large sparse systems of linear equations will permit to improve calculation accuracy enable to increase data processing. Multigrid method is chosen for assessing efficiency of RCS, for attacked sparse large and extra-large SLAE, because of it is speed of convergence solution and precision of calculates. Multigrid method of solving SLAE by RSC is classified as strongly connected type task of high performance mean that both of interprocessor exchanges and intermemory exchanges which are compatible to or exceed the number of executed operations. In connection with this thereby efficient implementation of this task requires to both multichannel access and nonlinear memory access. This approach is impossible to implement by using compute systems of traditional architecture and directly affects the performance. High performance can be achieved due to multiconveyer calculations, so we use more flexible architecture compute system, as RSC, which are based on FPGA. Recent studies have revealed that most demanding function of multigrid method is sparse general matrix-matrix multiplication (spGEMM).Utilization of RSC can decrease problem time large and extra-large sparse SLAE, research result has showed by the example of sparse general matrix-matrix multiplication. Comparison of RSC productivity with multiprocessing compute system show multiple advantages of RSC.

Download PDF

Keywords Extra-large sparse systems of linear algebraic equations; spGEMM; multigrid method; reconfigurable computing systems; systems of linear algebraic equation; SLAE.
References 1. Tikhonov A.N., Samarskiy A.A. Uravneniya matematicheskoy fiziki [Mathematical physics equations]. Moscow: Izd-vo Moskovskogo universiteta, 1999. 6 ed. 798 p. Science library dissertation and abstracts disserCat. Available at: http://www.dissercat.com/content/razrabotka-i-issledovanie-ekonomichnykh-algoritmov-resheniya-setochnykh-zadach-na-klastere-r#ixzz5WvO2qG2e (accessed 23 November 2018).
2. Sukhinov A.I., Chistyakov A.E., Protsenko E.A. Matematicheskoe modelirovanie transporta nanosov v pribrezhnykh vodnykh sistemakh na mnogoprotsessornoy vychislitel'noy sisteme [Mathematical modeling of sediment transport in coastal water systems by multiprocessor computing system], Vychislitel'nye metody i programmirovanie [Computational methods and programming], 2014, Vol. 15, pp. 610-620.
3. Sukhinov A.I., Nikitina A. V., Chistyakov A.E., Semenov I.S. Matematicheskoe modelirovanie usloviy formirovaniya zamorov v melkovodnykh vodoemakh na mnogoprotsessornoy vychislitel'noy sisteme [Mathematical modeling of the formation pestilence in shallow waters by a Multiprocessor Computing System], Vychislitel'nye metody i programmirovanie [Computational methods and programming], 2013, Vol. 14:1, pp. 103-112.
4. Sudareva O.Yu. Vstrechnaya optimizatsiya klassa zadach trekhmernogo modelirovaniya dlya arkhitektur mnogoyadernykh protsessov [Counter-optimization of the class of three-dimensional modeling problems for multi-core process architectures], Na pravakh rukopisi [Manuscript], 2018, pp. 101-118. Available at: http://www.ispras.ru/dcouncil/docs/diss/ 2018/sudareva/dissertacija-sudareva.pdf (accessed 23 November 2018).
5. Samarskiy A.A. Vvedenie v teoriyu raznostnykh skhem [Introduction to the theory of difference schemes]. Moscow: Nauka, 1971, 552 p. Scientific library of dissertations and abstracts disserCat. Available at: http://www.dissercat.com/content/razrabotka-i-issledovanie-ekonomichnykh-algoritmov-resheniya-setochnykh-zadach-na-klastere-r#ixzz5WvOBEVuA (accessed 23 November 2018).
6. Podoprigora A.V., Chekina M.D. Reshenie bol'shikh i sverkhbol'shikh razrezhennykh SLAU na rekonfiguriruemykh vychislitel'nykh sistemakh [Multigrid method to solve sparse large and extra-large slae y reconfigurable compute system], Superkomp'yuternye tekhnologii (SKT-2018): Materialy 5-oy Vserossiyskoy nauchno-tekhnicheskoy konferentsii [Super computers technology (SKT-2018): files of 5-s all-Russian science-technology conference: v 2 t. (17-22 september 2018 g.)]: in 2 vol. (17-22 September 2018). Rostov-on-Don: Izd-vo YuFU, 2018, pp. 201.
7. NITS SE i NK. Tertsius-2. © Copyright 2004-2018. OOO "NITS super-EVM i neyrokomp'yuterov" [SRC SC & NC. Tertsius-2. © Copyright 2004-2018. OOO "Supercomputers and Neurocomputers Research Center"]. Available at: http://superevm.ru/ index.php?page=tertsius-2 (accessed 10 November 2018).
8. Maksimov D.Yu., Filatov M.A. Issledovanie nelineynykh mnogosetochnykh metodov resheniya zadach odnofaznoy fil'tratsii [Investigation of nonlinear multigrid methods for solving single-phase filtration problems], Preprinty IPM im. M.V. Keldysha [Preprints of IPM name
M.V. Keldysh], 2011, No. 43, 26 p. Available at: http://library.keldysh.ru/ preprint.asp?id=2011-43 (accessed 12 October 2017).
9. Zhukov V.T., Novikova N.D., Feodoritova O.B. Parallel'nyy mnogosetochnyy metod dlya raznostnykh ellipticheskikh uravneniy. Ch. I. Osnovnye elementy algoritma [Parallel multigrid method for difference elliptic equations. Part I. The main elements of the algorithm], Preprinty IPM im. M.V. Keldysha [Preprints of IPM name M.V. Keldysh], 2012, No. 30, 32 p.
10. Zhukov V.T., Novikova N.D., Feodoritova O.B. Parallel'nyy mnogosetochnyy metod dlya raznostnykh ellipticheskikh uravneniy [Parallel multigrid method for difference elliptic equations]. Part II. Preprinty IPM im. M.V. Keldysha [Preprints of IPM name M.V. Keldysh], 2012, No. 30. Available at: http://www.keldysh.ru/papers/2012/prep2012_30.pdf (accessed 23 November 2018).
11. Baza razrezhennykh matrits. Matritsa gruppy Williams - webbase-1M. by Tim Davis, last updated 12-Mar-2014 [Base of sparse matrices. Group matrix Williams - webbase-1M. by Tim Davis, last updated 12-Mar-2014]. Available at: https://www.cise.ufl.edu/research/ sparse/matrices/Williams/webbase-1M.html (accessed 10 November 2018).
12. Kunchum R. On Improving Sparse Matrix-Matrix Multiplication on GPUs (Thesis). The Ohio State University, 2017, pp. 36-42 Available at: https://etd.ohiolink.edu/!etd.send_file? accession=osu1492694387445938&disposition=inline.
13. Nvideo. NVIDIA TITAN V, Copyright © 2018 NVIDIA Corporation. Available at: https://www.nvidia.com/ru-ru/titan/titan-v/ (accessed 10 November 2018).
14. Dordopulo A.I. Kalyaev I.A., Levin I.I., Semernikov E.A. Semeystvo mnogoprotsessornykh vychislitel'nykh sistem s dinamicheski perestraivaemoy arkhitekturoy [Family of multiprocessor computing systems with dynamically tunable architecture], Mnogoprotsessornye vychislitel'nye i upravlyayushchie sistemy: Materialy nauchno-tekhnicheskoy konferentsii [Multiprocessor computing and control systems: Materials of scientific and technical conference]. Taganrog, 2007, pp. 11-17.
15. Kalyaev I.A., Levin I.I., Semernikov E.A., Dordopulo A.I. Rekonfiguriruemye vychislitel'nye sistemy na osnove PLIS semeystva VIRTEX-6 [Reconfigurable computer systems based on the FPGA of the VIRTEX-6 family], Parallel'nye vychislitel'nye tekhnologii (PAVT’2011): Trudy mezhdunarodnoy nauchnoy konferentsii [Parallel computing technologies (PAVT’2011): Proceedings of the international scientific conference], 2011, pp. 203-211.
16. Maksimov D.Yu., Filatov M.A. Issledovanie nelineynykh mnogosetochnykh metodov resheniya zadach odnofaznoy fil'tratsii [Study of nonlinear multigrid methods for solving single-phase filtration problems], Preprinty IPM im. M.V. Keldysha [Preprints of IPM name M.V. Keldysh], 2011, NO. 43, 26 p. Available at: http://library.keldysh.ru/preprint.asp?id=2011-43 (accessed 09 October 2017).
17. Parallel'nye vychisleniya CUDA / NVIDIA Corporation [Parallel computing CUDA / NVIDIA Corporation], 2018. Available at: http://www.nvidia.ru/object/cuda-parallel-computing-ru.html (accessed 10 November 2018).
18. Superkomp'yuter RoadRunner. Laboratoriya Parallel'nykh informatsionnykh tekhnologiy NIVTS MGU [RoadRunner supercomputer. Laboratory of Parallel Information Technologies NIVTs MSU], 2008. Available at: http://parallel.ru/computers/reviews/RoadRunner.html (accessed 25 August 2017).
19. Vasil'ev Yu.V. Ol'shanskiy M.A. Kratkiy kurs po mnogosetochnym metodam i metodam dekompozitsii oblasti [Short course on multigrid methods and methods of region decomposition]. Moscow, 2007.
20. Fedorenko R.P. Relaksatsionnyy metod resheniya raznostnykh ellipticheskikh uravneniy [Relaxation method for solving difference elliptic equations], Vychislitel'noy matematiki i matematicheskoy fiziki [Computational Mathematics and Mathematical Physics], 1961, Vol. 1, No. 5, pp. 922-927.
21. Kopchenova N.V., Maron I.A. Vychislitel'naya matematika v primerakh i zadachakh [Computational Mathematics in Examples and Tasks]. Moscow: Nauka, 1972, 367 p.

Comments are closed.