In this paper we consider an approach to the parallel partitioning of a arbitrary domain into connected subdomains without branching of internal boundaries. The Reeb graph is a simplified representation of the topology of the required domain. Algorithms are shown in this paper is a modification of the presented earlier algorithm of the formation of the plane Reeb graph. The algorithm for constructing the volume Reeb graph allows us to determine the internal topology of the domain. A new algorithm of the formation of the partitioning into subdomains without branching of internal boundaries is presented.
Algorithm 1: Formation of the Reeb graph
Data: T triangulation, consisting of 2-simplexes 2 T ; f level Morse function; nt number of available threads
Result: Reeb graph Ri(V; E) 1 while m < jV (T )j do 2 Partition nodes, according to coordinate z(v), where k = 1:::nt 3 Computing values of Morse function f (vk; m), for nodes in thread k 4 m m + 1 5 Form layers of Morse function f 6 while Pjm=1 jLSj ( )j < jT j do 7 Each layer we will distribute between available threads k = 0::nt forall vk do 8 LSm( ) = P LSmk( ) = f 2 Cl(LS( )) : 8v ; f (vk) > g 9
m = m + 1 10 foreach LS( m) do 11 Define 2-simplexes , containing vi foreach vi do 12 St(vi) = f 2 T jvi g link ¾star¿ 13 foreach vh 2 St do 14 Define link of 0-simplexes vh 15 if (Lk+(vh); Lk (vh); Lk (vh); Lk (vh)) then 16 vhc = vh 17 L(vhc) = l, где l = f1; 2; 3; 4; 5g link type of 0-simplexes 18 Find auxiliary nodes 19 foreach vic do 20 if L(vic) = 2 ^ L(vic+1) = 3 then 2212 vFici+n1d=novdiaesи vviaic+;v2ia+=1 voian+1s,uvraface vlicn, eL, (bveic+tw1)ee=n 0vic^aLn(dvicv+ic+1)1.= 0. 23 Renumbering nodes and suppose that i ! i + 2 24 Form and compile Reeb graph Ri(V; E) 2
Define a tree of connections between the critical nodes vc and construct the
Reeb graph R(V; E) with the edges e(vi; vj) 2 E for the triangulation T in R3 ,
consisting of 3-simplexes [
We will use the Morse level function f of different directions in some
coordinate planes. To determine the critical nodes vc and introduce the parameter
c(vc) corresponding to the number of edges outgoing from it, and taking the
value: 1 - one node; 2 - two nodes; 3 - branch; 0 is an auxiliary point va, which
with the nearest critical nodes vc form curvilinear arcs between the critical nodes
in the branching case [
Note by 0 the simplex vs, as the "auxiliary". In contrast to the previously implemented approach to the formation of the Reeb graph, this algorithm uses a volume triangulation of the domain T . 2 T ; nt number of available Algorithm 2: Computing volume Reeb graph
Data: T triangulation of 3-simplexes
threads.
Result: Volume Reeb graph R(V; E) 1 Compute graph by Algorithm 1 on result - 2d vertical Reeb graph R0(V; E) while m < jV (T )j do 2 for k = 1 to nt do 3 For each thread we assign a separate subgraph. 4 for i 6 n do 5 if va auxilary then 6 Form layer Si = f8v T j v z(va) of 3-simplexes
Si level layer for triangulation of 2-simplexes T 7 foreach Sn do 8 Compile Reeb graphs Rn+1(V; E) from Algorithm 1, separately for each Sn
Bypassing the Morse function f , one of the horizontal axes 9
Compile volume Reeb graph R(V; E), where R0::n(V; E) m = m + 1 R(V; E)
The volume Reeb graph R(V; E) is represented as a set of subgraphs that are constructed from the mesh (or cells) layers in different directions of traversal of the Morse function.
The general graph has the notation R0(V; E), the remaining subgraphs will have the notation Rn+1(V; E), where nt is the number of inner layers. 3
Domain Partitioning by Volume Reeb Graph Segmentation of subdomains into smaller fragments, which are blocks that represent split pants-decomposition. After obtaining the volume Reeb graph it is necessary to cut the domain T along the auxiliary nodes of the graph. The obtained layers S, which represent some contour of 2 or 3 simplexes, have some upper bound.
For each layer, the Morse function f with a different direction in the coordinate system is applied.
Algorithm 3: Partitioning of triangulation T on basis of Reeb graph Data: T triangulation of 3-simplexes 2 T ; R(V; E) Reeb graph Result: Set of layers fLSm( )g 1 We defince auxiliary vertices va = fva vc j c(vc) 0g 2 while vm < jV (R0)j do 3 Distribute each layer for auxilary nodes for available threads k = 0::nt 4 Looking for the nearest auxiliary nodes vmc for holes 5 Abstractly draw the cutting planes with respect to 4 vc along two axes 6 Define the layers LSmk( ) = 2 LSmk( ); 2= LSmk( ) S LSmk 1( ) 7 m m + 1
The resulting Reeb graph is associated with the main graph obtained in
Algorithm 1 and is positioned relative to the auxiliary nodes[
An example of how the algorithm works is shown in the figure 2. On the figure 2 (a) presented partition of "frame" without branching of inner boundaries with only 1 secant axis. This decomposition cannot produce many subdomains without branching. On the figure 2 (b) decomposition produced in two axis on a large number of subdomains.
The topology of this domain and the graph characterizing it allow us to divide
the domain into minimal independent parts.[
Computational experiments were carried out on three-dimensional unstructured meshes for multiply connected regions, differing in the topological type, surface geometry and the details of its description by the mesh itself.
On figure 4 was hidden some subdomains to present the difference between (a) partition without branching of inner boundaries and (b) with branching.
At the moment, by parallelizing the main cycles and passes through 2 and 3 simplexes of triangulation, the following estimates of computations are achieved. To measure estimate speed of algorithms in this paper we will use "speedup" S = TTnst . The speedup is defined as the ratio of the serial runtime of the best sequential algorithm for solving a problem Ts to the time taken by the parallel algorithm time Tnt to solve the same problem on nt processors, cores or threads.
The results of parallel algorithm speedup shown in Table 1 was computed only on main parts of algorithm. The main parts of algorithm is compute of volume Reeb graph and partition on subdomains. We didn’t measured parts of reading and writing mesh from external memory.
Source codes produced in C++ and parallel part made by using OpenMP. The algorithms considered in this paper make it possible to determine the features of the topology of various domains. The parallel version of algorithm was evaluated in O(K log2 K=n), where n is the number of available threads and K is a number of 0-simplexes of mesh. The estimation of the computational costs of the partitioning algorithm by the Reeb graph is O(L log2 L), where L is a sum of all simplexes of mesh. Algorithms showed sufficiently accurate results, which indicates the reliability of their application.
The considered partitions, due to the elimination of branching of inner boundaries, reduce the number and simplify the structure of exchanges between computational processes in parallel algorithms of mesh methods.
The layer-by-layer ordering of mesh cells in the subdomains of the unstructured mesh excludes conflicts in computing in the shared memory of computational systems with a hybrid architecture.
Partitioning into a given number of subdomains can be provided by recursively dividing the obtained subdomains of an unstructured mesh and combining the layers of cells that provide independent access to the data.