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_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 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. 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. 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.

  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 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