Merge branch 'charm' of charmgit:charm into charm
[charm.git] / src / ck-ldb / tm_mapping.c
1 #include <unistd.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
5 #include <float.h>
6 #include "treetimings.h"
7 #include "treematch.h"
8 #include <ctype.h>
9 #include <math.h>
10 #include <assert.h> 
11 #ifdef _WIN32
12 #include <windows.h>
13 #include <winbase.h>
14 #define random() rand()
15 #define srandom(x)  srand(x)
16 #define strsep     strtok
17 #endif
18 #include "treemapping.h"
19  
20 #define TEST_ERROR(n) {if(n!=0){fprintf(stderr,"Error %d Line %d\n",n,__LINE__);exit(-1);}}
21 #undef DEBUG
22
23 #define LINE_SIZE 1000000
24
25 typedef struct{
26   int  val;
27   long key;
28 }hash_t;
29
30
31 typedef struct{
32   double val;
33   int key1;
34   int key2;
35 }hash2_t;
36
37
38 int nb_nodes(tm_topology_t *topology){
39   return topology->nb_nodes[topology->nb_levels-1];
40 }
41
42
43 void free_topology(tm_topology_t *topology){
44    int i;
45   for(i=0;i<topology->nb_levels;i++)
46     free(topology->node_id[i]);
47   free(topology->node_id);
48   free(topology->nb_nodes);
49   free(topology->arity);
50   free(topology);
51 }
52
53 double print_sol(int N,int *Value,double **comm, double **arch){
54   double sol;
55   int i,j;
56   double a,c;
57
58   sol=0;
59   for (i=0;i<N;i++){
60     for (j=i+1;j<N;j++){
61       c=comm[i][j];
62       a=arch[Value[i]][Value[j]];
63       //printf("T_%d_%d %f/%f=%f\n",i,j,c,a,c/a);
64       sol+=c/a;
65     }
66   }
67   for (i = 0; i < N; i++) {
68     printf("%d", Value[i]);
69     if(i<N-1)
70       printf(",");
71       
72   }
73   printf(" : %g\n",sol);
74
75   return sol;
76 }
77
78
79 void print_1D_tab(int *tab,int N){
80   int i;
81   for (i = 0; i < N; i++) {
82     printf("%d", tab[i]);
83     if(i<N-1)
84       printf(",");
85   }
86   printf("\n");
87
88 }
89
90 int nb_lines(char *filename){
91   FILE *pf;
92   char  line[LINE_SIZE];
93   int N=0;
94
95   if(!(pf=fopen(filename,"r"))){
96       fprintf(stderr,"Cannot open %s\n",filename);
97       exit(-1);
98   }
99
100   while(fgets(line,LINE_SIZE,pf))
101     N++;
102
103   printf("N=%d\n",N);
104
105   fclose(pf);
106   return N;
107 }
108
109 void init_comm(char *filename,int N,double **comm){
110   int i,j;
111   FILE *pf;
112   char *ptr;
113   char  line[LINE_SIZE];
114
115   if(!(pf=fopen(filename,"r"))){
116     fprintf(stderr,"Cannot open %s\n",filename);
117     exit(-1);
118   }
119
120
121   j=-1;
122   i=0;
123   while(fgets(line,LINE_SIZE,pf)){
124
125   
126     char *l=line;
127     j=0;
128     //printf("%s|",line);
129     while((ptr=strsep(&l," \t"))){
130       if((ptr[0]!='\n')&&(!isspace(ptr[0]))&&(*ptr)){
131         comm[i][j]=atof(ptr);
132         //printf ("comm[%d][%d]=%f|%s|\n",i,j,comm[i][j],ptr);
133         j++;
134       }
135     }
136     if(j!=N){
137       fprintf(stderr,"Error at %d %d (%d!=%d)for %s\n",i,j,j,N,filename);
138       exit(-1);
139     }
140     i++;
141   }
142   if(i!=N){
143     fprintf(stderr,"Error at %d %d for %s\n",i,j,filename);
144     exit(-1);
145   }
146
147   /*  printf("%s:\n",filename);
148   for(i=0;i<N;i++){
149     for(j=0;j<N;j++){
150       printf("%6.1f ",comm[i][j]);
151     }
152     printf("\n");
153     } */
154
155 }    
156
157 int  build_comm(char *filename,double ***pcomm){
158   int i;
159   int N;
160   double **comm;
161   N=nb_lines(filename);
162   comm=(double**)malloc(N*sizeof(double*));
163   for(i=0;i<N;i++)
164     comm[i]=(double*)malloc(N*sizeof(double));
165   init_comm(filename,N,comm);
166   *pcomm=comm;
167   return N;
168 }
169
170 void map_Packed(tm_topology_t *topology,int N,int *Value){
171   int i,depth;
172
173   depth=topology->nb_levels-1;
174
175   for(i=0;i<N;i++){
176     //printf ("%d -> %d\n",objs[i]->os_index,i);
177     Value[i]=topology->node_id[depth][i];
178   }
179
180 }
181
182 void map_RR(int N,int *Value){
183   int i;
184
185   for(i=0;i<N;i++){
186     //printf ("%d -> %d\n",i,i);
187     Value[i]=i;
188   }
189
190 }
191
192
193
194 int hash_asc(const void* x1,const void* x2){ 
195
196   hash_t *e1,*e2;
197
198   e1=((hash_t*)x1);
199   e2=((hash_t*)x2);
200
201   
202   return e1->key<e2->key?-1:1;
203
204
205
206 int *generate_random_sol(tm_topology_t *topology,int N,int level,int seed){
207   hash_t *hash_tab;
208   int *sol,i;
209   int *nodes_id;
210
211   nodes_id=topology->node_id[level];
212
213
214   hash_tab=(hash_t*)malloc(sizeof(hash_t)*N);
215   sol=(int*)malloc(sizeof(int)*N);
216   
217   srandom(seed);
218   
219   for(i=0;i<N;i++){
220     hash_tab[i].val=nodes_id[i];
221     hash_tab[i].key=random();
222   }
223   
224   qsort(hash_tab,N,sizeof(hash_t),hash_asc);
225   for(i=0;i<N;i++){
226     sol[i]=hash_tab[i].val;
227   }
228   free(hash_tab);
229   return sol;
230 }
231
232
233 double eval_sol(int *sol,int N,double **comm, double **arch){
234   double res;
235   int i,j;
236   double a,c;
237
238   res=0;
239   for (i=0;i<N;i++){
240     for (j=i+1;j<N;j++){
241       c=comm[i][j];
242       a=arch[sol[i]][sol[j]];
243       res+=c/a;
244     }
245   }
246   return res;
247 }
248
249 void exchange(int *sol,int i,int j){
250   int tmp;
251   tmp=sol[i];
252   sol[i]=sol[j];
253   sol[j]=tmp;
254 }
255
256 double gain_exchange(int *sol,int l,int m,double eval1,int N,double **comm, double **arch){
257   double eval2;
258   if(l==m)
259     return 0;
260   exchange(sol,l,m);
261   eval2=eval_sol(sol,N,comm,arch);
262   exchange(sol,l,m);
263   return eval1-eval2;
264 }
265
266 void select_max(int *l,int *m,double **gain,int N,int *state){
267   int i,j;
268   double max;
269   max=-DBL_MAX;
270   
271   for(i=0;i<N;i++){
272     if(!state[i]){
273       for(j=0;j<N;j++){
274           if((i!=j)&&(!state[j])){
275             if(gain[i][j]>max){
276               *l=i;*m=j;
277               max=gain[i][j];
278             }
279           }
280       }
281     }
282   }
283   
284 }
285
286 void compute_gain(int *sol,int N,double **gain,double **comm, double **arch){
287   int i,j;
288   double eval1;
289   eval1=eval_sol(sol,N,comm,arch);
290   for(i=0;i<N;i++){
291     for(j=0;j<=i;j++){
292       gain[i][j]=gain[j][i]=gain_exchange(sol,i,j,eval1,N,comm,arch);
293     }
294   } 
295 }
296
297
298
299 /* Randomized Algorithm of
300 Hu Chen, Wenguang Chen, Jian Huang ,Bob Robert,and H.Kuhn. Mpipp: an automatic profile-guided
301 parallel process placement toolset for smp clusters and multiclusters. In
302 Gregory K. Egan and Yoichi Muraoka, editors, ICS, pages 353-360. ACM, 2006.
303  */
304
305 void map_MPIPP(tm_topology_t *topology,int nb_seed,int N,int *Value,double **comm, double **arch){
306   int *sol;
307   int *state;
308   double **gain;
309   int **history;
310   double *temp;
311   int i,j,t,l=0,m=0,loop=0,seed=0;
312   double max,sum,best_eval,eval;
313
314   
315   gain=(double**)malloc(sizeof(double*)*N);
316   for(i=0;i<N;i++){
317     gain[i]=(double*)malloc(sizeof(double)*N);  
318     if(!gain[i]){
319     }
320   }
321   history=(int**)malloc(sizeof(int*)*N);
322   for(i=0;i<N;i++)
323     history[i]=(int*)malloc(sizeof(int)*3);
324
325   state=(int*)malloc(sizeof(int)*N);
326   temp=(double*)malloc(sizeof(double)*N);
327
328   sol=generate_random_sol(topology,N,topology->nb_levels-1,seed++);
329   for(i=0;i<N;i++)
330     Value[i]=sol[i];
331   
332   best_eval=DBL_MAX;
333   while(seed<=nb_seed){
334     loop=0;
335     do{
336
337       for(i=0;i<N;i++){
338         state[i]=0;
339         //printf("%d ",sol[i]);
340       }
341       //printf("\n");
342       compute_gain(sol,N,gain,comm,arch);
343   
344       //display_tab(gain,N);
345       //exit(-1);
346       for(i=0;i<N/2;i++){
347         select_max(&l,&m,gain,N,state);
348         //printf("%d: %d <=> %d : %f\n",i,l,m,gain[l][m]);
349         state[l]=1;state[m]=1;
350         exchange(sol,l,m);
351         history[i][1]=l;history[i][2]=m;
352         temp[i]=gain[l][m];
353         compute_gain(sol,N,gain,comm,arch);
354       }
355
356       t=-1;
357       max=0;
358       sum=0;
359       for(i=0;i<N/2;i++){
360         sum+=temp[i];
361         if(sum>max){
362           max=sum;
363           t=i;
364         }
365       }
366       /*for(j=0;j<=t;j++)
367         printf("exchanging: %d with %d for gain: %f\n",history[j][1],history[j][2],temp[j]); */
368       for(j=t+1;j<N/2;j++){
369         exchange(sol,history[j][1],history[j][2]);
370         //printf("Undoing: %d with %d for gain: %f\n",history[j][1],history[j][2],temp[j]); 
371       }
372       //printf("max=%f\n",max);
373
374       /*for(i=0;i<N;i++){
375         printf("%d ",sol[i]);
376         }
377         printf("\n");*/
378       eval=eval_sol(sol,N,comm,arch);
379       if(eval<best_eval){
380         best_eval=eval;
381         for(i=0;i<N;i++)
382           Value[i]=sol[i];
383         //print_sol(N);
384       }
385     
386
387     }while(max>0);
388     
389     sol=generate_random_sol(topology,N,topology->nb_levels-1,seed++);
390
391   }
392
393 }
394   
395
396
397
398 void map_tree(tree_t* t1,tree_t *t2){
399   /*  double x1,x2;
400   if((!t1->left)&&(!t1->right)){
401     printf ("%d -> %d\n",t1->id,t2->id);
402     Value[t2->id]=t1->id;
403    return;
404   }
405   x1=t2->right->val/t1->right->val+t2->left->val/t1->left->val;
406   x2=t2->left->val/t1->right->val+t2->right->val/t1->left->val;
407   if(x1<x2){
408     map_tree(t1->left,t2->left);
409     map_tree(t1->right,t2->right);
410   }else{
411     map_tree(t1->right,t2->left);
412     map_tree(t1->left,t2->right);
413     }*/
414 }
415
416 void depth_first(tree_t *comm_tree, int *proc_list,int *i){
417   int j;
418   if(!comm_tree->child){
419     proc_list[(*i)++]=comm_tree->id;
420     return;
421   }
422
423   for(j=0;j<comm_tree->arity;j++){
424     depth_first(comm_tree->child[j],proc_list,i);
425   }
426 }
427
428 int nb_leaves(tree_t *comm_tree){
429   int n=0,j;
430
431   if(!comm_tree->child){
432     return 1;
433   }
434
435   for(j=0;j<comm_tree->arity;j++){
436     n+=nb_leaves(comm_tree->child[j]);
437   }
438   return n;
439 }
440
441
442
443
444 /*Map topology to cores: 
445  sigma_i is such that  process i is mapped on core sigma_i
446  k_i is such that core i exectutes process k_i
447
448  size of sigma is the number of process
449  size of k is the number of cores/nodes
450
451  We must have numbe of process<=number of cores
452
453  k_i =-1 if no process is mapped on core i
454 */
455 void map_topology(tm_topology_t *topology,tree_t *comm_tree,int nb_proc,int level,
456                   int *sigma, int *k){
457   int *nodes_id;
458   int N;
459   int *proc_list,i,l;
460   int M;
461   int block_size;
462
463  
464   M=nb_leaves(comm_tree);
465   printf("nb_leaves=%d\n",M);
466
467
468
469   nodes_id=topology->node_id[level];
470   N=topology->nb_nodes[level];
471   //printf("level=%d, nodes_id=%p, N=%d\n",level,nodes_id,N);
472
473
474   //printf("N=%d,nb_proc=%d\n",N,nb_proc);
475   /* The number of node at level "level" in the tree should be equal to the number of processors*/
476   assert(N==nb_proc);
477
478
479   proc_list=(int*)malloc(sizeof(int)*M);
480   i=0;
481   depth_first(comm_tree,proc_list,&i);
482
483   l=0;
484   for(i=0;i<M;i++){
485     //printf ("%d\n",proc_list[i]);
486   }
487
488
489   block_size=M/N;
490
491
492   if(k){/*if we need the k vector*/
493     printf("M=%d, N=%d, BS=%d\n",M,N,block_size);
494     for(i=0;i<nb_nodes(topology);i++){
495       k[i]=-1;
496     }
497     for(i=0;i<M;i++){
498       if(proc_list[i]!=-1){
499 #ifdef DEBUG
500         printf ("%d->%d\n",proc_list[i],nodes_id[i/block_size]);
501 #endif
502         sigma[proc_list[i]]=nodes_id[i/block_size];
503         k[nodes_id[i/block_size]]=proc_list[i];
504       }
505     }
506   }else{
507     printf("M=%d, N=%d, BS=%d\n",M,N,block_size);
508     for(i=0;i<M;i++){
509       if(proc_list[i]!=-1){
510 #ifdef DEBUG
511         printf ("%d->%d\n",proc_list[i],nodes_id[i/block_size]);
512 #endif
513         sigma[proc_list[i]]=nodes_id[i/block_size];
514       }
515     }
516
517   }
518   free(proc_list);
519
520 }
521
522 void map_topology_simple(tm_topology_t *topology,tree_t *comm_tree, int *sigma,int *k){
523   map_topology(topology,comm_tree,topology->nb_nodes[topology->nb_levels-1],topology->nb_levels-1,sigma,k);
524 }
525
526 int int_cmp(const void* x1,const void* x2){ 
527
528   int *e1,*e2;
529
530   e1=((int *)x1);
531   e2=((int *)x2);
532
533   
534   return (*e1)>(*e2)?-1:1;
535
536
537
538 int decompose(int n,int optimize,int *tab){
539   int primes[6]={2,3,5,7,11,0},i=0;
540   int flag=2;
541   int j=1;
542
543
544   while(primes[i]&&(n!=1)){
545     printf("[%d] before=%d\n",primes[i],n);
546     if(flag&&optimize&&(n%primes[i]!=0)){
547       n+=primes[i]-n%primes[i];
548       flag--;
549       i=0;
550       continue;
551     }
552     printf("after=%d\n",n);
553     if(n%primes[i]==0){
554       tab[j++]=primes[i];
555       n/=primes[i];
556     }else{
557       i++;
558       flag=1;
559     }
560   }
561   if(n!=1){
562     tab[j++]=n;
563   }
564
565   qsort(tab+1,j-1,sizeof(int),int_cmp);
566
567   for(i=0;i<j;i++)
568     printf("%d:",tab[i]);
569   printf("\n");
570
571   tab[j]=0;
572   
573   return j+1;
574 }
575
576
577 tree_t *build_synthetic_topology(int *synt_tab,int id,int depth,int nb_levels){
578   tree_t *res,**child;
579   int arity=synt_tab[0];
580   int val,i; 
581
582   res=(tree_t*)malloc(sizeof(tree_t));
583   val=0;
584   if(depth>=nb_levels)
585     child=NULL;
586   else{
587     child=(tree_t**)malloc(sizeof(tree_t*)*arity);
588     for(i=0;i<arity;i++){
589       child[i]=build_synthetic_topology(synt_tab+1,i,depth+1,nb_levels);
590     child[i]->parent=res;
591     val+=child[i]->val;
592     }
593   }
594   set_node(res,child,arity,NULL,id,val+speed(depth),child[0]);
595   return res;
596 }
597
598
599 void   build_synthetic_proc_id(tm_topology_t *topology){
600   int n=1,i,j;
601   topology->node_id=(int**)malloc(sizeof(int*)*topology->nb_levels);
602   topology->nb_nodes=(int*)malloc(sizeof(int)*topology->nb_levels);
603
604
605   for(i=0;i<topology->nb_levels;i++){
606     topology->nb_nodes[i]=n;
607     topology->node_id[i]=(int*)malloc(sizeof(int)*n);
608     for(j=0;j<n;j++)
609       topology->node_id[i][j]=j;
610     n*=topology->arity[i]; 
611   }
612
613 }
614
615 void TreeMatchMapping(int nb_obj, int nb_proc,double **comm_mat,  int *sol){
616   tree_t *comm_tree;
617   tm_topology_t *topology;
618
619   int i;
620   for(i=0;i<nb_obj;i++)
621     sol[i]=i;
622
623
624   //  return;
625
626   topology=(tm_topology_t*)malloc(sizeof(tm_topology_t));
627   topology->arity=(int*)malloc(sizeof(int)*MAX_LEVELS);
628   topology->arity[0]=nb_proc;
629   topology->nb_levels=decompose((int)ceil((1.0*nb_obj)/nb_proc),1,topology->arity);
630   printf("Topology nb levels=%d\n",topology->nb_levels);
631   build_synthetic_proc_id(topology);
632
633
634   //exit(-1);
635   //topology_to_arch(topology);
636
637   //display_tab(arch,hwloc_get_nbobjs_by_type(topology, HWLOC_OBJ_PROC));
638   //display_tab(arch,96);
639   //exit(-1);
640   //int nb_core=topo_nb_proc(topology,1000);
641
642   //display_tab(comm_mat,N);
643
644   comm_tree=build_tree_from_topology(topology,comm_mat,nb_obj);
645   map_topology(topology,comm_tree,nb_proc,1,sol,NULL);
646
647
648   free_topology(topology);
649   free_tree(comm_tree);
650   printf("-------------- Mapping done!\n");
651 }
652
653 void display_other_heuristics(tm_topology_t *topology,int N,double **comm,double **arch){
654   CLOCK_T time1,time0;
655   double duration; 
656   int *sol;
657  
658   sol=(int*)malloc(sizeof(int)*N);
659
660   map_Packed(topology,N,sol);
661   printf("Packed: "); 
662   print_sol(N,sol,comm,arch);
663
664
665
666   map_RR(N,sol);
667   printf("RR: "); 
668   print_sol(N,sol,comm,arch);
669
670   CLOCK(time0);
671   map_MPIPP(topology,1,N,sol,comm,arch);
672   CLOCK(time1);
673   duration=CLOCK_DIFF(time1,time0);
674   printf("MPIPP-1-D:%f\n",duration);
675   printf("MPIPP-1: ");
676   print_sol(N,sol,comm,arch);
677
678   CLOCK(time0);
679   map_MPIPP(topology,5,N,sol,comm,arch);
680   CLOCK(time1);
681   duration=CLOCK_DIFF(time1,time0);
682   printf("MPIPP-5-D:%f\n",duration);
683   printf("MPIPP-5: ");
684   print_sol(N,sol,comm,arch);
685
686   free(sol);
687 }
688
689