Асинхронная реализация метода Холецкого для разреженных матриц на компьютерах с NUMA-архитектурой
DOI:
https://doi.org/10.26089/NumMet.v26r210Ключевые слова:
разложение Холецкого, NUMA-архитектура, парадигма асинхронного выполнения, ориентированный ациклический граф, библиотека hwlocАннотация
Реализован параллельный алгоритм разложения Холецкого для разреженных матриц, основанный на парадигме асинхронного выполнения и учитывающий особенности NUMA-архитектуры. Выполнение стадий численного разложения и прямой/обратной подстановки представляется в виде ориентированного ациклического графа, что позволяет обходиться без барьеров синхронизации, а также увеличить локальность доступа к данным с целью более эффективного использования иерархии подсистемы памяти вычислительного устройства. Оценка производительности показывает хорошую масштабируемость в сравнении с высоко оптимизированным коммерческим пакетом Intel MKL PARDISO, подтверждая эффективность предлагаемого подхода.
Библиографические ссылки
O. Schenk, K. G854rtner, W. Fichtner, and A. Stricker, “PARDISO: A High-Performance Serial and Parallel Sparse Linear Solver in Semiconductor Device Simulation,” Future Gener. Comput. Syst. 18 (1), 69-78 (2001).
doi 10.1016/S0167-739X(00)00076-5
U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid (Academic Press, London, 2001).
P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent, and J. Koster, “A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling,” SIAM J. Matrix Anal. Appl. 23 (1), 15-41 (2001).
doi 10.1137/S0895479899358194
P. Hénon, P. Ramet, and J. Roman, “PaStiX: A High-Performance Parallel Direct Solver for Sparse Symmetric Positive Definite Systems,” Parallel Comput. 28 (2), 301-321 (2002).
doi 10.1016/S0167-8191(01)00141-7
M. Jacquelin, Y. Zheng, E. Ng, and K. Yelick, “An Asynchronous Task-based Fan-Both Sparse Cholesky Solver,” arXiv: 1608.00044v2 (2016).
doi 10.48550/arXiv.1608.00044
G. Ballard, E. Carson, J. Demmel, et al., “Communication Lower Bounds and Optimal Algorithms for Numerical Linear Algebra,” Acta Numer. 23, 1-155 (2014).
doi 10.1017/S0962492914000038
M. Bollhöfer, O. Schenk, R. Janalik, et al., “State-of-the-Art Sparse Direct Solvers,” in Parallel Algorithms in Computational Science and Engineering (Birkh854user, Cham, 2020), pp. 3-33.
doi 10.1007/978-3-030-43736-7_1
oneAPI Threading Building Blocks (oneTBB).
https://www.threadingbuildingblocks.org/.
O. Schenk and K. G854rtner, “Two-Level Dynamic Scheduling in PARDISO: Improved Scalability on Shared Memory Multiprocessing Systems,” Parallel Comput. 28 (2), 187-197 (2002).
doi 10.1016/S0167-8191(01)00135-1
G. Karypis and V. Kumar, “A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs,” SIAM J. Sci. Comput. 20 (1), 359-392 (1998).
doi 10.1137/S1064827595287997
C. Chevalier and F. Pellegrini, “PT-Scotch: A Tool for Efficient Parallel Graph Ordering,” Parallel Comput. 34 (6-8), 318-331 (2008).
doi 10.1016/j.parco.2007.12.001
J. W. H. Liu, “The Role of Elimination Trees in Sparse Factorization,” SIAM J. Matrix Anal. Appl. 11 (1), 134-172 (1990).
doi 10.1137/0611010
C. C. Ashcraft, A Taxonomy of Column-Based Cholesky Factorizations , PhD Thesis in Mathematics (Yale University, New Haven, US, 1996).
https://dl.acm.org/doi/book/10.5555/241365.
F. Broquedis, J. Clet-Ortega, S. Moreaud, et al., “hwloc: A Generic Framework for Managing Hardware Affinities in HPC Applications,” 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing (2010).
doi 10.1109/PDP.2010.67
T. A. Davis and Y. Hu, “The University of Florida Sparse Matrix Collection,” ACM Trans. Math. Softw. 38 (1), Article No 1, 1-25 (2011).
doi 10.1145/2049662.2049663
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2025 А. С. Маслов, М. М. Макаров, Н. Н. Потравкин, С. О. Проскурня
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
