NAMD
AlgSeven.C
Go to the documentation of this file.
1 
7 /*****************************************************************************
8  * $Source: /home/cvs/namd/cvsroot/namd2/src/AlgSeven.C,v $
9  * $Author: jim $
10  * $Date: 2013/06/07 22:34:36 $
11  * $Revision: 1.60 $
12  *****************************************************************************/
13 
14 #include "common.h"
15 #include "InfoStream.h"
16 #include "Node.h"
17 #include "Alg7.h"
18 
19 #define TINYLOAD 0.0005
20 
21 Alg7::Alg7(computeInfo *computeArray, patchInfo *patchArray,
22  processorInfo *processorArray, int nComps,
23  int nPatches, int nPes) :
24  Rebalancer(computeArray, patchArray,
25  processorArray, nComps,
26  nPatches, nPes)
27 {
28 strategyName = "Alg7";
29 strategy();
30 }
31 
32 extern int isPmeProcessor(int);
33 
34 void Alg7::togrid(processorInfo* goodP[3][3][2], processorInfo* poorP[3][3][2],
35  processorInfo *p, computeInfo *c) {
36  if(p->available == false) return;
37 
38  int nPatches, nProxies, badForComm;
39  numAvailable(c,p,&nPatches,&nProxies,&badForComm);
40 
41  if (c->load + p->load < overLoad*averageLoad) {
42  processorInfo* &altp = goodP[nPatches][nProxies][badForComm];
43 
44 #if USE_TOPOMAP
45  if(!altp)
46  altp = p;
47  else {
48  //Find processors that are patch neighbors on the BGL torus
49  int neighbor = 0, neighbor_alt = 0;
50 
51  /*
52  if((tmgr->isNeighbor(altp->Id, patches[c->patch1].processor) ||
53  tmgr->isNeighbor(altp->Id, patches[c->patch2].processor)))
54  neighbor_alt = 1;
55 
56  if(tmgr->isNeighbor(p->Id, patches[c->patch1].processor) ||
57  tmgr->isNeighbor(p->Id, patches[c->patch2].processor))
58  neighbor = 1;
59  */
60 
61  if(tmgr.areNeighbors(altp->Id, patches[c->patch1].processor,
62  patches[c->patch2].processor, 4))
63  neighbor_alt = 1;
64 
65  if(tmgr.areNeighbors(p->Id, patches[c->patch1].processor,
66  patches[c->patch2].processor, 4))
67  neighbor = 1;
68 
69  if(neighbor_alt == 1 && neighbor == 1) {
70  //Both are neighbors, only replace if lighter
71  if (p->load < altp->load ) {
72  altp = p;
73  }
74  }
75  else if(neighbor_alt == 0 && neighbor == 1)
76  //Previous was not a neighbor, kick him out
77  altp = p;
78  else if(neighbor_alt == 1 && neighbor == 0)
79  ; //Give preference to good neighbors
80  else {
81  //Both not neighbors, choose nearby node to minimize hop bytes
82  /*
83  if (!altp || p->load < altp->load ) {
84  altp = p;
85  }
86  */
87 
88  int alt_dist = 0, dist = 0;
89  int ax,ay,az, x,y,z, p1x,p1y,p1z, p2x,p2y,p2z;
90 
91  tmgr.rankToCoordinates(altp->Id, ax,ay,az);
92  tmgr.rankToCoordinates(p->Id, x,y,z);
93  tmgr.rankToCoordinates(patches[c->patch1].processor, p1x, p1y, p1z);
94  tmgr.rankToCoordinates(patches[c->patch2].processor, p2x, p2y, p2z);
95 
96  alt_dist = abs(p1x - ax) + abs(p2x - ax) +
97  abs(p1y - ay) + abs(p1z - az) +
98  abs(p2y - ay) + abs(p2z - az);
99 
100  dist = abs(p1x - x) + abs(p2x - x) +
101  abs(p1y - y) + abs(p1z - z) +
102  abs(p2y - y) + abs(p2z - z);
103 
104  if(alt_dist > dist)
105  altp = p;
106  }
107  }
108 #else
109  if (!altp || p->load < altp->load ) {
110  altp = p;
111  }
112 #endif
113  }
114 
115  {
116  processorInfo* &altp = poorP[nPatches][nProxies][badForComm];
117  if (!altp || p->load < altp->load ) {
118  altp = p;
119  }
120  }
121 }
122 
123 void Alg7::strategy()
124 {
125  // double bestSize0, bestSize1, bestSize2;
126  computeInfo *c;
127  int numAssigned;
128  processorInfo* goodP[3][3][2]; // goodP[# of real patches][# of proxies]
129  processorInfo* poorP[3][3][2]; // fallback option
130 
131  double startTime = CmiWallTimer();
132 
133  // iout << iINFO << "calling makeHeaps. \n";
135  makeHeaps();
136  // iout << iINFO << "Before assignment\n" << endi;
137  // printLoads();
138 
139  /*
140  int numOverloaded = 0;
141  for (int ip=0; ip<P; ip++) {
142  if ( processors[ip].backgroundLoad > averageLoad ) ++numOverloaded;
143  }
144  if ( numOverloaded ) {
145  iout << iWARN << numOverloaded
146  << " processors are overloaded due to background load.\n" << endi;
147  }
148  */
149 
150  numAssigned = 0;
151 
152  // for (int i=0; i<numPatches; i++)
153  // { std::cout << "(" << patches[i].Id << "," << patches[i].processor ;}
154  overLoad = 1.2;
155  for (int ic=0; ic<numComputes; ic++) {
156 
157  // place computes w/ patches on heavily background loaded nodes first
158  // place pair before self, because self is more flexible
160  if ( ! c ) c = (computeInfo *) computeBgSelfHeap->deleteMax();
161  if ( ! c ) c = (computeInfo *) computePairHeap->deleteMax();
162  if ( ! c ) c = (computeInfo *) computeSelfHeap->deleteMax();
163 
164  if (c->processor != -1) continue; // skip to the next compute;
165 
166  if ( ! c ) NAMD_bug("Alg7: computesHeap empty!");
167  int i,j,k;
168  for(i=0;i<3;i++)
169  for(j=0;j<3;j++) {
170  for(k=0;k<2;k++) {
171  goodP[i][j][k]=0;
172  poorP[i][j][k]=0;
173  }
174  }
175 
176  // first try for at least one proxy
177  {
178  Iterator nextProc;
179  processorInfo *p;
180 
182  togrid(goodP, poorP, p, c);
183 
184  p = &processors[patches[c->patch2].processor];
185  togrid(goodP, poorP, p, c);
186 
187  p = (processorInfo *)patches[c->patch1].
188  proxiesOn.iterator((Iterator *)&nextProc);
189  while (p) {
190  togrid(goodP, poorP, p, c);
191  p = (processorInfo *)patches[c->patch1].
192  proxiesOn.next((Iterator*)&nextProc);
193  }
194 
195  p = (processorInfo *)patches[c->patch2].
196  proxiesOn.iterator((Iterator *)&nextProc);
197  while (p) {
198  togrid(goodP, poorP, p, c);
199  p = (processorInfo *)patches[c->patch2].
200  proxiesOn.next((Iterator*)&nextProc);
201  }
202  p = 0;
203  // prefer to place compute with existing proxies over home patches
204  if ((p = goodP[0][2][0]) // No home, two proxies
205  || (p = goodP[1][1][0]) // One home, one proxy
206  || (p = goodP[2][0][0]) // Two home, no proxies
207  || (p = goodP[0][1][0]) // No home, one proxy
208  || (p = goodP[1][0][0]) // One home, no proxies
209  || (p = goodP[0][0][0]) // No home, no proxies
210  || (p = goodP[0][1][1]) // No home, one proxy
211  || (p = goodP[1][0][1]) // One home, no proxies
212  || (p = goodP[0][0][1]) // No home, no proxies
213  ) {
214  assign(c,p); numAssigned++;
215  continue;
216  }
217  }
218 
219  // no luck, do it the long way
220 
221  heapIterator nextProcessor;
222  processorInfo *p = (processorInfo *)
223  pes->iterator((heapIterator *) &nextProcessor);
224  while (p) {
225  togrid(goodP, poorP, p, c);
226  p = (processorInfo *) pes->next(&nextProcessor);
227  }
228 
229  // if (numAssigned >= 0) { Else is commented out below
230 
231  p = 0;
232  // prefer to place compute with existing proxies over home patches
233  if ((p = goodP[0][2][0]) // No home, two proxies
234  || (p = goodP[1][1][0]) // One home, one proxy
235  || (p = goodP[2][0][0]) // Two home, no proxies
236  || (p = goodP[0][1][0]) // No home, one proxy
237  || (p = goodP[1][0][0]) // One home, no proxies
238  || (p = goodP[0][0][0]) // No home, no proxies
239  || (p = goodP[0][1][1]) // No home, one proxy
240  || (p = goodP[1][0][1]) // One home, no proxies
241  || (p = goodP[0][0][1]) // No home, no proxies
242  ) {
243  assign(c,p); numAssigned++;
244  } else if ( // overloaded processors
245  (p = poorP[0][2][0]) // No home, two proxies
246  || (p = poorP[1][1][0]) // One home, one proxy
247  || (p = poorP[2][0][0]) // Two home, no proxies
248  || (p = poorP[0][1][0]) // No home, one proxy
249  || (p = poorP[1][0][0]) // One home, no proxies
250  || (p = poorP[0][0][0]) // No home, no proxies
251  || (p = poorP[0][1][1]) // No home, one proxy
252  || (p = poorP[1][0][1]) // One home, no proxies
253  || (p = poorP[0][0][1]) // No home, no proxies
254  ) {
255  //iout << iWARN << "overload assign to " << p->Id << "\n" << endi;
256  assign(c,p); numAssigned++;
257  } else {
258  NAMD_bug("*** Alg 7 No receiver found 1 ***");
259  break;
260  }
261  }
262 
263  printLoads();
264 
265  if ( computeMax() <= origMaxLoad ) {
266  // binary-search refinement procedure
267  multirefine(1.05);
268  printLoads();
269  }
270 
271 }
272 
int numComputes
Definition: Rebalancer.h:138
int patch1
Definition: elements.h:23
Alg7(computeInfo *computeArray, patchInfo *patchArray, processorInfo *processorArray, int nComps, int nPatches, int nPes)
Definition: AlgSeven.C:21
int Id
Definition: elements.h:16
void assign(computeInfo *c, processorInfo *pRec)
Definition: Rebalancer.C:402
minHeap * pes
Definition: Rebalancer.h:131
double averageLoad
Definition: Rebalancer.h:141
int processor
Definition: elements.h:24
int isPmeProcessor(int)
Definition: ComputePme.C:604
processorInfo * processors
Definition: Rebalancer.h:130
void printLoads(int phase=0)
Definition: Rebalancer.C:874
void numAvailable(computeInfo *c, processorInfo *p, int *nPatches, int *nProxies, int *isBadForCommunication)
Definition: Rebalancer.C:1074
InfoRecord * next(heapIterator *)
Definition: heap.C:100
InfoRecord * deleteMax()
Definition: heap.C:152
void multirefine(double overload_start=1.02)
Definition: Rebalancer.C:784
int patch2
Definition: elements.h:23
void NAMD_bug(const char *err_msg)
Definition: common.C:129
maxHeap * computeBgSelfHeap
Definition: Rebalancer.h:135
maxHeap * computeSelfHeap
Definition: Rebalancer.h:133
gridSize z
maxHeap * computePairHeap
Definition: Rebalancer.h:132
void adjustBackgroundLoadAndComputeAverage()
Definition: Rebalancer.C:1023
double overLoad
Definition: Rebalancer.h:168
double load
Definition: elements.h:15
maxHeap * computeBgPairHeap
Definition: Rebalancer.h:134
Definition: Set.h:19
void makeHeaps()
Definition: Rebalancer.C:252
InfoRecord * iterator(heapIterator *)
Definition: heap.C:94
patchInfo * patches
Definition: Rebalancer.h:129
double origMaxLoad
Definition: Rebalancer.h:142
double computeMax()
Definition: Rebalancer.C:1057
gridSize y
int processor
Definition: elements.h:31
gridSize x
const char * strategyName
Definition: Rebalancer.h:127
bool available
Definition: elements.h:44