Add a lock-free synchronized queue.

[loba.git] / loba_bulk.cpp

diff --git a/loba_bulk.cpp b/loba_bulk.cpp
index 9af50cf0f22c3b4ec1d695dcdfdee97c252318d3..f5ec64ecfc0ffe9520e735364ebe75402f14d4bf 100644 (file)
--- a/loba_bulk.cpp
+++ b/loba_bulk.cpp
@@ -1,4 +1,5 @@
 #include <xbt/log.h>
 #include <xbt/log.h>

+#include <math.h>

 
 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(loba);
 
 
 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(loba);
 


@@ -6,8 +7,81 @@ XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(loba);
 
 void loba_bulk::load_balance()
 {
 
 void loba_bulk::load_balance()
 {

-    // write code here...
-    xbt_die("Load-balancing algorithm \"bulk\" not implemented!");
+       float myLoad = get_load();
+
+       unsigned NbNwMinLoad = 0;
+       unsigned NbNwLowerLoad = 0;
+       unsigned NbNeighbours = pneigh.size();
+
+       double *S = new double[NbNeighbours];
+       for (unsigned i = 0; i < NbNeighbours; i++) 
+               S[i] = 0.0;
+       //What is the minimum and maximum load under myLoad?
+       float minLoad = myLoad;
+       for (unsigned i = 0; i < NbNeighbours; i++) {
+               if (pneigh[i]->get_load() < minLoad) {
+                       minLoad = pneigh[i]->get_load();
+               }
+               if (pneigh[i]->get_load() < myLoad) {
+                       NbNwLowerLoad++;
+               }
+       }
+       for (unsigned i = 0; i < NbNeighbours; i++)
+               if (pneigh[i]->get_load() == minLoad)
+                       NbNwMinLoad++;
+
+       float maxLoad = minLoad;
+       for (unsigned i = 0; i < NbNeighbours; i++) {
+               if (pneigh[i]->get_load() > minLoad && pneigh[i]->get_load() < myLoad)
+                       if (maxLoad < pneigh[i]->get_load())
+                               maxLoad = pneigh[i]->get_load();
+       }
+
+       double alpha = 0.0;
+
+       if (NbNwLowerLoad && NbNwMinLoad < NbNwLowerLoad) //There is one or many neighbors with minimum load but not all neighbors have minimum load
+               alpha = (1. / ((double) NbNwMinLoad + 2));
+       if (NbNwMinLoad == NbNwLowerLoad) //All neighbors have minimum load
+               alpha = (1. / ((double) NbNwMinLoad + 1));
+       float myS = 0.;
+       //There exist underloaded neighbors
+       if (NbNwMinLoad && myLoad != 0.0) {
+               for (unsigned i = 0; i < NbNeighbours; i++) {
+                       if (pneigh[i]->get_load() == minLoad) {
+                               S[i] = floor(alpha * (myLoad - minLoad));
+                               myS +=  S[i];
+                       } else {
+                               if (pneigh[i]->get_load() < myLoad) {
+                                       S[i] = floor(alpha * (myLoad - pneigh[i]->get_load()));
+                                       myS +=  S[i];
+                               }
+                       }
+               }
+               //Check assumption 4.2 (b) page 520
+               bool HaveToCorrectS = false;
+               for (unsigned i = 0; i < NbNeighbours; i++) {
+                       if (pneigh[i]->get_load() < myLoad) { //
+                               //Condition 4.6
+                               if ((myLoad - myS) < (pneigh[i]->get_load() + S[i])) {
+                                       HaveToCorrectS = true;
+                               }
+                       }
+               }
+               if (HaveToCorrectS) {
+                               for (unsigned i = 0; i < NbNeighbours; i++) {
+                                       while (((myLoad - myS) < pneigh[i]->get_load() + S[i]) && (S[i] > 0)) {
+                                               myS -= 1.0;
+                                               S[i] -= 1.0;
+                                       }
+                               }
+               }
+       }//End there are underloaded neighbors;
+       for (unsigned i = 0 ; i < NbNeighbours ; i++) {
+                send(pneigh[i], S[i]);
+                XBT_DEBUG("sent to %s", pneigh[i]->get_name());
+        }
+
+       delete[] S;

 }
 
 // Local variables:
 }
 
 // Local variables: