Zoltan Developer's Guide: Part Remapping

Zoltan Developer's Guide | Next | Previous

Part Remapping

Part remapping can be incorporated into load-balancing algorithms. The part remapping algorithm works as follows:

After partitioning within an ZOLTAN_LB_FN but before import or export lists are built, the partitioning algorithm calls Zoltan_LB_Remap.
Zoltan_LB_Remap builds a bipartite graph based on local import or export information (depending on which is available in the partitioning algorithm). Vertices of the graph are processor or part numbers used in the old (input to the partitioner) and new (computed by the partitioner) decompositions. Edges connect old and new vertices; edge weight for edge e_ij is the number of objects in old part i that are also in new part j. The bipartite graph is stored as a hypergraph, so that Zoltan's hypergraph matching routines may be applied.
Zoltan_LB_Remap gathers the local hypergraph edges onto each processor and performs a serial matching of the vertices. This matching defines the remapping.
Zoltan_LB_Remap remaps the input processor and part information to reflect the remapping and returns the result to the application. It also builds array zz->LB.Remap that is used in other functions (e.g., Zoltan_LB_Box_PP_Assign and Zoltan_LB_Point_PP_Assign).
Using the remapping information returned from Zoltan_LB_Remap, the partitioning algorithm builds the import or export lists to return to the application. Note: if the partitioning algorithm builds import lists, data may have to be moved to appropriate processors before building import lists to reflect the remapping; see rcb/shared.c for an example.

int Zoltan_LB_Remap (struct Zoltan_Struct *zz, int *new_map, int num_obj, int *procs, int *old_parts, int *new_parts, int export_list_flag);

Zoltan_LB_Remap remaps computed part (or processor) numbers in an attempt to maximize the amount of data that does not have to be migrated to the new decomposition. It is incorporated directly into partitioning algorithms, and should be called after the new decomposition is computed but before return lists (import or export lists) are created. Zoltan_LB_Remap should be invoked when Zoltan parameter REMAP is one. Even when REMAP is one, remapping is not done under a number of conditions; these conditions are listed with the description of REMAP.

Arguments:
zz	A pointer to the Zoltan_Struct used in the partitioning algorithm.
new_map	Upon return, a flag indicating whether remapping was actually done. Remapping is not done under a number of conditions (described with parameter REMAP) or when the computed remap gives a worse or equivalent result than the decomposition computed by the partitioning algorithm.
num_obj	Input: the number of objects the processor knows about after computing the decomposition. If the partitioning algorithm computes export lists, num_obj is the number of objects stored on the processor; if it computes import lists, num_obj is the number of objects that will be stored on the processor in the new decomposition.
procs	Upon input: an array of size num_obj containing processor assignments for the objects; if export_list_flag == 1, procs contains processor assignments in the NEW decomposition (computed by the partitioner); otherwise, procs contains processor assignments in the OLD decomposition (input by the application). Upon return, procs contains remapped processor assignments for the NEW decomposition, regardless of the value of export_list_flag.
old_parts	Upon input: an array of size num_obj containing part assignments for the objects in the OLD decomposition (input by the application).
new_parts	Upon input: an array of size num_obj containing part assignments for the objects in the NEW decomposition (computed by the partitioning algorithm). Upon return: new_parts contains remapped part assignments in the NEW decomposition.
export_list_flag	Flag indicating whether the partitioning algorithm computes export lists or import lists. The procedure for building the bipartite graph depends on whether the partitioning algorithm knows export or import information.

Returned Value:
int	Error code.

[Table of Contents | Next: Migration Tools | Previous: Adding new parameters | Privacy and Security]