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