Hypergraph grammar based multi-thread multi-frontal direct solver with Galois scheduler

• Autorzy: Jopek Konrad , Paszyński Maciej , Paszyńska Anna , Hassan Muhammad Amber , Pingali Keshav

Identyfikatory

DOI

10.7494/csci.2019.20.1.3010

• Języki publikacji: EN

Abstrakty

EN

In this paper, we analyze two-dimensional grids with point and edge singularities in order to develop an eficient parallel hypergraph grammar-based multi- frontal direct solver algorithm. We express these grids by a hypergraph. For these meshes, we define a sequence of hypergraph grammar productions expressing the construction of frontal matrices, eliminating fully assembled nodes, merging the resulting Schur complements, and repeating the process of elimination and merging until a single frontal matrix remains. The dependency relationship between hypergraph grammar productions is analyzed, and a dependency graph is plotted (which is equivalent to the elimination tree of a multi- frontal solver algorithm). We utilize a classical multi-frontal solver algorithm; the hypergraph grammar productions allow us to construct an eficient elimination tree based on the graph representation of the computational mesh (not the global matrix itself). The hypergraph grammar productions are assigned to nodes on a dependency graph, and they are implemented as tasks in the GALOIS parallel environment and scheduled according to the developed dependency graph over the shared memory parallel machine. We show that our hypergraph grammar-based solver outperforms the parallel MUMPS solver.

Słowa kluczowe

EN

graph grammar; direct solver; h adaptive finite element method; GALOIS

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2019
• Tom: Vol. 20 (1)
• Strony: 27--55
• Opis fizyczny: Bibliogr. 39 poz., rys., tab.

Twórcy

autor

Jopek Konrad

• AGH University of Science and Technology, Department of Computer Sciences, Krakow, Poland

autor

Paszyński Maciej

• AGH University of Science and Technology, Department of Computer Sciences, Krakow, Polan

autor

Paszyńska Anna

• Jagiellonian University, Krakow, Poland

autor

Hassan Muhammad Amber

• The University of Texas at Austin, Institute for Computational and Engineering Sciences, USA

autor

Pingali Keshav

• The University of Texas at Austin, Institute for Computational and Engineering Sciences, USA

Bibliografia

