SAMRAI::mesh::BalanceUtilities

SAMRAI::mesh::BalanceUtilities< DIM > Struct Template Reference

Utility class BalanceUtilities<DIM> provides several functions useful in various load balancing operations. These utilities include bin packing operations, box chopping by recursive bisection, and computation of effective processor layouts for boxes. More...

#include <source/mesh/load_balance/BalanceUtilities.h>

List of all members.

Static Public Member Functions

static double binPack (hier::ProcessorMapping &mapping, tbox::Array< double > &weights, int nproc)
static double spatialBinPack (hier::ProcessorMapping &mapping, tbox::Array< double > &weights, hier::BoxArray< DIM > &boxes, const int nproc)
static void recursiveBisectionUniform (hier::BoxList< DIM > &out_boxes, tbox::List< double > &out_workloads, const hier::BoxList< DIM > &in_boxes, double ideal_workload, const double workload_tolerance, const hier::IntVector< DIM > &min_size, const hier::IntVector< DIM > &cut_factor, const hier::IntVector< DIM > &bad_interval, const hier::BoxArray< DIM > &physical_domain)
static void recursiveBisectionNonuniform (hier::BoxList< DIM > &out_boxes, tbox::List< double > &out_workloads, const tbox::Pointer< hier::PatchLevel< DIM > > &in_level, int work_id, double ideal_workload, const double workload_tolerance, const hier::IntVector< DIM > &min_size, const hier::IntVector< DIM > &cut_factor, const hier::IntVector< DIM > &bad_interval, const hier::BoxArray< DIM > &physical_domain)
static void computeDomainDependentProcessorLayout (hier::IntVector< DIM > &proc_dist, int num_procs, const hier::Box< DIM > &box)
static void computeDomainIndependentProcessorLayout (hier::IntVector< DIM > &proc_dist, int num_procs, const hier::Box< DIM > &box)
static void sortDescendingBoxWorkloads (hier::BoxArray< DIM > &boxes, tbox::Array< double > &workload)
static double computeNonUniformWorkload (tbox::Pointer< hier::Patch< DIM > > patch, int wrk_indx, const hier::Box< DIM > &box)
static double computeLoadBalanceEfficiency (const tbox::Pointer< hier::PatchLevel< DIM > > &level, std::ostream &os, int workload_data_id=-1)

Detailed Description

template<int DIM>
struct SAMRAI::mesh::BalanceUtilities< DIM >

Utility class BalanceUtilities<DIM> provides several functions useful in various load balancing operations. These utilities include bin packing operations, box chopping by recursive bisection, and computation of effective processor layouts for boxes.

Member Function Documentation

template<int DIM>
double SAMRAI::mesh::BalanceUtilities< DIM >::binPack ( hier::ProcessorMapping &  mapping,
tbox::Array< double > &  weights,
int  nproc 
) [static]

Assign workloads to processors using a greedy algorithm that attempts to distribute the sum of weights on each processor evenly across the given number of processors.

Returns:
double-valued estimate of the load balance efficiency (ranges from zero to one hundred percent)
Parameters:
mapping Output processor mapping.
weights tbox::Array of double-valued weights to distribute.
nproc Integer number of processors, must be > 0.

template<int DIM>
double SAMRAI::mesh::BalanceUtilities< DIM >::spatialBinPack ( hier::ProcessorMapping &  mapping,
tbox::Array< double > &  weights,
hier::BoxArray< DIM > &  boxes,
const int  nproc 
) [static]

Assign boxes to processors so that boxes spatially near each other are likely to be assigned to processors near each other (assuming that processor ordering is reflected in processor rank) and so that the workload is approximately evenly distributed among the processors. The routine uses a Morton space-filling curve algorithm.

Note that this routine potentially reorders the boxes passed in to achieve the first goal.

Returns:
Double-valued estimate of the load balance efficiency (ranges from zero to one hundred percent)
Parameters:
mapping Output processor mapping.
weights tbox::Array of double-valued box weights to distribute.
boxes tbox::Array of boxes to distribute to processors.
nproc Integer number of processors, must be > 0.
Note that the wight and box arrrays must be the same size.

template<int DIM>
void SAMRAI::mesh::BalanceUtilities< DIM >::recursiveBisectionUniform ( hier::BoxList< DIM > &  out_boxes,
tbox::List< double > &  out_workloads,
const hier::BoxList< DIM > &  in_boxes,
double  ideal_workload,
const double  workload_tolerance,
const hier::IntVector< DIM > &  min_size,
const hier::IntVector< DIM > &  cut_factor,
const hier::IntVector< DIM > &  bad_interval,
const hier::BoxArray< DIM > &  physical_domain 
) [static]

Recursively chop chops boxes in input boxlist until each box has a workload less than the prescribed ideal workload or no more more chopping is allowed by the given constraints. A spatially-uniform workload is assumed; i.e., all cells are weighted equally. This routine attempts to create as many boxes as possible with loads equal to or slightly less than the ideal workload value so that they can be mapped to processors effectively.

Parameters:
out_boxes Output box list.
out_workloads Output list of box workloads.
in_boxes Input boxlist for chopping.
ideal_workload Input double ideal box workload, must be > 0.
workload_tolerance Input double workload tolerance, must be >= 0 and < 1.0
min_size Input integer vector of minimum dimensions for output boxes. All entries must be > 0.
cut_factor Input integer vector used to create boxes with correct dimensions. The length of each box dimension will be an integer multiple of the corresponding cut factor vector entry. All vector entries must be > 0. See hier::BoxUtilities documentation for more details.
bad_interval Input integer vector used to create boxes near physical domain boundary with sufficient number of cells. No box face will be closer to the boundary than the corresponding interval of cells to the boundary (the corresponding value is given by the normal direction of the box face) unless the face coincides with the boundary itself. The point of this argument is to have no patch live within a certain ghost cell width of the boundary if its boundary does not coincide with that boundary . That is, all ghost cells along a face will be either in the domain interior or outside the domain. All entries must be >= 0. See hier::BoxUtilities documentation for more details.
physical_domain tbox::Array of boxes describing the physical extent of the index space associated with the in_boxes. This box array cannot be empty.

template<int DIM>
void SAMRAI::mesh::BalanceUtilities< DIM >::recursiveBisectionNonuniform ( hier::BoxList< DIM > &  out_boxes,
tbox::List< double > &  out_workloads,
const tbox::Pointer< hier::PatchLevel< DIM > > &  in_level,
int  work_id,
double  ideal_workload,
const double  workload_tolerance,
const hier::IntVector< DIM > &  min_size,
const hier::IntVector< DIM > &  cut_factor,
const hier::IntVector< DIM > &  bad_interval,
const hier::BoxArray< DIM > &  physical_domain 
) [static]

Recursively chops boxes given by patches on input patch level until each box has a workload less than the prescribed ideal workload or no more more chopping is allowed by the given constraints. A spatially-nonuniform workload is assumed. Cell weights must be given bydata defined by the given patch data id on the given patch level. This routine attempts to create as many boxes as possible with loads equal to or slightly less than the ideal workload value so that they can be mapped to processors effectively.

Parameters:
out_boxes Output box list.
out_workloads Output list of box workloads.
in_level Input patch level whose patches describe input box regions and whose patch data contain workload estimate for each cell.
work_id Input integer patch data id for cell-centered double work estimate for each cell.
ideal_workload Input double ideal box workload, must be > 0.
workload_tolerance Input double workload tolerance, must be >= 0 and < 1.0
min_size Input integer vector of minimum dimensions for output boxes. All entries must be > 0.
cut_factor Input integer vector used to create boxes with correct dimensions. The length of each box dimension will be an integer multiple of the corresponding cut factor vector entry. All vector entries must be > 0. See hier::BoxUtilities documentation for more details.
bad_interval Input integer vector used to create boxes near physical domain boundary with sufficient number of cells. No box face will be closer to the boundary than the corresponding interval of cells to the boundary (the corresponding value is given by the normal direction of the box face) unless the face coincides with the boundary itself. The point of this argument is to have no patch live within a certain ghost cell width of the boundary if its boundary does not coincide with that boundary . That is, all ghost cells along a face will be either in the domain interior or outside the domain. All entries must be >= 0. See hier::BoxUtilities documentation for more details.
physical_domain tbox::Array of boxes describing the physical extent of the index space associated with the in_boxes. This box array cannot be empty.

template<int DIM>
void SAMRAI::mesh::BalanceUtilities< DIM >::computeDomainDependentProcessorLayout ( hier::IntVector< DIM > &  proc_dist,
int  num_procs,
const hier::Box< DIM > &  box 
) [static]

Compute factorization of processors corresponding to dimensions of given box.

Parameters:
proc_dist Output number of processors for each coordinate direction.
num_procs Input integer number of processors, must be > 0.
box Input box to be distributed.

template<int DIM>
void SAMRAI::mesh::BalanceUtilities< DIM >::computeDomainIndependentProcessorLayout ( hier::IntVector< DIM > &  proc_dist,
int  num_procs,
const hier::Box< DIM > &  box 
) [static]

Compute a factorization of processors that does NOT necessarily correspond to the dimensions of the supplied box. For example, the processor distribution in each direction may simply be a square root (cube root in 3D) of the number of processors. The box information is used simply to determine a maximum number of processors in each coordinate direction.

Parameters:
proc_dist Output number of processors for each coordinate direction.
num_procs Input integer number of processors, must be > 0.
box Input box to be distributed.

template<int DIM>
void SAMRAI::mesh::BalanceUtilities< DIM >::sortDescendingBoxWorkloads ( hier::BoxArray< DIM > &  boxes,
tbox::Array< double > &  workload 
) [static]

Sort box array in descending order of workload according to the workload array. Both the box array and the work array will be sorted on return.

Note that if you simply want to sort boxes based on their size, see hier::BoxUtilities.

Parameters:
boxes Boxes to be sorted based on workload array.
workload Workloads to use for sorting boxes.
Note that both arrays must be the same size.

template<int DIM>
double SAMRAI::mesh::BalanceUtilities< DIM >::computeNonUniformWorkload ( tbox::Pointer< hier::Patch< DIM > >  patch,
int  wrk_indx,
const hier::Box< DIM > &  box 
) [static]

Compute total workload in region of argument box based on patch data defined by given integer index. The sum is computed on the intersection of argument box and box over which data associated with workload is defined.

Returns:
Double-valued sum of workload values in box region.
Parameters:
patch Input patch on which workload data is defined.
wrk_indx Input integer patch data identifier for work data.
box Input box region
Note that wrk_indx must refer to a valid cell-centered patch data entry.

template<int DIM>
double SAMRAI::mesh::BalanceUtilities< DIM >::computeLoadBalanceEfficiency ( const tbox::Pointer< hier::PatchLevel< DIM > > &  level,
std::ostream &  os,
int  workload_data_id = -1 
) [static]

Compute and return load balance efficiency for a level.

Returns:
Double-valued estimate of the load balance efficiency (ranges from zero to one hundred percent)
Parameters:
level Input patch level to consider, can't be null.
os Output stream for reporting load balance details.
workload_data_id (Optional) Input integer id for workload data on level. If no value is given, the calculation assumes spatially-uniform load.

The documentation for this struct was generated from the following files:
Generated on Thu Jun 18 11:28:41 2009 for SAMRAI by  doxygen 1.5.1