MULTIGRID METHOD TO SOLVE SPARSE LARGE AND EXTRA-LARGE SLAE BY RECONFIGURABLE COMPUTING SYSTEM
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 pro-cess 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 equa-tions 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 multipro-cessing compute system show multiple advantages of RSC.
References
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 [Compu-tational 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 differ-ence 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 "Supercom-puters and Neurocomputers Research Center"]. Available at: http://superevm.ru/ in-dex.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/ pre-print.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 equa-tions]. 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 No-vember 2018).
11. Baza razrezhennykh matrits. Matritsa gruppy Williams - webbase-1M. by Tim Davis, last up-dated 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? acces-sion=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 multiproces-sor 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 confer-ence]. 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 (ac-cessed 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 decomposi-tion]. Moscow, 2007.
20. Fedorenko R.P. Relaksatsionnyy metod resheniya raznostnykh ellipticheskikh uravneniy [Re-laxation 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 [Compu-tational Mathematics in Examples and Tasks]. Moscow: Nauka, 1972, 367 p.
