On the Parallelization of Self-Adaptive hp-Finite Element Methods Part II. Partitioning Communication Agglomeration Mapping (PCAM) Analysis

• Autorzy: Paszyński, M.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a general methodology for an efficient parallelization of the fully automatic hp-adaptive Finite Element Method (hp-FEM). The self-adaptive hp-FEM algorithm expressed in terms of the graph grammar productions is analyzed by utilizing the Partitioning Communication Agglomeration Mapping (PCAM) model. The computational tasks are defined over a graph model of the computational mesh. It is done for all parts of the algorithm: the generation of an initial mesh, direct solver (including the integration and elimination of degrees of freedom), mesh transformations (including the h and p refinements), as well as the selection of the optimal refinements. The computation and communication complexities of the resulting parallel algorithms are analyzed. The paper is concluded with the sequence of massive parallel computations. >From the performed tests it implies that the code scales well up to 200 processors.

Słowa kluczowe

EN

large scale parallel computations; automatic hp adaptivity; finite element method; parallel solvers; 3D resistivity logging simulations

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 93, nr 4
• Strony: 435-457
• Opis fizyczny: Bibliogr. 42 poz., wykr.

Twórcy

autor

Paszyński, M.

• Department of Computer Science, Al.Mickiewicza 30, 30-059 Krakow, Poland

Bibliografia

