ПОДХОД К ЭФФЕКТИВНОЙ РЕАЛИЗАЦИИ ЧИСЛЕННЫХ АЛГОРИТМОВ

Авторы: 
В.Н. Алеева
УДК: 
004.021, 004.032.24, 004.051, 004.272
DOI: 
10.24412/2073-0667-2025-1-29-44
Аннотация: 

В статье рассмотрен метод проектирования эффективных программ для реализации числен­ных алгоритмов, основанный на авторской концепции Q-детерминанта. Разработанные с помо­щью метода эффективные программы называются Q-эффективными. Они используют ресурс параллелизма алгоритмов полностью. Приводится обзор численных алгоритмов, для которых разработаны Q-эффективные программы. Введено понятие вычислительной инфраструктуры программы. Доказано, что каждая из Q-эффективных программ, реализующих один и тот же численный алгоритм, является самой эффективной для своей вычислительной инфраструкту­ры среди программ, реализующих тот же алгоритм. Проведенное исследование обосновывает теоретическую и практическую значимость метода проектирования эффективных программ для реализации численных алгоритмов.

Список литературы

  1. Aleeva V., Aleev R. Investigation and Implementation of Parallelism Resources of Numerical Algorithms // ACM Transactions on Parallel Computing. 2023. Vol. 10. N 2, Article number 8. P. 1¬64. DOI: 10.1145/3583755.
  2. Алеева B.H. Анализ параллельных численных алгоритмов. Препринт № 590. Новосибирск: ВЦ СО АН СССР, 1985. 23 с.
  3. Ершов Ю. Л., Палютин Е. А. Математическая логика. М.: Наука, 1987. 336 с.
  4. Алеева В.Н., Зотова П.С., Склезнев Д.С. Расширение возможностей исследования ре¬сурса параллелизма численных алгоритмов с помощью программной Q-системы // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 2. С. 66-81. DOI: 10.14529/cmse210205.
  5. 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.
  6. 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.
  7. 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. 2019. Vol. 1129. P. 641-652. DOI: 10.1007/978-3-030-36592¬9 52.
  8. 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.
  9. 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.
  10. Leung J.Y.-T., Zhao H. Scheduling problems in master-slave model // Annals of Operations Research. 2008. Vol. 159. P. 215-231. DOL 1007/sl0479-007-0271-4.
  11. Aleeva V. Designing a Parallel Programs on the Base of the Conception of Q-Determinant // Supercomputing. RuSCDays 2018. Communications in Computer and Information Science. 2019. Vol. 965. P. 565-577. DOL 10.1007/978-3-030-05807-4_48.
  12. Суперкомпьютер «Торнадо ЮУрГУ». [Электрон. Рес.]: http://supercomputer.susu.ru/ computers/tornado/. Дата обращения: 17.09.2024.
  13. Открытая энциклопедия свойств алгоритмов. [Электрон. Рес.]: https://algowiki¬project. org/ru. Дата обращения: 17.09.2024.
  14. Валькевич Н.В. Q-эффективная реализация алгоритма умножения матриц на суперком-пьютере «Торнадо ЮУрГУ»// Вып. квалиф. работа бакалавра по направлению «Фундаментальная информатика и информационные технологии»: 02.03.02 / Южно-Уральский государственный университет. Челябинск. 2017. 33 л. [Электрон. Рес.]: http://omega.sp.susu.ru/publications/ bachelorthesis/17-Valkevich.pdf. Дата обращения: 17.09.2024.
  15. Тарасов Д. Е. Q-эффективный кодизайн реализации метода Гаусса-Жордана на суперком-пьютере «Торнадо ЮУрГУ» // Вып. квалиф. работа магистра по направлению «Фундаменталь-ная информатика и информационные технологии»: 02.04.02 / Южно-Уральский государственный университет. Челябинск. 2017. 41 л. [Электрон. Рес.]: http://omega.sp.susu.ru/publications/ masterthesis/17- Tarasov. pdf. Дата обращения: 17.09.2024
  16. Лаптева Ю. С. Q-эффективная реализация метода Якоби для решения СЛАУ на суперком- пвютере «Торнадо ЮУрГУ» // Вып. квалиф. работа бакалавра по направлению «Фундаменталь¬ная информатика и информационные технологии»: 02.03.02 / Южно-Уральский государственный университет. Челябинск. 2017. 30 л. [Электрон. Рес.]: http://omega.sp.susu.ru/publications/ bachelorthesis/17-Lapteva.pdf. Дата обращения: 20.09.2024.
  17. Баженова Л. А. Применение метода проектирования Q-эффективной программы для ре¬шения системы сеточных уравнений // Вып. квалиф. работа бакалавра по направлению «Фун¬даментальная информатика и информационные технологии»: 02.03.02 / Южно-Уральский госу¬дарственный университет. Челябинск. 2018. 30 л. [Электрон. Рес.]: http://omega.sp.susu.ru/ publications/bachelorthesis/18-Bazhenova.pdf. Дата обращения: 20.09.2024.
  18. Кондакова А. С. Разработка Q-эффективной программы для решения пятиточечных раз¬ностных уравнений методом простой итерации и исследование ее динамических характеристик // Вып. квалиф. работа магистра по направлению «Фундаментальная информатика и инфор¬мационные технологии»: 02.04.02 / Южно-Уральский государственный университет. Челябинск. 2019. 40 л. [Электрон. Рес.]: http://omega.sp.susu.ru/publications/masterthesis/2019_220_ kondakovaas.pdf. Дата обращения: 20.09.2024.
  19. Нечепоренко А.Д. Разработка Q-эффективной программы для решения СЛАУ мето¬дом Гаусса-Зейделя // Вып. квалиф. работа бакалавра по направлению «Фундаментальная информатика и информационные технологии»: 02.03.02 / Южно-Уральский государственный университет. Челябинск. 2018. 32 л. [Электрон. Рес.]: http://omega.sp.susu.ru/publications/ bachelorthesis/18-Necheporenko .pdf. Дата обращения: 20.09.2024.
  20. Алеева В.Н., Шатов М.Б. Применение концепции Q-детерминанта для эффективной реа¬лизации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 3. С. 56-71. DOI: 10.14529/cmse210304.
  21. Dijkstra Е. W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. Vol. 1. P. 269-271. DOI: 10.1007/BF01386390.
  22. Алеева B.H., Манатин П.А. Применение метода проектирования Q-эффективных про¬грамм для алгоритма Дейкстры. // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2023. Т. 12, № 2. С. 62-77. DOI: 10.14529/cmse230203.
  23. SCISPACE. Ответ на вопрос «How does parallel computing improve the efficiency of AI algorithms?». [Электрон. Pec.]: https://typeset.io/questions/how-does-parallel-computing- improve-the-efficiency-of-ai-5gkdumloct. Дата обращения: 09.2024.
  24. Сапожников А. С. Применение метода проектирования Q-эффективных программ к ме¬тоду стохастического градиентного спуска для обучения нейронных сетей // Вып. квалиф. ра¬бота магистра по направлению «Программная инженерия»: 09.04.04 / Южно-Уральский госу¬дарственный университет. Челябинск. 20 43 л.[Электрон. Рес.]: https://sp.susu.ru/student/ masterthesis/2024_229_sapoznikovas .pdf. Дата обращения: 23.09.2024.
  25. Воеводин В. В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.
  26. Алеева В.Н. Автоматизированное проектирование и исполнение эффективных программ для численных алгоритмов // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2023. Т. 12, № 3. С. 31-49. DOI: 10.14529/cmse230303               

 

 

 

Ключевые слова: 
повышение эффективности параллельных вычислений, Q-детерминант алгоритма, представление алгоритма в форме Q-детерминанта, Q-эффективная реализация алгоритма, ресурс параллелизма алгоритма, Q-эффективная программа.
Номер журнала: 
1(66) 2025 г.
Год: 
2025
Адрес: 
Южно-Уральский государственный университет (НИУ), 454080, Челябинск, Россия
Библиографическая ссылка: 
Библиографическая ссылка: Алеева В. Н. Подход к эффективной реализации численных алгоритмов //"Проблемы информатики", 2025, № 1, с.29-44 DOI: 10.24412/2073-0667-2025-1-29-44. – EDN: QALLET