doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / NeighborLB.C
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 #include "elements.h"
7 #include "ckheap.h"
8 #include "NeighborLB.h"
9
10 CreateLBFunc_Def(NeighborLB, "The neighborhood load balancer")
11
12 NeighborLB::NeighborLB(const CkLBOptions &opt):NborBaseLB(opt)
13 {
14   lbname = "NeighborLB";
15   if (CkMyPe() == 0)
16     CkPrintf("[%d] NeighborLB created\n",CkMyPe());
17 }
18
19 LBMigrateMsg* NeighborLB::Strategy(NborBaseLB::LDStats* stats, int n_nbrs)
20 {
21 #if CMK_LBDB_ON
22   //  CkPrintf("[%d] Strategy starting\n",CkMyPe());
23   // Compute the average load to see if we are overloaded relative
24   // to our neighbors
25   double myload = myStats.total_walltime - myStats.idletime;
26   double avgload = myload;
27   int i;
28   for(i=0; i < n_nbrs; i++) {
29     // Scale times we need appropriately for relative proc speeds
30     const double scale =  ((double)myStats.pe_speed) 
31       / stats[i].pe_speed;
32
33     stats[i].total_walltime *= scale;
34     stats[i].idletime *= scale;
35
36     avgload += (stats[i].total_walltime - stats[i].idletime);
37   }
38   avgload /= (n_nbrs + 1);
39
40   CkVec<MigrateInfo*> migrateInfo;
41
42   if (myload > avgload) {
43     if (_lb_args.debug()>1) 
44       CkPrintf("[%d] OVERLOAD My load is %f, average load is %f\n", CkMyPe(),myload,avgload);
45
46     // First, build heaps of other processors and my objects
47     // Then assign objects to other processors until either
48     //   - The smallest remaining object would put me below average, or
49     //   - I only have 1 object left, or
50     //   - The smallest remaining object would put someone else 
51     //     above average
52
53     // Build heaps
54     minHeap procs(n_nbrs);
55     for(i=0; i < n_nbrs; i++) {
56       InfoRecord* item = new InfoRecord;
57       item->load = stats[i].total_walltime - stats[i].idletime;
58       item->Id =  stats[i].from_pe;
59       procs.insert(item);
60     }
61       
62     maxHeap objs(myStats.n_objs);
63     for(i=0; i < myStats.n_objs; i++) {
64       InfoRecord* item = new InfoRecord;
65       item->load = myStats.objData[i].wallTime;
66       item->Id = i;
67       objs.insert(item);
68     }
69
70     int objs_here = myStats.n_objs;
71     do {
72       if (objs_here <= 1) break;  // For now, always leave 1 object
73
74       InfoRecord* p;
75       InfoRecord* obj;
76
77       // Get the lightest-loaded processor
78       p = procs.deleteMin();
79       if (p == 0) {
80         //      CkPrintf("[%d] No destination PE found!\n",CkMyPe());
81         break;
82       }
83
84       // Get the biggest object
85       CmiBool objfound = CmiFalse;
86       do {
87         obj = objs.deleteMax();
88         if (obj == 0) break;
89
90         double new_p_load = p->load + obj->load;
91         double my_new_load = myload - obj->load;
92         if (new_p_load < my_new_load) {
93 //      if (new_p_load < avgload) {
94           objfound = CmiTrue;
95         } else {
96           // This object is too big, so throw it away
97 //        CkPrintf("[%d] Can't move object w/ load %f to proc %d load %f %f\n",
98 //                 CkMyPe(),obj->load,p->Id,p->load,avgload);
99           delete obj;
100         }
101       } while (!objfound);
102
103       if (!objfound) {
104         if (_lb_args.debug()>2) 
105           CkPrintf("[%d] No suitable object found!\n",CkMyPe());
106         break;
107       }
108
109       const int me = CkMyPe();
110       // Apparently we can give this object to this processor
111       //      CkPrintf("[%d] Obj %d of %d migrating from %d to %d\n",
112       //               CkMyPe(),obj->Id,myStats.n_objs,me,p->Id);
113
114       MigrateInfo* migrateMe = new MigrateInfo;
115       migrateMe->obj = myStats.objData[obj->Id].handle;
116       migrateMe->from_pe = me;
117       migrateMe->to_pe = p->Id;
118       migrateInfo.insertAtEnd(migrateMe);
119
120       objs_here--;
121       
122       // We may want to assign more to this processor, so lets
123       // update it and put it back in the heap
124       p->load += obj->load;
125       myload -= obj->load;
126       procs.insert(p);
127       
128       // This object is assigned, so we delete it from the heap
129       delete obj;
130
131     } while(myload > avgload);
132
133     // Now empty out the heaps
134     InfoRecord* p;
135     while (NULL!=(p=procs.deleteMin()))
136       delete p;
137
138     InfoRecord* obj;
139     while (NULL!=(obj=objs.deleteMax()))
140       delete obj;
141   }  
142
143   // Now build the message to actually perform the migrations
144   int migrate_count=migrateInfo.length();
145   //  if (migrate_count > 0) {
146   //    CkPrintf("PE %d migrating %d elements\n",CkMyPe(),migrate_count);
147   //  }
148   LBMigrateMsg* msg = new(migrate_count,CkNumPes(),CkNumPes(),0) LBMigrateMsg;
149   msg->n_moves = migrate_count;
150   for(i=0; i < migrate_count; i++) {
151     MigrateInfo* item = (MigrateInfo*) migrateInfo[i];
152     msg->moves[i] = *item;
153     delete item;
154     migrateInfo[i] = 0;
155   }
156
157   return msg;
158 #else
159   return NULL;
160 #endif
161 }
162
163 #include "NeighborLB.def.h"
164
165 /*@}*/