Parallel Partitioning Without Branching of Inner Boundaries for Arbitrary Domain? Ilyas Kadyrov1,2 , Sergey Kopysov1,2 , and Alexander Novikov1 1 Udmurt State University, Izhevsk, Russia slasheeck@gmail.com 2 Institute of Mechanics, Udmurt Federal Research Center UB RAS, Izhevsk, Russia Abstract. In this paper we consider an approach to the parallel parti- tioning of a arbitrary domain into connected subdomains without branch- ing 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 forma- tion 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. Keywords: Volume Reeb graph · Reeb graph · Unstructured mesh · Multiply connected domain · Topology definition · Mesh decomposition without branching 1 Reeb Graph Constructed by Surface Triangulation A Reeb graph is a topological data structure which is able to capture the topol- ogy of shapes. Considering a scalar-valued function defined on the domain of interest, the level sets of this function may consist of several components, which evolve while sweeping through the function values. The Reeb graph encodes the evolution of these level set components, which are sometimes referred to as con- tours in the literature, by collapsing each contour to a point. Normal Reeb graph is a 2-dimentional graph, based and constructed on surface mesh. Volume Reeb graph is an array of subgraphs, that perform 3-dimentional graph. Define a tree of connections between the critical nodes v c and construct the Reeb graph R(V, E) [1] with edges e(vi , vj ) ∈ E for the surface triangulation T in R3 , consisting of 2-simplexes (Algorithm 1). We will use the Morse level function f to determine the critical nodes v c and introduce the parameter c(v c ) corresponding to the number of edges outgoing from it and taking the value: 1 - one node ; 2 - two nodes; 3 - branch; 0 is the auxiliary nodes v a , which with the nearest critical v c forms curvilinear arcs between the critical nodes in the branching case [2]. ? This work is supported by the Russian Foundation for Basic Research (projects: 17-01-00402-a, 16-01-00129-a). Parallel Partitioning Without Branching for Arbitrary Domain 61 (a) (b) Fig. 1. The mesh and volume Reeb graph: (a) mesh (b) volume Reeb graph with critical and auxilary nodes Algorithm 1: Formation of the Reeb graph Data: T — triangulation, consisting of 2-simplexes σ ∈ T ; f —level Morse function; nt — number of available threads Result: Reeb graph Ri (V, E) 1 while m < |V (T )| 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 P  m 6 while j=1 |LSj (σ)| < |T | do 7 Each layer we will distribute between available threads k = 0..nt forall vk do P k 8 LSm (σ) = LSm (σ) = {σ ∈ Cl(LS(α)) : ∀v  σ, f (vk ) > α} 9 m=m+1 10 foreach LS(αm ) do 11 Define 2-simplexes σ, containing vi foreach vi do 12 St(vi ) = {σ ∈ T |vi  σ} link «star» 13 foreach vh ∈ 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 = {1, 2, 3, 4, 5}— link type of 0-simplexes 62 I. Kadyrov et al. 18 Find auxiliary nodes 19 foreach vic do 20 if L(vic ) = 2 ∧ L(vi+1 c ) = 3 then 21 Find nodes vi , vi+1 on surface line, between vic and vi+1 a a c . c a c a a c c c 22 vi+1 = vi и vi+2 = vi+1 , v ⊆ v , L(vi+1 ) = 0 ∧ L(vi+1 ) = 0. 23 Renumbering nodes and suppose that i → i + 2 24 Form and compile Reeb graph Ri (V, E) 2 The Volume Reeb Graph Define a tree of connections between the critical nodes v c and construct the Reeb graph R(V, E) with the edges e(vi , vj ) ∈ E for the triangulation T in R3 , consisting of 3-simplexes [3]. We will use the Morse level function f of different directions in some coor- dinate planes. To determine the critical nodes v c and introduce the parameter c(v c ) 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 v a , which with the nearest critical nodes v c form curvilinear arcs between the critical nodes in the branching case [4]. Note by 0 the simplex v s , 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 . Algorithm 2: Computing volume Reeb graph Data: T — triangulation of 3-simplexes σ ∈ T ; nt — number of available 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 < |V (T )| 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 v a — auxilary then 6 Form layer Si = {∀v ⊆ T | v  z(v a ) 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) ⊆ R(V, E) m=m+1 Parallel Partitioning Without Branching for Arbitrary Domain 63 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 rep- resent 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 ob- tained 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 coordi- nate system is applied. Algorithm 3: Partitioning of triangulation T on basis of Reeb graph Data: T — triangulation of 3-simplexes σ ∈ T ; R(V, E) — Reeb graph Result: Set of layers {LSm (σ)} 1 We define auxiliary vertices v a = {v a ⊆ v c | c(v c ) ≡ 0} c 2 while vm < |V (R0 )| do 3 Distribute each layer for auxilary nodes for available threads k = 0..nt c 4 Looking for the nearest auxiliary nodes vm for holes 5 Abstractly draw the cutting planes with respect to 4 v c along two axes k (σ) = σ − ∈ LSm k k k S 6 Define the layers LSm (σ), σ ∈ / LSm (σ) LSm−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[6]. Thus we obtain a volume connected graph which characterize the complete topology of the given domain. 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.[5] The partitioning algorithm uses the Reeb graph for each layer, which makes it possible to implement a large number of algorithms. 4 Numerical Experiments 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. 64 I. Kadyrov et al. (a) (b) Fig. 2. Partition on basis of Volume Reeb graph: (a) without branching of inner bound- aries; (b) with branching (a) (b) (c) Fig. 3. The partitions: (a) without branching of inner boundaries; (b) partition with branching to 10 subdomains and (c) partition, made by METIS algorithm Figure 3 presents us result of decomposition by volume Reeb graph and algorithm METIS. Decomposition produced by algorithm of volume Reeb graph on figure 3 (a), (b) uses topology of arbitary domain. Decomposition by the METIS algorithm partitions the domain based on cells connectivity, but does not limit the number of adjacent subdomains. 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 = TTns . The speedup is defined as the ratio of the serial runtime of the best t Parallel Partitioning Without Branching for Arbitrary Domain 65 (a) (b) Fig. 4. Hidden layers in partition of mesh: (a) without branching of inner boundaries; (b) with branching 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. Table 1. Speedup by parallelizing of partitioning with Reeb graph Threads 623552 nodes 1123102 nodes 7620096 nodes Intel Xeon E5-1650 Six-core 12-threads 16 GB RAM Ts , sec 4103 6591 37532 4 (2 cores) 2,78 2,84 2,90 6 3,21 3,25 3,29 12 5,28 5,32 5,35 Intel i5-4460 Quad-core 4-threads 8 GB RAM Ts , s 3705 5772 33718 2 1,78 1,81 1,82 4 3,69 3,65 3,51 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 fea- tures 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 66 I. Kadyrov et al. 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 bound- aries, reduce the number and simplify the structure of exchanges between com- putational processes in parallel algorithms of mesh methods. The layer-by-layer ordering of mesh cells in the subdomains of the unstruc- tured mesh excludes conflicts in computing in the shared memory of computa- tional systems with a hybrid architecture. Partitioning into a given number of subdomains can be provided by recur- sively dividing the obtained subdomains of an unstructured mesh and combining the layers of cells that provide independent access to the data. References 1. Korneev V., Langer U. 2004 Encyclopedia of Computational Mechanics pp 617-647 2. Kadyrov I. R., Kopysov S. P., Novikov A. K. 2018 Partitioning of Triangulated Mul- tiply Connected Domain into Subdomains Without Branching of Inner Boudaries (Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki) 160 [In print] 3. Kopysov S. P., Kuzmin I. M., Nedozhogin N. S., Novikov A. K. 2012 Parallel Al- gorithms for Constructing and Solving the Schur Complement on Graphics Accel- erators (Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki) 154 (3) pp 202-215. 4. Martynenko S. I. 2008 Formalization of Computations at Numerical Solution of Boundary Value Problems (Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki) 150 (1) pp 76-90 5. Postnikov M. M. 1971 Introduction in Morse Theory (Moscow: Nauka) p 568 6. Zimovnov A. V., Mestetskiy L. M. 2016 On algorithm of curve-skeleton extrac- tion for 3D model based on planar projections (Vestn. TvGU Seriya: Prikladnaya matematika) (3) pp 67-83 7. Hajij M., Dey T., Li Х. 2016 Segmenting a surface mesh into pants using Morse theory (Graphical Models) 88 pp 12-21 8. Mestetskiy L. M. 2009 Continuous morphology of binary images: figures, skeletons and circulars (Moscow: Fizmatlit) p 288 9. Harvey W., Wang Y., Wenger R. 2010 A Randomized O. (M log M) Time Algo- rithm for Computing Reeb Graphs of Arbitary Simplical Complexes (USA: SoCG ’10) p 267-276 10. Novikov A. K., Piminova N. K., Kopysov S. P., Sagdeeva Y. A. 2016 Layer-by- layer ordering in parallel finite composition on shared-memory multiprocessors (IOP Conf. Ser.: Mater. Sci. Eng.) 158 (1)