src/ck-ldb/tm_bucket.C

   1 #include <stdio.h>
   2 #include <float.h>
   3 #include <math.h>
   4 #include <assert.h>
   5 #include "tm_tree.h"
   6 #include "tm_bucket.h"
   7 #include "tm_timings.h"
   8 #ifdef _WIN32
   9 #include <windows.h>
  10 #include <winbase.h>
  11 #define random() rand()
  12 #define srandom(x)  srand(x)
  13 #endif
  14
  15 #if __CHARMC__
  16 #include "converse.h"
  17 #else
  18 #define CmiLog2  log2
  19 #endif
  20
  21 #undef DEBUG
  22 bucket_list_t global_bl;
  23
  24 int tab_cmp(const void* x1,const void* x2){
  25   int *e1,*e2,i1,i2,j1,j2;
  26   double **tab;
  27   bucket_list_t bl;
  28
  29   bl=global_bl;
  30
  31   e1=((int *)x1);
  32   e2=((int *)x2);
  33
  34
  35   tab=bl->tab;
  36
  37   i1=e1[0];
  38   j1=e1[1];
  39   i2=e2[0];
  40   j2=e2[1];
  41
  42   return tab[i1][j1]>tab[i2][j2]?-1:1;
  43 }
  44
  45
  46 int old_bucket_id(int i,int j,bucket_list_t bucket_list){
  47   double *pivot,val;
  48   int n,sup,inf,p;
  49   pivot=bucket_list->pivot;
  50   n=bucket_list->nb_buckets;
  51   val=bucket_list->tab[i][j];
  52
  53   inf=-1;
  54   sup=n;
  55
  56   while(sup-inf>1){
  57     p=(sup+inf)/2;
  58     //printf("%f [%d,%d,%d]=%f\n",val,inf,p,sup,pivot[p]);
  59     if(val<pivot[p]){
  60       inf=p;
  61       if(inf==sup)
  62         inf--;
  63     }else{
  64       sup=p;
  65       if(sup==inf)
  66         sup++;
  67     }
  68   }
  69   //exit(-1);
  70   return sup;
  71 }
  72
  73
  74 int bucket_id(int i,int j,bucket_list_t bucket_list){
  75   double *pivot_tree,val;
  76   int p,k;
  77   pivot_tree=bucket_list->pivot_tree;
  78   val=bucket_list->tab[i][j];
  79
  80
  81
  82   p=1;
  83   for(k=0;k<bucket_list->max_depth;k++){
  84     if(val>pivot_tree[p])
  85       p=p*2;
  86     else
  87       p=p*2+1;
  88   }
  89
  90   return  (int)pivot_tree[p];
  91 }
  92
  93
  94
  95 void  display_bucket(bucket_t *b){
  96   printf("\tb.bucket=%p\n",(void *)b->bucket);
  97   printf("\tb.bucket_len=%d\n",(int)b->bucket_len);
  98   printf("\tb.nb_elem=%d\n",(int)b->nb_elem);
  99
 100 }
 101
 102 void check_bucket(bucket_t *b,double **tab,double inf, double sup,int N){
 103   int k,i,j;
 104   for(k=0;k<b->nb_elem;k++){
 105     i=b->bucket[k].i;
 106     j=b->bucket[k].j;
 107     if((tab[i][j]<inf)||(tab[i][j]>sup)){
 108       printf("[%d] (%d,%d):%f not in [%f,%f]\n",k,i,j,tab[i][j],inf,sup);
 109       exit(-1);
 110     }
 111   }
 112 }
 113
 114 void  display_pivots(bucket_list_t bucket_list){
 115   int i;
 116
 117   for(i=0;i<bucket_list->nb_buckets-1;i++){
 118     printf("pivot[%d]=%f\n",i,bucket_list->pivot[i]);
 119   }
 120   printf("\n");
 121 }
 122
 123 void  display_bucket_list(bucket_list_t bucket_list){
 124   int i;
 125   double inf,sup;
 126
 127   display_pivots(bucket_list);
 128
 129   for(i=0;i<bucket_list->nb_buckets;i++){
 130     inf=bucket_list->pivot[i];
 131     sup=bucket_list->pivot[i-1];
 132     if(i==0)
 133       sup=DBL_MAX;
 134     if(i==bucket_list->nb_buckets-1)
 135       inf=0;
 136     printf("Bucket %d:\n",i);
 137     display_bucket(bucket_list->bucket_tab[i]);
 138     printf("\n");
 139     check_bucket(bucket_list->bucket_tab[i],bucket_list->tab,inf,sup,bucket_list->N);
 140   }
 141
 142 }
 143
 144 void add_to_bucket(int id,int i,int j,bucket_list_t bucket_list){
 145   bucket_t *bucket;
 146   int N,n,size;
 147
 148   bucket=bucket_list->bucket_tab[id];
 149   //display_bucket(bucket);
 150
 151   if(bucket->bucket_len==bucket->nb_elem){
 152     N=bucket_list->N;
 153     n=bucket_list->nb_buckets;
 154     size=N*N/n;
 155     //display_bucket(bucket);
 156     bucket->bucket=(coord*)realloc(bucket->bucket,sizeof(coord)*(size+bucket->bucket_len));
 157     bucket->bucket_len+=size;
 158 #ifdef DEBUG
 159     printf("malloc/realloc: %d\n",id);
 160     printf("(%d,%d)\n",i,j);
 161     display_bucket(bucket);
 162     printf("\n");
 163 #endif
 164   }
 165
 166  bucket->bucket[bucket->nb_elem].i=i;
 167  bucket->bucket[bucket->nb_elem].j=j;
 168  bucket->nb_elem++;
 169
 170   //printf("\n");
 171   //exit(-1);
 172 }
 173
 174 void dfs(int i,int inf,int sup,double *pivot,double *pivot_tree,int depth,int max_depth){
 175   int p;
 176   if(depth==max_depth)
 177     return;
 178
 179   p=(inf+sup)/2;
 180   pivot_tree[i]=pivot[p-1];
 181
 182   dfs(2*i,inf,p-1,pivot,pivot_tree,depth+1,max_depth);
 183   dfs(2*i+1,p+1,sup,pivot,pivot_tree,depth+1,max_depth);
 184 }
 185
 186 void  built_pivot_tree(bucket_list_t bucket_list){
 187   double *pivot_tree,*pivot;
 188   int n,i,k;
 189   pivot=bucket_list->pivot;
 190   n=bucket_list->nb_buckets;
 191   pivot_tree=(double*)malloc(sizeof(double)*2*n);
 192   bucket_list->max_depth=(int)CmiLog2(n);
 193
 194   dfs(1,1,n-1,pivot,pivot_tree,0,bucket_list->max_depth);
 195
 196   k=0;
 197   for(i=n;i<2*n;i++)
 198     pivot_tree[i]=k++;
 199
 200   bucket_list->pivot_tree=pivot_tree;
 201   /*
 202   for(i=0;i<2*n;i++)
 203     printf("%d:%f\t",i,pivot_tree[i]);
 204   printf("\n");
 205   */
 206 }
 207
 208 void fill_buckets(bucket_list_t bucket_list){
 209   int N,i,j,id;
 210
 211   N=bucket_list->N;
 212
 213   for(i=0;i<N;i++){
 214     for(j=i+1;j<N;j++){
 215       id=bucket_id(i,j,bucket_list);
 216       add_to_bucket(id,i,j,bucket_list);
 217     }
 218   }
 219
 220
 221 }
 222
 223 int is_power_of_2(int val){
 224   int n=1;
 225   do{
 226     if(n==val)
 227       return 1;
 228     n<<=1;
 229   }while(n>0);
 230   return 0;
 231 }
 232
 233
 234 void partial_sort(bucket_list_t *bl,double **tab,int N,int nb_buckets){
 235   int *sample;
 236   int i,j,k,n;
 237   int id;
 238   double *pivot;
 239   bucket_list_t bucket_list;
 240
 241
 242   if(!is_power_of_2(nb_buckets)){
 243     fprintf(stderr,"Error! Paramater nb_buckets is: %d and should be a power of 2\n",nb_buckets);
 244     exit(-1);
 245   }
 246
 247
 248   bucket_list=(bucket_list_t)malloc(sizeof(_bucket_list_t));
 249
 250   bucket_list->tab=tab;
 251   bucket_list->N=N;
 252
 253
 254   n=pow(nb_buckets,2);
 255
 256   assert(n=N);
 257   printf("N=%d, n=%d\n",N,n);
 258   sample=(int*)malloc(2*sizeof(int)*n);
 259
 260   for(k=0;k<n;k++){
 261     i=random()%(N-2)+1;
 262     if(i==N-2)
 263       j=N-1;
 264     else
 265       j=random()%(N-i-2)+i+1;
 266     assert(i!=j);
 267     assert(i<j);
 268     assert(i<N);
 269     assert(j<N);
 270     sample[2*k]=i;
 271     sample[2*k+1]=j;
 272   }
 273
 274   global_bl=bucket_list;
 275   qsort(sample,n,2*sizeof(int),tab_cmp);
 276   /*
 277   for(k=0;k<n;k++){
 278     i=sample[2*k];
 279     j=sample[2*k+1];
 280     printf("%f\n",tab[i][j]);
 281     }*/
 282
 283   pivot=(double*)malloc(sizeof(double)*nb_buckets-1);
 284   id=1;
 285   for(k=1;k<nb_buckets;k++){
 286     i=sample[2*(id-1)];
 287     j=sample[2*(id-1)+1];
 288     id*=2;
 289
 290
 291     /*    i=sample[k*N/nb_buckets]/N;
 292           j=sample[k*N/nb_buckets]%N;*/
 293     pivot[k-1]=tab[i][j];
 294     //printf("pivot[%d]=%f\n",k-1,tab[i][j]);
 295   }
 296
 297   bucket_list->pivot=pivot;
 298   bucket_list->nb_buckets=nb_buckets;
 299   built_pivot_tree(bucket_list);
 300
 301   bucket_list->bucket_tab=(bucket_t**)malloc(nb_buckets*sizeof(bucket_t*));
 302   for(i=0;i<nb_buckets;i++){
 303     bucket_list->bucket_tab[i]=(bucket_t*)calloc(1,sizeof(bucket_t));
 304   }
 305
 306   fill_buckets(bucket_list);
 307
 308   //display_bucket_list(bucket_list);
 309
 310   bucket_list->cur_bucket=0;
 311   bucket_list->bucket_indice=0;
 312
 313   free(sample);
 314
 315   *bl=bucket_list;
 316 }
 317
 318 void next_bucket_elem(bucket_list_t bucket_list,int *i,int *j){
 319   int N;
 320   bucket_t *bucket=bucket_list->bucket_tab[bucket_list->cur_bucket];
 321
 322     //display_bucket_list(bucket_list);
 323   //printf("nb_elem: %d, indice: %d, bucket_id: %d\n",(int)bucket->nb_elem,bucket_list->bucket_indice,bucket_list->cur_bucket);
 324
 325   while(bucket->nb_elem<=bucket_list->bucket_indice){
 326
 327     bucket_list->bucket_indice=0;
 328     bucket_list->cur_bucket++;
 329     bucket=bucket_list->bucket_tab[bucket_list->cur_bucket];
 330
 331     //printf("### From bucket %d to bucket %d\n",bucket_list->cur_bucket-1,bucket_list->cur_bucket);
 332     //printf("nb_elem: %d, indice: %d, bucket_id: %d\n",(int)bucket->nb_elem,bucket_list->bucket_indice,bucket_list->cur_bucket);
 333     //sleep(1);
 334   }
 335
 336   if(!bucket->sorted){
 337     global_bl=bucket_list;
 338     qsort(bucket->bucket,bucket->nb_elem,2*sizeof(int),tab_cmp);
 339     bucket->sorted=1;
 340   }
 341
 342
 343
 344   N=bucket_list->N;
 345
 346   *i=bucket->bucket[bucket_list->bucket_indice].i;
 347   *j=bucket->bucket[bucket_list->bucket_indice].j;
 348   bucket_list->bucket_indice++;
 349 }
 350
 351
 352 int add_edge_3(double **tab,tree_t *tab_node, tree_t *parent,int i,int j,int N,int *nb_groups){
 353   //printf("%d <-> %d ?\n",tab_node[i].id,tab_node[j].id);
 354
 355   if((!tab_node[i].parent) && (!tab_node[j].parent)){
 356     if(parent){
 357       parent->child[0]=&tab_node[i];
 358       parent->child[1]=&tab_node[j];
 359       tab_node[i].parent=parent;
 360       tab_node[j].parent=parent;
 361 #ifdef DEBUG
 362       printf("%d: %d-%d\n",*nb_groups,parent->child[0]->id,parent->child[1]->id);
 363 #endif
 364       return 1;
 365     }
 366     return 0;
 367   }
 368
 369   if(tab_node[i].parent && (!tab_node[j].parent)){
 370     parent=tab_node[i].parent;
 371     if(!parent->child[2]){
 372       parent->child[2]=&tab_node[j];
 373       tab_node[j].parent=parent;
 374 #ifdef DEBUG
 375       printf("%d: %d-%d-%d\n",*nb_groups,parent->child[0]->id,parent->child[1]->id,parent->child[2]->id);
 376 #endif
 377       (*nb_groups)++;
 378     }
 379     return 0;
 380   }
 381
 382   if(tab_node[j].parent && (!tab_node[i].parent)){
 383     parent=tab_node[j].parent;
 384     if(!parent->child[2]){
 385       parent->child[2]=&tab_node[i];
 386       tab_node[i].parent=parent;
 387 #ifdef DEBUG
 388       printf("%d: %d-%d-%d\n",*nb_groups,parent->child[0]->id,parent->child[1]->id,parent->child[2]->id);
 389 #endif
 390       (*nb_groups)++;
 391     }
 392     return 0;
 393   }
 394
 395   return 0;
 396 }
 397
 398 int try_add_edge(double **tab,tree_t *tab_node, tree_t *parent,int arity,int i,int j,int N,int *nb_groups){
 399
 400   assert(i!=j);
 401
 402
 403   switch(arity){
 404   case 2:
 405     if(tab_node[i].parent)
 406       return 0;
 407     if(tab_node[j].parent)
 408       return 0;
 409
 410     parent->child[0]=&tab_node[i];
 411     parent->child[1]=&tab_node[j];
 412     tab_node[i].parent=parent;
 413     tab_node[j].parent=parent;
 414
 415     (*nb_groups)++;
 416
 417     return 1;
 418   case 3:
 419     return add_edge_3(tab,tab_node,parent,i,j,N,nb_groups);
 420   default:
 421     fprintf(stderr,"Cannot handle arity %d\n",parent->arity);
 422     exit(-1);
 423   }
 424 }
 425
 426
 427 void free_bucket(bucket_t *bucket){
 428   free(bucket->bucket);
 429   free(bucket);
 430
 431 }
 432
 433 void free_tab_bucket(bucket_t **bucket_tab,int N){
 434   int i;
 435   for(i=0;i<N;i++){
 436     free_bucket(bucket_tab[i]);
 437   }
 438   free(bucket_tab);
 439 }
 440
 441
 442 void free_bucket_list(bucket_list_t bucket_list){
 443
 444   // Do not free the tab field it is used elsewhere
 445
 446   free_tab_bucket(bucket_list->bucket_tab,bucket_list->nb_buckets);
 447   free(bucket_list->pivot);
 448   free(bucket_list->pivot_tree);
 449   free(bucket_list);
 450 }
 451
 452 void bucket_grouping(double **tab,tree_t *tab_node, tree_t *new_tab_node, int arity,int N, int M,long int k){
 453   bucket_list_t bucket_list;
 454   double duration;
 455   int l,i,j,nb_groups;
 456   double val=0;
 457
 458   TIC;
 459   partial_sort(&bucket_list,tab,N,8);
 460   duration=TOC;
 461   printf("Partial sorting=%fs\n",duration);
 462
 463   display_pivots(bucket_list);
 464
 465
 466   TIC;
 467   l=0;
 468   i=0;
 469   nb_groups=0;
 470   while(l<M){
 471     next_bucket_elem(bucket_list,&i,&j);
 472     if(try_add_edge(tab,tab_node,&new_tab_node[l],arity,i,j,N,&nb_groups)){
 473       l++;
 474     }
 475   }
 476
 477 #ifdef DEBUG
 478   printf("l=%d,nb_groups=%d\n",l,nb_groups);
 479 #endif
 480
 481   while(nb_groups<M){
 482     next_bucket_elem(bucket_list,&i,&j);
 483     try_add_edge(tab,tab_node,NULL,arity,i,j,N,&nb_groups);
 484   }
 485
 486 #ifdef DEBUG
 487   printf("l=%d,nb_groups=%d\n",l,nb_groups);
 488 #endif
 489
 490   for(l=0;l<M;l++){
 491     update_val(tab,&new_tab_node[l],N);
 492     val+=new_tab_node[l].val;
 493   }
 494
 495
 496
 497
 498
 499   duration=TOC;
 500   printf("Grouping =%fs\n",duration);
 501
 502   printf("Bucket: %d, indice:%d\n",bucket_list->cur_bucket,bucket_list->bucket_indice);
 503
 504   printf("val=%f\n",val);
 505   free_bucket_list(bucket_list);
 506
 507   //  exit(-1);
 508
 509   //  display_grouping(new_tab_node,M,arity,val);
 510
 511
 512 }
 513