X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/a15306a130d26b8c7ca2d2ffb044d7dfb36c03bd..778f65057da68465382593cd036b6ee59ada54e9:/src/surf/sdp.c diff --git a/src/surf/sdp.c b/src/surf/sdp.c index 35a49bf33f..547f6849ae 100644 --- a/src/surf/sdp.c +++ b/src/surf/sdp.c @@ -43,6 +43,10 @@ XBT_LOG_NEW_SUBCATEGORY(surf_sdp_out, surf, # (A.x)_2 <= b_2 # ... # (A.x)_m <= b_m +# x_1 <= c_1 +# x_2 <= c_2 +# ... +# x_m <= c_m # x>=0 # # We assume in the following that n=2^K @@ -89,6 +93,13 @@ XBT_LOG_NEW_SUBCATEGORY(surf_sdp_out, surf, # forall k in [0,K], and i in [1,2^k] # y(k,i) >= 0 # +# Latency Constraints: +# forall i in [1,2^k] and v in [0,m-1] +# if(i <= m-1){ +# y(k-1, i) <= bound +# }else{ +# y(k-1, i) <= 1 +# } # Minimize -y(0,1) */ @@ -106,7 +117,6 @@ XBT_LOG_NEW_SUBCATEGORY(surf_sdp_out, surf, void sdp_solve(lmm_system_t sys) { - lmm_variable_t var = NULL; /* * SDP mapping variables. @@ -119,6 +129,7 @@ void sdp_solve(lmm_system_t sys) int nb_cnsts_capacity=0; int nb_cnsts_struct=0; int nb_cnsts_positivy=0; + int nb_cnsts_latency=0; int block_num=0; int block_size; int total_block_size=0; @@ -149,6 +160,15 @@ void sdp_solve(lmm_system_t sys) xbt_swag_t cnst_list = NULL; xbt_swag_t var_list = NULL; xbt_swag_t elem_list = NULL; + lmm_variable_t var = NULL; + + double tmp_k; + struct sparseblock *p; + char *tmp = NULL; + FILE *stdout_sav; + int ret; + + if ( !(sys->modified)) return; @@ -160,17 +180,30 @@ void sdp_solve(lmm_system_t sys) var_list = &(sys->variable_set); i=0; xbt_swag_foreach(var, var_list) { - if(var->weight) i++; + if(var->weight != 0.0) i++; } + + + flows=i; DEBUG1("Variable set : %d", xbt_swag_size(var_list)); + DEBUG1("Flows : %d", flows); + + if(flows == 0){ + return; + } + + xbt_swag_foreach(var, var_list) { var->value = 0.0; - if(var->weight) var->index = i--; + if(var->weight) { + var->index = i--; + } } cnst_list=&(sys->active_constraint_set); DEBUG1("Active constraints : %d", xbt_swag_size(cnst_list)); + DEBUG1("Links : %d", links); /* * Those fields are the top level description of the platform furnished in the xml file. @@ -180,18 +213,17 @@ void sdp_solve(lmm_system_t sys) /* * This number is found based on the tree structure explained on top. */ - double tmp_k; - tmp_k = (double) log((double)flows)/log(2.0); K = (int) ceil(tmp_k); - + //xbt_assert1(K!=0, "Invalide value of K (=%d) aborting.", K); + /* * The number of variables in the SDP program. */ nb_var = get_y(K, pow(2,K)); DEBUG1("Number of variables in the SDP program : %d", nb_var); - CDEBUG1(surf_sdp_out,"%d", nb_var); + /* * Find the size of each group of constraints. @@ -199,12 +231,15 @@ void sdp_solve(lmm_system_t sys) nb_cnsts_capacity = links + ((int)pow(2,K)) - flows; nb_cnsts_struct = (int)pow(2,K) - 1; nb_cnsts_positivy = (int)pow(2,K); + nb_cnsts_latency = nb_var; + /* * The total number of constraints. */ - nb_cnsts = nb_cnsts_capacity + nb_cnsts_struct + nb_cnsts_positivy; - //fprintf(sdpout,"%d\n", nb_cnsts); + nb_cnsts = nb_cnsts_capacity + nb_cnsts_struct + nb_cnsts_positivy + nb_cnsts_latency; + CDEBUG1(surf_sdp_out,"Number of constraints = %d", nb_cnsts); + DEBUG1("Number of constraints in the SDP program : %d", nb_cnsts); /* * Keep track of which blocks have off diagonal entries. @@ -239,10 +274,10 @@ void sdp_solve(lmm_system_t sys) */ if(i <= nb_cnsts_struct){ total_block_size += block_size = 2; - //fprintf(sdpout,"2 "); + DEBUG0("2 "); }else{ total_block_size += block_size = 1; - //fprintf(sdpout,"1 "); + CDEBUG0(surf_sdp_out,"1 "); } /* @@ -255,7 +290,7 @@ void sdp_solve(lmm_system_t sys) block_num++; } - //fprintf(sdpout,"\n"); + CDEBUG0(surf_sdp_out," "); /* @@ -265,14 +300,13 @@ void sdp_solve(lmm_system_t sys) for(i = 1; i <= nb_var; i++){ if(get_y(0,1)==i){ - //fprintf(sdpout,"-1 "); + //CDEBUG0(surf_sdp_out,"-1 "); a[i]=-1; }else{ - //fprintf(sdpout,"0 "); + //CDEBUG0(surf_sdp_out,"0 "); a[i]=0; } } - //fprintf(sdpout,"\n"); /* @@ -283,19 +317,19 @@ void sdp_solve(lmm_system_t sys) for(k = 1; k <= K; k++){ for(i = 1; i <= pow(2,k-1); i++){ matno=get_y(k,2*i-1); - //fprintf(sdpout,"%d %d 1 1 1\n", matno , block_num); + CDEBUG2(surf_sdp_out,"%d %d 1 1 1", matno , block_num); addentry(constraints, &C, matno, block_num, 1, 1, 1.0, C.blocks[block_num].blocksize); matno=get_y(k,2*i); - //fprintf(sdpout,"%d %d 2 2 1\n", matno , block_num); + CDEBUG2(surf_sdp_out,"%d %d 2 2 1", matno , block_num); addentry(constraints, &C, matno, block_num, 2, 2, 1.0, C.blocks[block_num].blocksize); matno=get_y(k-1,i); - //fprintf(sdpout,"%d %d 1 2 1\n", matno , block_num); + CDEBUG2(surf_sdp_out,"%d %d 1 2 1", matno , block_num); addentry(constraints, &C, matno, block_num, 1, 2, 1.0, C.blocks[block_num].blocksize); matno=get_y(k-1,i); - //fprintf(sdpout,"%d %d 2 1 1\n", matno , block_num); + CDEBUG2(surf_sdp_out,"%d %d 2 1 1", matno , block_num); addentry(constraints, &C, matno, block_num, 2, 1, 1.0, C.blocks[block_num].blocksize); isdiag[block_num] = 0; @@ -309,15 +343,14 @@ void sdp_solve(lmm_system_t sys) */ xbt_swag_foreach(cnst, cnst_list) { - //fprintf(sdpout,"0 %d 1 1 %f\n", block_num, - (cnst->bound)); - addentry(constraints, &C, 0, block_num, 1, 1, - (cnst->bound) , C.blocks[block_num].blocksize); - + CDEBUG2(surf_sdp_out,"0 %d 1 1 %f", block_num, - (cnst->bound)); + addentry(constraints, &C, 0, block_num, 1, 1, - (cnst->bound) , C.blocks[block_num].blocksize); elem_list = &(cnst->element_set); - xbt_swag_foreach(elem, elem_list) { + xbt_swag_foreach(elem, elem_list){ if(elem->variable->weight <=0) break; matno=get_y(K,elem->variable->index); - //fprintf(sdpout,"%d %d 1 1 %f\n", elem->variable->index, block_num, - (elem->value)); + CDEBUG3(surf_sdp_out,"%d %d 1 1 %f", matno, block_num, - (elem->value)); addentry(constraints, &C, matno, block_num, 1, 1, - (elem->value), C.blocks[block_num].blocksize); } @@ -330,11 +363,21 @@ void sdp_solve(lmm_system_t sys) */ for(i = 1; i <= pow(2,K); i++){ matno=get_y(K, i); - //fprintf(sdpout,"%d %d 1 1 1\n", matno, block_num); + CDEBUG2(surf_sdp_out,"%d %d 1 1 1", matno, block_num); addentry(constraints, &C, matno, block_num, 1, 1, 1.0, C.blocks[block_num].blocksize); block_num++; } - + /* + * Latency constraint blocks. + */ + xbt_swag_foreach(var, var_list) { + var->value = 0.0; + if(var->weight && var->bound > 0) { + matno = get_y(K,var->index); + CDEBUG3(surf_sdp_out,"%d %d 1 1 %f", matno, block_num, var->bound); + addentry(constraints, &C, matno, block_num, 1, 1, var->bound, C.blocks[block_num].blocksize); + } + } /* * At this point, we'll stop to recognize whether any of the blocks @@ -347,8 +390,6 @@ void sdp_solve(lmm_system_t sys) * We have a hidden diagonal block! */ - //printf("Block %d is actually diagonal.\n",i); - blocksz=C.blocks[i].blocksize; tempdiag=(double *)calloc((blocksz+1), sizeof(double)); for (j=1; j<=blocksz; j++) @@ -363,7 +404,7 @@ void sdp_solve(lmm_system_t sys) /* * Next, setup issparse and NULL out all nextbyblock pointers. */ - struct sparseblock *p=NULL; + p=NULL; for (i=1; i<=k; i++) { p=constraints[i].blocks; while (p != NULL){ @@ -399,16 +440,15 @@ void sdp_solve(lmm_system_t sys) * Debuging print problem in SDPA format. */ if(XBT_LOG_ISENABLED(surf_sdp, xbt_log_priority_debug)) { - DEBUG0("Printing SDPA...\n"); - char *tmp=strdup("SURF-PROPORTIONNAL.sdpa"); + DEBUG0("Printing SDPA..."); + tmp=strdup("SURF-PROPORTIONNAL.sdpa"); write_prob(tmp,total_block_size,nb_var,C,a,constraints); - free(tmp); } /* * Initialize parameters. */ - DEBUG0("Initializing solution...\n"); + DEBUG0("Initializing solution..."); initsoln(total_block_size, nb_var, C, a, constraints, &X, &y, &Z); @@ -416,22 +456,22 @@ void sdp_solve(lmm_system_t sys) /* * Call the solver. */ - DEBUG0("Calling the solver...\n"); - FILE *stdout_sav=stdout; + DEBUG0("Calling the solver..."); + stdout_sav=stdout; stdout=fopen("/dev/null","w"); - int ret = easy_sdp(total_block_size, nb_var, C, a, constraints, 0.0, &X, &y, &Z, &pobj, &dobj); + ret = easy_sdp(total_block_size, nb_var, C, a, constraints, 0.0, &X, &y, &Z, &pobj, &dobj); fclose(stdout); stdout=stdout_sav; switch(ret){ case 0: - case 1: DEBUG0("SUCCESS The problem is primal infeasible\n"); + case 1: DEBUG0("SUCCESS The problem is primal infeasible"); break; - case 2: DEBUG0("SUCCESS The problem is dual infeasible\n"); + case 2: DEBUG0("SUCCESS The problem is dual infeasible"); break; - case 3: DEBUG0("Partial SUCCESS A solution has been found, but full accuracy was not achieved. One or more of primal infeasibility, dual infeasibility, or relative duality gap are larger than their tolerances, but by a factor of less than 1000.\n"); + case 3: DEBUG0("Partial SUCCESS A solution has been found, but full accuracy was not achieved. One or more of primal infeasibility, dual infeasibility, or relative duality gap are larger than their tolerances, but by a factor of less than 1000."); break; case 4: DEBUG0("Failure. Maximum number of iterations reached."); @@ -443,9 +483,8 @@ void sdp_solve(lmm_system_t sys) } if(XBT_LOG_ISENABLED(surf_sdp, xbt_log_priority_debug)) { - char *tmp=strdup("SURF-PROPORTIONNAL.sol"); + tmp=strdup("SURF-PROPORTIONNAL.sol"); write_sol(tmp,total_block_size, nb_var, X, y, Z); - free(tmp); } /* @@ -468,15 +507,17 @@ void sdp_solve(lmm_system_t sys) * Free up memory. */ free_prob(total_block_size, nb_var, C, a, constraints, X, y, Z); - - // fclose(sdpout); + free(isdiag); + free(tempdiag); + free(tmp); + sys->modified = 0; - + if(XBT_LOG_ISENABLED(surf_sdp, xbt_log_priority_debug)) { lmm_print(sys); } - + }