Zoltan User's Guide  |  Next  |  Previous

Migration Examples

Data migration using Zoltan's migration tools can be accomplished in two different ways:
auto-migration, or
user-guided migration.
The choice of migration method depends upon the complexity of the application's data. For some applications, only the objects used in balancing must be migrated; no auxiliary data structures must be moved. Particle simulations are examples of such applications; load balancing is based on the number of particles per processor, and only the particles and their data must be moved to establish the new decomposition. For such applications, Zoltan's auto-migration tools can be used. Other applications, such as finite element methods, perform load balancing on, say, the nodes of the finite element mesh, but nodes that are moved to new processors also need to have their connected elements moved to the new processors, and migrated elements may also need "ghost" nodes (i.e., copies of nodes assigned to other processors) to satisfy their connectivity requirements on the new processor. This complex data migration requires a more user-controlled approach to data migration than the auto-migration capabilities Zoltan can provide.
 

Auto-Migration Example

In the figure below, an example of the load-balancing calling sequence for a particle simulation using Zoltan's auto-migration tools is shown. The application requests auto-migration by turning on the AUTO_MIGRATE option through a call to Zoltan_Set_Param and registers functions to pack and unpack a particle's data. During the call to Zoltan_LB_Partition, Zoltan computes the new decomposition and, using calls to the packing and unpacking query functions, automatically migrates particles to their new processors. The application then frees the arrays returned by Zoltan_LB_Partition and can continue computation without having to perform any additional operations for data migration.
 
 
/* Tell Zoltan to automatically migrate data for the application. */ 
Zoltan_Set_Param(zz, "AUTO_MIGRATE", "TRUE"); 

/* Register additional functions for packing and unpacking data */ 
/* by migration tools. */ 
Zoltan_Set_Fn(zz, ZOLTAN_OBJ_SIZE_FN_TYPE,
          (void (*)()) user_return_particle_data_size, NULL); 
Zoltan_Set_Fn(zz, ZOLTAN_PACK_OBJ_FN_TYPE,
          (void (*)()) user_pack_particle_data, NULL); 
Zoltan_Set_Fn(zz, ZOLTAN_UNPACK_OBJ_FN_TYPE,
          (void (*)()) user_unpack_particle_data, NULL); 
... 
/* Perform computations */ 
... 
/* Perform load balancing AND automatic data migration! */ 
Zoltan_LB_Partition(zz,&new,&num_gid_entries,&num_lid_entries,
    &num_imp,&imp_global_ids,&imp_local_ids,&imp_procs,&imp_to_part,
    &num_exp,&exp_global_ids,&exp_local_ids,&exp_procs,&exp_to_part); 

/* Free memory allocated for load-balancing results by Zoltan */ 
Zoltan_LB_Free_Part(&imp_global_ids, &imp_local_ids, &imp_procs, &imp_to_part);
Zoltan_LB_Free_Part(&exp_global_ids, &exp_local_ids, &exp_procs, &exp_to_part);
...
Typical calling sequence for using the migration tools' auto-migration capability with the dynamic load-balancing tools.
 

User-Guided Migration Example