• [1] Amestoy, P. R., Duff, I. S., L'Excellent, J.-Y.: Multifrontal parallel distributed symmetric and unsymmetric solvers, Comput. Methods in Appl. Mech. Eng., 184, 2000, 501-520.
• [2] Amestoy, P. R., Duff, I. S., Koster, J., L'Excellent, J.-Y.: A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM Journal of Matrix Analysis and Applications, 23(1), 2001, 15-41.
• [3] Amestoy, P. R., Guermouche, A., L'Excellent, J.-Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems, Parallel Computing, 32(2), 2005, 136-156
• [4] Babuśka, I., Guo, B.: The /ip-version of the finite element method, Part I: The basic approximation results, Comput. Mech., 1, 1986,21-41.
• [5] Babuśka, I., Guo, B.: The hp-version of the finite element method, Part II: General results and applications, Comput. Mech., 1, 1986, 203-220.
• [6] Banaś, K.: A Model for Parallel Adaptive Finite Element Software, Proc. of 15th International Conference on Domain Decomposition Methods, Freie Universitat Berlin, July 21-25, 2003.
• [7] Banaś, K., Plazek, J.: Parallel Iterative Solvers for the Finite Element Method, Proc. of 13th Polish Conference on Computer Methods in Mechanics, Vol.1, 1997, 115-120.
• [8] Bastian, P., Birken, K., Johannsen, K., Lang, S., Neuss, N., Rentz-Reichart, H.: UG - a flexible software toolbox for solving partial differential equations, Computing and Visualization in Science, 1(1), 1997, 27-40.
• [9] Cios, C: A Study of Non-Blocking Switch Networks, Interconnection Networsk for Parallel and Distributed Processing, Chuan-lin Wu and Tse-yun Feng (ed.) IEEE Computer Society Press, 1984, 126-144.
• [10] Bauer, A. C, Patra, A. K: Robust and Efficient Domain Decomposition Preconditioners for Adaptive hp Finite Element Approximations of Linear Elasticity with and without Discontinuous Coefficients, Int. J. Numer. Meth. Engng, 59(3), 2004, 337-364.
• [11] Demkowicz, L., Kurtz, J., Pardo, D., Paszyński, M., Rachowicz, W., Zdunek, A.: Computing with hp-Adaptive Finite Elements, Vol. II. Frontiers: Three Dimensional Elliptic and Maxwell Problems with Applications, Chapman & Hall/Crc Applied Mathematics & Nonlinear Science, 2007.
• [12] Duff, I.S., Reid, J.K: The multifrontal solution of indefinite sparse symmetric linear systems, ACM Trans, on Math. Soft., 9, 1983, 302-325.
• [13] Edwards, H. C: A Parallel Infrastructure for Scalable Adaptive Finite Element Methods and its application to Least Squares C-infinity Collocation, Dissertation, The University of Texas at Austin, 1997.
• [14] Foster, I.: Desiging and Building Parallel Programs, http://www-unix.mcs.aml.gov/dbpp
• [15] Giraud, L., Marocco, A., Rioual, J.-C: Iterative versus direct parallel substructuring methods in semiconductor device modelling, Numerical Linear Algebra with Applications, 12(1), 2005, 33-55.
• [16] Hwang, Y-S., Moon, B., Sharma, S. D., Ponnusamy, R., Das, R., Saltz, J. H.: Runtime and Language Support for Compiling Adaptive Irregular Programs on Distributed Memory Machines, Software - Practice and Experience, 25(6), 1995, 597-621.
• [17] Laszloffy, A., Long, J., Patra, A. K.: Simple data management, scheduling and solution strategies for managing the irregularities in parallel adaptive hp finite element simulations, Parallel Computing, 26, 2000, 1765-1788.
• [I8] Merlin, J., Baden, S., Fink, S., Chapman, B.: Multiple Data Parallelism with HPF and KeLP, Elsevier Science, 1998.
• [19] Paszyński, M.: On the Parallelization of Self-Adaptive /z/?-Finite Element Methods, Part I. Composite Programmable Graph Grammar Model, Fundamenta Informaticae 2009.
• [20] Paszyński, M.: Performace of Multi Level Parallel Direct Solver for hp FEM, Lecture Notes in Computer Science, 4967, 2007, 1303-1312.
• [21] Paszyński, M.: Agent Based'Hierarchical Parallelization of Complex Algorithms on the Example of hp Fintite Element Method, Lecture Notes in Computer Science, 4488, 2007, 912-919.
• [22] Paszyński, M.: The aplication of agents to parallel mesh refinements in domain decomposition based parallel fully automatic hp adaptive finite element codes, Lectures Notes in Computer Science, 3993, 2006, 751-758.
• [23] Paszyński, M., Demkowicz, L.: Parallel Fully Automatic hp-Adaptive 3D Finite Element Package, Engineering with Computers, 22(3-4), 2006,255-276.
• [24] Paszyński, M., Kurtz, J., Demkowicz, L.: Parallel Fully Automatic hp-Adaptive 2D Finite Element Package, Computer Methods in Applied Mechanics and Engineering, 195(7-8), 2006,711-741.
• [25] Paszyński, M., Paszyńska, A.: Graph transformations for modeling parallel /ip-adaptive FEM computations, Lecture Notes in Computer Science, 4967, 2007, 1313-1322.
• [26] Paszyński, M., Pardo, D., Torres-Verdin, C: Simulation of 3D Resistivity Logging Measurements with a Parallel Implementation of 2D hp-Adaptive Goal-Oriented Finite Element Method, Proc. of International Conference of Numerical Analysis and Applied Mathematics, 16-20 September, Corfu, Greece, 2007.
• [27] Pardo, D., Calo, V., Torres-Verdin, C, Nam, M.J.: Fourier Series Expansion in a Non-Orthogonal System of Coordinates for Simulation of 3D Borehole Resistivity Measurements. Part I: DC, Computer Methods in Applied Mechanics and Engineering, 197(1-3), 2008, 1906-1925.
• [28] Pardo, D.: Integration of hp-Adaptivity and Two-Grid Solver, PhD. Dissertation, The University of Texas at Austin, 2004.
• [29] Patra, A.K.: Parallel HP Adaptive Finite Element Analysis for Viscous Incompressible Fluid Problems, Dissertation, University of Texas at Austin, 1999.
• [30] Pike, G., Semenzato, L., Colella, P., Hilfinger, P.N.: Parallel 3D Adaptive Mesh Refinement in Titanium, Proc. of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, San Antonio, Texas, March, 1999, http://www.cs.berkeley.edu/projects/titanium
• [31] Plazek, J.: Scalable CFD Computations Using Message-Passing and Distributed Shared Memory Algorithms, Lecture Notes in Computer Science, 1908, 2000, 282-288.
• [32] Plazek, L: Implementation Issues of Computational Fluid Dynamics Algorithms on Parallel Computers, Lecture Notes in Computer Science, 1697,1999, 349-355.
• [33] Remade, J. F., Xiangrong, Li, Shephard, M.S., Flaherty, J.E.: Anisotropic Adaptive Simulations of Transient Flows using Discontinuous Galerkin Methods, Int. J. Numer. Meth. Engng., 00(1-6), 2000.
• [34] Stewart, J. R., Edwards, H. C: SIERRA Framework Version 3: h-Adaptivity Design and Use, SAND2002-4016, Albuquerque, NM, Sandia National Laboratories, 2002.
• [35] Edwards, H. C: SIERRA Framework Version 3: Core Services Theory and Design, SAND2002-3616, Albuquerque, NM, Sandia National Laboratories, 2002.
• [36] Edwards, H. C, Stewart, J. R., Zepper, J. D.: Mathematical Abstractions of the SIERRA Computational Mechanics Framework, Proc. of the 5th World Congress Comp. Mech., Vienna, Austria, 2002.
• [37] Edwards, H. C, Stewart, J. R.: SIERRA, A Software Environment for Developing Complex Multiphysics Applications, Computational Fluid and Solid Mechanics Proc. First MIT Conf., Cambridge MA, 2001.
• [38] Yelick, K., et al.: Titanium: A High-Performance Java Dialect, ACM 1998 Workshop on Java for High-Performance Network Computing, Stanford, California, February, 1998, http//www.cs.berkeley.edu/projects/titanium
• [39] Champion Cluster Users' Manual, http://www.tacc.utexas.edu/services/userguides/champion
• [40] Lonestar Cluster Users' Manual, http://www.tacc.utexas.edu/services/userguides/lonestar
• [41 ] A MUltifrontal Massively Parallel sparse direct Solver, http://www.enseeiht.fr/lima/apo/MUMPS/
• [42] Zoltan: Data-Management Services for Parallel Applications, http://www.cs.sandia.gov/Zoltan/