Improving an Existing Partition

Contents

Necessary Includes

Getting Started

Load Balancing

Necessary Includes

  #include <engpar.h>
  #include <engpar_input.h>

Getting Started

To use EnGPar's different algorithms, first the application must construct an N-graph from the user's data. To do this see Constructing the N-graph.

Load Balancing

The general way to run EnGPar's load balancing procedures is in the following form:

  // C++
  agi::Balancer* balancer = engpar::callToBalancer(...)
  balancer->balance(tolerance)

If the goal is to balance out the vertices of the graph one can use the following function to construct a balancer that does so:

  agi::Balancer* engpar::makeVtxBalancer(agi::Ngraph* g,
                                         double stepFactor=0.1,
                                         int verbosity=0);

The first argument, g, is the graph. The second, stepFactor, controls how much weight can be sent in a single iteration, and the final, verbosity, is the level of output provided by EnGPar; the higher the value the more output. Note that higher levels of verbosity can increase computation and communication costs.

To have more control over how EnGPar balances the graph a general balancer can be constructed with the following calls:

 engpar::Input* input = engpar::createDiffusiveInput(graph,stepFactor);
 //Add a priority for each dimension that needs balancing  
 input->addPriority(edge_type,imbalance_tol);
 agi::Balancer balancer = makeBalancer(input,verbosity);

The addPriority function allows you to specify what level each dimension should be balanced. Multiple calls to the function will cause EnGPar to balance the different dimensions in the order the calls are given. Passing an edge_type of -1 to the function will add the graph vertices as a priority.

When using the FORTRAN interface, graph vertices can be balanced with the following call:

  // FORTRAN
  call cengpar_balanceVertices(graph, tol, stepfactor, verbosity);

and the general balancer can be called as follows:

  // FORTRAN
  type(c_ptr) :: graph, diffusiveInput
  real(C_DOUBLE) :: tol, stepfactor
  integer :: verbosity
  ...
  tol=1.05       ! target a 5% imbalance
  stepfactor=0.1 ! a sane value to start with 
  verbosity=1    ! print some additional output
  diffusiveInput = cengpar_createDiffusiveInput(graph,stepFactor)
  call cengpar_addPriority(diffusiveInput,edge_type,tol)
  call cengpar_balance(diffusiveInput,verbosity);

For details of the FORTRAN interface see engpar.f90

Once the N-graph is balanced, the user data can be repartitioned using a partition map provided by the N-graph. To do this see Retrieving the Partition.

Examples

A FORTRAN example which loads one of our graph files, increases the part count via parmetis, and then runs the balancer:

https://github.com/SCOREC/EnGPar/blob/master/test/splitAndBalance.f90