From: alegrand Date: Wed, 25 Jul 2007 12:45:36 +0000 (+0000) Subject: * Added an "exact" alternative computation for test1 to check the lagrange results... X-Git-Tag: v3.3~1470 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/645f6efc7c0b668fccd73c6c9176eba04fc6cd5a * Added an "exact" alternative computation for test1 to check the lagrange results. Quite depressing for the moment but it should help in the end... * Cosmetics (indent). git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@3890 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- diff --git a/testsuite/surf/simeng_usage.c b/testsuite/surf/simeng_usage.c index 17cc29e7ba..f517beb691 100644 --- a/testsuite/surf/simeng_usage.c +++ b/testsuite/surf/simeng_usage.c @@ -15,14 +15,15 @@ #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); /* */ /* ______ */ @@ -37,10 +38,66 @@ typedef enum { 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; @@ -50,29 +107,31 @@ void test1(method_t method) lmm_variable_t R_2 = NULL; lmm_variable_t R_3 = NULL; - if(method==LAGRANGE_VEGAS){ + double a = 1.0, b = 10.0; + + if (method == LAGRANGE_VEGAS) { //set default functions for TCP Vegas lmm_set_default_protocol_function(func_vegas_fpi); - }else if(method==LAGRANGE_RENO){ + } else if (method == LAGRANGE_RENO) { //set default functions for TCP Reno lmm_set_default_protocol_function(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_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); @@ -85,20 +144,84 @@ void test1(method_t method) lmm_expand(Sys, L3, R_3, 1.0); - 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_VEGAS){ - //set default functions for TCP Vegas - lagrange_solve(Sys); - }else if(method==LAGRANGE_RENO){ - //set default functions for TCP Reno - 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 > 1e-8) { + DEBUG1("Max Deviation from optimal solution : %g", max_deviation); + DEBUG1("Found x = %1.20f", x); + DEBUG1("Deviation from optimal solution (R_1): %1.20f", + lmm_variable_getvalue(R_1) - x); + DEBUG1("Deviation from optimal solution (R_2): %1.20f", + lmm_variable_getvalue(R_2) - (b - a + x)); + DEBUG1("Deviation from optimal solution (R_3): %1.20f", + lmm_variable_getvalue(R_3) - x); + DEBUG1("Deviation from optimal solution (R_1_2_3): %1.20f", + 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 > 1e-8) { + DEBUG1("Max Deviation from optimal solution : %g", max_deviation); + DEBUG1("Found x = %1.20f", x); + DEBUG1("Deviation from optimal solution (R_1): %1.20f", + lmm_variable_getvalue(R_1) - x); + DEBUG1("Deviation from optimal solution (R_2): %1.20f", + lmm_variable_getvalue(R_2) - (b - a + x)); + DEBUG1("Deviation from optimal solution (R_3): %1.20f", + lmm_variable_getvalue(R_3) - x); + DEBUG1("Deviation from optimal solution (R_1_2_3): %1.20f", + lmm_variable_getvalue(R_1_2_3) - (a - x)); + } + } else { + xbt_assert0(0, "Invalid method"); } PRINT_VAR(R_1_2_3); @@ -107,12 +230,12 @@ void test1(method_t method) 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; @@ -120,10 +243,10 @@ void test2(method_t method) lmm_variable_t T2 = NULL; - if(method==LAGRANGE_VEGAS){ + if (method == LAGRANGE_VEGAS) { //set default functions for TCP Vegas lmm_set_default_protocol_function(func_vegas_fpi); - }else if(method==LAGRANGE_RENO){ + } else if (method == LAGRANGE_RENO) { //set default functions for TCP Reno lmm_set_default_protocol_function(func_reno_fpi); } @@ -132,8 +255,8 @@ void test2(method_t method) 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); @@ -144,20 +267,18 @@ void test2(method_t method) - 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_VEGAS){ - //set default functions for TCP Vegas - lagrange_solve(Sys); - }else if(method==LAGRANGE_RENO){ - //set default functions for TCP Reno - 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); @@ -171,43 +292,43 @@ void test2(method_t method) 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; + 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, + double B[15] = { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, + + 1, 1, 1, 1, 1 + }; - 1, 1, 1, 1, 1}; + A = (double **) calloc(links + 5, sizeof(double)); - A = (double **)calloc(links+5, sizeof(double)); - - for(i=0 ; i< links+5; i++){ - A[i] = (double *)calloc(flows+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++){ + 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}, @@ -217,7 +338,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}, @@ -225,49 +346,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[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[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[3][8] = 1.0; - A[4][0] = 1.0; - A[4][3] = 1.0; - A[4][9] = 1.0; + A[4][0] = 1.0; + A[4][3] = 1.0; + A[4][9] = 1.0; - A[5][0] = 1.0; - A[5][3] = 1.0; - A[5][4] = 1.0; - A[5][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][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; @@ -275,29 +396,27 @@ void test3(method_t method) A[14][15] = 1.0; - if(method==LAGRANGE_VEGAS){ - //set default functions for TCP Vegas + if (method == LAGRANGE_VEGAS) { lmm_set_default_protocol_function(func_vegas_fpi); - }else if(method==LAGRANGE_RENO){ - //set default functions for TCP Reno + } else if (method == LAGRANGE_RENO) { lmm_set_default_protocol_function(func_reno_fpi); } Sys = lmm_system_new(); - + tmp_name = (char **) calloc(31, sizeof(char *)); - for(i=0; i<31; i++){ + 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[i], "C_%03d", 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]); } @@ -306,42 +425,41 @@ 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[i+j], "X_%03d", j); - tmp_var[j] = lmm_variable_new(Sys, (void *) tmp_name[i+j], 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); } } } - 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_VEGAS){ - //set default functions for TCP Vegas - lagrange_solve(Sys); - }else if(method==LAGRANGE_RENO){ - //set default functions for TCP Reno - 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]); } @@ -357,7 +475,7 @@ void test3(method_t method) int main(int argc, char **argv) { - xbt_init(&argc,argv); + xbt_init(&argc, argv); DEBUG0("**************************** ");