Ресурсно-эффективные конечно-элементные вычисления на многоядерных архитектурах

Сергей Петрович Копысов; Ильяс Ринатович Кадыров; Александр Константинович Новиков

doi:10.20537/2226-3594-2019-53-08

Сергей Петрович Копысов
- Удмуртский государственный университет
Ильяс Ринатович Кадыров
- Удмуртский государственный университет
Александр Константинович Новиков
- Удмуртский государственный университет

DOI: https://doi.org/10.20537/2226-3594-2019-53-08

Ключевые слова: метод конечных элементов, параллельные вычисления, разделение неструктурированной сетки, граф Риба, интенсивность арифметических операций, универсальная модель масштабируемости

Аннотация

В данной работе рассматривается построение эффективных конечно-элементных алгоритмов на трехмерных неструктурированных сетках, учитывающих сложные параллельные процессы синхронизации, вопросы распределения памяти и хранения данных. Предлагается послойное разделение расчетной сетки на подобласти без ветвления внутренних границ, упрощающее доступ к независимым данным и параллельным вычислениям на различных этапах конечно-элементного решения задач на неструктурированных сетках в многосвязных областях. Анализируется возможность прогнозирования временной эффективности и ресурсоемкости предложенных алгоритмических решений. Приводится анализ ресурсной эффективности алгоритмов в поэлементной схеме решения системы линейных алгебраических уравнений метода конечных элементов. Показано, что низкая арифметическая интенсивность рассматриваемых алгоритмов приводит к тому, что их производительность ограничивается пропускной способностью подсистемы памяти, а не производительностью процессоров. Графическая память обладает большей пропускной способностью, чем оперативная, что позволяет существенно увеличить производительность алгоритма на GPU.

Литература

1. Копысов С.П., Новиков А.К., Пономарев А.Б., Рычков В.Н., Сагдеева Ю.А. Программная среда построения расчетных моделей метода конечных элементов для параллельных распределенных вычислений // Информационные технологии. 2008. № 3. С. 75-82.
2. Копысов С.П., Новиков А.К., Недожогин Н.С., Караваев А.С. Послойное упорядочение ячеек для задач разделения, отображения и параллельных вычислений без конфликтов на неструктурированных сетках // Параллельные вычислительные технологии - XI международная конференция, ПаВТ'2017, Казань, 2017. Челябинск: Издательский центр ЮУрГУ, 2017. С. 386-398.
3. Кадыров И.Р., Копысов С.П., Новиков А.К. Разделение триангулированной многосвязной области на подобласти без ветвления внутренних границ // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. 2018. Т. 160. № 3. C. 544-560.
http://mi.mathnet.ru/uzku1477
4. Копысов С.П., Новиков А.К. Метод декомпозиции для параллельного адаптивного конечно-элементного алгоритма // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2010. Вып. 3. C. 141-154.
https://doi.org/10.20537/vm100315
5. Komatitsch D., Michea D., Erlebacher G. Porting a high-order finite-element earthquake modeling application to NVIDIA graphics cards using CUDA // Journal of Parallel and Distributed Computing. 2009. Vol. 69. Issue 5. P. 451-460.
https://doi.org/10.1016/j.jpdc.2009.01.006
6. Kadyrov I.R., Kopysov S.P., Novikov A.K. Partitioning of an arbitrary domain into subdomains without branching of inner boundaries // Journal of Physics: Conference Series. 2019. Vol. 1158. Issue 3. 032001.
https://doi.org/10.1088/1742-6596/1158/3/032001
7. Kadyrov I.R., Kopysov S.P., Novikov A.K. Parallel partitioning without branching of inner boundaries for arbitrary domain // Proceedings of the 4th Ural Workshop on Parallel, Distributed, and Cloud Computing for Young Scientists (Ural-PDC 2018). Yekaterinburg, Russia. CEUR Workshop Proceedings. 2018. Vol-2281. P. 60-66.
http://ceur-ws.org/Vol-2281/
8. Novikov A., Piminova N., Kopysov S., Sagdeeva Yu. Layer-by-layer partitioning of finite-element meshes for multi-core architectures // Communications in Computer and Information Science. Cham: Springer, 2016. P. 106-117.
https://doi.org/10.1007/978-3-319-55669-7_9
9. Копысов С.П., Новиков А.К. Методы декомпозиции: разделение расчетных сеток. Ижевск: Издательский центр «Удмуртский университет», 2018. 102 с.
10. Постников М.М. Введение в теорию Морса. М.: Наука, 1971. 568 с.
11. Иванов А.О., Тужилин А.А., Фоменко А.Т. Компьютерное моделирование кривых и поверхностей // Фундамент. и прикл. матем. 2009. Т. 15. Вып. 5. C. 63-94.
12. Karypis G., Kumar V. Multilevel $k$-way partitioning scheme for irregular graphs // Journal of Parallel and Distributed Computing. 1998. Vol. 48. No. 1. P. 96-129.
https://doi.org/10.1006/jpdc.1997.1404
13. Gunther N.J., Puglia P., Tomasette K. Hadoop superlinear scalability // Communications of the ACM. 2015. Vol. 58. No. 4. P. 46-55.
https://doi.org/10.1145/2719919
14. Dennis J.E. (Jr.), Gay D.M., Welsch R.E. Algorithm 573: NL2SOL - An adaptive nonlinear least-squares algorithm // ACM Transactions on Mathematical Software. 1981. Vol. 7. No. 3. P. 369-383.
https://doi.org/10.1145/355958.355966
15. Williams S., Waterman A., Patterson D. Roofline: an insightful visual performance model for multicore architectures // Communications of the ACM. 2009. Vol. 52. No. 4. P. 65-76.
https://doi.org/10.1145/1498765.1498785