a various optimizatons for multicore:
authorGengbin Zheng <gzheng@illinois.edu>
Fri, 5 Dec 2008 22:02:17 +0000 (22:02 +0000)
committerGengbin Zheng <gzheng@illinois.edu>
Fri, 5 Dec 2008 22:02:17 +0000 (22:02 +0000)
1. fix for SMP run
2.  exchanging load with neighbors are using direct access
3.  send token to neighbors use simple one-by-one sends to avoid building array of messages for multiple send. (SyncSendAndFree is efficient enough for SMP)
4. tweak formular of sending how many tokens to underloaded processors

src/conv-ldb/cldb.c
src/conv-ldb/cldb.h
src/conv-ldb/cldb.neighbor.c

index 0eca21ef21eae648cfa0caaa7a004c81de7831ba..7face2f07454b1bc257cad9043a16d3626af9504 100644 (file)
@@ -126,6 +126,17 @@ int CldLoad(void)
   return (CsdLength() - CpvAccess(CldLoadOffset));
 }
 
+int CldLoadRank(int rank)
+{
+  int len, offset;
+  /* CmiLock(CpvAccessOther(cldLock, rank));  */
+  len = CqsLength(CpvAccessOther(CsdSchedQueue, rank));
+     /* CldLoadOffset is the empty token counter */
+  offset = CpvAccessOther(CldLoadOffset, rank);
+  /* CmiUnlock(CpvAccessOther(cldLock, rank)); */
+  return len - offset;
+}
+
 void CldPutToken(char *msg)
 {
   CldProcInfo proc = CpvAccess(CldProc);
@@ -152,6 +163,7 @@ void CldPutToken(char *msg)
   CmiUnlock(CpvAccess(cldLock));
 }
 
+
 static void * _CldGetTokenMsg(CldProcInfo proc)
 {
   CldToken tok;
@@ -172,10 +184,11 @@ static void * _CldGetTokenMsg(CldProcInfo proc)
 void CldGetToken(char **msg)
 {
   CldProcInfo proc = CpvAccess(CldProc);
-  CmiLock(CpvAccess(cldLock));
+  CmiNodeLock cldlock = CpvAccess(cldLock);
+  CmiLock(cldlock);
   *msg = _CldGetTokenMsg(proc);
   if (*msg) CpvAccess(CldLoadOffset)++;
-  CmiUnlock(CpvAccess(cldLock));
+  CmiUnlock(cldlock);
 }
 
 /* called at node level */
@@ -183,10 +196,11 @@ void CldGetToken(char **msg)
 static void CldGetTokenFromRank(char **msg, int rank)
 {
   CldProcInfo proc = CpvAccessOther(CldProc, rank);
-  CmiLock(CpvAccessOther(cldLock, rank));
+  CmiNodeLock cldlock = CpvAccessOther(cldLock, rank);
+  CmiLock(cldlock);
   *msg = _CldGetTokenMsg(proc);
   if (*msg) CpvAccessOther(CldLoadOffset, rank)++;
-  CmiUnlock(CpvAccessOther(cldLock, rank));
+  CmiUnlock(cldlock);
 }
 
 /* Bit Vector Stuff */
@@ -269,6 +283,7 @@ void CldMultipleSend(int pe, int numToSend, int rank, int immed)
 
   if (numToSend == 0)
     return;
+
   msgs = (char **)calloc(numToSend, sizeof(char *));
   msgSizes = (int *)calloc(numToSend, sizeof(int));
 
@@ -319,3 +334,35 @@ void CldMultipleSend(int pe, int numToSend, int rank, int immed)
   free(msgSizes);
 }
 
