Parmmg data structures

Home

ParMmg Data Structures and how to perform a communication

Data structures

ParMmg 's main data structure is PMMG_ParMesh. For each processor there is one PMMG_ParMesh struct instance containing:

• a list of external communicators (1 external communicator per neighboring processor).
• one internal communicator.
• a list of groups, each group containing:
  • one mesh + associated solution.
  • 2 arrays (node2int_node_comm_index1 and node2int_node_comm_index2) allowing to recover the position of the nodes at group interface in the internal communicator.

The following image visualizes the PMMG_ParMesh struct:

Outline of the algorithm to initialize the data structures

We start with a sequential mesh (for the sake of simplicity we only consider the node numbering shown)

This is distributed to the processors as shown in the following picture

So far, each processor has 1 parmesh with one group, ie 1 mesh per processor.

The next step is to further subdivide each processors' group into subgroups of smaller size, if required. We want to have subgroups of roughly SUB_GROUP_MAX_SIZE or REMESHER_TARGET_MESH_SIZE which is the maximum size that is appropriate for the remesher. SOME MORE INFO PERHAPS HERE?

In our example:

• proc 0's group does not need to be subdivided into (sub)groups
• proc 1's group should be subdivided into two groups ((sub)group 0 and (sub)group 1)
• proc 2's group does not need to be subdivided into further (sub)groups
• proc 3's group should be subdivided into 3 groups ((sub)group 0, 1, 2)

Each group's mesh's node numbering starts from 1:

Algorithm to initialize the data structures

Describing how the data structures are initialized is easier done using the example above:

ParMesh structure on processor 0

In our example, processor 0 does not need to further subdivide its mesh. The mesh assigned to this processor is in only one group entity (there is only listgrp[0] while listgrp[1], listgrp[2], etc are out of bound accesses):

• parmesh->listgrp[0]: the list of groups is initialized as:

  • nitem_int_node_comm = 11 because our group shares 11 nodes with other groups, thus 11 nodes have to use the internal communicator to communicate data with other groups.
  • node2int_node_comm_index1 = {5,18,33,3,9,37,36,35,2,20,6} holds the 11 node indices shared with other groups.
  • node2int_node_comm_index2 = {0,1,2,3,4,5,6,7,8,9,10} store the position of these nodes in the internal communicator(index1), thus where to store and load node values/information from. Each node's position has been arbitrarily given THIS IS NOT VERY ACCURATE I THINK, I WILL REVISE IT LATER.

• parmesh->int_node_comm: the internal communicator, is initialized as :

  • nitem = 11 because there are 11 nodes shared with other groups.
  • int_node_comm->{intvalues,doublevalues} needs not be initialized in this example as it is only used to exchange data between groups. If and when needed it has to be allocated and of size nitem.

• parmesh->next_node_comm = 3: there are 3 external communicators to be initialized because proc 0 shares nodes with 3 other processors. The indices used to fill the parmesh->ext_node_comm[i]->int_comm_index arrays are those found in the parmesh->listgrp[0]->node2int_node_comm_index2:

  • parmesh->ext_node_comm[0] external communicator for processor 0 -> 1 communication :
    • nitem = 3 because proc 0 shares 3 nodes with proc 1
    • color_in = 0 local proc number for this external communicator is 0
    • color_out = 1 remote proc number for this external communicator is 1
    • int_comm_index = {10,9,8} because
      • node 6 which is shared with proc 1 is at position 10 in the internal comm
      • node 20 is at position 9
      • node 2 is at position 8
  • parmesh->ext_node_comm[1] external communicator for processor 0->2 communication:
    • nitem = 6 because proc 0 shares 6 nodes with proc 2
    • color_in = 0 local proc number for this external communicator is 0
    • color_out = 2 remote proc number for this external communicator is 2
    • int_comm_index = {8,7,6,5,4,3} because - node 2 shared with proc 2 is at position 8 in the internal comm - node 35 at potision 7 - etc.
  • parmesh->ext_node_comm[2] external communicator for processor 0->3 communication:
    • nitem = 4 because proc 0 shares 4 nodes with proc 3
    • color_in = 0 local proc number for this external communicator is 0
    • color_out = 3 remote proc number for this external communicator is 3
    • int_comm_index = {0,1,2,3} because - node 5 shared with proc 2 is at position 0 in the internal comm - etc.

Note on the ordering of the external communicator entries: The first of the two processor involved in a communicator arbitrarily sets the ordering orientation which however must be respected by the second processor. This means that the matching external communicator on the second proc (ie ext_node_comm[] on the second proc) must follow the same orientation that the first processor followed. For example : since we just chose an ordering for the external communicator 0->2 at processor 0, the external communicator 2->0 at processor 2 must follow the same ordering.

