Parallel Algorithms for Forward and Back Substitution in Linear Algebraic Equations of Finite Element Method

• Autorzy: Fialko Sergiy

Identyfikatory

DOI

10.26636/jtit.2019.134919

• Języki publikacji: EN

Abstrakty

EN

This paper considers several algorithms for parallelizing the procedure of forward and back substitution for high-order symmetric sparse matrices on multi-core computers with shared memory. It compares the proposed approaches for various finite-element problems of structural mechanics which generate sparse matrices of different structures.

Słowa kluczowe

EN

finite element method; multithreaded parallelization; sparse symmetric matrices; triangular solution

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2019
• Tom: nr 4
• Strony: 20--29
• Opis fizyczny: Bibliogr. 27 poz., rys., tab.

Twórcy

autor

Fialko Sergiy

• Institute of Computer Science, Faculty of Physics, Mathematics and Computer Science, Cracow University ofTechnology, Warszawska24, 31-155 Cracow, Poland

Bibliografia

• [1] S. Yu. Fialko, „Iterative methods for solving large-scale problems of structural mechanics using multi-core computers", Archiv. of Civil and Mechan. Engin., vol. 14, pp. 190-203, 2014 (doi: 10.1016/j.acme.2013.05.009).
• [2] A. V. Perelmuter and S. Yu. Fialko, „Problems of computational mechanics relate to finite-element analysis of structural constructions", Int. J. for Computat. Civil and Struct. Engin., vol. 1, no 2, 2005, pp. 72-86 (doi: 10.1615/IntJCompCivStructEng.v1.i2.70).
• [3] P. R. Amestoy, I. S. Duff, and J-Y. L'Excellent, „Multifrontal paralel distributed symmetric and unsymmetric solvers", Comp. Meth. Appl. Mechan. Engin., vol. 184, no. 2, pp. 501-520, 2000 (doi: 10.1016/S0045-7825(99)00242-X).
• [4] S. Yu. Fialko, „PARFES: A method for solving finite element linear equations on multi-core computers", Advan. in Engin. Software, vol. 40, no. 12, pp. 1256-1265, 2010 (doi: 10.1016/j.advengsoft.2010.09.002).
• [5] S. Yu. Fialko, „Parallel direct solver for solving systems of linear equations resulting from finite element method on multi-core desktops and workstations", Comp. and Mathema. with Appl., vol. 70, pp. 2968-2987, 2015 (doi: 10.1016/j.camwa.2015.10.009).
• [6] O. Schenk and K. Gartner, „Two-level dynamic scheduling in PARDISO: Improved scalability on shared memory multiprocessing systems", Parall. Comput., vol. 28, pp. 187-197, 2002 (doi: 10.1016/S0167-8191(01)00135-1).
• [7] S. Fialko and V. Karpilovskyi, „Time history analysis formulation in SCAD FEA software", J. of Measur. in Engin., vol. 6, no. 4, pp. 173-180, 2018 (doi: 10.21595/jme.2018.20408).
• [8] S. Fialko and V. Karpilovskyi, „Multithreaded parallelization of the finite element method algorithms for solving physically nonlinear problems", in Proc. of the Federated Conf. on Comp. Sci. and Inform. Syst., Pozna«, Poland, 2018, vol. 15, pp. 31-318 (doi: 10.15439/2018F40).
• [9] S. Yu. Fialko, E. Z. Kriksunov, and V. S. Karpilovskyy, „A block Lanczos method with spectral transformations for natural vibrations and seismic analysis of large structures in SCAD software", in Proc. 15th Int. Conf. on Comp. Methods in Mechan. CMM-2003, Gliwice, Poland, 2003, pp. 12-130 [Online]. Available: https://pdfs.semanticscholar.org/046c/c4f0e921c75f6dc081909324de3c31a1f8ea.pdf
• [10] S. Fialko and V. Karpilovskyi, „Block subspace projection preconditioned conjugate gradient method for structural modal analysis", in Proc. of the Federated Conf. on Comp. Sci. and Inform. Syst., Praha, Czech Republik, 2017, vol. 11, pp. 497-506 (doi: 10.15439/2017F64).
• [11] E. Gallopoulos, B. Philippe, and A. H. Sameh, Parallelism in Matrix Computations. New York, London: Springer, 2016 (ISBN: 9789401771870).
• [12] C. C. K. Mikkelsen, A. B. Schwarz, and L. Karlsson, „Parallel robust solution of triangular linear systems. Concurrency and computation, practice and experiments", Concurr. and Comput. Pract. and Exper., vol. 30, pp. 1-19, 2018, (doi: 10.1002/cpe.5064).
• [13] T. Iwashita and M. Shimasaki, „Algebraic multi-color ordering method for parallelized ICCG solver in unstructured finite element analyses", IEEE Trans. on Magnet., vol. 38, no. 2, pp. 429-432, 2002 (doi: 10.1109/20.996114).
• [14] M. Naumov, „Parallel solution of sparse triangular linear systems in the preconditioned iterative methods on the GPU", NVIDIA Tech. Rep. NVR-2011-001, June 2011, pp. 1-21 [Online]. Available: https://research.nvidia.com/sites/default/_les/pubs/2011-06 Parallel-Solution-of/nvr-2011-001.pdf (accessed on 11.04.2019).
• [15] S. Fialko and F. Zeglen, „Preconditioned conjugate gradient method for solution of large finite element problems on CPU and GPU", J. of Telecommun. and Inform. Technol., no. 2, 2016, pp. 26-33 [Online]. Available: https://www.il-pib.pl/czasopisma/JTIT/2016/2/26.pdf
• [16] W. Liu, A. Li, J. Hogg, I. S. Duff, and B. Vinter, „Synchronizationfree algorithm for parallel sparse triangular solves", in Euro-Par 2016: Parallel Processing 22nd International Conference on Parallel and Distributed Computing, Grenoble, France, August 24-26, 2016, Proceedings, P.-F, Dutot and D. Trystram, Eds. LNCS, vol. 9833, pp. 617-630. Springer, 2016 (doi: 10.1007/978-3-319-43659-3 45).
• [17] H. Anzt, E. Chow, and J. Dongarra, „Iterative sparse triangular solves for preconditioning", in Euro-Par 2015: Parallel Processing 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings, J. L. Traff, S. Hunold, and F. Versaci, Eds. LNCS, vol. 9233, pp. 650-661. Springer, 2015 (doi:: 10.1007/978-3-662-48096-0 50).
• [18] R. Vuduc et al., „Automatic performance tuning and analysis of sparse triangular solve", Semantic Scholar, 2002 [Online]. Available: https://www.semanticscholar.org/paper/Automatic-Performance-Tuning-and-Analysis-of-Sparse-Vuduc-Kamil/002ed5f20260cb140cd12da352db61daf6bd3984(accessed on 12.04.2019).
• [19] M. M. Wolf, M. A. Heroux, and E. G. Boman, „Factors impacting performance of multithreaded sparse triangular solve", in High Performance Computing for Computational Science - VECPAR 2010. 9th International conference, Berkeley, CA, USA, June 22-25, 2010, Revised Selected Papers, J. M. Laginha M. Palma et al., Eds. LNCS, vol. 6449, pp. 32-44. Springer, 2010 (doi: 10.1007/978-3-642-19328-6 6).
• [20] E. Rothberg and A. Gupta, „Parallel ICCG on a hierarchical memory multiprocessor-addressing the triangular solve bottleneck", Parall. Comput., vol. 18, no. 7, 1992, pp. 719-741 (doi: 10.1016/0167-819(92)90041-5).
• [21] F. L. Alvarado, A. Pothen, and R. Schreiber, „Highly parallel sparse triangular solution", in Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert, and J.W. H. Liu, Eds. Springer-Verlag, 1993 (ISBN: 9781461383710).
• [22] B. Suchoski, C. Severn, M. Shantharam, and P. Raghavan, „Adapting sparse triangular solution to GPUs", in Proc. 41st Int. Conf. On Parall. Process. Worksh., Pittsburgh, PA, USA, 2012 (doi: 10.1109/ICPPW.2012.23).
• [23] S. Marrakchi and M. Jemni, „Fine-grained parallel solution for solving sparse triangular systems on multicore platform using OpenMP interface", in Proc. Int. Conf. on High Perform. Comput. & Simul. HPCS 2017, Genoa, Italy, 2017, pp. 659-666 (doi: 10.1109/HPCS.2017.102).
• [24] E. Totoni, M. T. Heath, and L. V. Kale, „Structure-adaptive paralel solution of sparse triangular linear systems", Parall. Comput., vol. 40, 2014, pp. 454-470 (doi: 10.1016/j.parco.2014.06.006).
• [25] „Developer Guide for Intel Math Kernel Library for Windows", Intel Math Kernel Library [Online]. Available: https://software.intel.com/en-us/mkl-windows-developer-guide (accessed on 20.04.2019).
• [26] A. George and J. W. H. Liu, Computer Solution of Sparse Positive Definite Systems. New Jersey: Prentice-Hall, 1981 (ISBN: 0131652745).
• [27] G. Karypis and V. Kumar, „METIS: Unstructured graph partitioning and sparse matrix ordering system", Tech. Rep., Department of Computer Science, University of Minnesota, Minneapolis, 1995 [Online]. Available: https://dm.kaist.ac.kr/kse625/resources/metis.pdf

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).