doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / tm_tree.c
1 #include <float.h>
2 #include <stdlib.h>
3 #include <stdio.h>
4 #include <math.h>
5 #include <assert.h>
6 #include "tm_tree.h"
7 #include "tm_timings.h"
8 #include "tm_bucket.h"
9
10 #if __CHARMC__
11 #include "converse.h"
12 #else
13 #define CmiLog2 log2
14 #endif
15
16 #define MIN(a,b) ((a)<(b)?(a):(b))
17 #define MAX(a,b) ((a)>(b)?(a):(b))
18 #undef DEBUG
19
20
21 void free_list_child(tree_t *tree){
22   int i;
23   if(tree){
24     for(i=0;i<tree->arity;i++){
25       free_list_child(tree->child[i]);
26     }
27   }
28   free(tree->child);
29   if(tree->dumb)
30     free(tree);
31 }
32
33
34
35
36 void free_tab_child(tree_t *tree){
37   if(tree){
38     free_tab_child(tree->tab_child);
39     free(tree->tab_child);
40   }
41 }
42
43
44
45 void free_tree(tree_t *tree){
46
47   free_list_child(tree);
48   free_tab_child(tree);
49   free(tree);
50 }
51
52 long int choose (long n,long k){
53   // compute C_n_k
54   double res=1;
55   int i;
56   for(i=0;i<k;i++)
57     res*=(double)(n-i)/(double)(k-i);
58   
59   return (long int)res;
60 }
61
62 void set_node(tree_t *node,tree_t ** child, int arity,tree_t *parent,int id,double val,tree_t *tab_child){
63   static int uniq=0;
64   node->child=child;
65   node->arity=arity;
66   node->tab_child=NULL;
67   node->parent=parent;
68   node->id=id;
69   node->val=val;
70   node->uniq=uniq++;
71   node->dumb=0;
72 }
73
74 void display_node(tree_t *node){
75   printf("child : %p\narity : %d\nparent : %p\nid : %d\nval : %f\nuniq : %d\n\n" ,
76          node->child,node->arity,node->parent,node->id,node->val,node->uniq);
77 }
78 void clone_tree(tree_t *new,tree_t *old){
79   int i;
80   new->child=old->child;
81   new->arity=old->arity;
82   new->parent=old->parent;
83   //new->deb_tab_child=old->deb_tab_child;
84   new->id=old->id;
85   new->val=old->val;
86   new->uniq=old->uniq;
87   new->dumb=old->dumb;
88   for(i=0;i<new->arity;i++)
89     new->child[i]->parent=new;
90 }
91
92
93
94 double *aggregate_obj_weight(tree_t *new_tab_node, double *tab, int M){
95   int i,i1,id1;
96   double *res;
97   
98   if(!tab)
99     return NULL;
100   
101   res=(double*)malloc(M*sizeof(double));
102   
103   for(i=0;i<M;i++){
104     res[i]=0.0;
105     for(i1=0;i1<new_tab_node[i].arity;i1++){
106       id1=new_tab_node[i].child[i1]->id;
107       res[i]+=tab[id1];
108     }
109   }
110   
111   return res;
112
113 }
114
115
116 double **aggregate_com_mat(tree_t *new_tab_node, double **tab, int M){
117   int i,j,i1,j1,id1,id2;
118   double **res;
119     
120   
121
122   res=(double**)malloc(M*sizeof(double*));
123   for(i=0;i<M;i++)
124     res[i]=(double*)malloc(M*sizeof(double));
125   
126   for(i=0;i<M;i++){
127     for(j=0;j<M;j++){
128       if(i==j)
129         res[i][j]=0;
130       else{
131         res[i][j]=0;
132         for(i1=0;i1<new_tab_node[i].arity;i1++){
133           id1=new_tab_node[i].child[i1]->id;
134           for(j1=0;j1<new_tab_node[j].arity;j1++){
135             id2=new_tab_node[j].child[j1]->id;
136             res[i][j]+=tab[id1][id2];
137             //printf("res[%d][%d]+=tab[%d][%d]=%f\n",i,j,id1,id2,tab[id1][id2]);
138           }
139         }
140       }
141     }
142   }
143   
144   return res;
145
146 }
147
148 void free_tab_double(double**tab,int N){
149   int i;
150   for(i=0;i<N;i++){
151     free(tab[i]);
152   }
153   free(tab);
154 }
155
156 void free_tab_int(int**tab,int N){
157   int i;
158   for(i=0;i<N;i++){
159     free(tab[i]);
160   }
161   free(tab);
162 }
163
164 void display_tab(double **tab,int N){
165   int i,j;
166   double line,total=0;;
167   for(i=0;i<N;i++){
168     line=0;
169     for(j=0;j<N;j++){
170       printf("%g ",tab[i][j]);
171       line+=tab[i][j];
172     }
173     total+=line;
174     //printf(": %g",line);
175     printf("\n");
176   }
177   printf("Total: %.2f\n",total);
178 }
179
180
181 double eval_grouping(double **tab,tree_t **cur_group,int arity,int N){
182   double res=0;
183   int i,k,j,id,id1,id2;
184   //display_tab(tab,N);
185
186
187   for(i=0;i<arity;i++){
188     id=cur_group[i]->id;
189     //printf("%d ",id);
190     for(k=0;k<N;k++){
191       //printf("res+=tab[%d][%d]+tab[%d][%d]=%f+%f \n",k,id,id,k,tab[k][id],tab[id][k]);
192       res+=tab[k][id];
193     }
194   }
195   
196   for(i=0;i<arity;i++){
197     id1=cur_group[i]->id;
198     for(j=0;j<arity;j++){
199       id2=cur_group[j]->id;
200       //printf("res-=tab[%d][%d]=%f\n",id1,id2,tab[id1][id2]);
201       res-=tab[id1][id2];
202     }
203   }
204   //printf(" = %f\n",res);
205   return res;
206 }
207
208
209
210 group_list_t *new_group_list(tree_t **tab,double val,group_list_t *next){
211   group_list_t *res;
212   res=(group_list_t *)malloc(sizeof(group_list_t));
213   res->tab=tab;
214   res->val=val;
215   res->next=next;
216   res->sum_neighbour=0;
217   return res;
218 }
219
220
221 void add_to_list(group_list_t *list,tree_t **cur_group, int arity, double val){
222
223   group_list_t *elem;
224   int i;
225   tree_t **tab;
226   
227   tab=(tree_t **)malloc(sizeof(tree_t *)*arity);
228
229   for(i=0;i<arity;i++){
230     tab[i]=cur_group[i];
231     //printf("%d ",cur_group[i]->id);
232   }
233
234   //printf("\n");
235   elem=new_group_list(tab,val,list->next);
236   list->next=elem;
237   list->val++;
238 }
239
240
241
242 void  list_all_possible_groups(double **tab,tree_t *tab_node,int id,int arity, int depth,
243                                tree_t **cur_group,int N,group_list_t *list){
244   double val;
245   int i;
246
247
248
249   if(depth==arity){
250     val=eval_grouping(tab,cur_group,arity,N);
251     add_to_list(list,cur_group,arity,val);
252     return;
253     }else if(N+depth>=arity+id){
254     //}else if(1){
255     for(i=id;i<N;i++){
256       if(tab_node[i].parent)
257         continue;
258       cur_group[depth]=&tab_node[i];
259       //printf("%d<-%d\n",depth,i);
260       list_all_possible_groups(tab,tab_node,i+1,arity,depth+1,cur_group,N,list);
261     }
262   }
263 }
264
265
266 void update_val(double **tab,tree_t *parent,int N){
267   int i;
268
269   parent->val=eval_grouping(tab,parent->child,parent->arity,N);
270   //printf("connecting: ");
271   for(i=0;i<parent->arity;i++){
272     //printf("%d ",parent->child[i]->id);
273     /*  if(parent->child[i]->parent!=parent){
274       parent->child[i]->parent=parent;
275     }else{
276       fprintf(stderr,"redundant operation!\n");
277       exit(-1);
278       }*/
279   }
280
281
282   //printf(": %f\n",parent->val);
283 }
284
285
286 int independent_groups(group_list_t **selection,int d,group_list_t *elem,int arity){
287   int i,j,k;
288
289   if(d==0)
290     return 1;
291
292   for(i=0;i<arity;i++){
293     for(j=0;j<d;j++){
294       for(k=0;k<arity;k++){
295         if(elem->tab[i]->id==selection[j]->tab[k]->id)
296           return 0;
297       }
298     }
299   }
300   
301   return 1;
302
303
304 }
305
306 void display_selection (group_list_t** selection,int M,int arity,double val){
307   int i,j;
308   for(i=0;i<M;i++){
309     for(j=0;j<arity;j++)
310       printf("%d ",selection[i]->tab[j]->id);
311     printf("-- ");
312   }
313   printf(":%f\n",val); 
314
315 }
316
317 void display_grouping (tree_t *father,int M,int arity,double val){
318   int i,j;
319   for(i=0;i<M;i++){
320     for(j=0;j<arity;j++)
321       printf("%d ",father[i].child[j]->id);
322     printf("-- ");
323   }
324   printf(":%f\n",val); 
325
326 }
327
328
329 int recurs_select_independent_groups(group_list_t **tab,int i,int n,int arity,int d,int M,double val,double *best_val,group_list_t **selection,group_list_t **best_selection){
330   group_list_t *elem;
331
332   //if(val>=*best_val)
333   // return 0;
334
335   if(d==M){
336     //display_selection(selection,M,arity,val);
337     if(val<*best_val){
338       *best_val=val;
339       for(i=0;i<M;i++)
340         best_selection[i]=selection[i];
341       return 1;
342     }
343     return 0;
344   }
345   
346   while(i<n){
347     elem=tab[i];
348     if(independent_groups(selection,d,elem,arity)){
349       //printf("%d: %d\n",d,i);
350       selection[d]=elem;
351       val+=elem->val;
352       return recurs_select_independent_groups(tab,i+1,n,arity,d+1,M,val,best_val,selection,best_selection);
353     }
354     i++;
355   }
356   return 0;
357 }
358
359
360 int test_independent_groups(group_list_t **tab,int i,int n,int arity,int d,int M,double val,double *best_val,group_list_t **selection,group_list_t **best_selection){
361   group_list_t *elem;
362
363   if(d==M){
364     //display_selection(selection,M,arity,val);
365     return 1;
366   }
367   
368   while(i<n){
369     elem=tab[i];
370     if(independent_groups(selection,d,elem,arity)){
371       //printf("%d: %d\n",d,i);
372       selection[d]=elem;
373       val+=elem->val;
374       return recurs_select_independent_groups(tab,i+1,n,arity,d+1,M,val,best_val,selection,best_selection);
375     }
376     i++;
377   }
378   return 0;
379 }
380
381 void  delete_group_list(group_list_t *list){
382
383   if(list){
384     delete_group_list(list->next);
385     free(list->tab);
386     free(list);
387   }
388 }
389
390
391 int group_list_id(const void* x1,const void* x2){ 
392
393   group_list_t *e1,*e2;
394
395   e1=*((group_list_t**)x1);
396   e2=*((group_list_t**)x2);
397
398   
399   return e1->tab[0]->id<e2->tab[0]->id?-1:1;
400
401
402 int group_list_asc(const void* x1,const void* x2){ 
403
404   group_list_t *e1,*e2;
405
406   e1=*((group_list_t**)x1);
407   e2=*((group_list_t**)x2);
408
409   
410   return e1->val<e2->val?-1:1;
411
412
413
414 int group_list_dsc(const void* x1,const void* x2){ 
415
416   group_list_t *e1,*e2;
417
418   e1=*((group_list_t**)x1);
419   e2=*((group_list_t**)x2);
420
421   
422   return e1->val>e2->val?-1:1;
423
424
425
426 int weighted_degree_asc(const void* x1,const void* x2){ 
427
428   group_list_t *e1,*e2;
429
430   e1=*((group_list_t**)x1);
431   e2=*((group_list_t**)x2);
432
433   
434   return e1->wg>e2->wg?1:-1;
435
436
437
438 int weighted_degree_dsc(const void* x1,const void* x2){ 
439
440   group_list_t *e1,*e2;
441
442   e1=*((group_list_t**)x1);
443   e2=*((group_list_t**)x2);
444
445   
446   return e1->wg>e2->wg?-1:1;
447
448
449 int  select_independent_groups(group_list_t **tab_group,int n,int arity,int M,double *best_val,group_list_t **best_selection,int bound,double max_duration){
450   int i;
451   group_list_t **selection;
452   double val,duration;
453   CLOCK_T time1,time0;
454
455
456   selection=(group_list_t **)malloc(sizeof(group_list_t*)*M);
457   CLOCK(time0);
458   for(i=0;i<MIN(bound,n);i++){
459     selection[0]=tab_group[i];
460     val=tab_group[i]->val;
461     recurs_select_independent_groups(tab_group,i+1,n,arity,1,M,val,best_val,selection,best_selection);
462     if(i%5){
463       CLOCK(time1);
464       duration=CLOCK_DIFF(time1,time0);
465       if(duration>max_duration){
466         free(selection);
467         return 1;
468       }
469     }
470   }
471
472   free(selection);
473
474 #ifdef DEBUG
475   display_selection(best_selection,M,arity,*best_val);
476 #endif
477   return 0;
478 }
479
480 int  select_independent_groups_by_largest_index(group_list_t **tab_group,int n,int arity,int M,double *best_val,group_list_t **best_selection,int bound,double max_duration){
481   int i,nb_groups=0;
482   group_list_t **selection;
483   double val,duration;
484   int dec;
485   CLOCK_T time1,time0;
486
487   selection=(group_list_t **)malloc(sizeof(group_list_t*)*M);
488   CLOCK(time0);
489   
490   dec=MAX(n/10000,1);
491   for(i=n-1;i>=0;i-=dec*dec){
492     selection[0]=tab_group[i];
493     val=tab_group[i]->val;
494     nb_groups+=test_independent_groups(tab_group,i+1,n,arity,1,M,val,best_val,selection,best_selection);
495     //printf("%d:%d\n",i,nb_groups);
496     if(nb_groups>=bound){
497       free(selection);
498       return 0;
499     }
500     if(i%5){
501       CLOCK(time1);
502       duration=CLOCK_DIFF(time1,time0);
503       if(duration>max_duration){
504         free(selection);
505         return 1;
506       }
507     }
508   }
509
510   free(selection);
511   return 0;
512 }
513
514 void list_to_tab(group_list_t *list,group_list_t **tab,int n){
515   int i;
516   for(i=0;i<n;i++){
517     if(!list){
518       fprintf(stderr,"Error not enough elements. Only %d on %d\n",i,n);
519       exit(-1);
520     }
521     tab[n-i-1]=list;
522     list=list->next;
523   }
524   if(list){
525     fprintf(stderr,"Error too many elements\n");
526     exit(-1);
527   }
528 }
529
530 void display_tab_group(group_list_t **tab, int n,int arity){
531   int i,j;
532   for(i=0;i<n;i++){
533     for(j=0;j<arity;j++)
534       printf("%d ",tab[i]->tab[j]->id);
535     printf(": %.2f %.2f\n",tab[i]->val,tab[i]->wg);
536   }
537 }
538
539 int independent_tab(tree_t **tab1,tree_t **tab2,int n){
540   int i,j;
541   i=0;j=0;
542   while((i<n)&&(j<n)){
543     if(tab1[i]->id==tab2[j]->id)
544       return 0;
545     else if(tab1[i]->id>tab2[j]->id)
546       j++;
547     else
548       i++;
549   }
550   return 1;
551 }
552
553     
554
555 void compute_weighted_degree(group_list_t **tab, int n,int arity){
556   int i,j;
557   for(i=0;i<n;i++)
558     tab[i]->sum_neighbour=0;
559   for(i=0;i<n;i++){
560     //printf("%d/%d=%f%%\n",i,n,(100.0*i)/n);
561     for(j=i+1;j<n;j++){
562       //if(!independent_groups(&tab[i],1,tab[j],arity)){
563         if(!independent_tab(tab[i]->tab,tab[j]->tab,arity)){
564         tab[i]->sum_neighbour+=tab[j]->val;
565         tab[j]->sum_neighbour+=tab[i]->val;
566      }
567     }
568
569     tab[i]->wg=tab[i]->sum_neighbour/tab[i]->val;
570     if(tab[i]->sum_neighbour==0)
571       tab[i]->wg=0;
572     //printf("%d:%f/%f=%f\n",i,tab[i]->sum_neighbour,tab[i]->val,tab[i]->wg);
573   }
574 }
575
576
577 /*
578   Very slow: explore all possibilities
579   tab: comm_matrix at the considered level (used to evaluate a grouping)
580   tab_node: array of the node to group
581   parent: node to which attached the computed group
582   id: current considered node of tab_node
583   arity: number of children of parent (i.e.) size of the group to compute
584   best_val: current value of th grouping
585   cur_group: current grouping
586  */
587 void  group(double **tab,tree_t *tab_node,tree_t *parent,int id,int arity, int n,double *best_val,tree_t **cur_group,int N){
588   double val;
589   int i;
590
591
592   //if we have found enough noide in the group
593   if(n==arity){
594     // evaluate this group
595     val=eval_grouping(tab,cur_group,arity,N);
596     // If we improve compared to previous grouping: uodate the children of parent accordingly
597     if(val<*best_val){
598       *best_val=val;
599         for(i=0;i<arity;i++){
600           parent->child[i]=cur_group[i];
601         }
602       parent->arity=arity;
603     } 
604     return;
605   }
606   
607
608
609   // If we need more node in the group
610   // Continue to explore avilable nodes
611   for(i=id+1;i<N;i++){
612     // If this node is allready in a group: skip it
613     if(tab_node[i].parent)
614       continue;
615     //Otherwise, add it to the group at place n
616     cur_group[n]=&tab_node[i];
617     //printf("%d<-%d\n",n,i);
618     //recursively add the next element to this group
619     group(tab,tab_node,parent,i,arity,n+1,best_val,cur_group,N);
620   }
621 }
622
623 /*
624    tab: comm_matrix at the considered level (use to evaluate a grouping)
625   tab_node: array of the node to group
626   parent: node to which attached the computed group
627   id: current considered node of tab_node
628   arity: number of children of parent (i.e.) size of the group to compute
629   best_val: current value of th grouping
630   cur_group: current grouping
631   N: size of tab and tab_node. i.e. number of nodes at the considered level
632  */
633 void  fast_group(double **tab,tree_t *tab_node,tree_t *parent,int id,int arity, int n,
634                  double *best_val,tree_t **cur_group,int N, int *nb_groups,int max_groups){
635   double val;
636   int i;
637
638   //printf("Max groups=%d\n",max_groups);
639
640   //if we have found enough node in the group
641   if(n==arity){
642     (*nb_groups)++;
643     // evaluate this group
644     val=eval_grouping(tab,cur_group,arity,N);
645     // If we improve compared to previous grouping: uodate the children of parent accordingly
646     if(val<*best_val){
647       *best_val=val;
648         for(i=0;i<arity;i++){
649           parent->child[i]=cur_group[i];
650         }
651       parent->arity=arity;
652     } 
653     return;
654   }
655   
656
657
658   // If we need more node in the group
659   // Continue to explore avilable nodes
660   for(i=id+1;i<N;i++){
661     // If this node is allready in a group: skip it
662     if(tab_node[i].parent)
663       continue;
664     //Otherwise, add it to the group at place n
665     cur_group[n]=&tab_node[i];
666     //printf("%d<-%d %d/%d\n",n,i,*nb_groups,max_groups);
667     //exit(-1);
668     //recursively add the next element to this group
669     fast_group(tab,tab_node,parent,i,arity,n+1,best_val,cur_group,N,nb_groups,max_groups);
670     if(*nb_groups>max_groups)
671       return;
672   }
673 }
674
675
676
677
678 void fast_grouping(double **tab,tree_t *tab_node, tree_t *new_tab_node, int arity,int N, int M,long int k){
679   tree_t **cur_group;
680   int l,i;
681   double best_val,val=0;
682   int nb_groups;
683
684   cur_group=(tree_t**)malloc(sizeof(tree_t*)*arity);
685   for(l=0;l<M;l++){
686     best_val=DBL_MAX;
687     nb_groups=0;
688     //printf("k%d/%d, k=%ld\n",l,M,k);
689     /* select the best greedy grouping among the 10 first one*/
690     //fast_group(tab,tab_node,&new_tab_node[l],-1,arity,0,&best_val,cur_group,N,&nb_groups,MAX(2,(int)(50-log2(k))-M/10));
691     fast_group(tab,tab_node,&new_tab_node[l],-1,arity,0,&best_val,cur_group,N,&nb_groups,MAX(1,(int)(50-CmiLog2(k))-M/10));
692     val+=best_val;
693     for(i=0;i<new_tab_node[l].arity;i++){
694       new_tab_node[l].child[i]->parent=&new_tab_node[l];
695     }
696     update_val(tab,&new_tab_node[l],N);
697   }
698
699   free(cur_group);  
700
701   printf("val=%f\n",val);
702   //exit(-1);
703
704 #ifdef DEBUG
705   display_grouping(new_tab_node,M,arity,val);
706 #endif
707 }
708
709
710
711
712 int adjacency_asc(const void* x1,const void* x2){ 
713
714   adjacency_t *e1,*e2;
715
716   e1=((adjacency_t*)x1);
717   e2=((adjacency_t*)x2);
718
719   
720   return e1->val<e2->val?-1:1;
721
722
723
724 int adjacency_dsc(const void* x1,const void* x2){ 
725
726   adjacency_t *e1,*e2;
727
728   e1=((adjacency_t*)x1);
729   e2=((adjacency_t*)x2);
730
731   
732   return e1->val>e2->val?-1:1;
733
734 void super_fast_grouping(double **tab,tree_t *tab_node, tree_t *new_tab_node, int arity,int N, int M,int k){
735   double val=0;
736   adjacency_t *graph;
737   int i,j,e,l,nb_groups;
738   double duration;
739
740   assert(arity==2);
741
742   TIC;
743   graph=(adjacency_t*)malloc(sizeof(adjacency_t)*((N*N-N)/2));
744   e=0;
745   for(i=0;i<N;i++){
746     for(j=i+1;j<N;j++){
747       graph[e].i=i;
748       graph[e].j=j;
749       graph[e].val=tab[i][j];
750       e++;
751     }
752   }
753   duration=TOC;
754   printf("linearization=%fs\n",duration);
755   
756
757   assert(e==(N*N-N)/2);
758   TIC;  
759   qsort(graph,e,sizeof(adjacency_t),adjacency_dsc);
760   duration=TOC;
761   
762   printf("sorting=%fs\n",duration);
763
764   TIC;
765
766 TIC;
767   l=0;
768   nb_groups=0;
769   for(i=0;i<e&&l<M;i++){
770     if(try_add_edge(tab,tab_node,&new_tab_node[l],arity,graph[i].i,graph[i].j,N,&nb_groups)){
771       l++;
772     }
773   }
774
775   for(l=0;l<M;l++){
776     update_val(tab,&new_tab_node[l],N);      
777     val+=new_tab_node[l].val;
778   }
779
780   duration=TOC;
781   printf("Grouping=%fs\n",duration);
782
783   printf("val=%f\n",val);
784
785 #ifdef DEBUG
786   display_grouping(new_tab_node,M,arity,val);
787 #endif
788 }
789
790
791
792 double **build_cost_matrix(double **comm_matrix, double* obj_weight, double comm_speed, int N){
793   double **res,avg;
794   int i,j;
795
796   if(!obj_weight)
797     return comm_matrix;
798
799   res=(double**)malloc(N*sizeof(double*));
800   for(i=0;i<N;i++)
801     res[i]=(double*)malloc(N*sizeof(double));
802   
803   avg=0;
804   for(i=0;i<N;i++)
805     avg+=obj_weight[i];
806   avg/=N;
807
808   printf("avg=%f\n",avg);
809
810   for(i=0;i<N;i++)
811     for(j=0;j<N;j++)
812       if(i==j)
813         res[i][j]=0;
814       else
815         res[i][j]=1e-4*comm_matrix[i][j]/comm_speed-fabs(avg-(obj_weight[i]+obj_weight[j])/2);
816
817   return res;
818   
819 }
820
821
822
823 /*
824   comm_matrix: comm_matrix at the considered level (use to evaluate a grouping) of size N*N
825   tab_node: array of the node to group
826   new_tab_node: array of nodes at the next level (the parents of the node in tab_node once the grouping will be done). 
827   arity: number of children of parent (i.e.) size of the group to compute
828   N: size of tab and tab_node. i.e. number of nodes at the considered level
829   M: size of new_tab_node (i.e) the number of parents
830   Hence we have: M*arity=N
831 */void group_nodes(double **comm_matrix,tree_t *tab_node, tree_t *new_tab_node, int depth, int arity,int N, int M, double* obj_weigth, double comm_speed){
832   tree_t **cur_group;
833   int j,l,n;
834   long int k;
835   group_list_t list,**best_selection,**tab_group;
836   double best_val,last_best;
837   int timeout;
838   double **tab; /*cost matrix taking into account the communiocation cost but also the weight of the object*/
839   double duration;
840
841   TIC;
842
843   /* might return comm_matrix (if obj_weight==NULL): do not free this tab in this case*/ 
844   tab=build_cost_matrix(comm_matrix,obj_weigth,comm_speed,N);
845
846
847
848   k=choose(N,arity);
849   printf("Number of groups:%ld\n",k);
850   
851   if(k>30000||depth>5){
852   #ifdef DEBUG
853     printf("Fast Grouping...\n");
854 #endif
855
856     double duration;
857     
858     TIC;
859     if(arity<=2){
860       //super_fast_grouping(tab,tab_node,new_tab_node,arity,N,M,k);
861       bucket_grouping(tab,tab_node,new_tab_node,arity,N,M,k);
862     }else{
863       fast_grouping(tab,tab_node,new_tab_node,arity,N,M,k);
864     }
865     duration=TOC;
866
867     printf("Fast grouping duration=%f\n",duration);
868     
869     //exit(-1);
870   }else{
871 #ifdef DEBUG
872     printf("Grouping nodes...\n");
873 #endif
874     list.next=NULL;
875     list.val=0;//number of elements in the list
876     cur_group=(tree_t**)malloc(sizeof(tree_t*)*arity);
877     best_selection=(group_list_t **)malloc(sizeof(group_list_t*)*M);
878   
879     list_all_possible_groups(tab,tab_node,0,arity,0,cur_group,N,&list);
880     n=(int)list.val;
881     assert(n==k);
882     tab_group=(group_list_t**)malloc(sizeof(group_list_t)*n);
883     list_to_tab(list.next,tab_group,n);
884 #ifdef DEBUG
885     printf("List to tab done\n");
886 #endif
887     best_val=DBL_MAX;
888   
889     // perform the pack mapping fist
890     timeout=select_independent_groups(tab_group,n,arity,M,&best_val,best_selection,1,0.1);
891 #ifdef DEBUG
892     if(timeout){
893       printf("Packed mapping timeout!\n");
894     }
895 #endif
896     // give this mapping an exra credit (in general MPI application are made such that neighbour process communicates more than distant ones)
897     best_val/=1.001;
898 #ifdef DEBUG
899     printf("Packing computed\n");
900 #endif
901     // perform a mapping trying to use group that cost less first
902     qsort(tab_group,n,sizeof(group_list_t*),group_list_asc);
903     last_best=best_val;
904     timeout=select_independent_groups(tab_group,n,arity,M,&best_val,best_selection,10,0.1);
905 #ifdef DEBUG
906     if(timeout){
907       printf("Cost less first timeout!\n");
908     }else if(last_best>best_val){
909       printf("Cost less first Impoved solution\n");
910     }
911     printf("----\n");
912 #endif
913     // perform a mapping trying to minimize the use of groups that cost a lot 
914     qsort(tab_group,n,sizeof(group_list_t*),group_list_dsc);
915     last_best=best_val;
916     timeout=select_independent_groups_by_largest_index(tab_group,n,arity,M,&best_val,best_selection,10,0.1);
917 #ifdef DEBUG
918     if(timeout){
919       printf("Cost most last timeout!\n");
920     }else if(last_best>best_val){
921       printf("Cost most last impoved solution\n");
922     }
923 #endif
924     if(n<10000){
925       // perform a mapping in the weighted degree order 
926 #ifdef DEBUG
927       printf("----WG----\n");
928 #endif
929       compute_weighted_degree(tab_group,n,arity);
930 #ifdef DEBUG
931       printf("Weigted degree computed\n");
932 #endif
933       qsort(tab_group,n,sizeof(group_list_t*),weighted_degree_dsc);
934       //display_tab_group(tab_group,n,arity);
935       last_best=best_val;
936       timeout=select_independent_groups(tab_group,n,arity,M,&best_val,best_selection,10,0.1);
937 #ifdef DEBUG
938       if(timeout){
939         printf("WG timeout!\n");
940       }else if(last_best>best_val){
941         printf("WG impoved solution\n");
942       }
943 #endif
944     }
945     
946     qsort(best_selection,M,sizeof(group_list_t*),group_list_id);
947
948     for(l=0;l<M;l++){
949       for(j=0;j<arity;j++){
950         new_tab_node[l].child[j]=best_selection[l]->tab[j];
951         new_tab_node[l].child[j]->parent=&new_tab_node[l];
952       }
953       new_tab_node[l].arity=arity;
954     
955       //printf("arity=%d\n",new_tab_node[l].arity);
956       update_val(tab,&new_tab_node[l],N);
957     }
958     
959     delete_group_list((&list)->next);
960     free(best_selection);
961     free(tab_group);
962     free(cur_group);  
963   }
964
965   if(tab!=comm_matrix)
966     free_tab_double(tab,N);
967   
968   duration=TOC;
969   printf("Grouping done in %.4fs!\n",duration);
970 }
971
972
973
974
975
976 void complete_com_mat(double ***tab,int N, int K){
977   double **old_tab,**new_tab;
978   int M,i,j;
979
980   old_tab=*tab;
981   
982   M=N+K;
983   new_tab=(double**)malloc(M*sizeof(double*));
984   for(i=0;i<M;i++)
985     new_tab[i]=(double*)malloc(M*sizeof(double));
986   
987   *tab=new_tab;
988   for(i=0;i<M;i++){
989     for(j=0;j<M;j++){
990       if((i<N)&&(j<N)){
991         new_tab[i][j]=old_tab[i][j];
992       }else{
993         new_tab[i][j]=0;
994       }
995     }
996   }
997 }
998
999 void complete_obj_weight(double **tab,int N, int K){
1000   double *old_tab,*new_tab,avg;
1001   int M,i;
1002
1003   old_tab=*tab;
1004
1005   if(!old_tab)
1006     return;
1007
1008   
1009   avg=0;
1010   for(i=0;i<N;i++)
1011     avg+=old_tab[i];
1012   avg/=N;
1013
1014   
1015   M=N+K;
1016   new_tab=(double*)malloc(M*sizeof(double));
1017   
1018   *tab=new_tab;
1019   for(i=0;i<M;i++){
1020     if(i<N){
1021       new_tab[i]=old_tab[i];
1022     }else{
1023       new_tab[i]=avg;
1024     }
1025   }
1026 }
1027
1028
1029
1030 void create_dumb_tree(tree_t *node,int depth,tm_topology_t *topology){
1031   tree_t **list_child;
1032   int arity,i;
1033
1034   
1035   if(depth==topology->nb_levels-1){
1036     set_node(node,NULL,0,NULL,-1,0,NULL);  
1037     return;
1038   }
1039
1040   arity=topology->arity[depth];
1041   assert(arity>0);
1042   list_child=(tree_t**)calloc(arity,sizeof(tree_t*));
1043   for(i=0;i<arity;i++){
1044     list_child[i]=(tree_t*)malloc(sizeof(tree_t));
1045     create_dumb_tree(list_child[i],depth+1,topology);
1046     list_child[i]->parent=node;
1047     list_child[i]->dumb=1;
1048   }
1049
1050   set_node(node,list_child,arity,NULL,-1,0,list_child[0]);
1051   
1052 }
1053
1054 void complete_tab_node(tree_t **tab,int N, int K,int depth,tm_topology_t *topology){
1055   tree_t *old_tab,*new_tab;
1056   int M,i;
1057   if(K==0)
1058     return;
1059
1060   old_tab=*tab;
1061
1062   
1063   M=N+K;
1064   new_tab=(tree_t*)malloc(M*sizeof(tree_t));
1065   
1066   *tab=new_tab;
1067   for(i=0;i<M;i++){
1068     if((i<N)){
1069       clone_tree(&new_tab[i],&old_tab[i]);
1070     }else{
1071       create_dumb_tree(&new_tab[i],depth,topology);
1072       new_tab[i].id=i;
1073     }
1074   }
1075
1076   //do not suppress tab if you are at the depth-most level it will be used at the mapping stage
1077   free(old_tab);  
1078 }
1079
1080
1081 void set_deb_tab_child(tree_t *tree, tree_t *child,int depth){
1082   //printf("depth=%d\t%p\t%p\n",depth,child,tree);
1083   if(depth>0)
1084     set_deb_tab_child(tree->tab_child,child,depth-1);
1085   else
1086     tree->tab_child=child;
1087 }
1088
1089
1090
1091 /* 
1092 Build the tree of the matching. It is a bottom up algorithm: it starts from the bottom of the tree on proceed by decreasing the depth 
1093 It groups nodes of the matrix tab and link these groups to the nodes of the under level. 
1094 Then it calls recursivcely the function to prefrom the grouping at the above level. 
1095
1096 tab_node: array of nodes of the under level. 
1097 tab: local communication matrix 
1098 N: number of nodes. Order of com_mat, size of obj_weight 
1099 arity: arity of the nodes of the above level.
1100 depth: current depth of the algorithm
1101 toplogy: description of the hardware topology.  
1102 */
1103 tree_t *build_level_topology(tree_t *tab_node,double **com_mat,int N,int arity,int depth,tm_topology_t *topology, double *obj_weight, double *comm_speed){
1104   int M; /*N/Arity: number the groups*/
1105   int K=0,i;
1106   tree_t *new_tab_node; /*array of node for this level (of size M): there will be linked to the nodes of tab_nodes*/
1107   double **new_com_mat; /*New communication matrix (after grouyping nodes together)*/
1108   tree_t *res; /*resulting tree*/
1109   int completed=0;
1110   double speed; /* communication speed at this level*/
1111   double *new_obj_weight;
1112   if((depth==0)){
1113     if((N==1)&&(depth==0))
1114       return &tab_node[0];
1115     else{
1116       fprintf(stderr,"Error: matrix size: %d and depth:%d (should be 1 and -1 respectively)\n",N,depth);
1117       exit(-1);
1118     }
1119   }
1120
1121   
1122   /* If the number of nodes does not devide the arity: we add K nodes  */
1123   if(N%arity!=0){
1124     K=arity*((N/arity)+1)-N;
1125     //printf("****N=%d arity=%d K=%d\n",N,arity,K);  
1126     //display_tab(tab,N);
1127     /* add K rows and columns to comm_matrix*/
1128     complete_com_mat(&com_mat,N,K);
1129     /* add K element to the object weight*/
1130     complete_obj_weight(&obj_weight,N,K);
1131     //display_tab(tab,N+K);
1132     /* add a dumb tree to the K new "virtual nodes"*/
1133     complete_tab_node(&tab_node,N,K,depth,topology);
1134     completed=1; /*flag this addition*/
1135     N+=K; /*increase the number of nodes accordingly*/
1136   } //display_tab(tab,N);
1137
1138
1139   M=N/arity;
1140   printf("Depth=%d\tnb_nodes=%d\tnb_groups=%d\tsize of groups(arity)=%d\n",depth,N,M,arity);
1141
1142   /*create the new nodes*/
1143   new_tab_node=(tree_t*)malloc(sizeof(tree_t)*M);
1144   /*intitialize each node*/
1145   for(i=0;i<M;i++){
1146     tree_t **list_child;
1147     list_child=(tree_t**)calloc(arity,sizeof(tree_t*));
1148     set_node(&new_tab_node[i],list_child,arity,NULL,i,0,tab_node);
1149   }
1150
1151   /*Core of the algorithm: perfrom the grouping*/
1152   if(comm_speed)
1153     speed=comm_speed[depth];
1154   else
1155     speed=-1;
1156   group_nodes(com_mat,tab_node,new_tab_node,depth,arity,N,M,obj_weight,speed);
1157  
1158   /*based on that grouping aggregate the communication matrix*/
1159   new_com_mat=aggregate_com_mat(new_tab_node,com_mat,M);
1160   /*based on that grouping aggregate the object weight matrix*/
1161   new_obj_weight=aggregate_obj_weight(new_tab_node,obj_weight,M);
1162
1163   /* set ID of virtual nodes to -1*/
1164   for(i=N-K;i<N;i++)
1165     tab_node[i].id=-1;
1166
1167   //for(i=0;i<N;i++)
1168   //  display_node(&tab_node[i]);
1169
1170   //display_tab(new_com_mat,M);
1171
1172   /* decrease depth and compute arity of the above level*/
1173   depth--;
1174   if(depth>0)
1175     arity = topology->arity[depth-1];
1176   else
1177     arity=1;
1178   // assume all objects have the same arity
1179   res = build_level_topology(new_tab_node,new_com_mat,M,arity,depth,topology,new_obj_weight,comm_speed);  
1180
1181   set_deb_tab_child(res,tab_node,depth);
1182
1183
1184   if(completed){
1185     free_tab_double(com_mat,N);
1186     free(obj_weight);
1187   }
1188   free_tab_double(new_com_mat,M);
1189   free(new_obj_weight);
1190
1191   return res;
1192 }
1193
1194
1195
1196 double speed(int depth){
1197   // Bertha values
1198   //double tab[5]={21,9,4.5,2.5,0.001};
1199   //double tab[5]={1,1,1,1,1};
1200   //double tab[6]={100000,10000,1000,500,100,10};
1201   double tab[5]={100000,10000,1000,500,10};
1202     
1203   return 1.0/tab[depth];
1204   //return 10*log(depth+2);
1205   //return (depth+1);
1206   //return (long int)pow(100,depth);
1207 }
1208
1209 tree_t * build_tree_from_topology(tm_topology_t *topology,double **tab,int N,double *obj_weight, double *comm_speed){
1210   int depth,i; 
1211   tree_t *res,*tab_node;
1212
1213
1214   tab_node=(tree_t*)malloc(sizeof(tree_t)*N);
1215   for(i=0;i<N;i++)
1216     set_node(&tab_node[i],NULL,0,NULL,i,0,NULL); 
1217  
1218
1219   depth = topology->nb_levels -1;
1220   printf("nb_levels=%d\n",depth+1);
1221   // assume all objects have the same arity
1222   res = build_level_topology(tab_node,tab,N,topology->arity[depth-1],depth,topology, obj_weight, comm_speed);
1223   printf("Build tree done!\n");
1224   return res;
1225 }