From: Arnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Date: Thu, 3 Feb 2011 16:10:22 +0000 (+0100)
Subject: Add Makhoul's algorithm.
X-Git-Tag: v0.1~182
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba.git/commitdiff_plain/2e3129cd655efb5ccfa93000546cefd02b725154

Add Makhoul's algorithm.

Not tested.
---

diff --git a/loba_makhoul.cpp b/loba_makhoul.cpp
new file mode 100644
index 0000000..67a2359
--- /dev/null
+++ b/loba_makhoul.cpp
@@ -0,0 +1,33 @@
+#include <algorithm>
+#include <xbt/log.h>
+
+XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(loba);
+
+#include "loba_makhoul.h"
+
+class compare {
+public:
+    bool operator()(const neighbor*a, const neighbor*b) {
+        return a->get_load() < b->get_load();
+    }
+};
+
+void loba_makhoul::load_balance()
+{
+    std::sort(pneigh.begin(), pneigh.end(), compare());
+
+    print_loads_p(false, xbt_log_priority_debug);
+
+    double alpha = 1.0 / (pneigh.size() + 1.0);
+    double delta;
+    for (unsigned i = 0 ;
+         i < pneigh.size() &&
+             (delta = get_load() - pneigh[i]->get_load()) > 0.0 ;
+         ++i) {
+        send(pneigh[i], delta * alpha);
+    }
+}
+
+// Local variables:
+// mode: c++
+// End:
diff --git a/loba_makhoul.h b/loba_makhoul.h
new file mode 100644
index 0000000..46b6e55
--- /dev/null
+++ b/loba_makhoul.h
@@ -0,0 +1,19 @@
+#ifndef LOBA_MAKHOUL_H
+#define LOBA_MAKHOUL_H
+
+#include "process.h"
+
+class loba_makhoul: public process {
+public:
+    loba_makhoul(int argc, char* argv[]): process(argc, argv) { }
+    ~loba_makhoul()                                           { }
+
+private:
+    void load_balance();
+};
+
+#endif //!LOBA_MAKHOUL_H
+
+// Local variables:
+// mode: c++
+// End:
diff --git a/options.cpp b/options.cpp
index fd9da4e..96b53e0 100644
--- a/options.cpp
+++ b/options.cpp
@@ -11,6 +11,7 @@ XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(main);
 #include "process.h"
 #include "loba_simple.h"
 #include "loba_fairstrategy.h"
+#include "loba_makhoul.h"
 
 #include "options.h"
 
@@ -63,6 +64,7 @@ namespace opt {
     loba_algorithms_type::loba_algorithms_type()
     {
         NOL_INSERT("fairstrategy", "balance with fair strategy", loba_fairstrategy);
+        NOL_INSERT("makhoul", "balance with Makhoul's PhD algorithm", loba_makhoul);
         NOL_INSERT("none", "no load-balancing (for testing only)", process);
         NOL_INSERT("simple", "balance with least loaded neighbor", loba_simple);
     }