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