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 #################
# (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
# 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)
*/
void sdp_solve(lmm_system_t sys)
{
- lmm_variable_t var = NULL;
/*
* SDP mapping variables.
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;
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;
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;
* 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.
*/
- 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));
- fprintf(sdpout,"%d\n", nb_var);
+ 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;
- 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.
*/
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 ");
}
/*
block_num++;
}
- fprintf(sdpout,"\n");
+ CDEBUG0(surf_sdp_out," ");
/*
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");
/*
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;
*/
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++;
*/
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
* 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++)
/*
* 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){
/*
* 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");
+ 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(total_block_size, 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.
* 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);
}
-
+
}
