src/smpi/plugins/load_balancer/LoadBalancer.cpp

   1 /* Copyright (c) 2006-2018. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include <algorithm>
   7 #include <map>
   8 #include <unordered_map>
   9 #include <queue>
  10
  11 #include <boost/heap/fibonacci_heap.hpp>
  12 #include <simgrid/plugins/load.h>
  13 #include <src/smpi/plugins/load_balancer/load_balancer.hpp>
  14
  15 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(plugin_load_balancer);
  16
  17 namespace simgrid {
  18 namespace plugin {
  19 namespace loadbalancer {
  20
  21 struct XBT_PRIVATE compare_hosts {
  22   bool operator()(const simgrid::s4u::Host* a, const simgrid::s4u::Host* b) const;
  23 };
  24
  25 typedef boost::heap::fibonacci_heap<simgrid::s4u::Host*, boost::heap::compare<compare_hosts>>::handle_type heap_handle;
  26
  27 /**
  28  * Structure that imitates a std::pair, but it allows us
  29  * to use meaningful names instead of .first and .second
  30  */
  31 struct XBT_PRIVATE pair_handle_load
  32 {
  33   heap_handle update_handle;
  34   double load;
  35 };
  36
  37 static std::map<const simgrid::s4u::Host*, pair_handle_load> additional_load;
  38
  39 bool compare_hosts::operator()(const simgrid::s4u::Host* a, const simgrid::s4u::Host* b) const {
  40   return /*sg_host_get_avg_load(a) +*/ additional_load[a].load > /*sg_host_get_avg_load(b) +*/ additional_load[b].load;
  41 }
  42
  43
  44 LoadBalancer::LoadBalancer()
  45 {
  46 }
  47
  48 LoadBalancer::~LoadBalancer()
  49 {
  50 }
  51
  52 void LoadBalancer::run()
  53 {
  54   simgrid::s4u::Engine* engine                     = simgrid::s4u::Engine::get_instance();
  55   std::vector<simgrid::s4u::Host*> available_hosts = engine->get_filtered_hosts([](simgrid::s4u::Host* host) {
  56     return not host->is_off();
  57   });
  58   xbt_assert(available_hosts.size() > 0, "No hosts available; are they all switched off?");
  59
  60   // TODO: Account for daemon background load (-> use especially the availability file)
  61
  62   std::vector<simgrid::s4u::ActorPtr> all_actors =
  63       engine->get_filtered_actors([](simgrid::s4u::ActorPtr actor) { return not actor->is_daemon(); });
  64
  65   for (auto& actor : all_actors) {
  66     new_mapping.assign(actor, actor->get_host());
  67   }
  68   // Sort the actors, from highest to lowest load; we then just iterate over these actors
  69   std::sort(all_actors.begin(), all_actors.end(), [this](simgrid::s4u::ActorPtr a, simgrid::s4u::ActorPtr b) {
  70     return actor_computation[a->get_pid()] > actor_computation[b->get_pid()];
  71   });
  72
  73   // Sort the hosts. Use a heap datastructure, because we have to reorder
  74   // after a host got another actor assigned (or moved from).
  75   // We can't use std::priorityQueue here because we modify *two* elements: The top element, which
  76   // we can access and which has the lowest load, gets a new actor assigned.
  77   // However, the host loosing that actor must be updated as well.
  78   // std::priorityQueue is immutable and hence doesn't work for us.
  79   //
  80   // This heap contains the least loaded host at the top
  81   boost::heap::fibonacci_heap<simgrid::s4u::Host*, boost::heap::compare<compare_hosts>> usable_hosts;
  82   for (auto& host : available_hosts) {
  83     std::vector<simgrid::s4u::ActorPtr> actors = host->get_all_actors();
  84     heap_handle update_handle                  = usable_hosts.push(host); // Required to update elements in the heap
  85     additional_load[host]                      = {update_handle, 0}; // Save the handle for later
  86     for (auto& actor : actors) {
  87       additional_load[host].load += actor_computation[actor->get_pid()];
  88       XBT_DEBUG("Actor %li -> %f", actor->get_pid(), actor_computation[actor->get_pid()]);
  89     }
  90     XBT_DEBUG("Host %s initialized to %f", host->get_cname(), additional_load[host].load);
  91   }
  92
  93   // Implementation of the Greedy algorithm
  94   for (auto& actor : all_actors) {
  95     simgrid::s4u::Host* target_host = usable_hosts.top(); // This is the host with the lowest load
  96
  97     simgrid::s4u::Host* cur_mapped_host = new_mapping.get_host(actor);
  98     if (target_host != cur_mapped_host
  99         && additional_load[target_host].load + actor_computation[actor->get_pid()] < additional_load[cur_mapped_host].load
 100         && new_mapping.count_actors(cur_mapped_host) > 1) {
 101       usable_hosts.pop();
 102       XBT_DEBUG("Assigning %li from %s to %s -- actor_load: %f -- host_load: %f", actor->get_pid(), actor->get_host()->get_cname(), target_host->get_cname(), actor_computation[actor->get_pid()], additional_load[target_host].load);
 103       additional_load[cur_mapped_host].load = std::max<double>(0.0, additional_load[cur_mapped_host].load - actor_computation[actor->get_pid()]); // No negative loads, please!
 104       usable_hosts.update(additional_load[cur_mapped_host].update_handle, cur_mapped_host);
 105       additional_load[target_host].load         += actor_computation[actor->get_pid()];
 106
 107       new_mapping.assign(actor, target_host);
 108
 109       XBT_DEBUG("Assigning actor %li to host %s", actor->get_pid(), target_host->get_cname());
 110
 111       XBT_DEBUG("host_load: %f after the assignment", additional_load[target_host].load);
 112       additional_load[target_host].update_handle = usable_hosts.push(target_host); // Save update handle for later
 113     }
 114   }
 115
 116   while (!usable_hosts.empty()) {
 117     simgrid::s4u::Host* host = usable_hosts.top();
 118     usable_hosts.pop();
 119
 120     sg_host_load_reset(host); // Reset host load for next iterations
 121
 122     if (XBT_LOG_ISENABLED(plugin_load_balancer, e_xbt_log_priority_t::xbt_log_priority_debug)) {
 123       /* Debug messages that allow us to verify the load for each host */
 124       XBT_DEBUG("Host: %s, load total: %f", host->get_cname(), additional_load[host].load);
 125       double load_verif = 0.0;
 126       new_mapping.for_each_actor(host,
 127           [this, &load_verif](simgrid::s4u::ActorPtr actor) {
 128             load_verif += actor_computation[actor->get_pid()];
 129             XBT_DEBUG("        %li (load: %f)", actor->get_pid(), actor_computation[actor->get_pid()]);
 130       });
 131       XBT_DEBUG("Host load verification: %f", load_verif);
 132     }
 133   }
 134   for (auto& elem : actor_computation) { // Reset actor load
 135     elem.second = 0;
 136   }
 137 }
 138
 139 simgrid::s4u::Host* LoadBalancer::get_mapping()
 140 {
 141   return new_mapping.get_host(simgrid::s4u::Actor::self());
 142 }
 143
 144 void LoadBalancer::record_actor_computation(simgrid::s4u::ActorPtr actor, double load)
 145 {
 146   actor_computation[actor->get_pid()] += load;
 147 }
 148 }
 149 }
 150 }