X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/cf0cc38d8036303ec0886ac6361e8e2b62ff0514..61cbee9566cd330a3a307a256e287f39ae348798:/testsuite/surf/simeng_usage.c diff --git a/testsuite/surf/simeng_usage.c b/testsuite/surf/simeng_usage.c index f7a36fbcca..935c9faf22 100644 --- a/testsuite/surf/simeng_usage.c +++ b/testsuite/surf/simeng_usage.c @@ -13,14 +13,17 @@ #include "xbt/sysdep.h" #include "surf/maxmin.h" - #include "xbt/log.h" #include "xbt/module.h" +#include + -XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test,"Messages specific for surf example"); +XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test, + "Messages specific for surf example"); #define PRINT_VAR(var) DEBUG1(#var " = %g",lmm_variable_getvalue(var)); +#define SHOW_EXPR(expr) DEBUG1(#expr " = %g",expr); /* */ /* ______ */ @@ -31,13 +34,70 @@ XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test,"Messages specific for surf example"); typedef enum { MAXMIN, SDP, - LAGRANGE + LAGRANGE_RENO, + LAGRANGE_VEGAS, } method_t; +static double dichotomy(double func(double), double min, double max, + double min_error) +{ + double middle; + double min_func, max_func, middle_func; + + double overall_error = 2 * min_error; + + min_func = func(min); + max_func = func(max); + + if ((min_func > 0 && max_func > 0)) + return min - 1.0; + if ((min_func < 0 && max_func < 0)) + return max + 1.0; + if ((min_func > 0 && max_func < 0)) + abort(); + + while (overall_error > min_error) { + if ((min_func > 0 && max_func > 0) || + (min_func < 0 && max_func < 0) || (min_func > 0 && max_func < 0)) { + abort(); + } + + middle = (max + min) / 2.0; + if ((min == middle) || (max == middle)) { + break; + } + middle_func = func(middle); + + if (middle_func < 0) { + min = middle; + min_func = middle_func; + overall_error = max - middle_func; + } else if (middle_func > 0) { + max = middle; + max_func = middle_func; + overall_error = max - middle_func; + } else { + overall_error = 0; + } + } + return ((min + max) / 2.0); +} + +double a_test_1 = 0; +double b_test_1 = 0; +static double diff_lagrange_test_1(double x) +{ + return -(3 / (1 + 3 * x * x / 2) - + 3 / (2 * (3 * (a_test_1 - x) * (a_test_1 - x) / 2 + 1)) + + 3 / (2 * + (3 * (b_test_1 - a_test_1 + x) * + (b_test_1 - a_test_1 + x) / 2 + 1))); +} + void test1(method_t method); void test1(method_t method) { - lmm_system_t Sys = NULL ; + lmm_system_t Sys = NULL; lmm_constraint_t L1 = NULL; lmm_constraint_t L2 = NULL; lmm_constraint_t L3 = NULL; @@ -47,15 +107,29 @@ void test1(method_t method) lmm_variable_t R_2 = NULL; lmm_variable_t R_3 = NULL; + double a = 1.0, b = 10.0; + + if (method == LAGRANGE_VEGAS) + lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp, + func_vegas_fpi); + else if (method == LAGRANGE_RENO) + lmm_set_default_protocol_function(func_reno_f, func_reno_fpi, + func_reno_fpi); + Sys = lmm_system_new(); - L1 = lmm_constraint_new(Sys, (void *) "L1", 1.0); - L2 = lmm_constraint_new(Sys, (void *) "L2", 10.0); - L3 = lmm_constraint_new(Sys, (void *) "L3", 1.0); + L1 = lmm_constraint_new(Sys, (void *) "L1", a); + L2 = lmm_constraint_new(Sys, (void *) "L2", b); + L3 = lmm_constraint_new(Sys, (void *) "L3", a); + + R_1_2_3 = lmm_variable_new(Sys, (void *) "R 1->2->3", 1.0, -1.0, 3); + R_1 = lmm_variable_new(Sys, (void *) "R 1", 1.0, -1.0, 1); + R_2 = lmm_variable_new(Sys, (void *) "R 2", 1.0, -1.0, 1); + R_3 = lmm_variable_new(Sys, (void *) "R 3", 1.0, -1.0, 1); - R_1_2_3 = lmm_variable_new(Sys, (void *) "R 1->2->3", 1.0 , -1.0 , 3); - R_1 = lmm_variable_new(Sys, (void *) "R 1", 1.0 , -1.0 , 1); - R_2 = lmm_variable_new(Sys, (void *) "R 2", 1.0 , -1.0 , 1); - R_3 = lmm_variable_new(Sys, (void *) "R 3", 1.0 , -1.0 , 1); + lmm_update_variable_latency(Sys, R_1_2_3, 1.0); + lmm_update_variable_latency(Sys, R_1, 1.0); + lmm_update_variable_latency(Sys, R_2, 1.0); + lmm_update_variable_latency(Sys, R_3, 1.0); lmm_expand(Sys, L1, R_1_2_3, 1.0); lmm_expand(Sys, L2, R_1_2_3, 1.0); @@ -67,122 +141,191 @@ void test1(method_t method) lmm_expand(Sys, L3, R_3, 1.0); - PRINT_VAR(R_1_2_3); - PRINT_VAR(R_1); - PRINT_VAR(R_2); - PRINT_VAR(R_3); - DEBUG0("\n"); - if(method==MAXMIN) + if (method == MAXMIN) { lmm_solve(Sys); #ifdef HAVE_SDP - else if(method==SDP) - sdp_solve(Sys); + } else if (method == SDP) { + sdp_solve(Sys); #endif - else if(method==LAGRANGE) - lagrange_solve(Sys); - else - xbt_assert0(0,"Invalid method"); + } else if (method == LAGRANGE_VEGAS) { + double x = 3 * a / 4 - 3 * b / 8 + + sqrt(9 * b * b + 4 * a * a - 4 * a * b) / 8; + /* Computed with mupad and D_f=1.0 */ + double max_deviation = 0.0; + if (x > a) { + x = a; + } + if (x < 0) { + x = 0; + } + + lagrange_solve(Sys); + + max_deviation = + MAX(max_deviation, fabs(lmm_variable_getvalue(R_1) - x)); + max_deviation = + MAX(max_deviation, fabs(lmm_variable_getvalue(R_3) - x)); + max_deviation = + MAX(max_deviation, fabs(lmm_variable_getvalue(R_2) - (b - a + x))); + max_deviation = + MAX(max_deviation, fabs(lmm_variable_getvalue(R_1_2_3) - (a - x))); + + if (max_deviation > MAXMIN_PRECISION) { + WARN1("Max Deviation from optimal solution : %g", max_deviation); + WARN1("Found x = %1.20f", x); + WARN2("Deviation from optimal solution (R_1 = %g): %1.20f", x, + lmm_variable_getvalue(R_1) - x); + WARN2("Deviation from optimal solution (R_2 = %g): %1.20f", + b - a + x, lmm_variable_getvalue(R_2) - (b - a + x)); + WARN2("Deviation from optimal solution (R_3 = %g): %1.20f", x, + lmm_variable_getvalue(R_3) - x); + WARN2("Deviation from optimal solution (R_1_2_3 = %g): %1.20f", + a - x, lmm_variable_getvalue(R_1_2_3) - (a - x)); + } + } else if (method == LAGRANGE_RENO) { + double x; + double max_deviation = 0.0; + + a_test_1 = a; + b_test_1 = b; + x = dichotomy(diff_lagrange_test_1, 0, a, 1e-8); + + if (x < 0) + x = 0; + if (x > a) + x = a; + lagrange_solve(Sys); + + max_deviation = + MAX(max_deviation, fabs(lmm_variable_getvalue(R_1) - x)); + max_deviation = + MAX(max_deviation, fabs(lmm_variable_getvalue(R_3) - x)); + max_deviation = + MAX(max_deviation, fabs(lmm_variable_getvalue(R_2) - (b - a + x))); + max_deviation = + MAX(max_deviation, fabs(lmm_variable_getvalue(R_1_2_3) - (a - x))); + + if (max_deviation > MAXMIN_PRECISION) { + WARN1("Max Deviation from optimal solution : %g", max_deviation); + WARN1("Found x = %1.20f", x); + WARN2("Deviation from optimal solution (R_1 = %g): %1.20f", x, + lmm_variable_getvalue(R_1) - x); + WARN2("Deviation from optimal solution (R_2 = %g): %1.20f", + b - a + x, lmm_variable_getvalue(R_2) - (b - a + x)); + WARN2("Deviation from optimal solution (R_3 = %g): %1.20f", x, + lmm_variable_getvalue(R_3) - x); + WARN2("Deviation from optimal solution (R_1_2_3 = %g): %1.20f", + a - x, lmm_variable_getvalue(R_1_2_3) - (a - x)); + } + } else { + xbt_assert0(0, "Invalid method"); + } PRINT_VAR(R_1_2_3); PRINT_VAR(R_1); PRINT_VAR(R_2); PRINT_VAR(R_3); -/* DEBUG0("\n"); */ - -/* lmm_update_variable_weight(Sys,R_1_2_3,.5); */ -/* lmm_solve(Sys); */ - -/* PRINT_VAR(R_1_2_3); */ -/* PRINT_VAR(R_1); */ -/* PRINT_VAR(R_2); */ -/* PRINT_VAR(R_3); */ lmm_system_free(Sys); -} +} void test2(method_t method); void test2(method_t method) { - lmm_system_t Sys = NULL ; + lmm_system_t Sys = NULL; lmm_constraint_t CPU1 = NULL; lmm_constraint_t CPU2 = NULL; lmm_variable_t T1 = NULL; lmm_variable_t T2 = NULL; + + if (method == LAGRANGE_VEGAS) + lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp, + func_vegas_fpi); + else if (method == LAGRANGE_RENO) + lmm_set_default_protocol_function(func_reno_f, func_reno_fp, + func_reno_fpi); + Sys = lmm_system_new(); CPU1 = lmm_constraint_new(Sys, (void *) "CPU1", 200.0); CPU2 = lmm_constraint_new(Sys, (void *) "CPU2", 100.0); - T1 = lmm_variable_new(Sys, (void *) "T1", 1.0 , -1.0 , 1); - T2 = lmm_variable_new(Sys, (void *) "T2", 1.0 , -1.0 , 1); + T1 = lmm_variable_new(Sys, (void *) "T1", 1.0, -1.0, 1); + T2 = lmm_variable_new(Sys, (void *) "T2", 1.0, -1.0, 1); + + lmm_update_variable_latency(Sys, T1, 1.0); + lmm_update_variable_latency(Sys, T2, 1.0); + lmm_expand(Sys, CPU1, T1, 1.0); lmm_expand(Sys, CPU2, T2, 1.0); - PRINT_VAR(T1); - PRINT_VAR(T2); - DEBUG0("\n"); - if(method==MAXMIN) + + if (method == MAXMIN) { lmm_solve(Sys); #ifdef HAVE_SDP - else if(method==SDP) - sdp_solve(Sys); + } else if (method == SDP) { + sdp_solve(Sys); #endif - else if(method==LAGRANGE) - lagrange_solve(Sys); - else - xbt_assert0(0,"Invalid method"); + } else if (method == LAGRANGE_VEGAS) { + lagrange_solve(Sys); + } else if (method == LAGRANGE_RENO) { + lagrange_solve(Sys); + } else { + xbt_assert0(0, "Invalid method"); + } PRINT_VAR(T1); PRINT_VAR(T2); - DEBUG0("\n"); - lmm_system_free(Sys); } + + void test3(method_t method); void test3(method_t method) { - int flows=11; //flows and conexions are synonnims ? - int links=10; //topology info - - //just to be carefull + int flows = 11; + int links = 10; + int i = 0; int j = 0; double **A; - lmm_system_t Sys = NULL ; + lmm_system_t Sys = NULL; lmm_constraint_t *tmp_cnst = NULL; - lmm_variable_t *tmp_var = NULL; - char tmp_name[13]; + lmm_variable_t *tmp_var = NULL; + char **tmp_name; /*array to add the the constraints of fictiv variables */ - double B[15] = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, - 1, 1, 1, 1, 1}; + double B[15] = { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, - A = (double **)calloc(links+5, sizeof(double)); - - for(i=0 ; i< links+5; i++){ - A[i] = (double *)calloc(flows+5, sizeof(double)); + 1, 1, 1, 1, 1 + }; - for(j=0 ; j< flows+5; j++){ + A = (double **) calloc(links + 5, sizeof(double)); + + for (i = 0; i < links + 5; i++) { + A[i] = (double *) calloc(flows + 5, sizeof(double)); + + for (j = 0; j < flows + 5; j++) { A[i][j] = 0.0; - if(i >= links || j >= flows){ - A[i][j] = 0.0; + if (i >= links || j >= flows) { + A[i][j] = 0.0; } } } - /*matrix that store the constraints/topollogy*/ + /*matrix that store the constraints/topollogy */ /*double A[15][16]= - {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, + {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, @@ -192,7 +335,7 @@ void test3(method_t method) {0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0}, - + {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, @@ -200,49 +343,49 @@ void test3(method_t method) {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1} }; */ - A[0][1] = 1.0; - A[0][7] = 1.0; - - A[1][1] = 1.0; - A[1][7] = 1.0; - A[1][8] = 1.0; + A[0][1] = 1.0; + A[0][7] = 1.0; - A[2][1] = 1.0; - A[2][8] = 1.0; + A[1][1] = 1.0; + A[1][7] = 1.0; + A[1][8] = 1.0; - A[2][1] = 1.0; - A[2][8] = 1.0; + A[2][1] = 1.0; + A[2][8] = 1.0; - A[3][8] = 1.0; + A[2][1] = 1.0; + A[2][8] = 1.0; - A[4][0] = 1.0; - A[4][3] = 1.0; - A[4][9] = 1.0; + A[3][8] = 1.0; - A[5][0] = 1.0; - A[5][3] = 1.0; - A[5][4] = 1.0; - A[5][9] = 1.0; + A[4][0] = 1.0; + A[4][3] = 1.0; + A[4][9] = 1.0; - A[6][0] = 1.0; - A[6][4] = 1.0; - A[6][9] = 1.0; + A[5][0] = 1.0; + A[5][3] = 1.0; + A[5][4] = 1.0; + A[5][9] = 1.0; + + A[6][0] = 1.0; + A[6][4] = 1.0; + A[6][9] = 1.0; A[6][10] = 1.0; - A[7][2] = 1.0; - A[7][4] = 1.0; - A[7][6] = 1.0; - A[7][9] = 1.0; + A[7][2] = 1.0; + A[7][4] = 1.0; + A[7][6] = 1.0; + A[7][9] = 1.0; A[7][10] = 1.0; - A[8][2] = 1.0; + A[8][2] = 1.0; A[8][10] = 1.0; - A[9][5] = 1.0; - A[9][6] = 1.0; - A[9][9] = 1.0; + A[9][5] = 1.0; + A[9][6] = 1.0; + A[9][9] = 1.0; + - A[10][11] = 1.0; A[11][12] = 1.0; A[12][13] = 1.0; @@ -250,16 +393,29 @@ void test3(method_t method) A[14][15] = 1.0; + if (method == LAGRANGE_VEGAS) + lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp, + func_vegas_fpi); + else if (method == LAGRANGE_RENO) + lmm_set_default_protocol_function(func_reno_f, func_reno_fp, + func_reno_fpi); + Sys = lmm_system_new(); - - + + + + tmp_name = (char **) calloc(31, sizeof(char *)); + for (i = 0; i < 31; i++) { + tmp_name[i] = (char *) calloc(10, sizeof(char)); + } + /* * Creates the constraints */ tmp_cnst = calloc(15, sizeof(lmm_constraint_t)); - for(i=0; i<15; i++){ - sprintf(tmp_name, "C_%03d", i); - tmp_cnst[i] = lmm_constraint_new(Sys, (void *) tmp_name, B[i]); + for (i = 0; i < 15; i++) { + sprintf(tmp_name[i], "C_%03d", i); + tmp_cnst[i] = lmm_constraint_new(Sys, (void *) tmp_name[i], B[i]); } @@ -267,43 +423,47 @@ void test3(method_t method) * Creates the variables */ tmp_var = calloc(16, sizeof(lmm_variable_t)); - for(j=0; j<16; j++){ - sprintf(tmp_name, "X_%03d", j); - tmp_var[j] = lmm_variable_new(Sys, (void *) tmp_name, 1.0, -1.0 , 15); + for (j = 0; j < 16; j++) { + sprintf(tmp_name[i + j], "X_%03d", j); + tmp_var[j] = + lmm_variable_new(Sys, (void *) tmp_name[i + j], 1.0, -1.0, 15); + lmm_update_variable_latency(Sys, tmp_var[j], 1.0); } /* * Link constraints and variables */ - for(i=0;i<15;i++) { - for(j=0; j<16; j++){ - if(A[i][j]){ - lmm_expand(Sys, tmp_cnst[i], tmp_var[j], 1.0); + for (i = 0; i < 15; i++) { + for (j = 0; j < 16; j++) { + if (A[i][j]) { + lmm_expand(Sys, tmp_cnst[i], tmp_var[j], 1.0); } } } - for(j=0; j<16; j++){ - PRINT_VAR(tmp_var[j]); - } - if(method==MAXMIN) + + if (method == MAXMIN) { lmm_solve(Sys); #ifdef HAVE_SDP - else if(method==SDP) - sdp_solve(Sys); + } else if (method == SDP) { + sdp_solve(Sys); #endif - else if(method==LAGRANGE) - lagrange_solve(Sys); - else - xbt_assert0(0,"Invalid method"); + } else if (method == LAGRANGE_VEGAS) { + lagrange_solve(Sys); + } else if (method == LAGRANGE_RENO) { + lagrange_solve(Sys); + } else { + xbt_assert0(0, "Invalid method"); + } - for(j=0; j<16; j++){ + for (j = 0; j < 16; j++) { PRINT_VAR(tmp_var[j]); } free(tmp_var); free(tmp_cnst); + free(tmp_name); lmm_system_free(Sys); } @@ -313,38 +473,65 @@ void test3(method_t method) int main(int argc, char **argv) { - xbt_init(&argc,argv); + xbt_init(&argc, argv); + + + DEBUG0("**************************** "); + DEBUG0("***** ***** "); + DEBUG0("***** TEST 1 ***** "); + DEBUG0("***** ***** "); + DEBUG0("**************************** "); + + + DEBUG0("***** Test 1 (Max-Min) ***** "); + test1(MAXMIN); +#ifdef HAVE_SDP + DEBUG0("***** Test 1 (SDP) ***** "); + test1(SDP); +#endif + DEBUG0("***** Test 1 (Lagrange - Vegas) ***** "); + test1(LAGRANGE_VEGAS); + DEBUG0("***** Test 1 (Lagrange - Reno) ***** "); + test1(LAGRANGE_RENO); -/* DEBUG0("***** Test 1 (Max-Min) ***** \n"); */ -/* test1(MAXMIN); */ -/* #ifdef HAVE_SDP */ -/* DEBUG0("***** Test 1 (SDP) ***** \n"); */ -/* test1(SDP); */ -/* #endif */ -/* DEBUG0("***** Test 1 (Lagrange) ***** \n"); */ -/* test1(LAGRANGE); */ + DEBUG0("**************************** "); + DEBUG0("***** ***** "); + DEBUG0("***** TEST 2 ***** "); + DEBUG0("***** ***** "); + DEBUG0("**************************** "); -/* DEBUG0("***** Test 2 (Max-Min) ***** \n"); */ -/* test2(MAXMIN); */ -/* #ifdef HAVE_SDP */ -/* DEBUG0("***** Test 2 (SDP) ***** \n"); */ -/* test2(SDP); */ -/* #endif */ -/* DEBUG0("***** Test 2 (Lagrange) ***** \n"); */ -/* test2(LAGRANGE); */ + DEBUG0("***** Test 2 (Max-Min) ***** "); + test2(MAXMIN); +#ifdef HAVE_SDP + DEBUG0("***** Test 2 (SDP) ***** "); + test2(SDP); +#endif + DEBUG0("***** Test 2 (Lagrange - Vegas) ***** "); + test2(LAGRANGE_VEGAS); + DEBUG0("***** Test 2 (Lagrange - Reno) ***** "); + test2(LAGRANGE_RENO); -/* DEBUG0("***** Test 3 (Max-Min) ***** \n"); */ -/* test3(MAXMIN); */ + + DEBUG0("**************************** "); + DEBUG0("***** ***** "); + DEBUG0("***** TEST 3 ***** "); + DEBUG0("***** ***** "); + DEBUG0("**************************** "); + + + DEBUG0("***** Test 3 (Max-Min) ***** "); + test3(MAXMIN); #ifdef HAVE_SDP - DEBUG0("***** Test 3 (SDP) ***** \n"); + DEBUG0("***** Test 3 (SDP) ***** "); test3(SDP); #endif - DEBUG0("***** Test 3 (Lagrange) ***** \n"); - test3(LAGRANGE); - + DEBUG0("***** Test 3 (Lagrange - Vegas) ***** "); + test3(LAGRANGE_VEGAS); + DEBUG0("***** Test 3 (Lagrange - Reno) ***** "); + test3(LAGRANGE_RENO); return 0; }