From: Arnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Date: Fri, 3 Jun 2011 10:15:45 +0000 (+0200)
Subject: Add algorithm 2besteffort.
X-Git-Tag: v0.1~54
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba.git/commitdiff_plain/e101542b2694675251352f799e903d171a17b1a5?hp=bce2d1712db2962582aec9f56e78ec4c496cef67

Add algorithm 2besteffort.
---

diff --git a/ALGORITHMS b/ALGORITHMS
index f77223d..d73b675 100644
--- a/ALGORITHMS
+++ b/ALGORITHMS
@@ -1,5 +1,19 @@
 DESCRIPTIONS DES ALGORITHMES D'ÉQUILIBRAGE
 
+2besteffort
+===========
+Calcule la moyenne des charges des voisins et de soi-même.
+Ordonne ensuite les voisins du moins chargé au plus chargé, et
+effectue les transferts en prenant les voisins dans cet ordre.  Les
+transferts de charge sont faits en visant cette moyenne pour tous les
+voisins.  On envoie une quantité de charge égale à
+        min(moyenne - charge_du_voisin, charge_propre - moyenne),
+tant que cette quantité est positive.
+
+NB: Ceci est une variante de besteffort, la différence étant la
+    moyenne visée.
+
+
 besteffort
 ==========
 Ordonne les voisins du moins chargé au plus chargé.
diff --git a/loba_2besteffort.cpp b/loba_2besteffort.cpp
new file mode 100644
index 0000000..967476e
--- /dev/null
+++ b/loba_2besteffort.cpp
@@ -0,0 +1,41 @@
+#include <cmath>                // std::isfinite
+#include <functional>
+#include <numeric>
+#include <xbt/log.h>
+
+XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(loba);
+
+#include "loba_2besteffort.h"
+
+void loba_2besteffort::load_balance()
+{
+    using std::placeholders::_1;
+    using std::placeholders::_2;
+
+    pneigh_sort_by_load(std::less<double>());
+    print_loads_p(false, xbt_log_priority_debug);
+
+    double sum = get_load() +
+        std::accumulate(pneigh.begin(), pneigh.end(), 0.0,
+                        std::bind(std::plus<double>(), _1,
+                                  std::bind(&neighbor::get_load, _2)));
+    double mean = sum / (pneigh.size() + 1);
+    XBT_DEBUG("sum = %g ; mean = %g", sum, mean);
+
+    if (!std::isfinite(mean))
+        return;
+
+    for (unsigned i = 0 ; i < pneigh.size() ; ++i) {
+        double transfer = std::min(mean - pneigh[i]->get_load(),
+                                   get_load() - mean);
+        // don't continue if get_load() <= mean, or pneigh[i]->get_load >= mean
+        if (transfer <= 0.0)
+            break;
+        send(pneigh[i], transfer);
+        XBT_DEBUG("sent %g to %s", transfer, pneigh[i]->get_name());
+    }
+}
+
+// Local variables:
+// mode: c++
+// End:
diff --git a/loba_2besteffort.h b/loba_2besteffort.h
new file mode 100644
index 0000000..ab22941
--- /dev/null
+++ b/loba_2besteffort.h
@@ -0,0 +1,19 @@
+#ifndef LOBA_2BESTEFFORT_H
+#define LOBA_2BESTEFFORT_H
+
+#include "process.h"
+
+class loba_2besteffort: public process {
+public:
+    loba_2besteffort(int argc, char* argv[]): process(argc, argv) { }
+    ~loba_2besteffort()                                           { }
+
+private:
+    void load_balance();
+};
+
+#endif //!LOBA_2BESTEFFORT_H
+
+// Local variables:
+// mode: c++
+// End:
diff --git a/options.cpp b/options.cpp
index 3eed8a2..bde2ae8 100644
--- a/options.cpp
+++ b/options.cpp
@@ -10,6 +10,7 @@ XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(main);
 
 #include "deployment.h"
 #include "process.h"
+#include "loba_2besteffort.h"
 #include "loba_besteffort.h"
 #include "loba_bulk.h"
 #include "loba_fairstrategy.h"
@@ -79,6 +80,8 @@ namespace opt {
     loba_algorithms_type loba_algorithms;
     loba_algorithms_type::loba_algorithms_type()
     {
+        NOL_INSERT("2besteffort", "balance with best effort strategy (take #2)",
+                   loba_2besteffort);
         NOL_INSERT("besteffort", "balance with best effort strategy",
                    loba_besteffort);
         NOL_INSERT("bulk", "A multi-load-units assignation rule without ordering...",