Wyniki wyszukiwania - BazTech

1

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

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

Computer Science

|

2019

|

Vol. 20 (1)

27--55

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.

2

Hypergrammar-based parallel multi-frontal solver for grids with point singularities

Gurgul P., Paszyński M., Paszyńska A.

Computer Science

|

2015

|

Vol. 16 (1)

75--102

EN

This paper describes the application of hypergraph grammars to drive a linear computational cost solver for grids with point singularities. Such graph grammar productions are the first mathematical formalisms used to describe solver algorithms, and each indicates the smallest atomic task that can be executed in parallel, which is very useful in the case of parallel execution. In particular,the partial order of execution of graph grammar productions can be found, and the sets of independent graph grammar productions can be localized. They can be scheduled set by set into a shared memory parallel machine. The graph-grammar-based solver has been implemented with NVIDIA CUDA for GPU. Graph grammar productions are accompanied by numerical results for a 2D case. We show that our graph-grammar-based solver with a GPU accelerator is, by order of magnitude, faster than the state-of-the-art MUMPS solver.

3

Grammar based multi-frontal solver for isogeometric analysis in 1d

Kuźnik K., Paszyński M, Calo V.

Computer Science

|

2013

|

Vol. 14 (4)

589--613

EN

In this paper, we present a multi-frontal direct solver for one-dimensional iso-geometric finite element method. The solver implementation is based on the graph grammar (GG) model. The GG model allows us to express the entire solver algorithm, including generation of frontal matrices, merging, and eliminations as a set of basic undividable tasks called graph grammar productions. Having the solver algorithm expressed as GG productions, we can find the partial order of execution and create a dependency graph, allowing for scheduling of tasks into shared memory parallel machine. We focus on the implementation of the solver with NVIDIA CUDA on the graphic processing unit (GPU). The solver has been tested for linear, quadratic, cubic, and higher-order B-splines, resulting in logarithmic scalability.

4

Graph grammar based Petri net controlled direct solver algorithm

Szymczak A., Paszyński M., Pardo D.

Computer Science

|

2010

|

Vol. 11

65-79

EN

In this paper we present the Petri net setting the optimal order of elimination for direct solver working with hp refined finite finite element meshes. The computational mesh is represented by a graph, with graph vertices corresponding to finite element nodes. The direct solver algorithm is expressed as a sequence of graph grammar productions, attributing the graph vertices. The Petri net dictates the order of graph grammar productions, representing the execution of the solver algorithm over a graph representation of computational mesh. The presentation is concluded with numerical experiments performed for a model L-shape domain.

PL

W artykule przedstawiona została sieć Petriego sterująca kolejnością wykonania produkcji gramatyki grafowej reprezentującej wykonanie algorytmu solvera dokładnego na h adaptowanej siatce metody elementów skończonych. Siatka obliczeniowa przedstawiona została w postaci grafu, którego wierzchołki odpowiadają węzłom elementów skończonych. Algorytm solvera dokładnego wyrażony jest w postaci sekwencji produkcji gramatyki grafowej, atrybutujących wierzchołki grafu. Sieć Petriego określa kolejność wykonania produkcji gramatyki grafowej, reprezentujących wykonanie algorytmu solvera na grafowej reprezentacji siatki obliczeniowej. Artykuł podsumowuje eksperyment numeryczny dotyczący wykonania algorytmu solvera na problemie modelowym w kształcie litery L.