+/* simple scheme - just send one by one. useful for multicore */
+void CldSimpleMultipleSend(int pe, int numToSend)
+{
+  char *msg;
+  int len, queueing, priobits, *msgSizes, i, numSent, done=0;
+  unsigned int *prioptr;
+  CldInfoFn ifn;
+  CldPackFn pfn;
+
+  if (numToSend == 0)
+    return;
+
+  numSent = 0;
+  while (!done) {
+    for (i=0; i<numToSend; i++) {
+      CldGetToken(&msg);
+      if (msg != 0) {
+       done = 1;
+       numToSend--;
+       ifn = (CldInfoFn)CmiHandlerToFunction(CmiGetInfo(msg));
+       ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
+       CldSwitchHandler(msg, CpvAccessOther(CldBalanceHandlerIndex, pe));
+        CmiSyncSendAndFree(pe, len, msg);
+        if (numToSend == 0) done = 1;
+      }
+      else {
+       done = 1;
+       break;
+      }
+    }
+  }
+}
index bd78e0c7e1c6757fa60a236faa6b7e8de54627e5..d184e5fde45ececd449d17165349ef2fab725fbb 100644 (file)
@@ -14,9 +14,11 @@ CpvExtern(int, CldLoadNotify);
 CpvExtern(CmiNodeLock, cldLock);
 
 void CldMultipleSend(int pe, int numToSend, int rank, int immed);
+void CldSimpleMultipleSend(int pe, int numToSend);
 void CldSetPEBitVector(const char *);
 
 int  CldLoad(void);
+int  CldLoadRank(int rank);
 int  CldCountTokens(void);
 void CldPutToken(char *);
 void CldRestoreHandler(char *);
index bbd3dbb7709dc945c4ced70c256b2505586e4f66..770580fa36364d712b0a8399e182387ef13b2c22 100644 (file)
@@ -139,6 +139,24 @@ static void CldAskLoadHandler(requestmsg *msg)
 
 void CldSendLoad()
 {
+#if CMK_MULTICORE
+  /* directly send load to neighbors */
+  double myload = CldLoad();
+  int nNeighbors = CpvAccess(numNeighbors);
+  int i;
+  for (i=0; i<nNeighbors; i++) {
+    int neighbor_pe = CpvAccess(neighbors)[i].pe;
+    int j, found=0;
+    for (j=0; j<CpvAccessOther(numNeighbors, neighbor_pe); j++)
+      if (CpvAccessOther(neighbors, neighbor_pe)[j].pe == CmiMyPe())
+      {
+        CpvAccessOther(neighbors, neighbor_pe)[j].load = myload;
+        found = 1;
+        break;
+      }
+    CmiAssert(found == 1);
+  }
+#else
   loadmsg msg;
 
   msg.pe = CmiMyPe();
@@ -146,6 +164,7 @@ void CldSendLoad()
   CmiSetHandler(&msg, CpvAccess(CldLoadResponseHandlerIndex));
   CmiSyncMulticast(CpvAccess(neighborGroup), sizeof(loadmsg), &msg);
   CpvAccess(CldLoadBalanceMessages) += CpvAccess(numNeighbors);
+#endif
 }
 
 int CldMinAvg()
@@ -153,14 +172,22 @@ int CldMinAvg()
   int sum=0, i;
   static int start=-1;
 
+  int nNeighbors = CpvAccess(numNeighbors);
   if (start == -1)
-    start = CmiMyPe() % CpvAccess(numNeighbors);
+    start = CmiMyPe() % nNeighbors;
+
+#if 0
+    /* update load from neighbors for multicore */
+  for (i=0; i<nNeighbors; i++) {
+    CpvAccess(neighbors)[i].load = CldLoadRank(CpvAccess(neighbors)[i].pe);
+  }
+#endif
   CpvAccess(MinProc) = CpvAccess(neighbors)[start].pe;
   CpvAccess(MinLoad) = CpvAccess(neighbors)[start].load;
   sum = CpvAccess(neighbors)[start].load;
   CpvAccess(Mindex) = start;
