X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/ee5ba64df41bb3f6540616ac2ba157951d79245b..c54088bd491b10bb563f1b672027dd457957dbca:/src/surf/sdp.c

diff --git a/src/surf/sdp.c b/src/surf/sdp.c
index caa920ed1d..547f6849ae 100644
--- a/src/surf/sdp.c
+++ b/src/surf/sdp.c
@@ -30,6 +30,8 @@ static void addentry(struct constraintmatrix *constraints,
 
 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_sdp, surf,
 				"Logging specific to SURF (sdp)");
+XBT_LOG_NEW_SUBCATEGORY(surf_sdp_out, surf,
+				"Logging specific to SURF (sdp)");
 /*
 ########################################################################
 ######################## Simple Proportionnal fairness #################
@@ -41,6 +43,10 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_sdp, 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
@@ -87,6 +93,13 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_sdp, 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)
 */
 
@@ -104,7 +117,6 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_sdp, surf,
 
 void sdp_solve(lmm_system_t sys)
 {
-  lmm_variable_t var = NULL;
 
   /*
    * SDP mapping variables.
@@ -117,10 +129,12 @@ 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 block_size; 
+  int total_block_size=0;
   int *isdiag=NULL;
-  FILE *sdpout = fopen("SDPA-printf.tmp","w");
+  //  FILE *sdpout = fopen("SDPA-printf.tmp","w");
   int blocksz = 0;
   double *tempdiag = NULL;
   int matno=0;
@@ -146,53 +160,86 @@ 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;
 
-
-  DEBUG0("HI!!!!");
   /* 
    * Initialize the var list variable with only the active variables. 
    * Associate an index in the swag variables.
    */
-  i = 1;
   var_list = &(sys->variable_set);
+  i=0;
+  xbt_swag_foreach(var, var_list) {
+    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->saturated_constraint_set);  
+
+  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.
    */
-  flows = i-1;
   links = xbt_swag_size(&(sys->active_constraint_set));
 
   /* 
    * This  number is found based on the tree structure explained on top.
    */
-  K = (int)log((double)flows)/log(2.0);
-  
+  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 style.
+   * 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);
   
+ 
   /*
    * Find the size of each group of constraints.
    */
   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;
-
+  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. 
@@ -226,11 +273,11 @@ void sdp_solve(lmm_system_t sys)
      * Structured blocks are size 2 and all others are size 1.
      */
     if(i <= nb_cnsts_struct){
-      block_size = 2;
-      fprintf(sdpout,"2 ");
+      total_block_size += block_size = 2;
+      DEBUG0("2 ");
     }else{
-      block_size = 1;
-      fprintf(sdpout,"1 ");
+      total_block_size += block_size = 1;
+      CDEBUG0(surf_sdp_out,"1 ");
     }
     
     /*
@@ -243,7 +290,7 @@ void sdp_solve(lmm_system_t sys)
     block_num++;
   }
 
-  fprintf(sdpout,"\n");
+  CDEBUG0(surf_sdp_out," ");
 
 
   /*
@@ -253,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");
 
 
   /*
@@ -271,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;
@@ -297,26 +343,41 @@ void sdp_solve(lmm_system_t sys)
    */
   xbt_swag_foreach(cnst, cnst_list) {
 
-    fprintf(sdpout,"0 %d 1 1 %d\n", block_num,  (int) - (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;
-      fprintf(sdpout,"%d %d 1 1 %d\n", elem->variable->index, block_num, (int) - (elem->variable->value)); 
-      addentry(constraints, &C, elem->variable->index, block_num, 1, 1, - (elem->value), C.blocks[block_num].blocksize);
+      matno=get_y(K,elem->variable->index);
+      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);
+ 
     }
+    block_num++;
   }
 
   
-  //Positivy constraint blocks
+  /*
+   * Positivy constraint blocks.
+   */
   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
@@ -329,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++)
@@ -345,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){
@@ -380,66 +439,85 @@ void sdp_solve(lmm_system_t sys)
   /*
    * Debuging print problem in SDPA format.
    */
-  printf("Printing SDPA...\n");
   if(XBT_LOG_ISENABLED(surf_sdp, xbt_log_priority_debug)) {
-    char *tmp=strdup("SDPA.tmp");
-    write_prob(tmp, nb_cnsts, nb_var, C, a, constraints);  
-    //int write_prob(char *fname, int n, int k, struct blockmatrix C, double *a, struct constraintmatrix *constraints);
-    free(tmp);
+    DEBUG0("Printing SDPA...");
+    tmp=strdup("SURF-PROPORTIONNAL.sdpa");
+    write_prob(tmp,total_block_size,nb_var,C,a,constraints);
   }
 
   /*
    * Initialize parameters.
    */
-  printf("Initializing solution...\n");
-  initsoln(nb_cnsts, nb_var, C, a, constraints, &X, &y, &Z);  
+  DEBUG0("Initializing solution...");
+  initsoln(total_block_size, nb_var, C, a, constraints, &X, &y, &Z);  
   
 
 
   /*
    * Call the solver.
    */
-  printf("Calling the solver...\n");
-  int ret = easy_sdp(nb_cnsts, nb_var, C, a, constraints, 0.0, &X, &y, &Z, &pobj, &dobj);
+  DEBUG0("Calling the solver...");
+  stdout_sav=stdout;
+  stdout=fopen("/dev/null","w");
+  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: printf("SUCCESS The problem is primal infeasible\n");
+  case 1: DEBUG0("SUCCESS The problem is primal infeasible");
           break;
 
-  case 2: printf("SUCCESS The problem is dual infeasible\n");
+  case 2: DEBUG0("SUCCESS The problem is dual infeasible");
           break;
  
-  case 3: printf("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: printf("Failure. Maximum number of iterations reached.");
+  case 4: DEBUG0("Failure. Maximum number of iterations reached.");
           break;
 
-  case 5: printf("Failure. Stuck at edge of primal feasibility.");
+  case 5: DEBUG0("Failure. Stuck at edge of primal feasibility.");
           break;
 
   }
 
+  if(XBT_LOG_ISENABLED(surf_sdp, xbt_log_priority_debug)) {
+    tmp=strdup("SURF-PROPORTIONNAL.sol");
+    write_sol(tmp,total_block_size, nb_var, X, y, Z);
+  }
+
   /*
    * Write out the solution if necessary.
    */
-  //printf("Writting simple dsp...\n");
-  //write_sol("output.sol", n, k, X, y, Z);
+  xbt_swag_foreach(cnst, cnst_list) {
+
+    elem_list = &(cnst->element_set);
+    xbt_swag_foreach(elem, elem_list) {
+      if(elem->variable->weight <=0) break;
+      
+      i = (int)get_y(K, elem->variable->index);
+      elem->variable->value = y[i]; 
+      
+    }
+  }
+
 
   /*
    * Free up memory.
    */
-  //free_prob(n, k, C, a, constraints, X, y, Z);
+  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);
   }
-
+ 
 }
 
 
@@ -601,3 +679,4 @@ void addentry(struct constraintmatrix *constraints,
     
   }
 }
+