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 create an initial partitioning on a static part count.

Necessary Includes

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

  #include <engpar.h>
  #include <engpar_split.h>

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.

  int group = rank%split_factor!=0;
  int groupRank = rank%split_factor;
  MPI_Comm_split(T_Communicator,group,groupRank,&S_Communicator);

Note if the graph will already be partitioned to t parts and you are just getting a better initial partition, then MPI_COMM_WORLD can be used and this step can be skipped.

Once the communicator is setup. Each process must create an empty N-graph:

  agi::Ngraph* g = agi::createEmptyGraph();

Next, the split input structure will be created. 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:

  engpar::Input* input_split = engpar::createSplitInput(graph,S_Communicator,T_Communicator, isPartOfS,
                                                        split_factor, tolerance, edge_type);

This call will setup the internal communicator used in EnGPar so it must be done before the next steps.

After the input is created, the graph must be constructed on each of the original s parts. The other t-s parts should not construct anything beyond the initial createEmptyGraph() call. To construct the graph see this page

Splitting

Once the graph is constructed you can call the split routine:

  engpar::split(input_s,SPLIT_METHOD)

where the split method is a defined value in EnGPar. Currently the only method available is engpar::GLOBAL_PARMETIS. This call will split and partition the N-graph from s to t parts.

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

  engpar::evaluatePartition(graph);

Note that every process in the communicator must run this. 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