00001 // -*- C++ -*- 00002 /*************************************************************************** 00003 * 00004 * The IPPL Framework 00005 * 00006 * 00007 * Visit http://people.web.psi.ch/adelmann/ for more details 00008 * 00009 ***************************************************************************/ 00010 00011 #ifndef VRB_H 00012 #define VRB_H 00013 00015 // 00016 // Vnode Recursive Bisection package 00017 // 00018 // This package figures out how to distribute rectangular arrays of 00019 // vnodes onto processors with an attempt to minimize communication 00020 // and unbalance. 00021 // 00022 // There one function with external linkage in this package: 00023 // 00024 // VnodeRecurseiveBisection(int dim, const int* sizes, int nprocs, int *vprocs); 00025 // 00026 // Input: 00027 // dim : The number of dimensions. 00028 // sizes: The number of vnodes in each dimension. 00029 // nprocs: The number of procs to distribute them over. 00030 // 00031 // Output: 00032 // procs: the proc number for each vnode, in the range 0..nprocs-1. 00033 // 00035 00037 // 00038 // The problem: 00039 // 00040 // Given a set of vnodes in D dimensions, we need to allocate them 00041 // to processors in a way that satisfies three criteria: 00042 // 00043 // 1. Layouts with the same number of vnodes in each direction should 00044 // be aligned independent of the size of the array in each dimension. 00045 // That means that the distribution is independent of whether it is 00046 // for a vert or cell centered Field. 00047 // 00048 // We do this by considering two things: 00049 // 00050 // a. Consider each vnode to have the same weight. That is, don't 00051 // try to consider the fact that different vnodes may have slightly 00052 // different numbers of cells in them. 00053 // 00054 // b. Each face between vnodes has the same computational cost. That is, 00055 // don't try to consider the fact that the faces between vnodes will 00056 // have different sizes if the vnodes are not square. 00057 // 00058 // 00059 // 2. Minimize communication. 00060 // 00061 // This means that you try to minimize the number of vnode faces 00062 // that must be communicated. 00063 // 00064 // 3. Minimize unbalance 00065 // 00066 // This means that you try to put the same number of vnodes on 00067 // each processor. 00068 // 00070 // 00071 // The Solution: Generalized Recursive Bisection 00072 // 00073 // The algorithm operates in a series of stages. 00074 // In each stage you split the work to be done approximately in half 00075 // and the processor pool approximately in half, and giving the split 00076 // work to the split processor pools. 00077 // 00078 // There are multipple ways of doing this. 00079 // 1. You can split along coordinate directions. 00080 // 2. You can renumber the vnodes with some space filling curve, and then 00081 // split along that curve. 00082 // 00083 // After trying both, we use number 1. 00084 // 00086 00087 void vnodeRecursiveBisection(int dim, const int* sizes, int nprocs, int *vprocs); 00088 00089 #endif // VRB_H 00090 00091 /*************************************************************************** 00092 * $RCSfile: VRB.h,v $ $Author: adelmann $ 00093 * $Revision: 1.1.1.1 $ $Date: 2003/01/23 07:40:27 $ 00094 * IPPL_VERSION_ID: $Id: VRB.h,v 1.1.1.1 2003/01/23 07:40:27 adelmann Exp $ 00095 ***************************************************************************/
1.4.6