ParMesh structure on processor 1

• parmesh->listgrp the mesh on processor 1 is split between 2 groups which are initialized as:

  • parmesh->listrgrp[0] group 0:
    • nitem_int_node_comm=10 because group 0 shares 10 nodes with other groups
    • node2int_node_comm_index_1 = {3,12,2,25,4,11,17,21,18,22} the 10 indices shared with other groups
    • node2int_node_comm_index_2 = {0,1,2,3,4,5,6,7,8,9} communicator indices of the node2int_node_comm_index_1 (chosen arbitrarily)
  • parmesh->listrgrp[1] group 1:
    • nitem_int_node_comm=12 because group 1 has 12 nodes in common with other groups
    • node2int_node_comm_index_1 = {21,16,19,18,12,3,33,5,8,20,14,1} the 12 indices shared with other groups
    • node2int_node_comm_index_2 = {9,8,7,6,5,4,10,11,12,13,14,15} are the communicator indices. Note that for nodes that also exist in parmesh->listrgrp[0]->node2int_node_comm_index_1 we reuse the already assigned index number in parmesh->listrgrp[0]->node2int_node_comm_index_2 and we do not assign a new one.

• parmesh->int_node_comm->nitem = 16 as there are 16 unique nodes (ie not counting twice the nodes shared between the processors' local 2 groups) shared between the processor's two local groups and with groups on other processors.

• parmesh->next_node_comm=2 because processor 1 is adjacent to processors 0 and 2 thus there are 2 external communicators:

  • parmesh->ext_node_comm[0] external communicator for processor 1->0 communication:
    • nitem = 3 because proc 1 shares 3 nodes with proc 0
    • color_in = 1 local proc number for this external communicator is 1
    • color_out = 0 remote proc number for this external communicator is 0
    • int_comm_index = {0,1,2} because
      • node 3 shared with proc 0 is at position 0 in listrgrp[0]->node2int_node_comm_index_2 (internal comm)
      • node 12 is at the position 1
      • node 2 isat the position 2. Note that the boundary nodes are sorted in respect to the mirror communicator on proc 0 (parmesh->ext_node_comm[0]) where node 6 is listed first on proc 0 (=3 on proc 1), node 20 on proc 0 is listed second (=12 on proc 1) and node 2 is last (=2 on proc 1).
  • parmesh->ext_node_comm[1] external communicator for processor 1->2 communication:
    • nitem = 9 because proc 1 shares 9 nodes with proc 2
    • color_in = 1 local proc number for this external communicator is 1
    • color_out = 2 remoet proc number for this external communicator is 2
    • int_comm_index = {2,3,4,10,11,12,13,14,5} which are the positions in the internal communicator of nodes {2,25,4} of group 0 and then {13,5,8,20,14,1} of group 1.

ParMesh structure on processor 2

• parmesh->listrgrp[0] there is only one group on processor 2 and similarly to the already seen examples:

  • nitem_int_node_comm=25 as this group shares 25 nodes
  • node2int_node_comm_index_1 = {3,32,38,25,19,30,10,43,4,33,36,37,13,6,20,44,5,21,2,15,7,27,24,28,9} shared nodes
  • node2int_node_comm_index_2 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24} indices of shared nodes (arbitrarily chosen)

• parmesh->int_node_comm->nitem = 25 as 25 nodes are shared

• parmesh->next_node_comm=3 as processor 2 is adjacent to processors 0, 1 and 3 thus we have 3 external communicators:

  • parmesh->ext_node_comm[0] external communicator for processor 2->0 communication:
    • nitem = 6 proc2 shares 6 nodes with proc0
    • color_in = 2 local proc number for this external communicator is 2
    • color_out = 0 remote proc number for this external communicator is 0
    • int_comm_index = {8,9,10,11,12,13}
  • parmesh->ext_node_comm[1] external communicator for processor 2->1 communication:
    • • nitem = 9 proc2 shares 6 nodes with proc1
    • color_in = 2 local proc number for this external communicator is 2
    • color_out = 1 remote proc number for this external communicator is 1
    • int_comm_index = {8,7,6,5,4,3,2,1,0}
  • parmesh->ext_node_comm[2] external communicator for processor 2->3 communication:
    • nitem = 12 proc2 shares 6 nodes with proc3
    • color_in = 2 local proc number for this external communicator is 2
    • color_out = 3 remote proc number for this external communicator is 3
    • int_comm_index = {24,23,22,21,20,19,18,17,16,15,14,13}

