Применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений

Валентина Николаевна Алеева, Михаил Борисович Шатов

Аннотация


Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье продемонстрировано применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений. Концепция Q-детерминанта основана на унифицированном представлении численных алгоритмов в форме Q-детерминанта. Любой численный алгоритм имеет Q-детерминант. Q-детерминант состоит из Q-термов. Их число равно числу выходных данных алгоритма. Каждый Q-терм описывает все возможные способы вычисления одного из выходных данных на основе входных данных. Q-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции Q-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции Q-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется Q-эффективной. В качестве применения метода проектирования Q-эффективных программ описано проектирование программ для реализации метода сопряженных градиентов на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ».


Ключевые слова


повышение эффективности параллельных вычислений; Q-детерминант алгоритма; представление алгоритма в форме Q-детерминанта; Q-эффективная реализация алгоритма; ресурс параллелизма алгоритма; Q-эффективная программа

Полный текст:

PDF

Литература


Aleeva V.N. Analysis of Parallel Numerical Algorithms. Preprint no. 590. Novosibirsk, Computing Center of the Siberian Branch of the Academy of Sciences of the USSR, 1985. 23 p. (in Russian)

Aleeva V.N., Zotova P.S., Skleznev D.S. Advancement of research for the parallelism resource of numerical algorithms with help of software Q-system. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2021. Vol. 10, no. 2. P. 66–81. (in Russian) DOI: 10.14529/cmse210205.

Voevodin V.V., Voevodin Vl.V. Parallel Computing. St. Petersburg, BHV-Petersburg, 2002. 608 p. (in Russian)

Ershov Yu.L., Palyutin E.A. Mathematical Logic. Moscow, Mir, 1984. 303 p.

Open Encyclopedia of Parallel Algorithmic Features. URL: https://algowiki-project.org/en (accessed: 16.05.2021).

"Tornado SUSU" Supercomputer. URL: http://supercomputer.susu.ru/en/computers/tornado/ (accessed: 16.05.2021).

Akhmed-Zaki D., Lebedev D., Malyshkin V., et al. Automated Construction of High Performance Distributed Programs in LuNA System. Parallel Computing Technologies (PaCT 2019). Lecture Notes in Computer Science. Vol. 11657. 2019. P. 3–9. DOI: 10.1007/978-3-030-25636-4_1.

Aleeva V. Designing a Parallel Programs on the Base of the Conception of Q-Determinant. Supercomputing. RuSCDays 2018. Communications in Computer and Information Science. Vol. 965. 2019. P. 565–577. DOI: 10.1007/978-3-030-05807-4_48.

Aleeva V.N. Improving Parallel Computing Efficiency. Proceedings – 2020 Global Smart Industry Conference, GloSIC 2020. IEEE, 2020. P. 113–120. Article number 9267828. DOI: 10.1109/GloSIC50886.2020.9267828.

Aleeva V.N., Aleev R.Zh. High-Performance Computing Using Application of Q-determinant of Numerical Algorithms. Proceedings – 2018 Global Smart Industry Conference, GloSIC 2018. IEEE, 2018. 8 p. Article number 8570160. DOI: 10.1109/GloSIC.2018.8570160.

Aleeva V., Bogatyreva E., Skleznev A., et al. Software Q-system for the Research of the Resource of Numerical Algorithms Parallelism. Supercomputing. RuSCDays 2019. Communications in Computer and Information Science. Vol. 1129. 2019. P. 641–652. DOI: 10.1007/978-3-030-36592-9_52.

Aleeva V.N., Sharabura I.S., Suleymanov D.E. Software System for Maximal Parallelization of Algorithms on the Base of the Conception of Q-determinant. Parallel Computing Technologies (PaCT 2015). Lecture Notes in Computer Science. Vol. 9251. 2015. P. 3–9. DOI: 10.1007/978-3-319-21909-7_1.

Antonov A.S., Dongarra J., Voevodin V.V. AlgoWiki Project as an Extension of the Top500 Methodology. Supercomputing Frontiers and Innovations. 2018. Vol. 5, no. 1. P. 4–10. DOI: 10.14529/jsfi180101.

Henk A. van der Vorst. Iterative Krylov Methods for Large Linear System. USA, Cambridge University Press, 2003. 221 p. DOI: 10.1017/CBO9780511615115.

Legalov A.I., Vasilyev V.S., Matkovskii I.V., et al. A Toolkit for the Development of Data-Driven Functional Parallel Programmes. Parallel Computational Technologies (PCT’2018). Communications in Computer and Information Science. Vol. 910. 2018. P. 16–30. DOI: 10.1007/978-3-319-99673-8_2.

Leung J.Y.-T., Zhao H. Scheduling problems in master-slave mode. Annals of Operations Research. 2008. Vol. 159. P. 215–231. DOI: 10.1007/s10479-007-0271-4.

Li Y., Dou W., Yang K., et al. Optimized Data I/O Strategy of the Algorithm of Parallel Digital Terrain Analysis. 13th International Symposium on Distributed Computing and Applications to Business, Engineering and Science. 2014. P. 34–37. DOI: 10.1109/DCABES.2014.10.

Matveev S.A., Zagidullin R.R., Smirnov A.P., et al. Parallel Numerical Algorithm for Solving Advection Equation for Coagulating Particles. Supercomputing Frontiers and Innovations. 2018. Vol. 5, no. 2. P. 43–54. DOI: 10.14529/jsfi180204.

McColl W.F. General Purpose Parallel Computing. Lectures on Parallel Computation, Cambridge International Series on Parallel Computation. USA, Cambridge University Press, 1993. P. 337–391.

Moskovsky A., Roganov V., Abramov S. Parallelism Granules Aggregation with the T-System. Parallel Computing Technologies (PaCT 2007). Lecture Notes in Computer Science. Vol. 4671. 2007. P. 293–302. DOI: 10.1007/978-3-540-73940-1_30.

Prifti V., Bala R., Tafa I., et al. The time profit obtained by parallelization of quicksort algorithm used for numerical sorting. Science and Information Conference (SAI). 2015. P. 897–901. DOI: 10.1109/SAI.2015.7237248.

Valiant L.G. A bridging model for parallel computation. Communications of the ACM. 1990. Vol. 33, no. 8. P. 103–111. DOI: 10.1145/79173.79181.

Voevodin V.V., Voevodin Vl.V. The V-Ray technology of optimizing programs to parallel computers. Numerical Analysis and Its Applications (WNAA 1996). Lecture Notes in Computer Science. Vol. 1196. 1997. P. 546–556. DOI: 10.1007/3-540-62598-4_136.

You J., Kezhang H., Liang H., et al. Research on parallel algorithms for calculating static characteristics of electromagnetic relay. IEEE 11th Conference on Industrial Electronics and Applications (ICIEA). 2016. P. 1421–1425. DOI: 10.1109/ICIEA.2016.7603808.




DOI: http://dx.doi.org/10.14529/cmse210304