Zoltan User's Guide  |  Next  |  Previous

Load-Balancing Functions

The following functions are the load-balancing interface functions in the Zoltan library; their descriptions are included below.
Zoltan_LB_Partition
Zoltan_LB_Set_Part_Sizes
Zoltan_LB_Eval
Zoltan_LB_Free_Part
For backward compatibility with previous versions of Zoltan, the following functions are also maintained. These functions are applicable only when the number of parts to be generated is equal to the number of processors on which the parts are computed. That is, these functions assume "parts" and "processors" are synonymous.
Zoltan_LB_Balance
Zoltan_LB_Free_Data
Descriptions of algorithm-specific interface functions are included with the documentation of their associated algorithms. Algorithm-specific functions include:
Zoltan_RCB_Box


C: int Zoltan_LB_Partition (
      struct Zoltan_Struct *zz,
      int *changes,
      int *num_gid_entries,
      int *num_lid_entries,
      int *num_import
      ZOLTAN_ID_PTR *import_global_ids,
      ZOLTAN_ID_PTR *import_local_ids,
      int **import_procs,
      int **import_to_part,
      int *num_export,
      ZOLTAN_ID_PTR *export_global_ids,
      ZOLTAN_ID_PTR *export_local_ids,
      int **export_procs,
      int **export_to_part);
FORTRAN: FUNCTION Zoltan_LB_Partition(zz, changes, num_gid_entries, num_lid_entries, num_import, import_global_ids, import_local_ids, import_procs, import_to_part, num_export, export_global_ids, export_local_ids, export_procs, export_to_part
INTEGER(Zoltan_INT) :: Zoltan_LB_Partition 
TYPE(Zoltan_Struct), INTENT(IN) :: zz 
LOGICAL, INTENT(OUT) :: changes 
INTEGER(Zoltan_INT), INTENT(OUT) :: num_gid_entries, num_lid_entries
INTEGER(Zoltan_INT), INTENT(OUT) :: num_import, num_export 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_global_ids, export_global_ids 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_local_ids, export_local_ids 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_procs, export_procs
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_to_part, export_to_part
C++: int Zoltan::LB_Partition (
      int &changes,
      int &num_gid_entries,
      int &num_lid_entries,
      int &num_import
      ZOLTAN_ID_PTR &import_global_ids,
      ZOLTAN_ID_PTR &import_local_ids,
      int * &import_procs,
      int * &import_to_part,
      int &num_export,
      ZOLTAN_ID_PTR &export_global_ids,
      ZOLTAN_ID_PTR &export_local_ids,
      int * &export_procs,
      int * &export_to_part);

Zoltan_LB_Partition invokes the load-balancing routine specified by the LB_METHOD parameter. The number of parts it generates is specified by the NUM_GLOBAL_PARTS or NUM_LOCAL_PARTS parameters. Results of the partitioning are returned in lists of objects to be imported into and exported from parts on this processor. Objects are included in these lists if either their part assignment or their processor assignment is changed by the new decomposition. If an application requests multiple parts on a single processor, these lists may include objects whose part assignment is changing, but whose processor assignment is unchanged.

Returned arrays are allocated in Zoltan; applications should not allocate these arrays before calling Zoltan_LB_Partition. The arrays are later freed through calls to Zoltan_LB_Free_Part.
 
Arguments:
    zz Pointer to the Zoltan structure, created by Zoltan_Create, to be used in this invocation of the load-balancing routine.
    changes Set to 1 or .TRUE. if the decomposition was changed by the load-balancing method; 0 or .FALSE. otherwise.
    num_gid_entries Upon return, the number of array entries used to describe a single global ID.  This value is the maximum value over all processors of the parameter NUM_GID_ENTRIES.
    num_lid_entries Upon return, the number of array entries used to describe a single local ID.  This value is the maximum value over all processors of the parameter NUM_LID_ENTRIES.
    num_import  Upon return, the number of objects that are newly assigned to this processor or to parts on this processor (i.e., the number of objects being imported from different parts to parts on this processor). If the value returned is -1, no import information has been returned and all import arrays below are NULL. (The RETURN_LISTS parameter determines whether import lists are returned).
    import_global_ids Upon return, an array of num_import global IDs of objects to be imported to parts on this processor.
(size = num_import * num_gid_entries)
    import_local_ids Upon return, an array of  num_import local IDs of objects to be imported to parts on this processor.
(size = num_import * num_lid_entries)
    import_procs Upon return, an array of size num_import listing the processor IDs of the processors that owned the imported objects in the previous decomposition (i.e., the source processors).
    import_to_part Upon return, an array of size num_import listing the parts to which the imported objects are being imported.
    num_export Upon return, this value of this count and the following lists depends on the value of the RETURN_LISTS parameter:
  • It is the count of objects on this processor that are newly assigned to other processors or to other parts on this processor, if RETURN_LISTS is "EXPORT" or "EXPORT AND IMPORT".
  • It is the count of all objects on this processor, if RETURN_LISTS is "PARTS" (or "PART ASSIGNMENTS").
  • It is -1 if the value of RETURN_LISTS indicates that either no lists are to be returned, or only import lists are to be returned. If the value returned is -1, no export information has been returned and all export arrays below are NULL .
    export_global_ids Upon return, an array of num_export global IDs of objects to be exported from parts on this processor (if RETURN_LISTS is equal to "EXPORT" or "EXPORT AND IMPORT"), or an array of num_export global IDs for every object on this processor (if RETURN_LISTS is equal to "PARTS" or "PART ASSIGNMENTS"), . 
(size = num_export * num_gid_entries)
    export_local_ids Upon return, an array of num_export local IDs associated with the global IDs returned in export_global_ids
(size = num_export * num_lid_entries)
    export_procs Upon return, an array of size num_export listing the processor ID of the processor to which each object is now assigned (i.e., the destination processor). If RETURN_LISTS is equal to "PARTS" or "PART ASSIGNMENTS", this list includes all objects, otherwise it only includes the objects which are moving to a new part and/or process.
    export_to_part Upon return, an array of size num_export listing the parts to which the objects are assigned under the new partition.
Returned Value:
    int Error code.



C: int Zoltan_LB_Set_Part_Sizes (
      struct Zoltan_Struct *zz,
       int global_num,
       int len,
       int *part_ids,
       int *wgt_idx,
      float *part_sizes);
FORTRAN: function Zoltan_LB_Set_Part_Sizes( zz,global_part,len,partids,wgtidx,partsizes)
integer(Zoltan_INT) :: Zoltan_LB_Set_Part_Sizes
type(Zoltan_Struct) INTENT(IN) zz
integer(Zoltan_INT) INTENT(IN) global_part,len,partids(*),wgtidx(*)
real(Zoltan_FLOAT) INTENT(IN) partsizes(*)
C++: int Zoltan::LB_Set_Part_Sizes (
       const int &global_num,
       const int &len,
       int *part_ids,
       int *wgt_idx,
      float *part_sizes);

Zoltan_LB_Set_Part_Sizes is used to specify the desired part sizes in Zoltan. By default, Zoltan assumes that all parts should be of equal size.  With Zoltan_LB_Set_Part_Sizes, one can specify the relative (not absolute) sizes of the parts. For example, if two parts are requested and the desired sizes are 1 and 2, that means that the first part will be assigned approximately one third of the total load. If the sizes were instead given as 1/3 and 2/3, respectively, the result would be exactly the same. Note that if there are multiple weights per object, one can (must) specify the part size for each weight dimension independently.
 
Arguments:
    zz Pointer to the Zoltan structure created by Zoltan_Create.
   global_num Set to 1 if global part numbers are given, 0 otherwise (local part numbers).
   len Length of the next three input arrays.
   part_ids Array of part numbers, either global or local. (Part numbers are integers starting from 0.)
   vwgt_idx Array of weight indices (between 0 and OBJ_WEIGHT_DIM-1). This array should contain all zeros when there is only one weight per object.
   part_sizes Relative values for part sizes; part_sizes[i] is the desired relative size of the vwgt_idx[i]'th weight of part part_ids[i].
Returned Value:
    int Error code.


C: int Zoltan_LB_Eval (
      struct Zoltan_Struct *zz,
      int print_stats,
      ZOLTAN_BALANCE_EVAL *obj_info,
      ZOLTAN_GRAPH_EVAL *graph_info,
      ZOLTAN_HG_EVAL *hg_info); 
FORTRAN: FUNCTION Zoltan_LB_Eval(zz, print_stats
INTEGER(Zoltan_INT) :: Zoltan_LB_Eval
TYPE(Zoltan_Struct), INTENT(IN) :: zz 
LOGICAL, INTENT(IN) :: print_stats 
C++: int Zoltan::LB_Eval (
      const int &print_stats,
      ZOLTAN_BALANCE_EVAL *obj_info,
      ZOLTAN_GRAPH_EVAL *graph_info,
      ZOLTAN_HG_EVAL *hg_info); 

Zoltan_LB_Eval evaluates the quality of a decomposition. The quality metrics of interest differ depending on how you are using Zoltan. If you are partitioning points in space using one of Zoltan's geometric methods, you will want to know the weighted balance of objects across parts. However if you are partitioning a graph, you will want to know about edges that have vertices in more than one part. Zoltan_LB_Eval can write three different structures with these differing metrics.

Arguments:
    zz Pointer to the Zoltan structure.
    print_stats If print_stats>0 (.TRUE. in Fortran), print the quality metrics to stdout.
    obj_info If obj_infois non-NULL, write object balance values to the ZOLTAN_BALANCE_EVAL structure.
    graph_info If graph_infois non-NULL, write graph partition metrics to the ZOLTAN_GRAPH_EVAL structure.
    hg_info If hg_infois non-NULL, write hypergraph partition metrics to the ZOLTAN_HG_EVAL structure.
Returned Value:
    int Error code.

The EVAL structures are defined in zoltan/src/include/zoltan_eval.h. Several of the fields in the EVAL structures are arrays of values. The arrays contain values for

  1. the total for the local process
  2. the total across all parts
  3. the minimum across all parts
  4. the maximum across all parts
  5. the average across all parts

in that order. The corresponding macros that refer to these fields are:

#define EVAL_LOCAL_SUM 0
#define EVAL_GLOBAL_SUM 1
#define EVAL_GLOBAL_MIN 2
#define EVAL_GLOBAL_MAX 3
#define EVAL_GLOBAL_AVG 4

The ZOLTAN_BALANCE_EVAL structure contains the following fields, and would be of interest if you are doing geometric partitioning:

The ZOLTAN_GRAPH_EVAL structure contains the following fields, and would be of interest if you are doing graph partitioning:

The ZOLTAN_HG_EVAL structure contains the following fields, and would be of interest if you are doing hypergraph partitioning:

Query functions:

     Required:

ZOLTAN_NUM_OBJ_FN and ZOLTAN_OBJ_LIST_FN
     Optional: Graph-Based functions are required for writing the ZOLTAN_GRAPH_EVAL structure.
Hypergraph-Based functions will be used for writing the ZOLTAN_HG_EVAL if they are available, otherwise Zoltan will create a hypergraph from the graph-Based functions.
If Zoltan_LB_Set_Part_Sizes has been called, the part sizes set by the Zoltan_LB_Set_Part_Sizes will be used in calculating imbalances.

Note that the sum of ncuts over all processors is actually twice the number of edges cut in the graph (because each edge is counted twice). The same principle holds for cut_wgt.

There are a few improvements in Zoltan_LB_Eval  in Zoltan version 1.5 (or higher). First, the balance data are computed with respect to both processors and parts (if applicable). Second, the desired part sizes (as set by Zoltan_LB_Set_Part_Sizes)  are taken into account when computing the imbalance.

Known bug: If a part is spread across several processors, the computed cut information (ncuts and cut_wgt) may be incorrect (too high).



C: int Zoltan_LB_Free_Part (
      ZOLTAN_ID_PTR *global_ids,
      ZOLTAN_ID_PTR *local_ids,
      int **procs
      int **to_part);
FORTRAN: FUNCTION Zoltan_LB_Free_Part(global_ids, local_ids, procs, to_part)
INTEGER(Zoltan_INT) :: Zoltan_LB_Free_Part 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: global_ids
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: local_ids
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: procs, to_part
C++: int Zoltan::LB_Free_Part (
      ZOLTAN_ID_PTR *global_ids,
      ZOLTAN_ID_PTR *local_ids,
      int **procs
      int **to_part);

Zoltan_LB_Free_Part frees the memory allocated by Zoltan to return the results of Zoltan_LB_Partition or Zoltan_Invert_Lists. Memory pointed to by the arguments is freed and the arguments are set to NULL in C and C++ or nullified in Fortran. NULL arguments may be passed to Zoltan_LB_Free_Part. Typically, Zoltan_LB_Free_Part is called twice: once for the import lists, and once for the export lists.
Note that this function does not destroy the Zoltan data structure itself; it is deallocated through a call to Zoltan_Destroy in C and Fortran and by the object destructor in C++.
Arguments:
    global_ids An array containing the global IDs of objects.
    local_ids An array containing the local IDs of objects.
    procs An array containing processor IDs.
    to_part An array containing part numbers.
Returned Value:
    int Error code


C: int Zoltan_LB_Balance (
      struct Zoltan_Struct *zz,
      int *changes,
      int *num_gid_entries,
      int *num_lid_entries,
      int *num_import
      ZOLTAN_ID_PTR *import_global_ids,
      ZOLTAN_ID_PTR *import_local_ids,
      int **import_procs,
      int *num_export,
      ZOLTAN_ID_PTR *export_global_ids,
      ZOLTAN_ID_PTR *export_local_ids,
      int **export_procs); 
FORTRAN: FUNCTION Zoltan_LB_Balance(zz, changes, num_gid_entries, num_lid_entries, num_import, import_global_ids, import_local_ids, import_procs, num_export, export_global_ids, export_local_ids, export_procs
INTEGER(Zoltan_INT) :: Zoltan_LB_Balance 
TYPE(Zoltan_Struct), INTENT(IN) :: zz 
LOGICAL, INTENT(OUT) :: changes 
INTEGER(Zoltan_INT), INTENT(OUT) :: num_gid_entries, num_lid_entries
INTEGER(Zoltan_INT), INTENT(OUT) :: num_import, num_export 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_global_ids, export_global_ids 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_local_ids, export_local_ids 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_procs, export_procs 

Zoltan_LB_Balance is a wrapper around Zoltan_LB_Partition that excludes the part assignment results. Zoltan_LB_Balance assumes the number of parts is equal to the number of processors; thus, the part assignment is equivalent to the processor assignment. Results of the partitioning are returned in lists of objects to be imported and exported. These arrays are allocated in Zoltan; applications should not allocate these arrays before calling Zoltan_LB_Balance. The arrays are later freed through calls to Zoltan_LB_Free_Data or Zoltan_LB_Free_Part.
 
Arguments:
All arguments are analogous to those in Zoltan_LB_Partition. Part-assignment arguments import_to_part and export_to_part are not included, as processor and parts numbers are considered to be the same in Zoltan_LB_Balance.
Returned Value:
    int Error code.



C: int Zoltan_LB_Free_Data (
      ZOLTAN_ID_PTR *import_global_ids,
      ZOLTAN_ID_PTR *import_local_ids,
      int **import_procs
      ZOLTAN_ID_PTR *export_global_ids,
      ZOLTAN_ID_PTR *export_local_ids,
      int **export_procs); 
FORTRAN: FUNCTION Zoltan_LB_Free_Data(import_global_ids, import_local_ids, import_procs, export_global_ids, export_local_ids, export_procs
INTEGER(Zoltan_INT) :: Zoltan_LB_Free_Data 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_global_ids, export_global_ids 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_local_ids, export_local_ids 
INTEGER(Zoltan_INT), POINTER, DIMENSION(:) :: import_procs, export_procs 

Zoltan_LB_Free_Data frees the memory allocated by the Zoltan to return the results of Zoltan_LB_Balance or Zoltan_Compute_Destinations. Memory pointed to by the arguments is freed and the arguments are set to NULL in C or nullified in Fortran. NULL arguments may be passed to Zoltan_LB_Free_Data. Note that this function does not destroy the Zoltan data structure itself; it is deallocated through a call to Zoltan_Destroy.
 
Arguments:
    import_global_ids The array containing the global IDs of objects imported to this processor.
    import_local_ids The array containing the local IDs of objects imported to this processor.
    import_procs The array containing the processor IDs of the processors that owned the imported objects in the previous decomposition (i.e., the source processors).
    export_global_ids  The array containing the global IDs of objects exported from this processor.
    export_local_ids The array containing the local IDs of objects exported from this processor.
    export_procs The array containing the processor IDs of processors that own the exported objects in the new decomposition (i.e., the destination processors).
Returned Value:
    int Error code

[Table of Contents  | Next:  Functions for Augmenting a Decomposition  |  Previous:  Initialization Functions  |  Privacy and Security]