]> AND Private Git Repository - loba.git/blob - process.cpp
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Add possibility to set the convergence threshold automatically.
[loba.git] / process.cpp
1 #include <algorithm>
2 #include <cmath>
3 #include <functional>
4 #include <iterator>
5 #include <numeric>
6 #include <stdexcept>
7 #include <sstream>
8 #include <xbt/log.h>
9 #include <xbt/time.h>
10
11 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(proc);
12
13 #include "misc.h"
14 #include "options.h"
15 #include "tracing.h"
16
17 #include "process.h"
18
19 mutex_t *process::proc_mutex;
20
21 double process::total_load_init = 0.0;
22 double process::total_load_running = 0.0;
23 double process::total_load_exit = 0.0;
24
25 int process::process_counter = 0;
26 double process::total_load_average;
27 double process::average_load_ratio;
28 double process::load_diff_threshold;
29
30 std::atomic<int> process::convergence_counter(0);
31
32 namespace {
33
34     void sleep_until_date(double& date, double duration)
35     {
36         double sleep_duration = date - MSG_get_clock();
37         if (sleep_duration > 0.0)
38             MSG_process_sleep(sleep_duration);
39         date = MSG_get_clock() + duration;
40     }
41
42 }
43
44 process::process(int argc, char* argv[])
45 {
46     if (argc < 2 || !(std::istringstream(argv[1]) >> real_load))
47         throw std::invalid_argument("bad or missing initial load parameter");
48
49     double iload = std::trunc(real_load);
50     if (opt::integer_transfer && real_load != iload) {
51         XBT_WARN("Initial load %g is not an integer.  Truncate it.",
52                  real_load);
53         real_load = iload;
54     }
55
56     neigh.assign(argv + 2, argv + argc);
57
58     pneigh.reserve(neigh.size());
59     for (unsigned i = 0 ; i < neigh.size() ; i++) {
60         neighbor* ptr = &neigh[i];
61         m_host_t host = MSG_get_host_by_name(ptr->get_name());
62         pneigh.push_back(ptr);
63         rev_neigh.insert(std::make_pair(host, ptr));
64     }
65
66     prev_load_broadcast = -1;   // force sending of load on first send_all()
67     expected_load = real_load;
68     received_load = 0.0;
69
70     idle_duration = 0.0;
71     convergence = -1.0;
72
73     proc_mutex->acquire();
74     process_counter++;
75     convergence_counter++;
76     total_load_init += real_load;
77     total_load_running += real_load;
78     total_load_average = total_load_running / process_counter;
79     if (opt::avg_load_ratio >= 0.0)
80         average_load_ratio = opt::avg_load_ratio;
81     else
82         average_load_ratio = 100.0 *
83             (process_counter / -opt::avg_load_ratio) / total_load_average;
84     load_diff_threshold = (opt::load_ratio_threshold +
85                            average_load_ratio * total_load_average) / 100.0;
86     proc_mutex->release();
87
88     ctrl_close_pending = data_close_pending = neigh.size();
89     close_received = false;
90     finalizing = false;
91
92     all_comp_iter = comp_iter = lb_iter = 0;
93
94     lb_thread = new_msg_thread("loba",
95                                std::bind(&process::load_balance_loop, this));
96
97     e_xbt_log_priority_t logp = xbt_log_priority_verbose;
98     if (!LOG_ISENABLED(logp))
99         return;
100     std::ostringstream oss;
101     oss << neigh.size() << " neighbor";
102     if (!neigh.empty()) {
103         oss << ESSE(neigh.size()) << ": ";
104         std::transform(neigh.begin(), neigh.end() - 1,
105                        std::ostream_iterator<const char*>(oss, ", "),
106                        std::mem_fn(&neighbor::get_name));
107         oss << neigh.back().get_name();
108     }
109     XBT_LOG(logp, "Got %s.", oss.str().c_str());
110     print_loads(false, logp);
111 }
112
113 process::~process()
114 {
115     delete lb_thread;
116     proc_mutex->acquire();
117     total_load_exit += real_load;
118     proc_mutex->release();
119     xbt_assert(received_load == 0.0,
120                "received_load is %g, but should be 0.0 !", received_load);
121     if (opt::log_rate < 0)
122         return;
123     XBT_INFO("Final load after %d:%d:%d iterations: %g",
124              lb_iter, comp_iter, all_comp_iter, real_load);
125     if (convergence >= 0.0)
126         XBT_INFO("Convergence within %g%% was achieved at time %g",
127                  average_load_ratio, convergence);
128     else
129         XBT_INFO("Convergence within %g%% was not achieved",
130                  average_load_ratio);
131     XBT_VERB("Expected load was: %g", expected_load);
132     XBT_VERB("Total computation for this process: %g", get_comp_amount());
133     print_loads(true, xbt_log_priority_debug);
134 }
135
136 double process::get_iter_deviation() const
137 {
138     double average_cost = opt::comp_cost(total_load_average); // fixme: get locked?
139     // Do not count idle periods
140     double comp_iter_opt = acc.comp_amount / average_cost;
141 /*
142     // Add iterations that could have been achieved while beeing idle
143     // (kept for documentation)
144     double self_speed = MSG_get_host_speed(MSG_host_self());
145     double average_duration = average_cost / self_speed;
146     comp_iter_opt += idle_duration / average_duration;
147 */
148     return comp_iter - comp_iter_opt;
149 }
150
151 int process::run()
152 {
153     if (opt::log_rate >= 0) {
154         XBT_INFO("Initial load: %g", real_load);
155         XBT_VERB("Initial expected load: %g", expected_load);
156     }
157     XBT_VERB("Starting...");
158     mutex.acquire();
159     lb_thread->start();
160     while (lb_iter <= opt::comp_iter_delay)
161         cond.wait(mutex);
162     mutex.release();
163     double sleep_duration = opt::comp_time_delay - MSG_get_clock();
164     if (sleep_duration > 0.0)
165         MSG_process_sleep(sleep_duration);
166     compute_loop();
167     lb_thread->wait();
168     XBT_VERB("Done.");
169     return 0;
170 }
171
172 void process::load_balance_loop()
173 {
174     using std::placeholders::_1;
175
176     double next_iter_after_date = MSG_get_clock() + opt::min_lb_iter_duration;
177     while (still_running()) {
178         if (lb_iter == opt::comp_iter_delay) {
179             mutex.acquire();
180             ++lb_iter;
181             cond.signal();
182             mutex.release();
183         } else {
184             ++lb_iter;
185         }
186
187         ctrl_receive(0.0);
188
189         mutex.acquire();
190         if (!opt::bookkeeping)
191             expected_load = real_load - get_sum_of_to_send();
192         // nothing to do with opt::bookkeeping
193
194         if (opt::log_rate && lb_iter % opt::log_rate == 0) {
195             XBT_INFO("(%u:%u:%u) current load: %g",
196                      lb_iter, comp_iter, all_comp_iter, real_load);
197             XBT_VERB("... expected load: %g", expected_load);
198         }
199
200         if (expected_load > 0.0)
201             load_balance();
202
203         print_loads(true, xbt_log_priority_debug);
204
205         // send
206         comm.ctrl_flush(false);
207         std::for_each(neigh.begin(), neigh.end(),
208                       std::bind(&process::ctrl_send, this, _1));
209         prev_load_broadcast = expected_load;
210         mutex.release();
211
212         sleep_until_date(next_iter_after_date, opt::min_lb_iter_duration);
213     }
214
215     XBT_VERB("Going to finalize for %s...", __func__);
216     XBT_DEBUG("send CTRL_CLOSE to %zu neighbor%s",
217               neigh.size(), ESSE(neigh.size()));
218     std::for_each(neigh.begin(), neigh.end(),
219                   std::bind(&process::ctrl_close, this, _1));
220     while (ctrl_close_pending) {
221         comm.ctrl_flush(false);
222         XBT_DEBUG("waiting for %d CTRL_CLOSE", ctrl_close_pending);
223         ctrl_receive(-1.0);
224     }
225     comm.ctrl_flush(true);
226 }
227
228 void process::compute_loop()
229 {
230     using std::placeholders::_1;
231
232     double next_iter_after_date = MSG_get_clock() + opt::min_comp_iter_duration;
233     double idle_since_date = 0.0;
234     while (still_running()) {
235         // receive
236         // if there is something to compute, do not block
237         // else, block the duration of an *lb* iteration
238         data_receive(real_load > 0.0 ? 0.0 : opt::min_lb_iter_duration);
239
240         // send
241         comm.data_flush(false);
242         mutex.acquire();
243         real_load += received_load;
244         received_load = 0.0;
245         std::for_each(neigh.begin(), neigh.end(),
246                       std::bind(&process::data_send, this, _1));
247         mutex.release();
248
249         ++all_comp_iter;
250         if (real_load == 0.0)
251             continue;
252
253         convergence_check();
254
255         // compute
256         idle_duration += MSG_get_clock() - idle_since_date;
257         ++comp_iter;
258         double flops = opt::comp_cost(real_load);
259         m_task_t task = MSG_task_create("computation", flops, 0.0, NULL);
260         TRACE_msg_set_task_category(task, TRACE_CAT_COMP);
261         XBT_DEBUG("compute %g flop%s", flops, ESSE(flops));
262         MSG_task_execute(task);
263         add_comp_amount(flops);
264         MSG_task_destroy(task);
265
266         idle_since_date = MSG_get_clock();
267
268         sleep_until_date(next_iter_after_date, opt::min_comp_iter_duration);
269     }
270
271     XBT_VERB("Going to finalize for %s...", __func__);
272     // Note: idle duration is not counted during finalization
273     finalizing = true;
274     XBT_DEBUG("send DATA_CLOSE to %zu neighbor%s",
275               neigh.size(), ESSE(neigh.size()));
276     std::for_each(neigh.begin(), neigh.end(),
277                   std::bind(&process::data_close, this, _1));
278     while (data_close_pending) {
279         comm.data_flush(false);
280         XBT_DEBUG("waiting for %d DATA_CLOSE", data_close_pending);
281         data_receive(-1.0);
282     }
283     real_load += received_load;
284     received_load = 0.0;
285     proc_mutex->acquire();
286     total_load_running -= real_load;
287     proc_mutex->release();
288     convergence_check();
289     comm.data_flush(true);
290 }
291
292 void process::convergence_check()
293 {
294     double average = total_load_average; // fixme: get locked?
295     double load_diff = std::fabs(real_load - average);
296     bool converged = load_diff <= load_diff_threshold;
297
298     if (convergence >= 0.0) {
299         if (!converged) {
300             XBT_VERB("current load has diverged: %g (%.4g%%)",
301                      real_load, 100.0 * load_diff / average);
302             convergence = -1.0;
303             convergence_counter++;
304         }
305     } else {
306         if (converged) {
307             XBT_VERB("current load has converged: %g (%.4g%%)",
308                      real_load,  100.0 * load_diff / average);
309             convergence = MSG_get_clock();
310             convergence_counter--;
311         }
312     }
313 }
314
315 bool process::still_running()
316 {
317     static bool last_status = true;
318
319     if (!last_status) {
320         /* nop */
321
322     } else if (opt::exit_request) {
323         XBT_VERB("Global exit requested");
324         last_status = false;
325
326     } else if (opt::time_limit && MSG_get_clock() >= opt::time_limit) {
327         XBT_VERB("Reached time limit: %g/%g", MSG_get_clock(), opt::time_limit);
328         last_status = false;
329
330     } else if (opt::lb_maxiter && lb_iter >= opt::lb_maxiter) {
331         XBT_VERB("Reached lb_maxiter: %d/%d", lb_iter, opt::lb_maxiter);
332         last_status = false;
333
334     } else if (opt::comp_maxiter && comp_iter >= opt::comp_maxiter) {
335         XBT_VERB("Reached comp_maxiter: %d/%d", comp_iter, opt::comp_maxiter);
336         last_status = false;
337
338     } else if (opt::exit_on_convergence && convergence_counter == 0) {
339         XBT_VERB("Global convergence detected");
340         last_status = false;
341
342     } else if (opt::exit_on_close && close_received) {
343         XBT_VERB("Close received");
344         last_status = false;
345
346     } else if (real_load == 0.0 && !data_close_pending) {
347         XBT_VERB("I'm a poor lonesome process, and I have no load...");
348         last_status = false;
349
350     } else if (100.0 * total_load_running / total_load_init <=
351                opt::load_ratio_threshold) { // fixme: get locked?
352         // fixme: this check should be implemented with a distributed
353         // algorithm, and not a shared global variable!
354         XBT_VERB("No more load to balance in system.");
355         last_status = false;
356     }
357
358     return last_status;
359 }
360
361 double process::get_sum_of_to_send() const
362 {
363     using std::placeholders::_1;
364     using std::placeholders::_2;
365
366     return std::accumulate(neigh.begin(), neigh.end(), 0.0,
367                            std::bind(std::plus<double>(), _1,
368                                      std::bind(&neighbor::get_to_send, _2)));
369 }
370
371 void process::load_balance()
372 {
373     if (lb_iter == 1)           // warn only once
374         XBT_WARN("process::load_balance() is a no-op!");
375 }
376
377 void process::send(neighbor& nb, double amount)
378 {
379     expected_load -= amount;
380     nb.set_to_send(nb.get_to_send() + amount);
381     nb.set_load(nb.get_load() + amount);
382 }
383
384 void process::ctrl_send(neighbor& nb)
385 {
386     double info_to_send = expected_load;
387     double debt_to_send;
388     if (opt::bookkeeping) {     // bookkeeping
389         debt_to_send = nb.get_to_send();
390         if (debt_to_send > 0.0) {
391             nb.set_to_send(0.0);
392             nb.set_debt(nb.get_debt() + debt_to_send);
393         }
394     } else {                    // !bookkeeping
395         debt_to_send = 0.0;
396     }
397     if (info_to_send != prev_load_broadcast || debt_to_send > 0.0) {
398         message* msg = new message(message::CTRL, info_to_send, debt_to_send);
399         add_ctrl_send_mesg(msg->get_size());
400         comm.ctrl_send(nb.get_ctrl_mbox(), msg);
401     }
402 }
403
404 double process::compute_load_to_send(double desired)
405 {
406     if (opt::integer_transfer)
407         desired = std::floor(desired);
408     return desired >= opt::min_transfer_amount ? desired : 0.0;
409 }
410
411 void process::data_send(neighbor& nb)
412 {
413     double load_to_send;
414     if (opt::bookkeeping) {     // bookkeeping
415         double excess_load;     // load amount we are able to send
416         if (opt::egocentric)
417             excess_load = std::max(0.0, real_load - expected_load);
418         else
419             excess_load = real_load;
420
421         double balance = nb.get_debt() - nb.get_credit();
422         load_to_send = std::min(excess_load,
423                                 std::max(0.0, balance));
424
425         // adjust load to send (rounding, truncation, etc.)
426         load_to_send = compute_load_to_send(load_to_send);
427         if (load_to_send > 0.0)
428             nb.set_debt(nb.get_debt() - load_to_send);
429     } else {                    // !bookkeeping
430         load_to_send = compute_load_to_send(nb.get_to_send());
431         if (load_to_send > 0.0)
432             nb.set_to_send(nb.get_to_send() - load_to_send);
433     }
434     real_load -= load_to_send;
435     while (load_to_send > 0.0) {
436         double amount;
437         if (opt::max_transfer_amount)
438             amount = std::min(load_to_send, opt::max_transfer_amount);
439         else
440             amount = load_to_send;
441         message* msg = new message(message::DATA, amount);
442         add_data_send_mesg(msg->get_size());
443         comm.data_send(nb.get_data_mbox(), msg);
444         load_to_send -= amount;
445     }
446 }
447
448 void process::ctrl_close(neighbor& nb)
449 {
450     comm.ctrl_send(nb.get_ctrl_mbox(), new message(message::CTRL_CLOSE, 0.0));
451 }
452
453 void process::data_close(neighbor& nb)
454 {
455     comm.data_send(nb.get_data_mbox(), new message(message::DATA_CLOSE, 0.0));
456 }
457
458 void process::ctrl_receive(double timeout)
459 {
460     message* msg;
461     m_host_t from;
462
463     XBT_DEBUG("%sblocking receive on ctrl (%g)", "\0non-" + !timeout, timeout);
464     while (ctrl_close_pending && comm.ctrl_recv(msg, from, timeout)) {
465         if (msg->get_type() != message::CTRL_CLOSE)
466             add_ctrl_recv_mesg(msg->get_size());
467         handle_message(msg, from);
468         timeout = 0.0;
469     }
470 }
471
472 void process::data_receive(double timeout)
473 {
474     message* msg;
475     m_host_t from;
476
477     XBT_DEBUG("%sblocking receive on data (%g)", "\0non-" + !timeout, timeout);
478     while (data_close_pending && comm.data_recv(msg, from, timeout)) {
479         if (msg->get_type() != message::DATA_CLOSE)
480             add_data_recv_mesg(msg->get_size());
481         handle_message(msg, from);
482         timeout = 0.0;
483     }
484 }
485
486 void process::handle_message(message* msg, m_host_t from)
487 {
488     switch (msg->get_type()) {
489     case message::CTRL: {
490         neighbor* n = rev_neigh[from];
491         n->set_load(msg->get_amount() + n->get_to_send());
492         if (opt::bookkeeping) {
493             double credit = msg->get_credit();
494             expected_load += credit;
495             n->set_credit(n->get_credit() + credit);
496         }
497         break;
498     }
499     case message::DATA: {
500         neighbor* n = rev_neigh[from];
501         double ld = msg->get_amount();
502         received_load += ld;
503         n->set_credit(n->get_credit() - ld);
504         break;
505     }
506     case message::CTRL_CLOSE:
507         ctrl_close_pending--;
508         close_received = true;
509         break;
510     case message::DATA_CLOSE:
511         data_close_pending--;
512         close_received = true;
513         break;
514     }
515     delete msg;
516 }
517
518 #define print_loads_generic(vec, verbose, logp, cat)                    \
519     if (_XBT_LOG_ISENABLEDV((*cat), logp)) {                            \
520         using std::placeholders::_1;                                    \
521         XBT_XCLOG(cat, logp, "My load: %g (real); %g (expected).  "     \
522                   "Neighbor loads:", real_load, expected_load);         \
523         std::for_each(vec.begin(), vec.end(),                           \
524                       std::bind(&neighbor::print, _1, verbose, logp, cat)); \
525     } else ((void)0)
526
527 void process::print_loads(bool verbose,
528                           e_xbt_log_priority_t logp,
529                           xbt_log_category_t cat) const
530 {
531     print_loads_generic(neigh, verbose, logp, cat);
532 }
533
534 void process::print_loads_p(bool verbose,
535                             e_xbt_log_priority_t logp,
536                             xbt_log_category_t cat) const
537 {
538     print_loads_generic(pneigh, verbose, logp, cat);
539 }
540
541 #undef print_loads_generic
542
543 // Local variables:
544 // mode: c++
545 // End: