doc: Add serial to list of ci file reserved words
[charm.git] / 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",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