HYPERGRAPH GRAMMAR-BASED, MULTI-THREAD, MULTI-FRONTAL DIRECT SOLVER SCHEDULED IN PARALLEL GALOIS ENVIRONMENT
The two-dimensional grids with point and edge singularities in order to develop an efficient parallel hypergraph grammar-based multifrontal 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 multifrontal solver algorithm). We utilize a classical multi-frontal solver algorithm; the hypergraph grammar productions allow us to construct an efficient 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.
In this paper, we have analyzed the concurrency of the multi-frontal direct solver executed over model two-dimensional grids with point and edge singularity. We defined several hypergraph grammar productions over the hypergraph representation of the computational mesh. We analyzed the dependency relationship Hypergraph grammar-based, multi-thread, multi-frontal direct solver. . . 51 between the so-called tasks (defined as application of the production to the subhypergraph of the hypergraph representing the mesh) and constructed dependency graphs that are the equivalents of elimination trees. The hypergraph grammar productions were implemented and executed in the GALOIS system. A sequence of numerical experiments tested the scalability of the resulting multi-thread multi-frontal direct solver. We show that our GALOIS-based solver outperforms the MUMPS solver on the example of edge singularity. This is because MUMPS is not a task-based programming model solver. The utilization of the graph grammar for the expression of the solver algorithm allows for a better granularity in the computations, and there are more independent tasks to be scheduled for concurrent execution. The hypergraph grammar model allows for a better definition of the computational tasks related to hypergraph grammar productions. Since the hypergraph represents the computational mesh as a flat structure, it is easy to process the elements surrounding the singularities layer by layer. This in turn produces more independent tasks to be scheduled for concurrent execution. The hypergraph is just a “flat” data structure allowing for a simple construction of tasks surrounding the singularities and processing them level by level. The hypergraph grammar is just a model for expressing the solver algorithm. For more- -complicated grids, it requires some control algorithm that chooses the parts of the mesh where the productions will be executed and allow for the selection of sets of tasks by coloring the dependency graph. For the problem of the propagation of electromagnetic waves in formation layers, we employ the bisections weighted by an element size algorithm  to identify the tasks. These sets are then scheduled by the GALOIS using the available cores. Our future work will involve a generalization to three-dimensional grids.
American Journal of Computer Science and Engineering Survey