root/ompi/mca/topo/treematch/treematch/k-partitioning.c

DEFINITIONS

1. kPartitioning
2. memory_allocation
3. initialization
4. algo
5. nextGain
6. balancing
7. destruction
8. kpartition_greedy2
9. allocate_vertex2
10. eval_cost2
11. build_p_vector

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include "k-partitioning.h"
   4 #include "tm_mt.h"
   5 #include "tm_verbose.h"
   6 
   7 void memory_allocation(PriorityQueue ** Q, PriorityQueue ** Qinst, double *** D, int n, int k);
   8 void initialization(int * const part, double ** const matrice, PriorityQueue * const Qpart, PriorityQueue * const Q, PriorityQueue * const Qinst, double ** const D, int n, int k, int * const deficit, int * const surplus);
   9 void algo(int * const part, double ** const matrice, PriorityQueue * const Qpart, PriorityQueue * const Q, PriorityQueue * const Qinst, double ** const D, int n,  int * const deficit, int * const surplus);
  10 double nextGain(PriorityQueue * const Qpart, PriorityQueue * const Q, int * const deficit, int * const surplus);
  11 void balancing(int n, int deficit, int surplus, double ** const D, int * const part);
  12 void destruction(PriorityQueue * Qpart, PriorityQueue * Q, PriorityQueue * Qinst, double ** D, int n, int k);
  13 
  14 void allocate_vertex2(int u, int *res, double **comm, int n, int *size, int max_size);
  15 double eval_cost2(int *,int,double **);
  16 int  *kpartition_greedy2(int k, double **comm, int n, int nb_try_max, int *constraints, int nb_constraints);
  17 int*  build_p_vector(double **comm, int n, int k, int greedy_trials, int * constraints, int nb_constraints);
  18 
  19 int* kPartitioning(double ** comm, int n, int k, int * constraints, int nb_constraints, int greedy_trials)
  20 {
  21   /* ##### declarations & allocations ##### */
  22 
  23   PriorityQueue Qpart, *Q = NULL, *Qinst = NULL;
  24   double **D = NULL;
  25   int deficit, surplus, *part = NULL;
  26   int real_n = n-nb_constraints;
  27 
  28   part = build_p_vector(comm, n, k, greedy_trials, constraints, nb_constraints);
  29 
  30   memory_allocation(&Q, &Qinst, &D, real_n, k);
  31 
  32   /* ##### Initialization ##### */
  33 
  34   initialization(part, comm, &Qpart, Q, Qinst, D, real_n, k, &deficit, &surplus);
  35 
  36   /* ##### Main loop ##### */
  37   while((nextGain(&Qpart, Q, &deficit, &surplus))>0)
  38     {
  39       algo(part, comm, &Qpart, Q, Qinst, D, real_n, &deficit, &surplus);
  40     }
  41 
  42   /* ##### Balancing the partition  ##### */
  43   balancing(real_n, deficit, surplus, D, part); /*if partition isn't balanced we have to make one last move*/
  44 
  45   /* ##### Memory deallocation ##### */
  46   destruction(&Qpart, Q, Qinst, D, real_n, k);
  47 
  48   return part;
  49 }
  50 
  51 void memory_allocation(PriorityQueue ** Q, PriorityQueue ** Qinst, double *** D, int n, int k)
  52 {
  53   int i;
  54   *Q = calloc(k, sizeof(PriorityQueue)); /*one Q for each partition*/
  55   *Qinst = calloc(n, sizeof(PriorityQueue)); /*one Qinst for each vertex*/
  56   *D = malloc(sizeof(double *) * n); /*D's size is n * k*/
  57   for(i=0; i < n; ++i)
  58     (*D)[i] = calloc(k, sizeof(double));
  59 }
  60 
  61 void initialization(int * const part, double ** const matrice, PriorityQueue * const Qpart, PriorityQueue * const Q, PriorityQueue * const Qinst, double ** const D, int n, int k, int * const deficit, int * const surplus)
  62 {
  63   int i,j;
  64 
  65   /* ##### PriorityQueue initializations ##### */
  66   /* We initialize Qpart with a size of k because it contains the subsets's indexes. */
  67   PQ_init(Qpart, k);
  68 
  69   /* We initialize each Q[i] with a size of n because each vertex is in one of these queue at any time. */
  70   /* However we could set a size of (n/k)+1 as this is the maximum size of a subset when the partition is not balanced. */
  71   for(i=0; i<k; ++i)
  72     PQ_init(&Q[i], n);
  73 
  74   /* We initialize each Qinst[i] with a size of k because fo each vertex i, Qinst[i] contains the D(i,j) values for j = 0...(k-1) */
  75   for(i=0; i<n; ++i)
  76     PQ_init(&Qinst[i], k);
  77 
  78   /* ##### Computing the D(i,j) values ##### */
  79   for(i=0; i < n; ++i) /*for each vertex i*/
  80     {
  81       for(j=0; j < n; ++j) /*and for each vertex j*/
  82         {
  83           D[i][part[j]] += matrice[i][j];
  84         }
  85     }
  86 
  87   /* ##### Filling up the queues ##### */
  88   /* ### Qinst ### */
  89   for(i=0; i < n; ++i) /*for each vertex i*/
  90     for(j=0; j < k; ++j) /*and for each subset j*/
  91       PQ_insert(&Qinst[i], j, D[i][j]); /*we insert the corresponding D(i,j) value in Qinst[i]*/
  92 
  93   /* ### Q ### */
  94   for(i=0; i<n; ++i) /*for each vertex i*/
  95     PQ_insert(&Q[part[i]], i, PQ_findMaxKey(&Qinst[i])-D[i][part[i]]); /*we insert in Q[part[i]] the vertex i with its highest possible gain*/
  96 
  97   /* ### Qpart ### */
  98   for(i=0; i < k; ++i) /*for each subset i*/
  99     PQ_insert(Qpart, i, PQ_findMaxKey(&Q[i])); /*we insert it in Qpart with the highest possible gain by one of its vertex as key*/
 100 
 101 
 102   /* ##### Initialization of deficit/surplus ##### */
 103   *surplus = *deficit = 0;
 104 }
 105 
 106 void algo(int * const part, double ** const matrice, PriorityQueue * const Qpart, PriorityQueue * const Q, PriorityQueue * const Qinst, double ** const D, int n, int * const deficit, int * const surplus)
 107 {
 108   int p,u,v,j;
 109   double d;
 110   if(*deficit == *surplus) /*if the current partition is balanced*/
 111     {
 112       p = PQ_deleteMax(Qpart); /*we get the subset with the highest possible gain in p and remove it from Qpart*/
 113       u = PQ_deleteMax(&Q[p]); /*then we get the vertex with this highest possible gain in u and remove it from Q[p] */
 114       *deficit = part[u]; /*p becomes the deficit */
 115     }
 116   else /*the current partition is not balanced*/
 117     {
 118       u = PQ_deleteMax(&Q[*surplus]); /*we get the vertex with the highest possible gain in surplus and remove it from Q[surplus] */
 119       PQ_delete(Qpart, part[u]); /*then we remove surplus from Qpart  (note that u is from surplus so part[u] is surplus) */
 120     }
 121   d = PQ_findMaxKey(&Q[part[u]]); /*we get the next highest possible gain in part[u] (without taking u in account as we already removed it from Q[part[u])*/
 122   PQ_insert(Qpart, part[u], d); /*we put part[u] back in Qpart with its new highest possible gain*/
 123   j = PQ_deleteMax(&Qinst[u]); /*we get from Qinst[u] the subset in which we have to move u to get the highest gain.*/
 124   if ( j < 0){
 125     if(tm_get_verbose_level() >= CRITICAL)
 126       fprintf(stderr,"Error Max element in priority queue negative!\n");
 127     exit(-1);
 128   }
 129   *surplus = j; /*this subset becomes surplus*/
 130 
 131   for(v=0; v < n; ++v) /*we scan though all edges (u,v) */
 132     {
 133       j = part[u]; /*we set j to the starting subset */
 134       D[v][j]= D[v][j] - matrice[u][v]; /*we compute the new D[v, i] (here j has the value of the starting subset of u, that's why we say i) */
 135       PQ_adjustKey(&Qinst[v], j, D[v][j]); /*we update this gain in Qinst[v]*/
 136       j = *surplus; /*we put back the arrival subset in j*/
 137       D[v][j] = D[v][j] + matrice[u][v]; /*matrice[u][v]; we compute the new D[v, j]*/
 138       PQ_adjustKey(&Qinst[v], j, D[v][j]);/*we update this gain in Qinst[v]*/
 139       d = PQ_findMaxKey(&Qinst[v]) - D[v][part[v]]; /*we compute v's new highest possible gain*/
 140       PQ_adjustKey(&Q[part[v]], v, d); /*we update it in Q[p[v]]*/
 141       d = PQ_findMaxKey(&Q[part[v]]); /*we get the highest possible gain in v's subset*/
 142       PQ_adjustKey(Qpart, part[v], d); /*we update it in Qpart*/
 143     }
 144   part[u] = *surplus; /*we move u from i to j (here surplus has the value of j the arrival subset)*/
 145 
 146   d = PQ_findMaxKey(&Qinst[u]) - D[u][part[u]]; /*we compute the new u's highest possible gain*/
 147   if(!PQ_isEmpty(&Qinst[u])) /*if at least one more move of u is possible*/
 148     PQ_insert(&Q[part[u]], u, d); /*we insert u in the Q queue of its new subset*/
 149   PQ_adjustKey(Qpart, part[u], d); /*we update the new highest possible gain in u's subset*/
 150 }
 151 
 152 double nextGain(PriorityQueue * const Qpart, PriorityQueue * const Q, int * const deficit, int * const surplus)
 153 {
 154   double res;
 155   if(*deficit == *surplus) /*if the current partition is balanced*/
 156     res = PQ_findMaxKey(Qpart); /*we get the highest possible gain*/
 157   else /*the current partition is not balanced*/
 158     res = PQ_findMaxKey(&Q[*surplus]); /*we get the highest possible gain from surplus*/
 159   return res;
 160 }
 161 
 162 void balancing(int n, int deficit, int surplus, double ** const D, int * const part)
 163 {
 164   if(surplus != deficit) /*if the current partition is not balanced*/
 165     {
 166       int i;
 167       PriorityQueue moves; /*we use a queue to store the possible moves from surplus to deficit*/
 168       PQ_init(&moves, n);
 169       for(i=0; i<n; ++i) /*for each vertex*/
 170         {
 171           if(part[i] == surplus) /*if i is from surplus*/
 172             PQ_insert(&moves, i, D[i][deficit]-D[i][surplus]); /*we insert i in moves with the gain we get from moving i from surplus to deficit as key */
 173         }
 174       part[PQ_deleteMax(&moves)] = deficit; /*we put the i from moves with the highest gain in deficit*/
 175       PQ_exit(&moves);
 176     }
 177 }
 178 
 179 void destruction(PriorityQueue * Qpart, PriorityQueue * Q, PriorityQueue * Qinst, double ** D, int n, int k)
 180 {
 181   int i;
 182   PQ_exit(Qpart);
 183   for(i=0; i<k; ++i)
 184     PQ_exit(&Q[i]);
 185   free(Q);
 186   for(i=0; i<n; ++i)
 187     {
 188       PQ_exit(&Qinst[i]);
 189     }
 190   free(Qinst);
 191 
 192   for(i=0; i<n; ++i)
 193     free(D[i]);
 194   free(D);
 195 }
 196 
 197 
 198 int  *kpartition_greedy2(int k, double **comm, int n, int nb_try_max, int *constraints, int nb_constraints)
 199 {
 200   int *res = NULL, *best_res=NULL, *size = NULL;
 201   int i,j,nb_trials;
 202   int max_size;
 203   double cost, best_cost = -1;
 204 
 205   for( nb_trials = 0 ; nb_trials < nb_try_max ; nb_trials++ ){
 206     res = (int *)malloc(sizeof(int)*n);
 207     for ( i = 0 ; i < n ; ++i )
 208       res[i] = -1;
 209 
 210     size = (int *)calloc(k,sizeof(int));
 211     max_size = n/k;
 212 
 213     /* put "dumb" vertices in the correct partition if there are any*/
 214     if (nb_constraints){ /*if there are at least one constraint*/
 215       int nb_real_nodes = n-nb_constraints; /*this is the number of "real" nodes by opposition to the dumb ones*/
 216       for(i=0; i<nb_constraints; ++i) /*for each constraint*/
 217         {
 218           int i_part = constraints[i]/max_size; /*we compute its partition*/
 219           res[nb_real_nodes+i] = i_part; /*and we set it in partition vector*/
 220           size[i_part]++; /*we update the partition's size*/
 221         }
 222     }
 223 
 224     /* choose k initial "true" vertices at random and put them in a different partition */
 225     for ( i = 0 ; i < k ; ++i ){
 226       /* if the partition is full of dumb vertices go to next partition*/
 227       if(size[i] >= max_size)
 228         continue;
 229       /* find a vertex not already partitionned*/
 230       do{
 231         /* call the mersenne twister PRNG of tm_mt.c*/
 232         j =  genrand_int32() % n;
 233       } while ( res[j] != -1 );
 234       /* allocate and update size of partition*/
 235       res[j] = i;
 236       /* printf("random: %d -> %d\n",j,i); */
 237       size[i]++;
 238     }
 239 
 240     /* allocate each unallocated vertices in the partition that maximize the communication*/
 241     for( i = 0 ;  i < n ; ++i )
 242       if( res[i] == -1)
 243         allocate_vertex2(i, res, comm, n-nb_constraints, size, max_size);
 244 
 245     cost = eval_cost2(res,n-nb_constraints,comm);
 246     /*print_1D_tab(res,n);
 247     printf("cost=%.2f\n",cost);*/
 248     if((cost<best_cost) || (best_cost == -1)){
 249       best_cost=cost;
 250       free(best_res);
 251       best_res=res;
 252     }else
 253       free(res);
 254 
 255     free(size);
 256   }
 257 
 258   /*print_1D_tab(best_res,n);
 259   printf("best_cost=%.2f\n",best_cost);
 260   */
 261   return best_res;
 262 }
 263 
 264 void allocate_vertex2(int u, int *res, double **comm, int n, int *size, int max_size)
 265 {
 266   int i,best_part = -1;
 267   double cost, best_cost = -1;
 268 
 269   /*printf("\n");
 270     print_1D_tab(res,n);*/
 271   for( i = 0 ; i < n ; ++i){
 272     if (( res[i] != -1 ) && ( size[res[i]] < max_size )){
 273       cost = comm[u][i];
 274       if (( cost > best_cost)){
 275         best_cost = cost;
 276         best_part = res[i];
 277       }
 278     }
 279   }
 280 
 281   /*  printf("size[%d]: %d\n",best_part, size[best_part]);*/
 282   /* printf("putting(%.2f): %d -> %d\n",best_cost, u, best_part); */
 283 
 284   res[u] = best_part;
 285   size[best_part]++;
 286 }
 287 
 288 double eval_cost2(int *partition, int n, double **comm)
 289 {
 290   double cost = 0;
 291   int i,j;
 292 
 293   for( i = 0 ; i < n ; ++i )
 294     for( j = i+1 ; j < n ; ++j )
 295       if(partition[i] != partition[j])
 296         cost += comm[i][j];
 297 
 298   return cost;
 299 }
 300 
 301 int* build_p_vector(double **comm, int n, int k, int greedy_trials, int * constraints, int nb_constraints)
 302 {
 303   int * part = NULL;
 304   if(greedy_trials>0) /*if greedy_trials > 0 then we use kpartition_greedy with greedy_trials trials*/
 305     {
 306       part = kpartition_greedy2(k, comm, n, greedy_trials, constraints, nb_constraints);
 307     }
 308   else
 309     {
 310       int * size = calloc(k, sizeof(int));
 311       int i,j;
 312       int nodes_per_part = n/k;
 313       int nb_real_nodes = n-nb_constraints;
 314       part = malloc(sizeof(int) * n);
 315       for(i=0; i<nb_constraints; i++) /*for each constraints*/
 316         {
 317           int i_part = constraints[i]/nodes_per_part; /*we compute the partition where we have to put this constraint*/
 318           part[nb_real_nodes+i] = i_part;
 319           size[i_part]++;
 320         }
 321       j=0;
 322       /* now we have to fill the partitions with the "real" nodes */
 323       for(i=0; i<nb_real_nodes; i++) /*for each node*/
 324         {
 325           if(size[j] < nodes_per_part) /*if j partition isn't full*/
 326             {
 327               size[j]++;
 328               part[i] = j; /*then we put the node in this part*/
 329             }
 330           else /*otherwise we decrement i to get the same node in the next loop*/
 331             {
 332               i--;
 333             }
 334           j = (j+1)%k; /*and we change j to the next partition*/
 335         }
 336       free(size);
 337     }
 338   return part;
 339 }