In the following figure, an example of user-guided migration using Zoltan's migration tools for a finite element application is shown. Several migration steps are needed to completely rebuild the application's data structures for the new decomposition. On each processor, newly imported nodes need copies of elements containing those nodes. Newly imported elements, then, need copies of "ghost" nodes, nodes that are in the element but are assigned to other processors. Each of these entities (nodes, elements, and ghost nodes) can be migrated in separate migration steps using the functions provided in the migration tools. First, the assignment of nodes to processors returned by Zoltan_LB_Partition is established. Query functions that pack and unpack nodes are registered and Zoltan_Migrate is called using the nodal decomposition returned from Zoltan_LB_Partition. Zoltan_Migrate packs the nodes to be exported, sends them to other processors, and unpacks nodes received by a processor. The packing routine migrate_node_pack includes with each node a list of the element IDs for elements containing that node. The unpacking routine migrate_node_unpack examines the list of element IDs and builds a list of requests for elements the processor needs but does not already store. At the end of the nodal migration, each processor has a list of element IDs for elements that it needs to support imported nodes but does not already store. Through a call to Zoltan_Invert_Lists, each processor computes the list of elements it has to send to other processors to satisfy their element requests. Packing and unpacking routines for elements are registered, and Zoltan_Migrate is again used to move element data to new processors. Requests for ghost nodes can be built within the element packing and unpacking routines, and calls to Zoltan_Invert_Lists and Zoltan_Migrate, with node packing and unpacking, satisfy requests for ghost nodes. In all three phases of migration, the migration tools handle communication; the application is responsible only for packing and unpacking data and for building the appropriate request lists.
 
 
/* Assume Zoltan returns a decomposition of the */ 
/* nodes of a finite element mesh. */ 
Zoltan_LB_Partition(zz,&new,&num_gid_entries,&num_lid_entries,
    &num_imp,&imp_global_ids,&imp_local_ids,&imp_procs,&imp_to_part,
    &num_exp,&exp_global_ids,&exp_local_ids,&exp_procs,&exp_to_part);

/* Migrate the nodes as directed by the results of Zoltan_LB_Partition. */
/* While unpacking nodes, build list of requests for elements needed */
/* to support the imported nodes.*/
Zoltan_Set_Fn(zz, ZOLTAN_OBJ_SIZE_FN_TYPE,
           (void (*)()) migrate_node_size, NULL); 
Zoltan_Set_Fn(zz, ZOLTAN_PACK_OBJ_FN_TYPE,
           (void (*)()) migrate_pack_node, NULL); 
Zoltan_Set_Fn(zz, ZOLTAN_UNPACK_OBJ_FN_TYPE,
           (void (*)()) migrate_unpack_node, NULL); 
Zoltan_Migrate(zz,num_import,imp_global_ids,imp_local_ids,imp_procs,imp_to_part,
        num_export,exp_global_ids,exp_local_ids,exp_procs,exp_to_part);

/* Prepare for migration of requested elements. */ 
Zoltan_Set_Fn(zz, ZOLTAN_PACK_OBJ_FN_TYPE,
           (void (*)()) migrate_pack_element, NULL); 
Zoltan_Set_Fn(zz, ZOLTAN_UNPACK_OBJ_FN_TYPE,
           (void (*)()) migrate_unpack_element, NULL); 
Zoltan_Set_Fn(zz, ZOLTAN_OBJ_SIZE_FN_TYPE,
           (void (*)()) migrate_element_size, NULL); 

/* From the request lists, a processor knows which elements it needs */ 
/* to support the imported nodes; it must compute which elements to */ 
/* send to other processors. */ 
Zoltan_Invert_Lists(zz, Num_Elt_Requests, Elt_Requests_Global_IDs,  
           Elt_Requests_Local_IDs, Elt_Requests_Procs, Elt_Requests_to_Part, 
           &num_tmp_exp, &tmp_exp_global_ids,  
           &tmp_exp_local_ids, &tmp_exp_procs, &tmp_exp_to_part);  

/* Processor now knows which elements to send to other processors. */ 
/* Send the requested elements. While unpacking elements, build */ 
/* request lists for "ghost" nodes needed by the imported elements. */ 
Zoltan_Migrate(zz, Num_Elt_Requests, Elt_Requests_Global_IDs,  
       Elt_Requests_Local_IDs, Elt_Requests_Procs, Elt_Request_to_Part,
       num_tmp_exp_objs, tmp_exp_global_ids, 
       tmp_exp_local_ids, tmp_exp_procs, tmp_exp_to_part);

/* Repeat process for "ghost" nodes. */ 
...
Typical calling sequence for user-guided use of the migration tools in Zoltan.
 
[Table of Contents  |  Next:  Query-Function Examples  |  Previous:  Load-Balancing Example  |  Privacy and Security]