×

Impact of data distribution on the parallel performance of iterative linear solvers with emphasis on CFD of incompressible flows. (English) Zbl 1311.76057

Summary: A parallel data structure that gives optimized memory layout for problems involving iterative solution of sparse linear systems is developed, and its efficient implementation is presented. The proposed method assigns a processor to a problem subdomain, and sorts data based on the shared entries with the adjacent subdomains. Matrix-vector-product communication overhead is reduced and parallel scalability is improved by overlapping inter-processor communications and local computations. The proposed method simplifies the implementation of parallel iterative linear equation solver algorithms and reduces the computational cost of vector inner products and matrix-vector products. Numerical results demonstrate very good performance of the proposed technique.

MSC:

76M10 Finite element methods applied to problems in fluid mechanics
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65Y05 Parallel numerical computation
76Dxx Incompressible viscous fluids

Software:

SPIKE; PETSc; METIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balay S, Brown J, Buschelman K, Eijkhout V, Gropp W, Kaushik D, Knepley M, Curfman McInnes L, Smith B, Zhang H (2013) PETSc Users Manual Revision 3.4, 2013
[2] Bazilevs Y, Calo VM, Cottrell JA, Hughes TJR, Reali A, Scovazzi G (2007) Variational multiscale residual-based turbulence modeling for large eddy simulation of incompressible flows. Comput Methods Appl Mech Eng 197(1-4):173-201 · Zbl 1169.76352 · doi:10.1016/j.cma.2007.07.016
[3] Bazilevs Y, Takizawa K, Tezduyar TE (2013) Computational fluid-structure interaction: methods and applications. Wiley, New York · Zbl 1286.74001 · doi:10.1002/9781118483565
[4] Behr M, Johnson A, Kennedy J, Mittal S, Tezduyar T (1993) Computation of incompressible flows with implicit finite element implementations on the Connection Machine. Comput Methods Appl Mech Eng 108:99-118 · Zbl 0784.76046 · doi:10.1016/0045-7825(93)90155-Q
[5] Behr M, Tezduyar TE (1994) Finite element solution strategies for large-scale flow simulations. Comput Methods Appl Mech Eng 112:3-24 · Zbl 0846.76041 · doi:10.1016/0045-7825(94)90016-7
[6] Brooks AN, Hughes TJR (1982) Streamline upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations. Comput Methods Appl Mech Eng 32(1-3):199-259 · Zbl 0497.76041 · doi:10.1016/0045-7825(82)90071-8
[7] Elman H, Silvester D, Wathen A (2014) Finite elements and fast iterative solvers with applications in incompressible fluid dynamics. Oxford University Press, New York · Zbl 1304.76002 · doi:10.1093/acprof:oso/9780199678792.001.0001
[8] Esmaily-Moghadam M, Bazilevs Y, Hsia TY, Vignon-Clementel I, Marsden AL (2011) A comparison of outlet boundary treatments for prevention of backflow divergence with relevance to blood flow simulations. Comput Mech 48(3):277-291 · Zbl 1398.76102 · doi:10.1007/s00466-011-0599-0
[9] Esmaily-Moghadam M, Bazilevs Y, Marsden AL (2013) Low entropy data mapping for sparse iterative linear solvers. In Proceedings of the conference on extreme science and engineering discovery environment: gateway to discovery, p 2. ACM, 2013 · Zbl 1311.76057
[10] Esmaily-Moghadam M, Bazilevs Y, Marsden AL (2013) A new preconditioning technique for implicitly coupled multidomain simulations with applications to hemodynamics. Comput Mech 52:1141-1152. doi:10.1007/s00466-013-0868-1 · Zbl 1388.76130 · doi:10.1007/s00466-013-0868-1
[11] Esmaily-Moghadam M, Bazilevs Y, Marsden AL (2014) A bi-partitioned iterative algorithm for solving linear systems arising from incompressible flow problems. Comput Methods Appl Mech Eng, in review · Zbl 1423.76228
[12] Esmaily-Moghadam M, Hsia T-Y, Marsden AL (2013) A non-discrete method for computation of residence time in fluid mechanics simulations. Phys Fluids. doi:10.1063/1.4819142 · Zbl 1427.76285
[13] Esmaily-Moghadam M, Migliavacca F, Vignon-Clementel IE, Hsia TY, Marsden AL (2012) Optimization of shunt placement for the Norwood surgery using multi-domain modeling. J Biomech Eng 134(5):051002 · doi:10.1115/1.4006814
[14] Esmaily-Moghadam M, Vignon-Clementel IE, Figliola R, Marsden AL (2013) A modular numerical method for implicit 0D/3D coupling in cardiovascular finite element simulations. J Comput Phys 224:63-79 · Zbl 1377.76041 · doi:10.1016/j.jcp.2012.07.035
[15] Hestenes MR, Stiefel E (1952) Methods of conjugate gradients for solving linear systems. J Res Natl Bur Stand 49:409-436 · Zbl 0048.09901 · doi:10.6028/jres.049.044
[16] Jansen KE, Whiting CH, Hulbert GM (2000) A generalized-[alpha] method for integrating the filtered Navier-Stokes equations with a stabilized finite element method. Comput Methods Appl Mech Eng 190(3—-4):305-319 · Zbl 0973.76048 · doi:10.1016/S0045-7825(00)00203-6
[17] Johnson AA, Tezduyar TE (1997) 3D simulation of fluid-particle interactions with the number of particles reaching 100. Comput Methods Appl Mech Eng 145:301-321 · Zbl 0893.76043 · doi:10.1016/S0045-7825(96)01223-6
[18] Karypis G, Kumar V (2009) MeTis: unstructured graph partitioning and sparse matrix ordering system, Version 4.0. http://www.cs.umn.edu/ metis · Zbl 0973.76048
[19] Kennedy JG, Behr M, Kalro V, Tezduyar TE (1994) Implementation of implicit finite element methods for incompressible flows on the CM-5. Comput Methods Appl Mech Eng 119:95-111 · Zbl 0848.76037 · doi:10.1016/0045-7825(94)00078-6
[20] Kuck DJ, Davidson ES, Lawrie DH, Sameh AH (1986) Parallel supercomputing today and the cedar approach. Science 231(4741):967-974 · doi:10.1126/science.231.4741.967
[21] Manguoglu M, Sameh AH, Saied F, Tezduyar TE, Sathe S (2009) Preconditioning techniques for nonsymmetric linear systems in the computation of incompressible flows. J Appl Mech 76(2):021204 · doi:10.1115/1.3059576
[22] Manguoglu M, Sameh AH, Tezduyar TE, Sathe S (2008) A nested iterative scheme for computation of incompressible flows in long domains. Comput Mech 43(1):73-80 · Zbl 1279.76024 · doi:10.1007/s00466-008-0276-0
[23] Manguoglu M, Takizawa K, Sameh AH, Tezduyar TE (2010) Solution of linear systems in arterial fluid mechanics computations with boundary layer mesh refinement. Comput Mech 46(1):83-89 · Zbl 1301.76087 · doi:10.1007/s00466-009-0426-z
[24] Manguoglu M, Takizawa K, Sameh AH, Tezduyar TE (2011) Nested and parallel sparse algorithms for arterial fluid mechanics computations with boundary layer mesh refinement. Int J Numer Methods Fluids 65(1-3):135-149 · Zbl 1427.76285 · doi:10.1002/fld.2415
[25] Manguoglu M, Takizawa K, Sameh AH, Tezduyar TE (2011) A parallel sparse algorithm targeting arterial fluid mechanics computations. Comput Mech 48(3):377-384 · Zbl 1398.76115 · doi:10.1007/s00466-011-0619-0
[26] Nigro N, Storti M, Idelsohn S, Tezduyar T (1998) Physics based GMRES preconditioner for compressible and incompressible Navier-Stokes equations. Comput Methods Appl Mech Eng 154:203-228 · Zbl 0957.76032
[27] Polizzi E, Sameh AH (2006) A parallel hybrid banded system solver: the SPIKE algorithm. Parallel Comput 32(2):177-194 · doi:10.1016/j.parco.2005.07.005
[28] Saad Y (2003) Iterative methods for sparse linear systems. In: SIAM, 2003 · Zbl 1031.65046
[29] Saad Y, Schultz MH (1983) GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. Technical Report YALEU/DCS/RR-254, Department of Computer Science, Yale University, Yale · Zbl 0599.65018
[30] Sameh AH, Kuck DJ (1978) On stable parallel linear system solvers. J ACM 25(1):81-91 · Zbl 0364.68051 · doi:10.1145/322047.322054
[31] Sengupta D, Kahn A, Burns J, Sankaran S, Shadden S, Marsden A (2012) Image-based modeling of hemodynamics in coronary artery aneurysms caused by Kawasaki disease. Biomech Model Mechanobiol 11:915-932 · doi:10.1007/s10237-011-0361-8
[32] Tezduyar T, Aliabadi S, Behr M, Johnson A, Mittal S (1993) Parallel finite-element computation of 3D flows. Computer 26(10):27-36 · Zbl 0875.76267 · doi:10.1109/2.237441
[33] Tezduyar TE (2001) Finite element methods for flow problems with moving boundaries and interfaces. Arch Comput Methods Eng 8:83-130 · Zbl 1039.76037 · doi:10.1007/BF02897870
[34] Tezduyar TE (2007) Finite elements in fluids: special methods and enhanced solution techniques. Comput Fluids 36:207-223 · Zbl 1177.76203 · doi:10.1016/j.compfluid.2005.02.010
[35] Tezduyar TE, Behr M, Aliabadi SK, Mittal S, Ray SE (1992) A new mixed preconditioning method for finite element computations. Comput Methods Appl Mech Eng 99:27-42 · Zbl 0762.65060 · doi:10.1016/0045-7825(92)90121-Y
[36] Tezduyar TE, Liou J (1989) Grouped element-by-element iteration schemes for incompressible flow computations. Comput Phys Commun 53:441-453 · Zbl 0803.76065 · doi:10.1016/0010-4655(89)90177-X
[37] Tezduyar TE, Mittal S, Ray SE, Shih R (1992) Incompressible flow computations with stabilized bilinear and linear equal-order-interpolation velocity-pressure elements. Comput Methods Appl Mech Eng 95:221-242 · Zbl 0756.76048 · doi:10.1016/0045-7825(92)90141-6
[38] Tezduyar TE, Sathe S (2004) Enhanced-approximation linear solution technique (EALST). Comput Methods Appl Mech Eng 193:2033-2049 · Zbl 1067.76574 · doi:10.1016/j.cma.2003.12.045
[39] Tezduyar TE, Sathe S (2005) Enhanced-discretization successive update method (EDSUM). Int J Numer Methods Fluids 47:633-654 · Zbl 1134.76445 · doi:10.1002/fld.836
[40] Tezduyar TE, Sathe S (2007) Modeling of fluid-structure interactions with the space-time finite elements: Solution techniques. Int J Numer Methods Fluids 54:855-900 · Zbl 1144.74044 · doi:10.1002/fld.1430
[41] Tezduyar TE (2003) Computation of moving boundaries and interfaces and stabilization parameters. Int J Numer Methods Fluids 43(5):555-575 · Zbl 1032.76605 · doi:10.1002/fld.505
[42] Tezduyar TE, Sameh AH (2006) Parallel finite element computations in fluid mechanics. Comput Methods Appl Mech Eng 195(13):1872-1884 · Zbl 1117.76037 · doi:10.1016/j.cma.2005.05.038
[43] Washio T, Hisada T, Watanabe H, Tezduyar TE (2005) A robust preconditioner for fluid-structure interaction problems. Comput Methods Appl Mech Eng 194:4027-4047 · Zbl 1151.74423 · doi:10.1016/j.cma.2004.10.001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.