00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #include "FieldLayout/MultiBalancer.h"
00028 #include "Utility/PAssert.h"
00029
00030 #ifdef IPPL_STDSTL
00031
00032 #include <algorithm>
00033 using namespace std;
00034 #else
00035 #include <algo.h>
00036 #endif // IPPL_STDSTL
00037
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048 MultiBalancer::MultiBalancer(int procs, int vnodes)
00049 :
00050
00051 m_procs(procs) ,
00052 m_vnodes(vnodes) ,
00053
00054 m_materials(0) ,
00055
00056 m_vnodeProcs(vnodes),
00057
00058 m_procWeights(procs),
00059
00060 m_phase( noMaterials )
00061 {
00062 }
00063
00065
00066
00067
00068
00069
00070 MultiBalancer::~MultiBalancer()
00071 {
00072
00073 for (int i=0; i<m_materials; ++i)
00074 {
00075 delete m_inputWeights[i];
00076 delete m_materialProcWeights[i];
00077 }
00078 }
00079
00081
00082
00083
00084
00085
00086 void MultiBalancer::newMaterial()
00087 {
00088
00089 PAssert( m_phase != distributed );
00090
00091
00092
00093 if ( m_phase == someMaterials )
00094
00095 PAssert( m_inputWeights.back()->size() == m_vnodes );
00096
00097
00098 m_inputWeights.push_back( new VnodeWeights_t );
00099
00100
00101 m_inputWeights.back()->reserve( m_vnodes );
00102
00103
00104 ++m_materials;
00105
00106
00107 m_phase = someMaterials;
00108 }
00109
00111
00112
00113
00114
00115
00116 void MultiBalancer::appendWeights(double *begin, double *end)
00117 {
00118
00119 PAssert(m_materials>0);
00120
00121
00122 VnodeWeights_t& weights = *m_inputWeights.back();
00123
00124
00125 for (; begin!=end; ++begin)
00126 weights.push_back(*begin);
00127
00128
00129 PAssert( weights.size() <= m_vnodes );
00130 }
00131
00133
00134
00135
00136
00137
00138 void MultiBalancer::distribute()
00139 {
00140
00141 PAssert( m_phase != noMaterials );
00142
00143
00144 if ( m_phase == distributed )
00145 return;
00146
00147 int m;
00148
00149
00150 VnodeWeights_t vnodeTotalWeights(m_vnodes,0.0);
00151 calcTotalWeights(vnodeTotalWeights);
00152
00153
00154
00155 vector<int> vnodeIndirect(m_vnodes);
00156 calcIndirectSort(vnodeIndirect,vnodeTotalWeights);
00157
00158
00159 m_materialMaxWeights.resize( m_materials );
00160 for (m=0; m<m_materials; ++m)
00161 m_materialMaxWeights[m] = 0.0;
00162
00163
00164 m_materialProcWeights.reserve(m_materials);
00165 for (m=0; m<m_materials; ++m)
00166 m_materialProcWeights.push_back(new VnodeWeights_t(m_procs));
00167
00168
00169
00170
00171 for (int i=m_vnodes-1; i>=0; --i)
00172 {
00173
00174 int vnode = vnodeIndirect[i];
00175
00176
00177
00178 int proc = findProcForVnode(vnode);
00179
00180
00181 m_vnodeProcs[vnode] = proc;
00182
00183
00184 m_procWeights[proc] += vnodeTotalWeights[vnode];
00185
00186
00187 for (int m=0; m<m_materials; ++m)
00188 {
00189
00190 m_materialProcWeights[m][0][proc] += m_inputWeights[m][0][vnode];
00191
00192
00193 if ( m_materialMaxWeights[m] < m_materialProcWeights[m][0][proc] )
00194 m_materialMaxWeights[m] = m_materialProcWeights[m][0][proc];
00195 }
00196 }
00197
00198
00199 m_phase = distributed;
00200 }
00201
00203
00204
00205
00206
00207
00208
00209
00210 int MultiBalancer::findProcForVnode( int v )
00211 {
00212
00213 double minWeight = 1e30;
00214
00215
00216 int minProc = -1;
00217
00218
00219 for (int p = 0; p<m_procs; ++p)
00220 {
00221
00222 double totalWeight = 0.0;
00223 for (int m=0; m<m_materials; ++m)
00224 {
00225
00226
00227 double w = m_materialProcWeights[m][0][p]+m_inputWeights[m][0][v];
00228
00229
00230
00231 if ( w < m_materialMaxWeights[m] )
00232 w = m_materialMaxWeights[m];
00233
00234
00235 totalWeight += w;
00236 }
00237
00238
00239
00240 if ( totalWeight < minWeight )
00241 {
00242 minWeight = totalWeight;
00243 minProc = p;
00244 }
00245 }
00246
00247
00248
00249 PAssert(minProc>=0);
00250 return minProc;
00251 }
00252
00254
00255
00256
00257
00258 void
00259 MultiBalancer::calcTotalWeights(VnodeWeights_t& vnodeTotalWeights)
00260 {
00261 MaterialVnodeWeights_t::iterator matp=m_inputWeights.begin();
00262 for (; matp != m_inputWeights.end(); ++matp)
00263 {
00264
00265
00266
00267 PAssert( (*matp)->size() == m_vnodes );
00268
00269
00270
00271 for (int i = 0; i<m_vnodes; ++i)
00272 vnodeTotalWeights[i] += (**matp)[i];
00273 }
00274 }
00275
00277
00278
00279
00280
00281
00282 void
00283 MultiBalancer::calcIndirectSort(vector<int>& vnodeIndirect,
00284 const VnodeWeights_t& vnodeTotalWeights)
00285 {
00286
00287 for (int i=0; i<m_vnodes; ++i)
00288 vnodeIndirect[i] = i;
00289
00290
00291
00292 sort(
00293 vnodeIndirect.begin(),
00294 vnodeIndirect.end(),
00295 IndirectComparator(vnodeTotalWeights.begin()));
00296 }
00297
00298
00299
00300
00301
00302
00303