ParMesh structure on processor 3

• parmesh->listrgrp the mesh on processor 3 is split in 3 groups:

  • parmesh->listrgrp[0] group0:
    • nitem_int_node_comm=12 as proc3/grp0 shares 12 nodes with proc 2 and proc3/grp0
    • node2int_node_comm_index_1 = {4,15,9,14,3,5,1,7,2,17,10,19} the shared nodes
    • node2int_node_comm_index_2 = {0,1,2,3,4,5,6,7,8,9,10,11} the indices of the shared nodes (arbitrarily chosen)
  • parmesh->listrgrp[1] group1:
    • nitem_int_node_comm=8 as proc3/group1 shares 8 nodes with proc3/grp0 and proc2/grp0
    • node2int_node_comm_index_1 = {13,9,12,2,18,8,5,3} the shared nodes
    • node2int_node_comm_index_2 = {11,10,9,8,12,13,14,15} the indices of the shared nodes (arbitrarily chosen)
  • parmesh->listrgrp[2] group2:
    • nitem_int_node_comm=9 as proc3/group2 shares 9 nodes with proc3/grp1,proc2/grp0 and proc0/grp0
    • node2int_node_comm_index_1 = {3,4,7,15,5,1,10,8,2} the shared nodes
    • node2int_node_comm_index_2 = {15,14,13,12,16,17,18,19,20} the indices of the shared nodes (arbitrarily chosen)

• parmesh->int_node_comm->nitem = 20 as there 20 nodes shared between the groups on proc3 and the between the groups on proc 3 and adjacent processors

• parmesh->next_node_comm=2 as proc3 is adjacent to processors 0 and 2 thus there are 2 external communicators:

  • parmesh->ext_node_comm[0] external communicator for processor 3->0 communication:
    • nitem = 4 as proc3 shares 4 nodes with proc 0
    • color_in = 3 local proc number for this external communicator is 3
    • color_out = 0 remote proc number for this external communicator is 0
    • int_comm_index = {20,19,18,17}
  • parmesh->ext_node_comm[1] external communicator for processor 3->2 communication:
    • nitem = 12 as proc3 shares 12 nodes with proc 2
    • color_in = 3 local proc number for this external communicator is 3
    • color_out = 2 remote proc number for this external communicator is 2
    • int_comm_index = {0,1,2,3,4,5,6,7,8,12,16,17}

Communication example

As an example of how these structures can be used, we will explain here how to perform a global reduction operation and find the minimum of the values at mesh nodes that are shared between groups.

1. parmesh->int_node_comm->doublevalue the double array that is used as the buffer has to be allocated for every parmesh instance (ie on each processor) to be of size parmesh->int_node_comm->nitem_int_node_nitem.
2. parmesh->int_node_comm->doublevalue is initialized to FLT_MAX.
3. On each group (i loop), we browse the node2int_node_comm_index1 array (k loop) and we store in int_node_comm->doublevalues[listgrp[i]->node2int_node_comm_index2[k]] the minimum between its previous value and the density value at node listgrp[i]->node2int_node_comm_index1[k]]:
   • int_node_comm->doublevalues[listgrp[i]->node2int_node_comm_index2[k]] = MIN(int_node_comm->doublevalues[listgrp[i]->node2int_node_comm_index2[k]], listgrp[i]->sol->m[listgrp[i]->node2int_node_comm_index1[k]]); At the end of this loop, the minimum is computed for a node shared between multiple groups on an unique processor.
4. We browse the external communicators (i loop):
   • We allocate an array of size ext_node_comm[i]->nitem (rtosend array of the external communicator). It will be use to share data from 1 processor to another one;
   • We fill this array: rtosend[k] = int_node_comm->doublevalues[ext_node_comm[i]->int_comm_index[k]];
   • We send this array to the proc ext_node_comm[i]->color_out;
   • We recieve the corresponding array from the proc color_out in the array rtorecv;
   • We travel through ext_node_comm[i]->int_comm_index (k loop) and compute: int_node_comm->doublevalues[ext_node_comm[i]->int_comm_index[k]] = MIN(int_node_comm->doublevalues[ext_node_comm[i]->int_comm_index[k]] , rtosend[k]);
5. We browse the internal communicator to update the values at group nodes (k loop): listgrp[i]->sol->m[listgrp[i]->node2int_node_comm_index1[k]] = int_node_comm->doublevalues[listgrp[i]->node2int_node_comm_index2[k]]

Home