Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Define FairBottleneck and Lagrange as subclasses of lmm::System.
[simgrid.git] / teshsuite / surf / lmm_usage / lmm_usage.cpp
1 /* A few tests for the maxmin library                                       */
2
3 /* Copyright (c) 2007-2018. The SimGrid Team. All rights reserved.          */
4
5 /* This program is free software; you can redistribute it and/or modify it
6  * under the terms of the license (GNU LGPL) which comes with this package. */
7
8 #include "simgrid/msg.h"
9 #include "src/kernel/lmm/maxmin.hpp"
10 #include "src/surf/surf_interface.hpp"
11 #include "xbt/log.h"
12 #include "xbt/module.h"
13 #include "xbt/sysdep.h"
14 #include <algorithm>
15 #include <cmath>
16
17 XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test, "Messages specific for surf example");
18
19 using namespace simgrid::surf;
20
21 #define PRINT_VAR(var) XBT_DEBUG(#var " = %g", (var)->get_value())
22 #define SHOW_EXPR(expr) XBT_DEBUG(#expr " = %g",expr)
23
24 /*        ______                 */
25 /*  ==l1==  L2  ==L3==           */
26 /*        ------                 */
27
28 enum method_t { MAXMIN, LAGRANGE_RENO, LAGRANGE_VEGAS };
29
30 static simgrid::kernel::lmm::System* new_system(method_t method, bool update)
31 {
32   switch (method) {
33     case MAXMIN:
34       return simgrid::kernel::lmm::make_new_maxmin_system(update);
35     case LAGRANGE_VEGAS:
36     case LAGRANGE_RENO:
37       return simgrid::kernel::lmm::make_new_lagrange_system(update);
38     default:
39       xbt_die("Invalid method");
40   }
41 }
42
43 static double dichotomy(double func(double), double min, double max, double min_error)
44 {
45   double overall_error = 2 * min_error;
46
47   double min_func = func(min);
48   double max_func = func(max);
49
50   if ((min_func > 0 && max_func > 0))
51     return min - 1.0;
52   if ((min_func < 0 && max_func < 0))
53     return max + 1.0;
54   if ((min_func > 0 && max_func < 0))
55     abort();
56
57   SHOW_EXPR(min_error);
58
59   while (overall_error > min_error) {
60     SHOW_EXPR(overall_error);
61     xbt_assert(min_func <= 0 || max_func <= 0);
62     xbt_assert(min_func >= 0 || max_func >= 0);
63     xbt_assert(min_func <= 0 || max_func >= 0);
64
65     SHOW_EXPR(min);
66     SHOW_EXPR(min_func);
67     SHOW_EXPR(max);
68     SHOW_EXPR(max_func);
69
70     double middle = (max + min) / 2.0;
71     if (fabs(min - middle) < 1e-12 || fabs(max - middle) < 1e-12) {
72       break;
73     }
74     double middle_func = func(middle);
75     SHOW_EXPR(middle);
76     SHOW_EXPR(middle_func);
77
78     if (middle_func < 0) {
79       min = middle;
80       min_func = middle_func;
81       overall_error = max_func - middle_func;
82     } else if (middle_func > 0) {
83       max = middle;
84       max_func = middle_func;
85       overall_error = middle_func - min_func;
86     } else {
87       overall_error = 0;
88     }
89   }
90   return ((min + max) / 2.0);
91 }
92
93 double a_test_1 = 0;
94 double b_test_1 = 0;
95 static double diff_lagrange_test_1(double x)
96 {
97   return -(3 / (1 + 3 * x * x / 2) - 3 / (2 * (3 * (a_test_1 - x) * (a_test_1 - x) / 2 + 1)) +
98            3 / (2 * (3 * (b_test_1 - a_test_1 + x) * (b_test_1 - a_test_1 + x) / 2 + 1)));
99 }
100
101 static void test1(method_t method)
102 {
103   double a = 1.0;
104   double b = 10.0;
105
106   if (method == LAGRANGE_VEGAS)
107     set_default_protocol_function(simgrid::kernel::lmm::func_vegas_f, simgrid::kernel::lmm::func_vegas_fp,
108                                   simgrid::kernel::lmm::func_vegas_fpi);
109   else if (method == LAGRANGE_RENO)
110     set_default_protocol_function(simgrid::kernel::lmm::func_reno_f, simgrid::kernel::lmm::func_reno_fpi,
111                                   simgrid::kernel::lmm::func_reno_fpi);
112
113   simgrid::kernel::lmm::System* Sys    = new_system(method, true);
114   simgrid::kernel::lmm::Constraint* L1 = Sys->constraint_new(nullptr, a);
115   simgrid::kernel::lmm::Constraint* L2 = Sys->constraint_new(nullptr, b);
116   simgrid::kernel::lmm::Constraint* L3 = Sys->constraint_new(nullptr, a);
117
118   simgrid::kernel::lmm::Variable* R_1_2_3 = Sys->variable_new(nullptr, 1.0, -1.0, 3);
119   simgrid::kernel::lmm::Variable* R_1     = Sys->variable_new(nullptr, 1.0, -1.0, 1);
120   simgrid::kernel::lmm::Variable* R_2     = Sys->variable_new(nullptr, 1.0, -1.0, 1);
121   simgrid::kernel::lmm::Variable* R_3     = Sys->variable_new(nullptr, 1.0, -1.0, 1);
122
123   Sys->update_variable_weight(R_1_2_3, 1.0);
124   Sys->update_variable_weight(R_1, 1.0);
125   Sys->update_variable_weight(R_2, 1.0);
126   Sys->update_variable_weight(R_3, 1.0);
127
128   Sys->expand(L1, R_1_2_3, 1.0);
129   Sys->expand(L2, R_1_2_3, 1.0);
130   Sys->expand(L3, R_1_2_3, 1.0);
131
132   Sys->expand(L1, R_1, 1.0);
133   Sys->expand(L2, R_2, 1.0);
134   Sys->expand(L3, R_3, 1.0);
135
136   if (method == MAXMIN) {
137     Sys->solve();
138   } else {
139     double x;
140     if (method == LAGRANGE_VEGAS) {
141       x = 3 * a / 4 - 3 * b / 8 + sqrt(9 * b * b + 4 * a * a - 4 * a * b) / 8;
142       /* Computed with mupad and D_f=1.0 */
143       if (x > a) {
144         x = a;
145       }
146       if (x < 0) {
147         x = 0;
148       }
149     } else if (method == LAGRANGE_RENO) {
150       a_test_1 = a;
151       b_test_1 = b;
152       x = dichotomy(diff_lagrange_test_1, 0, a, 1e-13);
153
154       if (x < 0)
155         x = 0;
156       if (x > a)
157         x = a;
158     } else {
159       xbt_die( "Invalid method");
160     }
161
162     Sys->solve();
163
164     double max_deviation = 0.0;
165     max_deviation        = std::max(max_deviation, fabs(R_1->get_value() - x));
166     max_deviation        = std::max(max_deviation, fabs(R_3->get_value() - x));
167     max_deviation        = std::max(max_deviation, fabs(R_2->get_value() - (b - a + x)));
168     max_deviation        = std::max(max_deviation, fabs(R_1_2_3->get_value() - (a - x)));
169
170     if (max_deviation > 0.00001) { // Legacy value used in lagrange.c
171       XBT_WARN("Max Deviation from optimal solution : %g", max_deviation);
172       XBT_WARN("Found x = %1.20f", x);
173       XBT_WARN("Deviation from optimal solution (R_1 = %g): %1.20f", x, R_1->get_value() - x);
174       XBT_WARN("Deviation from optimal solution (R_2 = %g): %1.20f", b - a + x, R_2->get_value() - (b - a + x));
175       XBT_WARN("Deviation from optimal solution (R_3 = %g): %1.20f", x, R_3->get_value() - x);
176       XBT_WARN("Deviation from optimal solution (R_1_2_3 = %g): %1.20f", a - x, R_1_2_3->get_value() - (a - x));
177     }
178   }
179
180   PRINT_VAR(R_1_2_3);
181   PRINT_VAR(R_1);
182   PRINT_VAR(R_2);
183   PRINT_VAR(R_3);
184
185   Sys->variable_free(R_1_2_3);
186   Sys->variable_free(R_1);
187   Sys->variable_free(R_2);
188   Sys->variable_free(R_3);
189   delete Sys;
190 }
191
192 static void test2(method_t method)
193 {
194   if (method == LAGRANGE_VEGAS)
195     set_default_protocol_function(simgrid::kernel::lmm::func_vegas_f, simgrid::kernel::lmm::func_vegas_fp,
196                                   simgrid::kernel::lmm::func_vegas_fpi);
197   if (method == LAGRANGE_RENO)
198     set_default_protocol_function(simgrid::kernel::lmm::func_reno_f, simgrid::kernel::lmm::func_reno_fp,
199                                   simgrid::kernel::lmm::func_reno_fpi);
200
201   simgrid::kernel::lmm::System* Sys = new_system(method, true);
202
203   simgrid::kernel::lmm::Constraint* CPU1 = Sys->constraint_new(nullptr, 200.0);
204   simgrid::kernel::lmm::Constraint* CPU2 = Sys->constraint_new(nullptr, 100.0);
205
206   simgrid::kernel::lmm::Variable* T1 = Sys->variable_new(nullptr, 1.0, -1.0, 1);
207   simgrid::kernel::lmm::Variable* T2 = Sys->variable_new(nullptr, 1.0, -1.0, 1);
208
209   Sys->update_variable_weight(T1, 1.0);
210   Sys->update_variable_weight(T2, 1.0);
211
212   Sys->expand(CPU1, T1, 1.0);
213   Sys->expand(CPU2, T2, 1.0);
214
215   Sys->solve();
216
217   PRINT_VAR(T1);
218   PRINT_VAR(T2);
219
220   Sys->variable_free(T1);
221   Sys->variable_free(T2);
222   delete Sys;
223 }
224
225 static void test3(method_t method)
226 {
227   int flows = 11;
228   int links = 10;
229
230   double** A = new double*[links + 5];
231   /* array to add the constraints of fictitious variables */
232   double B[15] = { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1 };
233
234   for (int i = 0; i < links + 5; i++) {
235     A[i] = new double[flows + 5];
236     for (int j = 0; j < flows + 5; j++) {
237       A[i][j] = 0.0;
238
239       if (i >= links || j >= flows) {
240         A[i][j] = 0.0;
241       }
242     }
243   }
244
245   /*matrix that store the constraints/topology */
246   A[0][1] = A[0][7] =                                1.0;
247   A[1][1] = A[1][7] = A[1][8] =                      1.0;
248   A[2][1] = A[2][8] =                                1.0;
249   A[3][8] =                                          1.0;
250   A[4][0] = A[4][3] = A[4][9] =                      1.0;
251   A[5][0] = A[5][3] = A[5][4] = A[5][9] =            1.0;
252   A[6][0] = A[6][4] = A[6][9] = A[6][10] =           1.0;
253   A[7][2] = A[7][4] = A[7][6] = A[7][9] = A[7][10] = 1.0;
254   A[8][2] = A[8][10] =                               1.0;
255   A[9][5] = A[9][6] = A[9][9] =                      1.0;
256   A[10][11] =                                        1.0;
257   A[11][12] =                                        1.0;
258   A[12][13] =                                        1.0;
259   A[13][14] =                                        1.0;
260   A[14][15] =                                        1.0;
261
262   if (method == LAGRANGE_VEGAS)
263     set_default_protocol_function(simgrid::kernel::lmm::func_vegas_f, simgrid::kernel::lmm::func_vegas_fp,
264                                   simgrid::kernel::lmm::func_vegas_fpi);
265   if (method == LAGRANGE_RENO)
266     set_default_protocol_function(simgrid::kernel::lmm::func_reno_f, simgrid::kernel::lmm::func_reno_fp,
267                                   simgrid::kernel::lmm::func_reno_fpi);
268
269   simgrid::kernel::lmm::System* Sys = new_system(method, true);
270
271   /* Creates the constraints */
272   simgrid::kernel::lmm::Constraint** tmp_cnst = new simgrid::kernel::lmm::Constraint*[15];
273   for (int i = 0; i < 15; i++)
274     tmp_cnst[i] = Sys->constraint_new(nullptr, B[i]);
275
276   /* Creates the variables */
277   simgrid::kernel::lmm::Variable** tmp_var = new simgrid::kernel::lmm::Variable*[16];
278   for (int j = 0; j < 16; j++) {
279     tmp_var[j] = Sys->variable_new(nullptr, 1.0, -1.0, 15);
280     Sys->update_variable_weight(tmp_var[j], 1.0);
281   }
282
283   /* Link constraints and variables */
284   for (int i = 0; i < 15; i++)
285     for (int j = 0; j < 16; j++)
286       if (A[i][j])
287         Sys->expand(tmp_cnst[i], tmp_var[j], 1.0);
288
289   Sys->solve();
290
291   for (int j = 0; j < 16; j++)
292     PRINT_VAR(tmp_var[j]);
293
294   for (int j = 0; j < 16; j++)
295     Sys->variable_free(tmp_var[j]);
296   delete[] tmp_var;
297   delete[] tmp_cnst;
298   delete Sys;
299   for (int i = 0; i < links + 5; i++)
300     delete[] A[i];
301   delete[] A;
302 }
303
304 int main(int argc, char** argv)
305 {
306   MSG_init(&argc, argv);
307   XBT_INFO("***** Test 1 (Max-Min)");
308   test1(MAXMIN);
309   XBT_INFO("***** Test 1 (Lagrange - Vegas)");
310   test1(LAGRANGE_VEGAS);
311   XBT_INFO("***** Test 1 (Lagrange - Reno)");
312   test1(LAGRANGE_RENO);
313
314   XBT_INFO("***** Test 2 (Max-Min)");
315   test2(MAXMIN);
316   XBT_INFO("***** Test 2 (Lagrange - Vegas)");
317   test2(LAGRANGE_VEGAS);
318   XBT_INFO("***** Test 2 (Lagrange - Reno)");
319   test2(LAGRANGE_RENO);
320
321   XBT_INFO("***** Test 3 (Max-Min)");
322   test3(MAXMIN);
323   XBT_INFO("***** Test 3 (Lagrange - Vegas)");
324   test3(LAGRANGE_VEGAS);
325   XBT_INFO("***** Test 3 (Lagrange - Reno)");
326   test3(LAGRANGE_RENO);
327
328   return 0;
329 }