7 #include "tm_timings.h"
11 #define random() rand()
12 #define srandom(x) srand(x)
22 bucket_list_t global_bl
;
24 int tab_cmp(const void* x1
,const void* x2
){
25 int *e1
,*e2
,i1
,i2
,j1
,j2
;
42 return tab
[i1
][j1
]>tab
[i2
][j2
]?-1:1;
46 int old_bucket_id(int i
,int j
,bucket_list_t bucket_list
){
49 pivot
=bucket_list
->pivot
;
50 n
=bucket_list
->nb_buckets
;
51 val
=bucket_list
->tab
[i
][j
];
58 //printf("%f [%d,%d,%d]=%f\n",val,inf,p,sup,pivot[p]);
74 int bucket_id(int i
,int j
,bucket_list_t bucket_list
){
75 double *pivot_tree
,val
;
77 pivot_tree
=bucket_list
->pivot_tree
;
78 val
=bucket_list
->tab
[i
][j
];
83 for(k
=0;k
<bucket_list
->max_depth
;k
++){
90 return (int)pivot_tree
[p
];
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
);
102 void check_bucket(bucket_t
*b
,double **tab
,double inf
, double sup
,int N
){
104 for(k
=0;k
<b
->nb_elem
;k
++){
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
);
114 void display_pivots(bucket_list_t bucket_list
){
117 for(i
=0;i
<bucket_list
->nb_buckets
-1;i
++){
118 printf("pivot[%d]=%f\n",i
,bucket_list
->pivot
[i
]);
123 void display_bucket_list(bucket_list_t bucket_list
){
127 display_pivots(bucket_list
);
129 for(i
=0;i
<bucket_list
->nb_buckets
;i
++){
130 inf
=bucket_list
->pivot
[i
];
131 sup
=bucket_list
->pivot
[i
-1];
134 if(i
==bucket_list
->nb_buckets
-1)
136 printf("Bucket %d:\n",i
);
137 display_bucket(bucket_list
->bucket_tab
[i
]);
139 check_bucket(bucket_list
->bucket_tab
[i
],bucket_list
->tab
,inf
,sup
,bucket_list
->N
);
144 void add_to_bucket(int id
,int i
,int j
,bucket_list_t bucket_list
){
148 bucket
=bucket_list
->bucket_tab
[id
];
149 //display_bucket(bucket);
151 if(bucket
->bucket_len
==bucket
->nb_elem
){
153 n
=bucket_list
->nb_buckets
;
155 //display_bucket(bucket);
156 bucket
->bucket
=(coord
*)realloc(bucket
->bucket
,sizeof(coord
)*(size
+bucket
->bucket_len
));
157 bucket
->bucket_len
+=size
;
159 printf("malloc/realloc: %d\n",id
);
160 printf("(%d,%d)\n",i
,j
);
161 display_bucket(bucket
);
166 bucket
->bucket
[bucket
->nb_elem
].i
=i
;
167 bucket
->bucket
[bucket
->nb_elem
].j
=j
;
174 void dfs(int i
,int inf
,int sup
,double *pivot
,double *pivot_tree
,int depth
,int max_depth
){
180 pivot_tree
[i
]=pivot
[p
-1];
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
);
186 void built_pivot_tree(bucket_list_t bucket_list
){
187 double *pivot_tree
,*pivot
;
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
);
194 dfs(1,1,n
-1,pivot
,pivot_tree
,0,bucket_list
->max_depth
);
200 bucket_list
->pivot_tree
=pivot_tree
;
203 printf("%d:%f\t",i,pivot_tree[i]);
208 void fill_buckets(bucket_list_t bucket_list
){
215 id
=bucket_id(i
,j
,bucket_list
);
216 add_to_bucket(id
,i
,j
,bucket_list
);
223 int is_power_of_2(int val
){
234 void partial_sort(bucket_list_t
*bl
,double **tab
,int N
,int nb_buckets
){
239 bucket_list_t bucket_list
;
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
);
248 bucket_list
=(bucket_list_t
)malloc(sizeof(_bucket_list_t
));
250 bucket_list
->tab
=tab
;
257 printf("N=%d, n=%d\n",N
,n
);
258 sample
=(int*)malloc(2*sizeof(int)*n
);
265 j
=random()%(N
-i
-2)+i
+1;
274 global_bl
=bucket_list
;
275 qsort(sample
,n
,2*sizeof(int),tab_cmp
);
280 printf("%f\n",tab[i][j]);
283 pivot
=(double*)malloc(sizeof(double)*nb_buckets
-1);
285 for(k
=1;k
<nb_buckets
;k
++){
287 j
=sample
[2*(id
-1)+1];
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]);
297 bucket_list
->pivot
=pivot
;
298 bucket_list
->nb_buckets
=nb_buckets
;
299 built_pivot_tree(bucket_list
);
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
));
306 fill_buckets(bucket_list
);
308 //display_bucket_list(bucket_list);
310 bucket_list
->cur_bucket
=0;
311 bucket_list
->bucket_indice
=0;
318 void next_bucket_elem(bucket_list_t bucket_list
,int *i
,int *j
){
320 bucket_t
*bucket
=bucket_list
->bucket_tab
[bucket_list
->cur_bucket
];
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);
325 while(bucket
->nb_elem
<=bucket_list
->bucket_indice
){
327 bucket_list
->bucket_indice
=0;
328 bucket_list
->cur_bucket
++;
329 bucket
=bucket_list
->bucket_tab
[bucket_list
->cur_bucket
];
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);
337 global_bl
=bucket_list
;
338 qsort(bucket
->bucket
,bucket
->nb_elem
,2*sizeof(int),tab_cmp
);
346 *i
=bucket
->bucket
[bucket_list
->bucket_indice
].i
;
347 *j
=bucket
->bucket
[bucket_list
->bucket_indice
].j
;
348 bucket_list
->bucket_indice
++;
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);
355 if((!tab_node
[i
].parent
) && (!tab_node
[j
].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
;
362 printf("%d: %d-%d\n",*nb_groups
,parent
->child
[0]->id
,parent
->child
[1]->id
);
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
;
375 printf("%d: %d-%d-%d\n",*nb_groups
,parent
->child
[0]->id
,parent
->child
[1]->id
,parent
->child
[2]->id
);
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
;
388 printf("%d: %d-%d-%d\n",*nb_groups
,parent
->child
[0]->id
,parent
->child
[1]->id
,parent
->child
[2]->id
);
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
){
405 if(tab_node
[i
].parent
)
407 if(tab_node
[j
].parent
)
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
;
419 return add_edge_3(tab
,tab_node
,parent
,i
,j
,N
,nb_groups
);
421 fprintf(stderr
,"Cannot handle arity %d\n",parent
->arity
);
427 void free_bucket(bucket_t
*bucket
){
428 free(bucket
->bucket
);
433 void free_tab_bucket(bucket_t
**bucket_tab
,int N
){
436 free_bucket(bucket_tab
[i
]);
442 void free_bucket_list(bucket_list_t bucket_list
){
444 // Do not free the tab field it is used elsewhere
446 free_tab_bucket(bucket_list
->bucket_tab
,bucket_list
->nb_buckets
);
447 free(bucket_list
->pivot
);
448 free(bucket_list
->pivot_tree
);
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
;
459 partial_sort(&bucket_list
,tab
,N
,8);
461 printf("Partial sorting=%fs\n",duration
);
463 display_pivots(bucket_list
);
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
)){
478 printf("l=%d,nb_groups=%d\n",l
,nb_groups
);
482 next_bucket_elem(bucket_list
,&i
,&j
);
483 try_add_edge(tab
,tab_node
,NULL
,arity
,i
,j
,N
,&nb_groups
);
487 printf("l=%d,nb_groups=%d\n",l
,nb_groups
);
491 update_val(tab
,&new_tab_node
[l
],N
);
492 val
+=new_tab_node
[l
].val
;
500 printf("Grouping =%fs\n",duration
);
502 printf("Bucket: %d, indice:%d\n",bucket_list
->cur_bucket
,bucket_list
->bucket_indice
);
504 printf("val=%f\n",val
);
505 free_bucket_list(bucket_list
);
509 // display_grouping(new_tab_node,M,arity,val);