From: Arnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Date: Thu, 24 Feb 2011 18:21:19 +0000 (+0100)
Subject: Add algorithm makhoul2.
X-Git-Tag: v0.1~107
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba.git/commitdiff_plain/96354e7d7c0f2985a2e8c08ec0f1ce64c6775628?ds=sidebyside;hp=7afbddc7bce5654b4b49095f75066b13c166fb14

Add algorithm makhoul2.
---

diff --git a/ALGORITHMS b/ALGORITHMS
index bebaaa4..11e7099 100644
--- a/ALGORITHMS
+++ b/ALGORITHMS
@@ -29,6 +29,16 @@ ou bien
     - Algorithme 6 (p.111) dans la thèse de Abdallah Makhoul.
 
 
+makhoul2
+========
+Comme makhoul, mais la différence est calculée avec la charge courante
+(intégrant donc les envois déjà faits).
+
+Références:
+    - le code source :-(
+      cf. makhoul.txt
+
+
 none
 ====
 Aucun équilibrage.  Peut-être utile pour tester/déboguer le code.
diff --git a/loba_makhoul2.cpp b/loba_makhoul2.cpp
new file mode 100644
index 0000000..6d7d12e
--- /dev/null
+++ b/loba_makhoul2.cpp
@@ -0,0 +1,37 @@
+#include <xbt/log.h>
+
+XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(loba);
+
+#include "loba_makhoul2.h"
+
+// Note: adapted from Makhoul's code
+
+void loba_makhoul2::load_balance()
+{
+    pneigh_sort_by_load(std::less<double>());
+
+    print_loads_p(false, xbt_log_priority_debug);
+
+    double alpha = 1.0 / (pneigh.size() + 1.0);
+    double neighborLoadMax = 0.0; // maximum load of neighbors to
+                                  // which something has been sent
+    for (unsigned i = 0;
+         i < pneigh.size() && pneigh[i]->get_load() < get_load(); i++) {
+        double delta = get_load() - pneigh[i]->get_load();
+
+        // do not violate ping-pong condition
+        double transfer = std::min(alpha * delta, get_load() - neighborLoadMax);
+        XBT_DEBUG("delta = %g ; transfer = %g", delta, transfer);
+
+        send(pneigh[i], transfer);
+        XBT_DEBUG("sent %g to %s", transfer, pneigh[i]->get_name());
+
+        double newNeighborLoad = pneigh[i]->get_load();
+        if (newNeighborLoad > neighborLoadMax)
+            neighborLoadMax = newNeighborLoad;
+    }
+}
+
+// Local variables:
+// mode: c++
+// End:
diff --git a/loba_makhoul2.h b/loba_makhoul2.h
new file mode 100644
index 0000000..8cff03e
--- /dev/null
+++ b/loba_makhoul2.h
@@ -0,0 +1,19 @@
+#ifndef LOBA_MAKHOUL2_H
+#define LOBA_MAKHOUL2_H
+
+#include "process.h"
+
+class loba_makhoul2: public process {
+public:
+    loba_makhoul2(int argc, char* argv[]): process(argc, argv) { }
+    ~loba_makhoul2()                                           { }
+
+private:
+    void load_balance();
+};
+
+#endif //!LOBA_MAKHOUL2_H
+
+// Local variables:
+// mode: c++
+// End:
diff --git a/options.cpp b/options.cpp
index 0d269d6..837aac7 100644
--- a/options.cpp
+++ b/options.cpp
@@ -12,6 +12,7 @@ XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(main);
 #include "loba_simple.h"
 #include "loba_fairstrategy.h"
 #include "loba_makhoul.h"
+#include "loba_makhoul2.h"
 #include "misc.h"
 
 #include "options.h"
@@ -74,6 +75,8 @@ namespace opt {
                    loba_fairstrategy);
         NOL_INSERT("makhoul", "balance with Makhoul's PhD algorithm",
                    loba_makhoul);
+        NOL_INSERT("makhoul2", "balance with Makhoul's source code",
+                   loba_makhoul2);
         NOL_INSERT("none", "no load-balancing (for testing only)",
                    process);
         NOL_INSERT("simple", "balance with least loaded neighbor",