Zoltan Developer's Guide  |  Next  |  Previous

Data Structures

The main data structures for the algorithm should be pointed to by the LB.Data_Structure field of the Zoltan_Struct. This requirement allows reuse of data structures from one invocation of the new load-balancing algorithm to the next. It also prevents the use of global data structures for the algorithm so that multiple instances of the algorithm may be used (i.e., the same algorithm can be used for multiple Zoltan_Struct structures).  An example showing the construction of data structures for the Recursive Coordinate Bisection (RCB) algorithm is included in the figure below.

/* Allocate RCB data structure for this Zoltan structure.
 * If the previous data structure still exists, free the Dots first;
 * the other fields can be reused.
 */
if (zz->LB.Data_Structure == NULL) {
   rcb = (RCB_STRUCT *) ZOLTAN_MALLOC(sizeof(RCB_STRUCT));
   zz->LB.Data_Structure = (void *) rcb;
   rcb->Tree_Ptr = (struct rcb_tree *) 
                    ZOLTAN_MALLOC(zz->Num_Proc*sizeof(struct rcb_tree));
   rcb->Box = (struct rcb_box *) ZOLTAN_MALLOC(sizeof(struct rcb_box));
}
else {
   rcb = (RCB_STRUCT *) zz->LB.Data_Structure;
   ZOLTAN_FREE(&(rcb->Dots));
}
Example demonstrating allocation of data structures for the RCB algorithm.  (Taken from rcb/rcb_util.c.)

The data needed for the algorithm is collected through calls to the query functions registered by the application. Algorithms should test the query function pointers for NULL and report errors when needed functions are not registered. The appropriate query functions can be called to build the algorithm's data structures up front, or they can be called during the algorithm's execution to gather data only as it is needed. The figure below shows how the Dots data structure needed by RCB is built.  The call to zz->Get_Num_Obj invokes an ZOLTAN_NUM_OBJ_FN query function to determine the number of objects on the processor.  Space for the Dots data structure is allocated through calls to ZOLTAN_MALLOC, ZOLTAN_MALLOC_GID_ARRAY, and ZOLTAN_MALLOC_LID_ARRAY.  The Dots information is obtained through a call to the Zoltan service function Zoltan_Get_Obj_List; this function calls either an ZOLTAN_OBJ_LIST_FN or an ZOLTAN_FIRST_OBJ_FN/ZOLTAN_NEXT_OBJ_FN pair to get the object IDs and weights. The data for each Dot is set in the function initialize_dot, which includes calls to zz->Get_Geom, an ZOLTAN_GEOM_FN query function.
 
 

  
/*
 * Allocate space for objects.  Allow extra space
 * for objects that are imported to the processor.
 */

*num_obj = zz->Get_Num_Obj(zz->Get_Num_Obj_Data, &ierr);
if (ierr) {
  ZOLTAN_PRINT_ERROR(zz->Proc, yo,
                 "Error returned from Get_Num_Obj.");
  return(ierr);
}

*max_obj = (int)(1.5 * *num_obj) + 1;
*global_ids = ZOLTAN_MALLOC_GID_ARRAY(zz, (*max_obj));
*local_ids  = ZOLTAN_MALLOC_LID_ARRAY(zz, (*max_obj));
*dots = (struct Dot_Struct *)
         ZOLTAN_MALLOC((*max_obj)*sizeof(struct Dot_Struct));

if (!(*global_ids) || (zz->Num_LID && !(*local_ids)) || !(*dots)) {
  ZOLTAN_PRINT_ERROR(zz->Proc, yo, "Insufficient memory.");
  return(ZOLTAN_MEMERR);
}

if (*num_obj > 0) {

  if (wgtflag) {

    /*
     *  Allocate space for object weights.
     */

    objs_wgt = (float *) ZOLTAN_MALLOC((*num_obj)*sizeof(float));
    if (!objs_wgt) {
      ZOLTAN_PRINT_ERROR(zz->Proc, yo, "Insufficient memory.");
      return(ZOLTAN_MEMERR);
    }
    for (i = 0; i < *num_obj; i++) objs_wgt[i] = 0.;
  }

  /*
   *  Get list of objects' IDs and weights.
   */

  Zoltan_Get_Obj_List(zz, *global_ids, *local_ids, wgtflag,
                  objs_wgt, &ierr);
  if (ierr) {
    ZOLTAN_PRINT_ERROR(zz->Proc, yo,
                   "Error returned from Zoltan_Get_Obj_List.");
    ZOLTAN_FREE(&objs_wgt);
    return(ierr);
  }

  ierr = initialize_dot(zz, *global_ids, *local_ids, *dots,
                        *num_obj, wgtflag, objs_wgt);
  if (ierr == ZOLTAN_FATAL || ierr == ZOLTAN_MEMERR) {
    ZOLTAN_PRINT_ERROR(zz->Proc, yo,
                   "Error returned from initialize_dot.");
    ZOLTAN_FREE(&objs_wgt);
    return(ierr);
  }

  ZOLTAN_FREE(&objs_wgt);
}

Example demonstrating how data structures are built for the RCB algorithm.  (Taken from rcb/shared.c.)

The data structures pointed to by zz->LB.Data_Structure will be freed at some point, and may be copied.

A function that frees these structures and resets zz->LB.Data_Structure to NULL should be written. The function should be called when the load-balancing algorithm exits, either normally or due to an error condition. The function Zoltan_RCB_Free_Structure in rcb/rcb_util.c may be used as an example.

If your algorithm uses the KEEP_CUTS parameter, a function that copies one zz->LB.Data_Structure to another is required. This is particularly important for C++, which may create temporary objects at runtime by invoking a copy operator (which will call your copy function). It is a convenience for C applications, which may wish to copy one Zoltan_Struct to another. See the function Zoltan_RCB_Copy_Structure in rcb/rcb_util.c for an example.


[Table of Contents  |  Next:  Memory Management  |  Previous:  Load-Balancing Function Implementation  |  Privacy and Security]