Load Balancing strategy with Heap
authorSameer Paranjpye <paranjpy@uiuc.edu>
Thu, 14 Oct 1999 00:55:36 +0000 (00:55 +0000)
committerSameer Paranjpye <paranjpy@uiuc.edu>
Thu, 14 Oct 1999 00:55:36 +0000 (00:55 +0000)
src/ck-ldb/HeapCentLB.C [new file with mode: 0644]
src/ck-ldb/HeapCentLB.ci [new file with mode: 0644]
src/ck-ldb/HeapCentLB.decl.h [new file with mode: 0644]
src/ck-ldb/HeapCentLB.def.h [new file with mode: 0644]
src/ck-ldb/HeapCentLB.h [new file with mode: 0644]

diff --git a/src/ck-ldb/HeapCentLB.C b/src/ck-ldb/HeapCentLB.C
new file mode 100644 (file)
index 0000000..c8327f0
--- /dev/null
@@ -0,0 +1,154 @@
+#include <charm++.h>
+
+#if CMK_LBDB_ON
+
+#if CMK_STL_USE_DOT_H
+#include <deque.h>
+#include <queue.h>
+#else
+#include <deque>
+#include <queue>
+#endif
+
+#include "HeapCentLB.h"
+#include "HeapCentLB.def.h"
+
+#if CMK_STL_USE_DOT_H
+template class deque<CentralLB::MigrateInfo>;
+#else
+template class std::deque<CentralLB::MigrateInfo>;
+#endif
+
+void CreateHeapCentLB()
+{
+  CkPrintf("[%d] creating HeapCentLB %d\n",CkMyPe(),loadbalancer);
+  loadbalancer = CProxy_HeapCentLB::ckNew();
+  CkPrintf("[%d] created RandCentLB %d\n",CkMyPe(),loadbalancer);
+}
+
+HeapCentLB::HeapCentLB()
+{
+  CkPrintf("[%d] RandCentLB created\n",CkMyPe());
+}
+
+CmiBool HeapCentLB::QueryBalanceNow(int _step)
+{
+  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
+  return CmiTrue;
+}
+
+void Heapify(HeapData *heap, int node, int heapSize)
+{
+       int left = 2*node+1;
+       int right = 2*node+2;
+       int largest;
+
+       if (left <= heapSize && heap[left].cpuTime < heap[node].cpuTime)
+               largest = left;
+       else largest = node;
+       
+       if (right <= heapSize && heap[right].cpuTime < heap[largest].cpuTime) 
+               largest = right;
+
+       if (largest != node) {
+               HeapData obj;
+               obj = heap[node];
+               heap[node] = heap[largest];
+               heap[largest] = obj;
+               Heapify(heap, largest, heapSize);
+       }
+               
+}
+
+
+CLBMigrateMsg* HeapCentLB::Strategy(CentralLB::LDStats* stats, int count)
+{
+  CkPrintf("[%d] HeapCentLB strategy\n",CkMyPe());
+
+#if CMK_STL_USE_DOT_H
+  queue<MigrateInfo> migrateInfo;
+#else
+  std::queue<MigrateInfo> migrateInfo;
+#endif
+       
+       int totalObjs = 0;
+       HeapData *cpuData = new HeapData[count];
+       HeapData *objData;
+
+       for (int pe=0; pe < count; pe++) {
+               totalObjs += stats[pe].n_objs;
+               cpuData[pe].cpuTime = 0.;
+               cpuData[pe].pe = cpuData[pe].id = pe;
+       }
+
+       objData = new HeapData[totalObjs];
+       int objCount = 0;
+  for(int pe=0; pe < count; pe++) {
+    CkPrintf("[%d] PE %d : %d Objects : %d Communication\n",
+            CkMyPe(),pe,stats[pe].n_objs,stats[pe].n_comm);
+
+    for(int obj=0; obj < stats[pe].n_objs; obj++, objCount++) {
+
+                       objData[objCount].cpuTime = stats[pe].objData[obj].cpuTime;
+                       objData[objCount].pe = pe;
+                       objData[objCount].id = obj;
+               }
+       }
+
+       for (int obj=1; obj < totalObjs; obj++) {
+               HeapData key = objData[obj];
+               int i = obj-1;
+               while (i >=0 && objData[i].cpuTime < key.cpuTime) {
+                       objData[i+1] = objData[i];
+                       i--;
+               }
+               objData[i+1] = key;
+       }
+
+       int heapSize = count-1;
+       HeapData minCpu;        
+       for (int obj=0; obj < totalObjs; obj++) {
+
+               //Operation of extracting the minimum(the least loaded processor) from the heap
+               minCpu = cpuData[0];
+               cpuData[0] = cpuData[heapSize];
+               heapSize--;
+               Heapify(cpuData, 0, heapSize);          
+
+               //Increment the time of the least loaded processor by the cpuTime of the `heaviest' object
+               minCpu.cpuTime += objData[obj].cpuTime;
+
+    //Insert object into migration queue if necessary
+               const int dest = minCpu.pe;
+               const int pe   = objData[obj].pe;
+               const int id   = objData[obj].id;
+               if (dest != pe) {
+                       CkPrintf("[%d] Obj %d migrating from %d to %d\n",
+                                                        CkMyPe(),obj,pe,dest);
+                       MigrateInfo migrateMe;
+                       migrateMe.obj = stats[pe].objData[id].handle;
+                       migrateMe.from_pe = pe;
+                       migrateMe.to_pe = dest;
+                       migrateInfo.push(migrateMe);
+               }
+               
+               //Insert the least loaded processor with load updated back into the heap
+               heapSize++;
+               int location = heapSize;
+               while (location>0 && cpuData[(location-1)/2].cpuTime > minCpu.cpuTime) {
+                       cpuData[location] = cpuData[(location-1)/2];
+                       location = (location-1)/2;
+               }
+               cpuData[location] = minCpu;
+       }
+  int migrate_count=migrateInfo.size();
+  CLBMigrateMsg* msg = new(&migrate_count,1) CLBMigrateMsg;
+  msg->n_moves = migrate_count;
+  for(int i=0; i < migrate_count; i++) {
+    msg->moves[i] = migrateInfo.front();
+    migrateInfo.pop();
+  }
+  return msg;
+};
+
+#endif
diff --git a/src/ck-ldb/HeapCentLB.ci b/src/ck-ldb/HeapCentLB.ci
new file mode 100644 (file)
index 0000000..5c88b70
--- /dev/null
@@ -0,0 +1,9 @@
+module HeapCentLB {
+
+extern module CentralLB;
+
+group HeapCentLB : CentralLB {
+  entry void HeapCentLB(void);  
+};
+
+};
diff --git a/src/ck-ldb/HeapCentLB.decl.h b/src/ck-ldb/HeapCentLB.decl.h
new file mode 100644 (file)
index 0000000..11cacaa
--- /dev/null
@@ -0,0 +1,45 @@
+#ifndef _DECL_HeapCentLB_H_
+#define _DECL_HeapCentLB_H_
+#include "charm++.h"
+#include "CentralLB.decl.h"
+
+/* DECLS: group HeapCentLB: CentralLB{
+void HeapCentLB(void);
+};
+ */
+class HeapCentLB;
+class CProxy_HeapCentLB:  public virtual _CK_GID, public CProxy_CentralLB{
+  public:
+    static int __idx;
+static void __register(const char *s, size_t size) {
+  __idx = CkRegisterChare(s, size);
+  _REGISTER_BASE(__idx, CProxy_CentralLB::__idx);
+/* REG: void HeapCentLB(void);
+ */
+  __idx_HeapCentLB_void = CkRegisterEp("HeapCentLB", (CkCallFnPtr)_call_HeapCentLB_void, 0, __idx);
+}
+    CProxy_HeapCentLB(CkGroupID _gid) :CProxy_CentralLB(_gid){ _ck_gid = _gid; _setChare(0); }
+    CProxy_HeapCentLB(CkChareID __cid) :CProxy_CentralLB(__cid){ ckSetChareId(__cid); }
+    CkChareID ckGetChareId(void) { return _ck_cid; }
+    void ckSetChareId(CkChareID __cid){_CHECK_CID(__cid,__idx);_ck_cid=__cid;_setChare(1);}
+    CkGroupID ckGetGroupId(void) { return _ck_gid; }
+   void ckSetGroupId(CkGroupID _gid){_ck_gid=_gid;_setChare(0);}
+    HeapCentLB* ckLocalBranch(void) {
+      return (HeapCentLB *) CkLocalBranch(_ck_gid);
+    }
+    static HeapCentLB* ckLocalBranch(CkGroupID gID) {
+      return (HeapCentLB *) CkLocalBranch(gID);
+    }
+/* DECLS: void HeapCentLB(void);
+ */
+    static int __idx_HeapCentLB_void;
+    static CkGroupID ckNew(void);
+    static CkGroupID ckNewSync(void);
+    CProxy_HeapCentLB(int retEP, CkChareID *cid);
+    CProxy_HeapCentLB(void);
+    static int ckIdx_HeapCentLB(void) { return __idx_HeapCentLB_void; }
+    static void  _call_HeapCentLB_void(void* msg, HeapCentLB* obj);
+};
+
+extern void _registerHeapCentLB(void);
+#endif
diff --git a/src/ck-ldb/HeapCentLB.def.h b/src/ck-ldb/HeapCentLB.def.h
new file mode 100644 (file)
index 0000000..54baecc
--- /dev/null
@@ -0,0 +1,55 @@
+
+/* DEFS: group HeapCentLB: CentralLB{
+void HeapCentLB(void);
+};
+ */
+#ifndef CK_TEMPLATES_ONLY
+int CProxy_HeapCentLB::__idx=0;
+#endif
+/* DEFS: void HeapCentLB(void);
+ */
+#ifndef CK_TEMPLATES_ONLY
+int CProxy_HeapCentLB::__idx_HeapCentLB_void=0;
+CkGroupID CProxy_HeapCentLB::ckNew(void)
+{
+  void *msg = CkAllocSysMsg();
+  return CkCreateGroup(__idx, __idx_HeapCentLB_void, msg, 0, 0);
+}
+CkGroupID CProxy_HeapCentLB::ckNewSync(void)
+{
+  void *msg = CkAllocSysMsg();
+  return CkCreateGroupSync(__idx, __idx_HeapCentLB_void, msg);
+}
+ CProxy_HeapCentLB::CProxy_HeapCentLB(int retEP, CkChareID *cid)
+{
+  void *msg = CkAllocSysMsg();
+  _ck_gid = CkCreateGroup(__idx, __idx_HeapCentLB_void, msg, retEP, cid);
+  _setChare(0);
+}
+ CProxy_HeapCentLB::CProxy_HeapCentLB(void)
+{
+  void *msg = CkAllocSysMsg();
+  _ck_gid = CkCreateGroup(__idx, __idx_HeapCentLB_void, msg, 0, 0);
+  _setChare(0);
+}
+ void CProxy_HeapCentLB::_call_HeapCentLB_void(void* msg, HeapCentLB* obj)
+{
+  new (obj) HeapCentLB();
+  CkFreeSysMsg(msg);
+}
+#endif
+
+#ifndef CK_TEMPLATES_ONLY
+void _registerHeapCentLB(void)
+{
+  static int _done = 0; if (_done) return; _done = 1;
+  _registerCentralLB();
+
+/* REG: group HeapCentLB: CentralLB{
+void HeapCentLB(void);
+};
+ */
+  CProxy_HeapCentLB::__register("HeapCentLB", sizeof(HeapCentLB));
+
+}
+#endif
diff --git a/src/ck-ldb/HeapCentLB.h b/src/ck-ldb/HeapCentLB.h
new file mode 100644 (file)
index 0000000..d162c97
--- /dev/null
@@ -0,0 +1,25 @@
+#ifndef _HEAPCENTLB_H_
+#define _HEAPCENTLB_H_
+
+#include "CentralLB.h"
+#include "HeapCentLB.decl.h"
+
+void CreateHeapCentLB();
+
+class HeapCentLB : public CentralLB {
+
+struct HeapData {
+       float cpuTime;
+       int   pe;
+       int   id;
+};
+
+public:
+  HeapCentLB();
+private:
+       void    Heapify(HeapData *, int, int)
+  CmiBool QueryBalanceNow(int step);
+  CLBMigrateMsg* Strategy(CentralLB::LDStats* stats, int count);
+};
+
+#endif /* _HEAPCENTLB_H_ */