Zoltan User's Guide: Load-Balancing Algorithms and Parameters

Zoltan User's Guide | Next | Previous

Load-Balancing Algorithms and Parameters

The following dynamic load-balancing algorithms are currently included in the Zoltan library:

Simple Partitioners for Testing
Block Partitioning (BLOCK)
Cyclic Partitioning (CYCLIC)
Random Partitioning (RANDOM)
Geometric (Coordinate-based) Partitioners
Recursive Coordinate Bisection (RCB)
Recursive Inertial Bisection (RIB)
Hilbert Space-Filling Curve Partitioning (HSFC)
Refinement Tree Based Partitioning (REFTREE)
Hypergraph Partitioning, Repartitioning and Refinement (HYPERGRAPH)
PHG
PaToH
Graph Partitioning and Repartitioning (GRAPH)
PHG
ParMETIS
Scotch
Hybrid Hierarchical Partitioning (HIER)

The parenthetical string is the parameter value for LB_METHOD parameter; the parameter is set through a call to Zoltan_Set_Param.

For further analysis and discussion of some of the algorithms, see [Hendrickson and Devine].

Load-Balancing Parameters

While the overall behavior of Zoltan is controlled by general Zoltan parameters, the behavior of each load-balancing method is controlled by parameters specific to partitioning which are also set by calls to Zoltan_Set_Param. Many of these parameters are specific to individual partitioning algorithms, and are listed in the descriptions of the individual algorithms. However, several have meaning across multiple partitioning algorithms. These load-balancing parameters are described below. Unless indicated otherwise, these parameters apply to both Zoltan_LB_Partition and Zoltan_LB_Balance.

Parameters:
LB_METHOD	The load-balancing algorithm used by Zoltan is specified by this parameter. Valid values are BLOCK (for block partitioning), RANDOM (for random partitioning), RCB (for recursive coordinate bisection), RIB (for recursive inertial bisection), HSFC (for Hilbert space-filling curve partitioning), REFTREE (for refinement tree based partitioning) GRAPH (to choose from collection of methods for graphs), HYPERGRAPH (to choose from a collection of methods for hypergraphs), HIER (for hybrid hierarchical partitioning) NONE (for no load balancing).
LB_APPROACH	The desired load balancing approach. Only LB_METHOD = HYPERGRAPH or GRAPH uses the LB_APPROACH parameter. Valid values are PARTITION (Partition "from scratch," not taking into account the current data distribution; this option is recommended for static load balancing.) REPARTITION (Partition but take into account current data distribution to keep data migration low; this option is recommended for dynamic load balancing.) REFINE (Quickly improve the current data distribution.)
NUM_GLOBAL_PARTS	The total number of parts to be generated by a call to Zoltan_LB_Partition. Integer values greater than zero are accepted. Not valid for Zoltan_LB_Balance.
NUM_LOCAL_PARTS	The number of parts to be generated on this processor by a call to Zoltan_LB_Partition. Integer values greater than or equal to zero are accepted. Not valid for Zoltan_LB_Balance. If any processor sets this parameter, NUM_LOCAL_PARTS is assumed to be zero on processors not setting this parameter.
RETURN_LISTS	The lists returned by calls to Zoltan_LB_Partition or Zoltan_LB_Balance. Valid values are "IMPORT", to return only information about objects to be imported to a processor "EXPORT", to return only information about objects to be exported from a processor "ALL", or "IMPORT AND EXPORT" (or any string with both "IMPORT" and "EXPORT" in it) to return both import and export information "PARTS" (or "PART ASSIGNMENT" or any string with "PART" in it) to return the new process and part assignment of every local object, including those not being exported. "NONE", to return neither import nor export information
REMAP	Within Zoltan_LB_Partition or Zoltan_LB_Balance, renumber parts to maximize overlap between the old decomposition and the new decomposition (to reduce data movement from old to new decompositions). Valid values are "0" (no remapping) or "1" (remapping). Part assignments from ZOLTAN_PART_MULTI_FN or ZOLTAN_PART_FN query functions can be used in remapping if provided; otherwise, processor numbers are used as part numbers. Requests for remapping are ignored when, in the new decomposition, a part is spread across multiple processors or part sizes are specified using Zoltan_LB_Set_Part_Sizes.
IMBALANCE_TOL	The amount of load imbalance the partitioning algorithm should deem acceptable. The load on each processor is computed as the sum of the weights of objects it is assigned. The imbalance is then computed as the maximum load divided by the average load. An value for IMBALANCE_TOL of 1.2 indicates that 20% imbalance is OK; that is, the maximum over the average shouldn't exceed 1.2.
MIGRATE_ONLY_PROC_CHANGES	If this value is set to TRUE (non-zero), Zoltan's migration functions will migrate only objects moving to new processors. They will not migrate objects for which only the part number has changed; the objects' processor numbers must change as well. If this value is set to FALSE (zero), Zoltan's migration functions will migrate all objects with new part or processor assignments.
AUTO_MIGRATE	If this value is set to TRUE (non-zero), Zoltan will automatically perform the data migration during calls to Zoltan_LB_Partition or Zoltan_LB_Balance. A full discussion of automatic migration can be found in the description of the migration interface functions.
Default Values:
	LB_METHOD = RCB
	LB_APPROACH = REPARTITION
	NUM_GLOBAL_PARTS = Number of processors specified in Zoltan_Create.
	NUM_LOCAL_PARTS = 1
	RETURN_LISTS = ALL
	REMAP = 1
	IMBALANCE_TOL = 1.1
	MIGRATE_ONLY_PROC_CHANGES = 1
	AUTO_MIGRATE = FALSE

[Table of Contents | Next: Simple Partitioners for Testing | Previous: Zoltan Parameters and Output Levels | Privacy and Security]