1 /* Copyright (c) 2006-2020. The SimGrid Team. All rights reserved. */
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. */
8 #include <unordered_map>
11 #include <boost/heap/fibonacci_heap.hpp>
12 #include <simgrid/plugins/load.h>
13 #include <src/smpi/plugins/load_balancer/load_balancer.hpp>
15 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(plugin_load_balancer);
19 namespace loadbalancer {
21 class XBT_PRIVATE compare_hosts {
23 bool operator()(s4u::Host* const a, s4u::Host* const b) const;
26 typedef boost::heap::fibonacci_heap<s4u::Host*, boost::heap::compare<compare_hosts>>::handle_type heap_handle;
28 /** Structure that imitates a std::pair, but it allows us to use meaningful names instead of .first and .second */
29 struct XBT_PRIVATE pair_handle_load
31 heap_handle update_handle;
35 static std::map<s4u::Host* const, pair_handle_load> additional_load;
37 bool compare_hosts::operator()(s4u::Host* const a, s4u::Host* const b) const
39 return additional_load[a].load > additional_load[b].load;
42 void LoadBalancer::run()
44 const s4u::Engine* engine = s4u::Engine::get_instance();
45 std::vector<s4u::Host*> available_hosts =
46 engine->get_filtered_hosts([](const s4u::Host* host) { return host->is_on(); });
47 xbt_assert(available_hosts.size() > 0, "No hosts available; are they all switched off?");
49 // TODO: Account for daemon background load (-> use especially the availability file)
51 std::vector<s4u::ActorPtr> all_actors =
52 engine->get_filtered_actors([](s4u::ActorPtr actor) { return not actor->is_daemon(); });
54 for (auto const& actor : all_actors) {
55 new_mapping.assign(actor, actor->get_host());
57 // Sort the actors, from highest to lowest load; we then just iterate over these actors
58 std::sort(all_actors.begin(), all_actors.end(), [this](s4u::ActorPtr a, s4u::ActorPtr b) {
59 return actor_computation[a->get_pid()] > actor_computation[b->get_pid()];
62 // Sort the hosts. Use a heap datastructure, because we have to reorder
63 // after a host got another actor assigned (or moved from).
64 // We can't use std::priorityQueue here because we modify *two* elements: The top element, which
65 // we can access and which has the lowest load, gets a new actor assigned.
66 // However, the host losing that actor must be updated as well.
67 // std::priorityQueue is immutable and hence doesn't work for us.
69 // This heap contains the least loaded host at the top
70 boost::heap::fibonacci_heap<s4u::Host*, boost::heap::compare<compare_hosts>> usable_hosts;
71 for (auto& host : available_hosts) {
72 std::vector<s4u::ActorPtr> actors = host->get_all_actors();
73 heap_handle update_handle = usable_hosts.push(host); // Required to update elements in the heap
74 additional_load[host] = {update_handle, 0}; // Save the handle for later
75 const double total_flops_computed = sg_host_get_computed_flops(host);
76 for (auto const& actor : actors) {
77 additional_load[host].load += actor_computation[actor->get_pid()] / total_flops_computed; // Normalize load - this allows comparison
78 // even between hosts with different frequencies
79 XBT_DEBUG("Actor %li -> %f", actor->get_pid(), actor_computation[actor->get_pid()]);
81 usable_hosts.increase(update_handle);
82 XBT_DEBUG("Host %s initialized to %f", host->get_cname(), additional_load[host].load);
85 // Implementation of the Greedy algorithm
86 for (auto const& actor : all_actors) {
87 s4u::Host* target_host = usable_hosts.top(); // This is the host with the lowest load
89 s4u::Host* cur_mapped_host = new_mapping.get_host(actor);
90 if (target_host != cur_mapped_host
91 && additional_load[target_host].load + actor_computation[actor->get_pid()] < additional_load[cur_mapped_host].load
92 && new_mapping.count_actors(cur_mapped_host) > 1) {
94 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);
95 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!
96 usable_hosts.update(additional_load[cur_mapped_host].update_handle, cur_mapped_host);
97 additional_load[target_host].load += actor_computation[actor->get_pid()];
99 new_mapping.assign(actor, target_host);
101 XBT_DEBUG("Assigning actor %li to host %s", actor->get_pid(), target_host->get_cname());
103 XBT_DEBUG("host_load: %f after the assignment", additional_load[target_host].load);
104 additional_load[target_host].update_handle = usable_hosts.push(target_host); // Save update handle for later
108 while (!usable_hosts.empty()) {
109 s4u::Host* host = usable_hosts.top();
112 sg_host_load_reset(host); // Reset host load for next iterations
114 if (XBT_LOG_ISENABLED(plugin_load_balancer, e_xbt_log_priority_t::xbt_log_priority_debug)) {
115 /* Debug messages that allow us to verify the load for each host */
116 XBT_DEBUG("Host: %s, load total: %f", host->get_cname(), additional_load[host].load);
117 double load_verif = 0.0;
118 new_mapping.for_each_actor(host, [this, &load_verif](s4u::ActorPtr actor) {
119 load_verif += actor_computation[actor->get_pid()];
120 XBT_DEBUG(" %li (load: %f)", actor->get_pid(), actor_computation[actor->get_pid()]);
122 XBT_DEBUG("Host load verification: %f", load_verif);
125 for (auto& elem : actor_computation) { // Reset actor load
130 s4u::Host* LoadBalancer::get_mapping(s4u::ActorPtr actor)
132 return new_mapping.get_host(actor);
135 void LoadBalancer::record_actor_computation(s4u::Actor const& actor, double load)
137 actor_computation[actor.get_pid()] += load;
139 } // namespace loadbalancer
140 } // namespace plugin
141 } // namespace simgrid