Creating an Initial Partitioning

Contents

Design

Necessary Includes

Initial Setup

Splitting

Example

Design

EnGPar supports creating a partition from a lower part count, s, to a larger part count, t. We will refer to this operation as splitting. The split operation can also be used to repartition an existing partition on t parts.

Necessary Includes

For the following operations these c++ headers must be included:

  #include <engpar.h>
  #include <engpar_support.h>

FORTRAN users should use the following modules:

  use engpar
  use iso_c_binding

Initial Setup

To run the EnGPar split routine, some specific setup must be done to get correct results. First, the application must create an MPI Communicator that contains the processes which represent the initial ranks in one group and all other ranks in a different group. Below is an example of creating this communicator. split_factor is the expansion factor to go from s parts to t parts or more simply it is equal to t/s.

  // C++
  int group = rank%split_factor!=0;
  int groupRank = rank%split_factor;
  MPI_Comm_split(T_Communicator,group,groupRank,&S_Communicator);
  // FORTRAN
  group = (modulo(self,splitFactor) .ne. 0)
  groupRank = self%splitFactor
  call mpi_comm_split(MPI_COMM_WORLD, group, groupRank, newComm, ierr)

Note if the graph is already be partitioned to t parts and you want a better initial partition, then MPI_COMM_WORLD can be used as the S_Communicator and the above step can be skipped.

Once the communicator is setup. You can switch the internal communicator of EnGPar with this:

  // C++
  EnGPar_Switch_Comm(S_Communicator)
  // FORTRAN
  call cengpar_setftncommunicator(newComm)

Then each process must create the N-graph. For the parts in the S_Communicator, the graph should be constructed based on the user data. For more details on how to do this see Constructing the N-graph. The other t-s parts should create an empty N-graph like so:

  // C++
  agi::Ngraph* g = agi::createEmptyGraph();
  // FORTRAN
  type(c_ptr) :: graph
  graph = cengpar_createEmptyGraph()

Splitting

In order to split, first, an input structure needs to be created. There are two different inputs depending on if you are performing a local split or global split.

Global Split Input

This input takes in the N-graph, the s communicator, the t communicator, a flag which is true if the part is one of the original s parts, the imbalance tolerance for the graph vertices, and the edge type of the N-graph to be used. The edge_type is a number >=0 that represents which set of edges you want to use. The first set of edges you create will be 0, second will be 1, etc.

  // C++
  engpar::Input* input_split = engpar::createGlobalSplitInput(graph,S_Communicator,T_Communicator, isPartOfS, tolerance, edge_type);
  // FORTRAN
  type(c_ptr) :: splitInput
  splitInput = cengpar_createGlobalSplitInput(graph,S_Communicator,T_Communicator,isPartOfS,tolerance,edge_type)

Local Split Input

This input takes in the N-graph, the s communicator, the t communicator, a flag which is true if the part is one of the original s parts, the split_factor, the imbalance tolerance for the graph vertices, and the edge type of the N-graph to be used. The edge_type is a number >=0 that represents which set of edges you want to use. The first set of edges you create will be 0, second will be 1, etc.

  // C++
  engpar::Input* input_split = engpar::createLocalSplitInput(graph,S_Communicator,T_Communicator, isPartOfS, tolerance, ranks, edge_type);
  // FORTRAN
  type(c_ptr) :: splitInput
  splitInput = cengpar_createLocalSplitInput(graph,S_Communicator,T_Communicator,isPartOfS,tolerance,ranks, edge_type)

With the input structure created, you can call the split routine like so:

  // C++
  engpar::split(input_s,SPLIT_METHOD)
  // FORTRAN
  splitMethod = c_char_"GLOBAL_PARMETIS"//c_null_char
  call cengpar_split(splitInput,splitMethod);

where the split method is a defined value in EnGPar. Currently the only methods available are engpar::GLOBAL_PARMETIS and engpar::LOCAL_PARMETIS. Both methods use ParMETIS Part-KWAY to partition the graph from s to t parts. The GLOBAL method will partition all s parts to t parts while the LOCAL method will split each part in s to split_factor parts.

To use the LOCAL method, an extra argument must be passed into createLocalSplitInput which is an array of size split_factor. This array lists the ranks of the T_Communicator that each part will split into. For the example before, with a split_factor of 4, this would look like:

  agi::part_t* ranks[4] = {rank,rank+1,rank+2,rank+3}
  engpar::Input* input_split = engpar::createLocalSplitInput(graph,S_Communicator,T_Communicator, isPartOfS,4, tolerance, ranks, edge_type);

To output some partition quality statistics, you can run the following:

  // C++
  engpar::evaluatePartition(graph);
  // FORTRAN
  call cengpar_evaluatePartition(graph);

Note that this call is a collective operation that uses the active communicator. Before running the split this is the s communicator, but after the split it is the t communicator.

After running the split operation, the partition can be further improved by running a diffusive load balancer. To use this see Improving an Existing Partition.

Finally to get the new partition see Retrieving the Partition.

Example

An example of using the split routine can be found here C++ and here FORTRAN.