root/ompi/mca/topo/treematch/treematch/tm_solution.c

DEFINITIONS

1. tm_free_solution
2. distance
3. display_sol_sum_com
4. display_sol_max_com
5. display_sol_hop_byte
6. display_sol
7. tm_display_solution
8. tm_display_other_heuristics
9. in_tab
10. map_Packed
11. map_RR
12. hash_asc
13. generate_random_sol
14. eval_sol
15. exchange
16. gain_exchange
17. select_max
18. compute_gain
19. map_MPIPP

   1 #include <ctype.h>
   2 #include <float.h>
   3 #include "tm_solution.h"
   4 #include "tm_mt.h"
   5 #include "tm_topology.h"
   6 
   7 typedef struct {
   8   int  val;
   9   long key;
  10 } hash_t;
  11 
  12 
  13 
  14 void tm_free_solution(tm_solution_t *sol);
  15 int distance(tm_topology_t *topology,int i, int j);
  16 double display_sol_sum_com(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma);
  17   double display_sol(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma, tm_metric_t metric);
  18 double tm_display_solution(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_solution_t *sol,
  19                            tm_metric_t metric);
  20 void tm_display_other_heuristics(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_metric_t metric);
  21 int in_tab(int *tab, int n, int val);
  22 void map_Packed(tm_topology_t *topology, int N, int *sigma);
  23 void map_RR(tm_topology_t * topology, int N, int *sigma);
  24 int hash_asc(const void* x1,const void* x2);
  25 int *generate_random_sol(tm_topology_t *topology,int N, int seed);
  26 double eval_sol(int *sol,int N,double **comm, double **arch);
  27 void exchange(int *sol,int i,int j);
  28 double gain_exchange(int *sol,int l,int m,double eval1,int N,double **comm, double **arch);
  29 void select_max(int *l,int *m,double **gain,int N,int *state);
  30 void compute_gain(int *sol,int N,double **gain,double **comm, double **arch);
  31 void map_MPIPP(tm_topology_t *topology,int nb_seed,int N,int *sigma,double **comm, double **arch);
  32 
  33 
  34 void tm_free_solution(tm_solution_t *sol){
  35   int i,n;
  36 
  37   n = sol->k_length;
  38 
  39   if(sol->k)
  40     for(i=0 ; i<n ; i++)
  41       FREE(sol->k[i]);
  42 
  43   FREE(sol->k);
  44   FREE(sol->sigma);
  45   FREE(sol);
  46 }
  47 
  48 /*
  49    Compute the distance in the tree
  50    between node i and j : the farther away node i and j, the
  51    larger the returned value.
  52 
  53    The algorithm looks at the largest level, starting from the top,
  54    for which node i and j are still in the same subtree. This is done
  55    by iteratively dividing their numbering by the arity of the levels
  56 */
  57 int distance(tm_topology_t *topology,int i, int j)
  58 {
  59   int level = 0;
  60   int arity;
  61   int f_i, f_j ;
  62   int vl = tm_get_verbose_level();
  63   int depth = topology->nb_levels-1;
  64 
  65   f_i = topology->node_rank[i];
  66   f_j = topology->node_rank[j];
  67 
  68   if(vl >= DEBUG)
  69     printf("i=%d, j=%d Level = %d f=(%d,%d)\n",i ,j, level, f_i, f_j);
  70 
  71 
  72   do{
  73     level++;
  74     arity = topology->arity[level];
  75     if( arity == 0 )
  76       arity = 1;
  77     f_i = f_i/arity;
  78     f_j = f_j/arity;
  79   } while((f_i!=f_j) && (level < depth));
  80 
  81   if(vl >= DEBUG)
  82     printf("distance(%d,%d):%d\n",topology->node_rank[i], topology->node_rank[j], level);
  83   /* exit(-1); */
  84   return level;
  85 }
  86 
  87 double display_sol_sum_com(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma)
  88 {
  89   double a,c,sol;
  90   int i,j;
  91   double *cost = topology->cost;
  92   double **mat = aff_mat->mat;
  93   int N = aff_mat->order;
  94   int depth = topology->nb_levels - 1;
  95 
  96 
  97   sol = 0;
  98   for ( i = 0 ; i < N ; i++ )
  99     for ( j = i+1 ; j < N ; j++){
 100       c = mat[i][j];
 101       /*
 102            Compute cost in funvtion of the inverse of the distance
 103            This is due to the fact that the cost matrix is numbered
 104            from top to bottom : cost[0] is the cost of the longest distance.
 105       */
 106       a = cost[depth-distance(topology,sigma[i],sigma[j])];
 107       if(tm_get_verbose_level() >= DEBUG)
 108         printf("T_%d_%d %f*%f=%f\n",i,j,c,a,c*a);
 109       sol += c*a;
 110     }
 111 
 112   for (i = 0; i < N; i++) {
 113     printf("%d", sigma[i]);
 114     if(i<N-1)
 115       printf(",");
 116   }
 117   printf(" : %g\n",sol);
 118 
 119   return sol;
 120 }
 121 
 122 
 123 static double display_sol_max_com(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma)
 124 {
 125   double a,c,sol;
 126   int i,j;
 127   double *cost = topology->cost;
 128   double **mat = aff_mat->mat;
 129   int N = aff_mat->order;
 130   int vl = tm_get_verbose_level();
 131   int depth = topology->nb_levels - 1;
 132 
 133   sol = 0;
 134   for ( i = 0 ; i < N ; i++ )
 135     for ( j = i+1 ; j < N ; j++){
 136       c = mat[i][j];
 137       /*
 138            Compute cost in funvtion of the inverse of the distance
 139            This is due to the fact that the cost matrix is numbered
 140            from top to bottom : cost[0] is the cost of the longest distance.
 141       */
 142       a = cost[depth-distance(topology,sigma[i],sigma[j])];
 143       if(vl >= DEBUG)
 144         printf("T_%d_%d %f*%f=%f\n",i,j,c,a,c*a);
 145       if(c*a > sol)
 146         sol = c*a;
 147     }
 148 
 149   for (i = 0; i < N; i++) {
 150     printf("%d", sigma[i]);
 151     if(i<N-1)
 152       printf(",");
 153   }
 154   printf(" : %g\n",sol);
 155 
 156   return sol;
 157 }
 158 
 159 static double display_sol_hop_byte(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma)
 160 {
 161   double c,sol;
 162   int nb_hops;
 163   int i,j;
 164   double **mat = aff_mat->mat;
 165   int N = aff_mat->order;
 166 
 167   sol = 0;
 168   for ( i = 0 ; i < N ; i++ )
 169     for ( j = i+1 ; j < N ; j++){
 170       c = mat[i][j];
 171       nb_hops = 2*distance(topology,sigma[i],sigma[j]);
 172       if(tm_get_verbose_level() >= DEBUG)
 173         printf("T_%d_%d %f*%d=%f\n",i,j,c,nb_hops,c*nb_hops);
 174       sol += c*nb_hops;
 175     }
 176 
 177   for (i = 0; i < N; i++) {
 178     printf("%d", sigma[i]);
 179     if(i<N-1)
 180       printf(",");
 181   }
 182   printf(" : %g\n",sol);
 183 
 184   return sol;
 185 }
 186 
 187 
 188 
 189 double display_sol(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma, tm_metric_t metric){
 190   switch (metric){
 191   case TM_METRIC_SUM_COM:
 192     return display_sol_sum_com(topology, aff_mat, sigma);
 193   case TM_METRIC_MAX_COM:
 194     return display_sol_max_com(topology, aff_mat, sigma);
 195   case TM_METRIC_HOP_BYTE:
 196     return display_sol_hop_byte(topology, aff_mat, sigma);
 197   default:
 198     if(tm_get_verbose_level() >= ERROR){
 199       fprintf(stderr,"Error printing solution: metric %d not implemented\n",metric);
 200       return -1;
 201     }
 202   }
 203   return -1;
 204 }
 205 
 206 double tm_display_solution(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_solution_t *sol,
 207                            tm_metric_t metric){
 208 
 209   int i,j;
 210   int **k = sol->k;
 211 
 212 
 213   if(tm_get_verbose_level() >= DEBUG){
 214     printf("k: \n");
 215     for( i = 0 ; i < nb_processing_units(topology) ; i++ ){
 216       if(k[i][0] != -1){
 217         printf("\tProcessing unit %d: ",i);
 218         for (j = 0 ; j<topology->oversub_fact; j++){
 219           if( k[i][j] == -1)
 220             break;
 221           printf("%d ",k[i][j]);
 222         }
 223         printf("\n");
 224       }
 225     }
 226   }
 227 
 228 
 229   return display_sol(topology, aff_mat, sol->sigma, metric);
 230 }
 231 
 232 void tm_display_other_heuristics(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_metric_t metric)
 233 {
 234   int *sigma = NULL;
 235   int N  = aff_mat->order;
 236 
 237   sigma = (int*)MALLOC(sizeof(int)*N);
 238 
 239   map_Packed(topology, N, sigma);
 240   printf("Packed: ");
 241   display_sol(topology, aff_mat, sigma, metric);
 242 
 243   map_RR(topology, N, sigma);
 244   printf("RR: ");
 245   display_sol(topology, aff_mat, sigma, metric);
 246 
 247 /*   double duration; */
 248 /*   CLOCK_T time1,time0; */
 249 /*   CLOCK(time0); */
 250 /*   map_MPIPP(topology,1,N,sigma,comm,arch); */
 251 /*   CLOCK(time1); */
 252 /*   duration=CLOCK_DIFF(time1,time0); */
 253 /*   printf("MPIPP-1-D:%f\n",duration); */
 254 /*   printf("MPIPP-1: "); */
 255 /*   if (TGT_flag == 1)  */
 256 /*     print_sigma_inv(N,sigma,comm,arch); */
 257 /*   else */
 258 /*   print_sigma(N,sigma,comm,arch); */
 259 
 260 /*   CLOCK(time0); */
 261 /*   map_MPIPP(topology,5,N,sigma,comm,arch); */
 262 /*   CLOCK(time1); */
 263 /*   duration=CLOCK_DIFF(time1,time0); */
 264 /*   printf("MPIPP-5-D:%f\n",duration); */
 265 /*   printf("MPIPP-5: "); */
 266 /*   if (TGT_flag == 1)  */
 267 /*     print_sigma_inv(N,sigma,comm,arch); */
 268 /*   else */
 269 /*   print_sigma(N,sigma,comm,arch); */
 270 
 271   FREE(sigma);
 272 }
 273 
 274 
 275 int in_tab(int *tab, int n, int val){
 276   int i;
 277   for( i = 0; i < n ; i++)
 278     if(tab[i] == val)
 279       return 1;
 280 
 281   return 0;
 282 }
 283 
 284 void map_Packed(tm_topology_t *topology, int N, int *sigma)
 285 {
 286   size_t i;
 287   int j = 0,depth;
 288   int vl = tm_get_verbose_level();
 289 
 290   depth = topology->nb_levels-1;
 291 
 292   for( i = 0 ; i < topology->nb_nodes[depth] ; i++){
 293     /* printf ("%d -> %d\n",objs[i]->os_index,i); */
 294     if((!topology->constraints) || (in_tab(topology->constraints, topology->nb_constraints, topology->node_id[i]))){
 295       if(vl >= DEBUG)
 296         printf ("%lu: %d -> %d\n", i, j, topology->node_id[i]);
 297       sigma[j++]=topology->node_id[i];
 298       if(j == N)
 299         break;
 300     }
 301   }
 302 }
 303 
 304 void map_RR(tm_topology_t *topology, int N,int *sigma)
 305 {
 306   int i;
 307   int vl = tm_get_verbose_level();
 308 
 309   for( i = 0 ; i < N ; i++ ){
 310     if(topology->constraints)
 311       sigma[i]=topology->constraints[i%topology->nb_constraints];
 312     else
 313       sigma[i]=i%topology->nb_proc_units;
 314     if(vl >= DEBUG)
 315       printf ("%d -> %d (%d)\n",i,sigma[i],topology->nb_proc_units);
 316   }
 317 }
 318 
 319 int hash_asc(const void* x1,const void* x2)
 320 {
 321   hash_t *e1 = NULL,*e2 = NULL;
 322 
 323   e1 = ((hash_t*)x1);
 324   e2 = ((hash_t*)x2);
 325 
 326   return (e1->key < e2->key) ? -1 : 1;
 327 }
 328 
 329 
 330 int *generate_random_sol(tm_topology_t *topology,int N, int seed)
 331 {
 332   hash_t *hash_tab = NULL;
 333   int *sol = NULL;
 334   int *nodes_id= NULL;
 335   int i;
 336 
 337   nodes_id = topology->node_id;
 338 
 339   hash_tab = (hash_t*)MALLOC(sizeof(hash_t)*N);
 340   sol = (int*)MALLOC(sizeof(int)*N);
 341 
 342   init_genrand(seed);
 343 
 344   for( i = 0 ; i < N ; i++ ){
 345     hash_tab[i].val = nodes_id[i];
 346     hash_tab[i].key = genrand_int32();
 347   }
 348 
 349   qsort(hash_tab,N,sizeof(hash_t),hash_asc);
 350   for( i = 0 ; i < N ; i++ )
 351     sol[i] = hash_tab[i].val;
 352 
 353   FREE(hash_tab);
 354   return sol;
 355 }
 356 
 357 
 358 double eval_sol(int *sol,int N,double **comm, double **arch)
 359 {
 360   double a,c,res;
 361   int i,j;
 362 
 363   res = 0;
 364   for ( i = 0 ; i < N ; i++ )
 365     for ( j = i+1 ; j < N ; j++ ){
 366       c = comm[i][j];
 367       a = arch[sol[i]][sol[j]];
 368       res += c/a;
 369     }
 370 
 371   return res;
 372 }
 373 
 374 void exchange(int *sol,int i,int j)
 375 {
 376   int tmp;
 377   tmp = sol[i];
 378   sol[i] = sol[j];
 379   sol[j] = tmp;
 380 }
 381 
 382 double gain_exchange(int *sol,int l,int m,double eval1,int N,double **comm, double **arch)
 383 {
 384   double eval2;
 385   if( l == m )
 386     return 0;
 387   exchange(sol,l,m);
 388   eval2 = eval_sol(sol,N,comm,arch);
 389   exchange(sol,l,m);
 390 
 391   return eval1-eval2;
 392 }
 393 
 394 void select_max(int *l,int *m,double **gain,int N,int *state)
 395 {
 396   double max;
 397   int i,j;
 398 
 399   max = -DBL_MAX;
 400 
 401   for( i = 0 ; i < N ; i++ )
 402     if(!state[i])
 403       for( j = 0 ; j < N ; j++ )
 404         if( (i != j) && (!state[j]) ){
 405           if(gain[i][j] > max){
 406             *l = i;
 407             *m = j;
 408             max=gain[i][j];
 409           }
 410         }
 411 }
 412 
 413 
 414 void compute_gain(int *sol,int N,double **gain,double **comm, double **arch)
 415 {
 416   double eval1;
 417   int i,j;
 418 
 419   eval1 = eval_sol(sol,N,comm,arch);
 420   for( i = 0 ; i < N ; i++ )
 421     for( j = 0 ; j <= i ; j++)
 422       gain[i][j] = gain[j][i] = gain_exchange(sol,i,j,eval1,N,comm,arch);
 423 }
 424 
 425 
 426 /* Randomized Algorithm of
 427 Hu Chen, Wenguang Chen, Jian Huang ,Bob Robert,and H.Kuhn. Mpipp: an automatic profile-guided
 428 parallel process placement toolset for smp clusters and multiclusters. In
 429 Gregory K. Egan and Yoichi Muraoka, editors, ICS, pages 353-360. ACM, 2006.
 430  */
 431 
 432 void map_MPIPP(tm_topology_t *topology,int nb_seed,int N,int *sigma,double **comm, double **arch)
 433 {
 434   int *sol = NULL;
 435   int *state = NULL;
 436   double **gain = NULL;
 437   int **history = NULL;
 438   double *temp = NULL;
 439   int i,j,t,l=0,m=0,seed=0;
 440   double max,sum,best_eval,eval;
 441 
 442   gain = (double**)MALLOC(sizeof(double*)*N);
 443   history = (int**)MALLOC(sizeof(int*)*N);
 444   for( i = 0 ; i < N ; i++){
 445     gain[i] = (double*)MALLOC(sizeof(double)*N);
 446     history[i] = (int*)MALLOC(sizeof(int)*3);
 447   }
 448 
 449   state = (int*)MALLOC(sizeof(int)*N);
 450   temp = (double*)MALLOC(sizeof(double)*N);
 451 
 452   sol = generate_random_sol(topology, N, seed++);
 453   for( i = 0 ; i < N ; i++)
 454     sigma[i] = sol[i];
 455 
 456   best_eval = DBL_MAX;
 457   while(seed <= nb_seed){
 458     do{
 459       for( i =  0 ; i < N ; i++ ){
 460         state[i] = 0;
 461         /* printf("%d ",sol[i]); */
 462       }
 463       /* printf("\n"); */
 464       compute_gain(sol,N,gain,comm,arch);
 465       /*
 466       display_tab(gain,N);
 467       exit(-1);
 468       */
 469       for( i = 0 ; i < N/2 ; i++ ){
 470         select_max(&l,&m,gain,N,state);
 471         /* printf("%d: %d <=> %d : %f\n",i,l,m,gain[l][m]); */
 472         state[l] = 1;
 473         state[m] = 1;
 474         exchange(sol,l,m);
 475         history[i][1] = l;
 476         history[i][2] = m;
 477         temp[i] = gain[l][m];
 478         compute_gain(sol,N,gain,comm,arch);
 479       }
 480 
 481       t = -1;
 482       max = 0;
 483       sum = 0;
 484       for(i = 0 ; i < N/2 ; i++ ){
 485         sum += temp[i];
 486         if( sum > max ){
 487           max = sum;
 488           t = i;
 489         }
 490       }
 491       /*for(j=0;j<=t;j++)
 492         printf("exchanging: %d with %d for gain: %f\n",history[j][1],history[j][2],temp[j]); */
 493       for( j = t+1 ; j < N/2 ; j++ ){
 494         exchange(sol,history[j][1],history[j][2]);
 495         /* printf("Undoing: %d with %d for gain: %f\n",history[j][1],history[j][2],temp[j]);  */
 496       }
 497       /* printf("max=%f\n",max); */
 498 
 499       /*for(i=0;i<N;i++){
 500         printf("%d ",sol[i]);
 501         }
 502         printf("\n");*/
 503       eval = eval_sol(sol,N,comm,arch);
 504       if(eval < best_eval){
 505         best_eval = eval;
 506         for(i = 0 ; i < N ; i++)
 507           sigma[i] = sol[i];
 508         /* print_sol(N); */
 509       }
 510     }while( max > 0 );
 511     FREE(sol);
 512     sol=generate_random_sol(topology, N, seed++);
 513   }
 514 
 515 
 516   FREE(sol);
 517   FREE(temp);
 518   FREE(state);
 519   for( i = 0 ; i < N ; i++){
 520     FREE(gain[i]);
 521     FREE(history[i]);
 522   }
 523   FREE(gain);
 524   FREE(history);
 525 }