РЕШЕНИЕ РАЗРЕЖЕННЫХ СЛАУ БОЛЬШОЙ И СВЕРХБОЛЬШОЙ РАЗМЕРНОСТИ МНОГОСЕТОЧНЫМ МЕТОДОМ НА РВС

  • А.В. Подопригора ООО "НИЦ супер-ЭВМ и нейрокомпьютеров"
  • М.Д. Чекина ООО "НИЦ супер-ЭВМ и нейрокомпьютеров"
Ключевые слова: Cверхбольшие разреженные системы линейных алгебраических уравнений, многосеточный метод, реконфигурируемые вычислительные системы, системы линейных алгеб-раический уравнений

Аннотация

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

Литература

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 dis-sertation 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 [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.
Опубликован
2019-04-04
Выпуск
Раздел
РАЗДЕЛ IV. РЕКОНФИГУРИРУЕМЫЕ И НЕЙРОСЕТЕВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