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

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

Автор: В.Н. Алеева, М.Б. Шатов

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 3 т.10, 2021 года.

Бесплатный доступ

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

Еще

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

Короткий адрес: https://sciup.org/147234532

IDR: 147234532   |   DOI: 10.14529/cmse210304

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

  • Алеева В.Н. Анализ параллельных численных алгоритмов. Препринт № 590. Новосибирск: ВЦ СО АН СССР, 1985. 23 с.
  • Алеева В.Н., Зотова П.С., Склезнев Д.С. Расширение возможностей исследования ресурса параллелизма численных алгоритмов с помощью программной Q-системы // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 2. С. 66–81. DOI: 10.14529/cmse210205.
  • Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.
  • Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, 1987. 336 с.
  • Открытая энциклопедия свойств алгоритмов. URL: https://algowiki-project.org/ru (дата обращения: 16.05.2021).
  • Суперкомпьютер «Торнадо ЮУрГУ». URL: http://supercomputer.susu.ru/computers/tornado/ (дата обращения: 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 model // 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 TSystem // 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.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp