LoadBalance.H

Go to the documentation of this file.

/*   _______              __
    / ___/ /  ___  __ _  / /  ___
   / /__/ _ \/ _ \/  V \/ _ \/ _ \
   \___/_//_/\___/_/_/_/_.__/\___/
*/
// CHOMBO Copyright (c) 2000-2004, The Regents of the University of
// California, through Lawrence Berkeley National Laboratory (subject to
// receipt of any required approvals from U.S. Dept. of Energy).  All
// rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// (1) Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// (2) Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// (3) Neither the name of Lawrence Berkeley National Laboratory, U.S.
// Dept. of Energy nor the names of its contributors may be used to endorse
// or promote products derived from this software without specific prior
// written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
// OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// You are under no obligation whatsoever to provide any bug fixes,
// patches, or upgrades to the features, functionality or performance of
// the source code ("Enhancements") to anyone; however, if you choose to
// make your Enhancements available either publicly, or directly to
// Lawrence Berkeley National Laboratory, without imposing a separate
// written license agreement for such Enhancements, then you hereby grant
// the following license: a non-exclusive, royalty-free perpetual license
// to install, use, modify, prepare derivative works, incorporate into
// other computer software, distribute, and sublicense such Enhancements or
// derivative works thereof, in binary and source code form.
//
// TRADEMARKS. Product and company names mentioned herein may be the
// trademarks of their respective owners.  Any rights not expressly granted
// herein are reserved.
//

// Purpose:
//  LoadBalance() is a global function to compute an assignment
//  of boxes to processors for an AMR mesh hierarchy.  The assignment
//  is made so as to balance the computation and communication
//  workload on each processor (i.e. make it as even as possible).
//
//  ********************************************************
//  CAVEAT: this version ignores the communication workload.
//          It balances ONLY the compute workload.
//  ********************************************************
//
// Usage:
//  The meshes in the AMR hierarchy are represented using
//   a Vector of Vectors of Boxes.
//
//  The computational workload is a real number for each box in the
//   hierarchy, also represented as a Vector of Vectors.
//
//  The communication workload is a real number for each connection
//   between pairs of boxes, which specifies the cost of communication
//   between the two boxes if they are on different processors.  No
//   allowance is made for varying the communication cost depending on the
//   distance between processors (ie. all processors are equally far apart)
//   and it assumes that the effective cost of communicating between two
//   boxes on the same processor is zero.  The communication workload is
//   represented as a graph.
//
//  ********************************************************
//  CAVEAT: the communication workload argument is not
//           present in this version of the function.
//  ********************************************************
//
//  The resulting assignment is an integer for each box in the hierarchy,
//   which gives the processor number (starting at zero) on which each box
//   should reside.  Again, represented as a Vector of Vectors.
//
//  The other output argument is the efficiency ratio, which is a measure
//   of how close to perfect the final load balance is.  The \var{effRatio}
//   output variable is defined as the smallest load on any processor divided
//   by the largest load.  A perfect load balance has efficiency == 1.
//
//  ********************************************************
//  CAVEAT: in this version, each level in the AMR hierarchy
//          is balanced independently, so the efficiency ratio
//          that is returned is the worst over all levels.
//  ********************************************************
//
//  It is important to note that it is the sum of the computation cost
//   and communication cost that is balanced, so the values in the two
//   variables must be in the same units.  It doesn't matter what the
//   units are.
//
//  ********************************************************
//  CAVEAT: the communication workload argument is not
//           present in this version of the function.
//  ********************************************************
//
// Interface Specification:
//  int LoadBalance() arguments are:
//       Vector<Vector<int>>& procAssignments  //output: processor number
//                                             //   for each box
//       Real&                effRatio         //output: efficiency ratio
// const Vector<Vector<Box>>& Grids            //input: meshes to balance
// const Vector<Vector<long>>&ComputeLoads     //input: computational cost
//                                             //   of each box
//###not used###
//### const [...something...]&CommunicateLoads //input: communication cost
//                                             //   between each pair of
//                                             //   neighboring boxes
// const Vector<int>&         RefRatios        //input: refinement ratio
//                                             //   for each level
//
// Returns: integer status_code
//    =0  means succesful completion
//  exceptions: (output variables are not defined)
//  -1011 input vectors (\var{Grids} and \var{ComputeLoads}) are not
//        the same size
//  -1012 one of the vector elements of the input vectors (\var{Grids}
//        and \var{ComputeLoads}) are not the same size
//  -1013 input vectors (\var{Grids} and \var{RefRatios}) are not
//        the same size
//
// Modification History
//  19Nov99 <dbs> initial design and coding
//

#ifndef _LOADBALANCE_H_
#define _LOADBALANCE_H_

#include "SPACE.H"
#include "REAL.H"
#include "Box.H"
#include "Vector.H"
#include "BoxLayout.H"
#include "SPMD.H"


int
LoadBalance( Vector<Vector<int> >&         a_procAssignments
             ,Real&                        a_effRatio
             ,const Vector<Vector<Box> >&  a_Grids
             ,const Vector<Vector<long> >& a_ComputeLoads
             ,const Vector<int>&           a_RefRatios
             ,int a_nProc = numProc()
             ) ;


int
LoadBalance( Vector<BoxLayout>&    Grids
             ,Real&                 effRatio
             ,const Vector<Vector<long> >& ComputeLoads
             ,const Vector<int>&           RefRatios
             ,int nProc = numProc()
             ) ;


int LoadBalance(Vector<int>& procAssignments, const Vector<Box>& boxes,
                int a_numProc = numProc());


int LoadBalance(Vector<int>&        procAssignments,
                const Vector<long>& a_computeLoads,
                const Vector<Box>&  a_boxes,
                const int a_numProc = numProc());

int
LoadBalance(Vector<int>& procAssignments
            ,Real&                 effRatio
            ,const Vector<Box>&  Grids
            ,const Vector<long>& ComputeLoads);

#endif

---