doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / tm_mapping.c
index d15843ffd88e0324088aeeaa1459a20401236f14..7f37cfe6e2b226b9f76fadbf70284d1542c62911 100644 (file)
@@ -3,19 +3,18 @@
 #include <stdlib.h>
 #include <string.h>
 #include <float.h>
-#include "treetimings.h"
-#include "treematch.h"
 #include <ctype.h>
 #include <math.h>
 #include <assert.h> 
+#include "tm_mapping.h"
+#include "tm_timings.h"
+#include "tm_tree.h"
 #ifdef _WIN32
 #include <windows.h>
 #include <winbase.h>
 #define random() rand()
 #define srandom(x)  srand(x)
-#define strsep     strtok
 #endif
-#include "treemapping.h"
  
 #define TEST_ERROR(n) {if(n!=0){fprintf(stderr,"Error %d Line %d\n",n,__LINE__);exit(-1);}}
 #undef DEBUG
@@ -40,6 +39,9 @@ int nb_nodes(tm_topology_t *topology){
 }
 
 
+
+
+
 void free_topology(tm_topology_t *topology){
    int i;
   for(i=0;i<topology->nb_levels;i++)
@@ -126,7 +128,7 @@ void init_comm(char *filename,int N,double **comm){
     char *l=line;
     j=0;
     //printf("%s|",line);
-    while((ptr=strsep(&l," \t"))){
+    while((ptr=strtok(l," \t"))){
       if((ptr[0]!='\n')&&(!isspace(ptr[0]))&&(*ptr)){
        comm[i][j]=atof(ptr);
        //printf ("comm[%d][%d]=%f|%s|\n",i,j,comm[i][j],ptr);
@@ -542,14 +544,14 @@ int decompose(int n,int optimize,int *tab){
 
 
   while(primes[i]&&(n!=1)){
-    printf("[%d] before=%d\n",primes[i],n);
+    //    printf("[%d] before=%d\n",primes[i],n);
     if(flag&&optimize&&(n%primes[i]!=0)){
       n+=primes[i]-n%primes[i];
       flag--;
       i=0;
       continue;
     }
-    printf("after=%d\n",n);
+    //printf("after=%d\n",n);
     if(n%primes[i]==0){
       tab[j++]=primes[i];
       n/=primes[i];
@@ -574,7 +576,7 @@ int decompose(int n,int optimize,int *tab){
 }
 
 
-tree_t *build_synthetic_topology(int *synt_tab,int id,int depth,int nb_levels){
+tree_t *build_synthetic_topology_old(int *synt_tab,int id,int depth,int nb_levels){
   tree_t *res,**child;
   int arity=synt_tab[0];
   int val,i; 
@@ -586,7 +588,7 @@ tree_t *build_synthetic_topology(int *synt_tab,int id,int depth,int nb_levels){
   else{
     child=(tree_t**)malloc(sizeof(tree_t*)*arity);
     for(i=0;i<arity;i++){
-      child[i]=build_synthetic_topology(synt_tab+1,i,depth+1,nb_levels);
+      child[i]=build_synthetic_topology_old(synt_tab+1,i,depth+1,nb_levels);
     child[i]->parent=res;
     val+=child[i]->val;
     }
@@ -596,6 +598,60 @@ tree_t *build_synthetic_topology(int *synt_tab,int id,int depth,int nb_levels){
 }
 
 
+void display_topology(tm_topology_t *topology){
+  int i,j;
+  for(i=0;i<topology->nb_levels;i++){
+    printf("%d: ",i);
+    for(j=0;j<topology->nb_nodes[i];j++)
+      printf("%d ",topology->node_id[i][j]);
+    printf("\n");
+  }
+}
+
+/* 
+   Build a synthetic balanced topology
+
+   arity : array of arity of the first nb_level (of size nb_levels-1)
+   core_numbering: numbering of the core by the system. Array of size nb_core_per_node
+
+   nb_core_per_nodes: number of cores of a given node
+
+   The numbering of the cores is done in round robin fashion after a width traversal of the topology
+ */
+
+tm_topology_t  *build_synthetic_topology(int *arity, int nb_levels, int *core_numbering, int nb_core_per_nodes){
+  tm_topology_t *topology;
+  int i,j,n=1;
+  
+  topology=(tm_topology_t*)malloc(sizeof(tm_topology_t));
+  topology->arity=(int*)malloc(sizeof(int)*nb_levels);
+  memcpy(topology->arity,arity,sizeof(int)*nb_levels);
+  topology->nb_levels=nb_levels;
+
+  topology->node_id=(int**)malloc(sizeof(int*)*topology->nb_levels);
+  topology->nb_nodes=(int*)malloc(sizeof(int)*topology->nb_levels);
+
+
+  for(i=0;i<topology->nb_levels;i++){
+    topology->nb_nodes[i]=n;
+    topology->node_id[i]=(int*)malloc(sizeof(int)*n);
+    if(i<topology->nb_levels-1){
+      for(j=0;j<n;j++)
+       topology->node_id[i][j]=j;
+    }else{
+      for(j=0;j<n;j++)
+       topology->node_id[i][j]=core_numbering[j%nb_core_per_nodes]+(nb_core_per_nodes)*(j/nb_core_per_nodes);
+    }
+
+    n*=topology->arity[i]; 
+  }
+  return topology;
+  
+}
+
+
+
+
 void   build_synthetic_proc_id(tm_topology_t *topology){
   int n=1,i,j;
   topology->node_id=(int**)malloc(sizeof(int*)*topology->nb_levels);
@@ -609,17 +665,49 @@ void   build_synthetic_proc_id(tm_topology_t *topology){
       topology->node_id[i][j]=j;
     n*=topology->arity[i]; 
   }
 
 }
 
-void TreeMatchMapping(int nb_obj, int nb_proc,double **comm_mat,  int *sol){
+void update_comm_speed(double **comm_speed,int old_size,int new_size){
+  double *old_tab,*new_tab;
+  int i;
+  printf("comm speed [%p]: ",*comm_speed);
+
+  old_tab=*comm_speed;
+  new_tab=(double*)malloc(sizeof(double)*new_size);
+  *comm_speed=new_tab;
+
+  for(i=0;i<new_size;i++){
+    if(i<old_size)
+      new_tab[i]=old_tab[i];
+    else
+      new_tab[i]=new_tab[i-1];
+
+    printf("%f ",new_tab[i]);
+  }
+  
+  printf("\n");
+}
+
+
+
+/* d: size of comm_speed */
+void TreeMatchMapping(int nb_obj, int nb_proc, double **comm_mat,  double *obj_weight, double * comm_speed, int d, int *sol){
   tree_t *comm_tree;
   tm_topology_t *topology;
+  double duration;
 
   int i;
-  for(i=0;i<nb_obj;i++)
+  TIC;
+  
+  for(i=0;i<nb_obj;i++){
     sol[i]=i;
-
+    //    printf("%f ",obj_weight[i]);
+  }
+  //printf("\n");
+  
 
   //  return;
 
@@ -630,6 +718,8 @@ void TreeMatchMapping(int nb_obj, int nb_proc,double **comm_mat,  int *sol){
   printf("Topology nb levels=%d\n",topology->nb_levels);
   build_synthetic_proc_id(topology);
 
+  if(topology->nb_levels>d)
+    update_comm_speed(&comm_speed,d,topology->nb_levels);
 
   //exit(-1);
   //topology_to_arch(topology);
@@ -641,13 +731,22 @@ void TreeMatchMapping(int nb_obj, int nb_proc,double **comm_mat,  int *sol){
 
   //display_tab(comm_mat,N);
 
-  comm_tree=build_tree_from_topology(topology,comm_mat,nb_obj);
+  TIC;
+  comm_tree=build_tree_from_topology(topology,comm_mat,nb_obj,obj_weight,comm_speed);
+  printf("Tree buildinbg time=%f\n",TOC);
+  TIC;
   map_topology(topology,comm_tree,nb_proc,1,sol,NULL);
+  printf("Topology mapping time=%f\n",TOC);
+
 
+  if(topology->nb_levels>d)
+    free(comm_speed);
 
   free_topology(topology);
   free_tree(comm_tree);
-  printf("-------------- Mapping done!\n");
+
+  duration=TOC;
+  printf("-------------- Mapping done in %.4fs!\n",duration);
 }
 
 void display_other_heuristics(tm_topology_t *topology,int N,double **comm,double **arch){