-  for (i=1; i<CpvAccess(numNeighbors); i++) {
-    start = (start+1) % CpvAccess(numNeighbors);
+  for (i=1; i<nNeighbors; i++) {
+    start = (start+1) % nNeighbors;
     sum += CpvAccess(neighbors)[start].load;
     if (CpvAccess(MinLoad) > CpvAccess(neighbors)[start].load) {
       CpvAccess(MinLoad) = CpvAccess(neighbors)[start].load;
@@ -168,13 +195,13 @@ int CldMinAvg()
       CpvAccess(Mindex) = start;
     }
   }
-  start = (start+2) % CpvAccess(numNeighbors);
+  start = (start+2) % nNeighbors;
   sum += CldLoad();
   if (CldLoad() < CpvAccess(MinLoad)) {
     CpvAccess(MinLoad) = CldLoad();
     CpvAccess(MinProc) = CmiMyPe();
   }
-  i = (int)(1.0 + (((float)sum) /((float)(CpvAccess(numNeighbors)+1))));
+  i = (int)(1.0 + (((float)sum) /((float)(nNeighbors+1))));
   return i;
 }
 
@@ -194,7 +221,8 @@ void CldBalance()
     overload = CldCountTokens();
 
   if (overload > MAXOVERLOAD) {
-    for (i=0; i<CpvAccess(numNeighbors); i++)
+    int nNeighbors = CpvAccess(numNeighbors);
+    for (i=0; i<nNeighbors; i++)
       if (CpvAccess(neighbors)[i].load < avgLoad) {
         totalUnderAvg += avgLoad-CpvAccess(neighbors)[i].load;
         if (avgLoad - CpvAccess(neighbors)[i].load > maxUnderAvg)
@@ -202,14 +230,17 @@ void CldBalance()
         numUnderAvg++;
       }
     if (numUnderAvg > 0)
-      for (i=0; ((i<CpvAccess(numNeighbors)) && (overload>0)); i++) {
+      for (i=0; ((i<nNeighbors) && (overload>0)); i++) {
        j = (i+CpvAccess(Mindex))%CpvAccess(numNeighbors);
         if (CpvAccess(neighbors)[j].load < avgLoad) {
-          numToMove = avgLoad - CpvAccess(neighbors)[j].load;
+          numToMove = (avgLoad - CpvAccess(neighbors)[j].load)/numUnderAvg;
           if (numToMove > overload)
             numToMove = overload;
           overload -= numToMove;
          CpvAccess(neighbors)[j].load += numToMove;
+#if CMK_MULTICORE
+          CldSimpleMultipleSend(CpvAccess(neighbors)[j].pe, numToMove);
+#else
           CldMultipleSend(CpvAccess(neighbors)[j].pe, 
                          numToMove, CmiMyRank(), 
 #if CMK_SMP
@@ -218,6 +249,7 @@ void CldBalance()
                          1
 #endif
                           );
+#endif
         }
       }
   }
@@ -515,17 +547,22 @@ void CldGraphModuleInit(char **argv)
     CldReadNeighborData();
 #endif
     CldComputeNeighborData();
+#if CMK_MULTICORE
+    CmiNodeBarrier();
+#endif
     CldBalance();
   }
 
 #if 1
-  CmiGetArgStringDesc(argv, "+workstealing", &_lbsteal, "Enable work stealing at idle time");
+  _lbsteal = CmiGetArgFlagDesc(argv, "+workstealing", "Charm++> Enable work stealing at idle time");
   if (_lbsteal) {
   /* register idle handlers - when idle, keep asking work from neighbors */
   CcdCallOnConditionKeep(CcdPROCESSOR_BEGIN_IDLE,
       (CcdVoidFn) CldStillIdle, NULL);
   CcdCallOnConditionKeep(CcdPROCESSOR_STILL_IDLE,
       (CcdVoidFn) CldStillIdle, NULL);
+    if (CmiMyPe() == 0) 
+      CmiPrintf("Charm++> Work stealing is enabled. \n");
   }
 #endif
 }
@@ -540,8 +577,8 @@ void CldModuleInit(char **argv)
   CpvAccess(CldRelocatedMessages) = CpvAccess(CldLoadBalanceMessages) = 
   CpvAccess(CldMessageChunks) = 0;
 
-  CpvAccess(CldLoadNotify) = 1;
-
   CldModuleGeneralInit(argv);
   CldGraphModuleInit(argv);
+
+  CpvAccess(CldLoadNotify) = 1;
 }