• [1] AbouEisha H., Moshkov M., Calo V.M., Paszyński M., Goik D., Jopek K.: Dynamic programming algorithm for generation of optimal elimination trees for multi-frontal direct solver over h-refined grids, Procedia Computer Science, vol. 29, pp. 947-959, 2014.
• [2] Amestoy P.R., Davis T.A., Du I.S.: An Approximate Minimum Degree Or- dering Algorithm, SIAM Journal of Matrix Analysis & Application, vol. 17(4), pp. 886-905, 1996.
• [3] Amestoy P.R., Du_ I.S., L'Excellent J.Y.: Multifrontal parallel distributed symmetric and unsymmetric solvers, Computer Methods in Applied Mechanics and Engineering, vol. 184(2), pp. 501-520, 2000.
• [4] Amestoy P.R., Duff I.S., L'Excellent J.Y., Koster J.: A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM Journal on Matrix Analysis and Applications, vol. 23(1), pp. 15-41, 2001.
• [5] Amestoy P.R., Guermouche A., L'Excellent J.Y., Pralet S.: Hybrid scheduling for the parallel solution of linear systems, Parallel Computing, vol. 32(2), pp. 136-156, 2006.
• [6] Avdeev D.B., Kuvshinov A.V., Pankratov O.V., Newman G.A.: Three-dimensional induction logging problems, Part I: An integral equation solution and model comparisons, Geophysics, vol. 67(2), pp. 413-426, 2002.
• [7] Davydycheva S., Druskin V., Habashy T.: An eficient finite-difference scheme for electromagnetic logging in 3D anisotropic inhomogeneous media, Geophysics, vol. 68(5), pp. 1525-1536, 2003.
• [8] Demkowicz L.: Computing with hp-Adaptive Finite Elements, Vol. I. One and Two Dimensional Elliptic and Maxwell Problems, Chapman and Hall/CRC Ap- plied Mathematics and Nonlinear Science, 2006.
• [9] Diekert V., Rozenberg G.: The book of traces, World Scientific Publishing, 1995.
• [10] Druskin V.L., Knizhnerman L.A., Lee P.: New spectral Lanczos decomposition method for induction modeling in arbitrary 3-D geometry, Geophysics, vol. 64(3), pp. 701-706, 1999.
• [11] Duff I.S., Reid J.K.: The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software, vol. 9, pp. 302-325, 1983.
• [12] Duff I.S., Reid J.K.: The Multifrontal Solution of Unsymmetric Sets of Linear Equations, SIAM Journal on Scientific and Statistical Computing, vol. 5, pp. 633-641, 1984.
• [13] Geng P., Oden J., van de Geijn R.: A parallel multifrontal algorithm and its implementation, Computer Methods in Applied Mechanics and Engineering, vol. 149(1), pp. 289-301, 1997.
• [14] Goik D., Jopek K., Paszyński M., Lenharth A., Nguyen D., Pingali K.: Graph Grammar based Multi-thread Multi-frontal Direct Solver with Galois Scheduler, Procedia Computer Science, vol. 29, pp. 960-969, 2014.
• [15] Habel A., Kreowski H.J.: May we introduce to you: Hyperedge replacement. In: Ehrig H., Nagl M., Rozenberg G., Rosenfeld A. (eds.), Graph-Grammars and Their Application to Computer Science. Graph Grammars 1986, Lecture Notes in Computer Science, vol. 291, pp. 15-26, Springer, Berlin, Heidelberg, 1987
• [16] Habel A., Kreowski H.J.: Some Structural Aspects of Hypergraph Languages Generated by Hyperedge Replacement. In: Brandenburg F.J., Vidal-Naquet G., Wirsing M. (eds.), STACS 87. STACS 1987, Lecture Notes in Computer Science, vol. 247, pp. 207-219, Springer, Berlin, Heidelberg, 1987.
• [17] Karypis G., Kumar V.: MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 4.0, 1998. http://umn.edu/home/karypis.
• [18] Liu J.: The role of elimination trees in sparse factorization, SIAM Journal of Matrix Analysis and Applications, vol. 11(1), pp. 134-172, 1990.
• [19] Newman G.A., Alumbaugh D.L.: Three-dimensional induction logging problems, Part 2: A finite-difference solution, Geophysics, vol. 67(2), pp. 484-491, 2002.
• [20] Obrok P., Pierzchala P., Szymczak A., Paszyński M.: Graph grammar-based multi-thread multi-frontal parallel solver with trace theory-based scheduler, Procedia Computer Science, vol. 1(1), pp. 1993-2001, 2010
• [21] Pardo D., Calo V., Torres-Verdin C., Nam M.: Fourier series expansion in a non- -orthogonal system of coordinates for the simulation of 3D-DC borehole resis- tivity measurements, Computer Methods in Applied Mechanics and Engineering, vol. 197(21), pp. 1906-1925, 2008.
• [22] Pardo D., Demkowicz L., Torres-Verdin C., Paszyński M.: A self-adaptive goal-oriented hp-finite element method with electromagnetic applications. Part II: Electrodynamics, Computer Methods in Applied Mechanics and Engineering, vol. 196(37), pp. 3585-3597, 2007.
• [23] Pardo D., Demkowicz L., Torres-Verdin C., Paszynski M.: Two-Dimensional High-Accuracy Simulation of Resistivity Logging-While-Drilling (LWD) Measure- ments Using a Self-Adaptive Goal-Oriented hp-Finite Element Method, SIAM Journal on Applied Mathematics, vol. 66(6), pp. 2085-2106, 2006.
• [24] Pardo D., Torres-Verdin C., Paszynski M.: Simulations of 3D DC borehole resistivity measurements with a goal-oriented hp finite-element method. Part II: through-casing resistivity instruments, Computational Geosciences, vol. 12(1), pp. 83-89, 2008.
• [25] Pardo D., Torres-Verdin C., Demkowicz L.F.: Simulation of multifrequency bore- hole resistivity measurements through metal casing using a goal-oriented hp finite-element method, IEEE Transactions on Geoscience and Remote Sensing, vol. 44(8), pp. 2125-2134, 2006.
• [26] Paszyńska A., Grabska E., Paszyński M.: A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part I, Fundamenta Informaticae, vol. 114, pp. 149-182, 2012.
• [27] Paszyńska A., Grabska E., Paszyński M.: A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part II, Fundamenta Informaticae, vol. 114, pp. 183-201, 2012.
• [28] Paszyńska A., Paszyński M., Grabska E.: Graph Transformations for Modeling hp-Adaptive Finite Element Method with Mixed Triangular and Rectangular Elements. In: Allen G., Nabrzyski J., Seidel E., van Albada G.D., Dongarra J., Sloot P.M.A. (eds.), Computational Science { ICCS 2009. ICCS 2009, Lecture Notes in Computer Science, vol. 5545, pp. 875-884, Springer, Berlin, Heidelberg, 2009.
• [29] Paszyńska A., Paszyński M., Jopek K., Woźniak M., Goik D., Gurgul P., AbouEisha P., Moshkov M., Calo V.M., Lenharth A., Nguyen D., Pingali K.: Quasi-Optimal Elimination Trees for 2D Grids with Singularities, Scientific Programming, vol. 2015, pp. 1-18, 2015.
• [30] Paszyński M.: On the Parallelization of Self-Adaptive hp-Finite Element Methods, Part I. Composite Programmable Graph Grammar Model, Fundamenta Informaticae, vol. 93(4), pp. 411-434, 2009.
• [31] Paszyński M.: On the Parallelization of Self-Adaptive hp-Finite Element Methods, Part II. Partitioning Communication Agglomeration Mapping (PCAM) Analysis, Fundamenta Informaticae, vol. 4(93), pp. 435-457, 2009.
• [32] Paszyński M., Schaefer R.: Graph grammar-driven parallel partial differential equation solver, Concurrency and Computation Practice and Experience, vol. 22, pp. 1063-1097, 2010.
• [33] Paszyński M., Demkowicz L., Pardo D.: Verification of goal-oriented HP-adaptivity, Computers & Mathematics with Applications, vol. 50(8), pp. 1395-1404, 2005.
• [34] Pingali K., Nguyen D., Kulkarni M., Burtscher M., Hassaan M.A., Kaleem R., Lee T.H., Lenharth A., Manevich R., Mendez-Lojo M., Prountzos D., Sui X.: The Tao of Parallelism in Algorithms, SIGPLAN Not., vol. 46(6), pp. 12-25, 2011.
• [35] Schmitz P.G., Ying L.: A fast direct solver for elliptic problems on general meshes in 2D, Journal of Computational Physics, vol. 231(4), pp. 1314-1338, 2012.
• [36] Ślusarczyk G., Paszyńska A.: Hypergraph Grammars in hp-adaptive Finite Element Method, Procedia Computer Science, vol. 18, pp. 1545-1554, 2013.
• [37] Wang T., Fang S.: 3-D electromagnetic anisotropy modeling using finite differences, Geophysics, vol. 66(5), pp. 1386-1398, 2001.
• [38] Wang T., Signorelli J.: Finite-difference modeling of electromagnetic tool response for logging while drilling, In: Geophysics, vol. 69(1), pp. 152-160, 2004.
• [39] Zhang J., Mackie R.L., Madden T.R.: 3-D resistivity forward modeling and in-version using conjugate gradients, Geophysics, vol. 60(5), pp. 1313-1325, 1995.