ompi/mca/topo/treematch/treematch/tm

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
compute_nb_leaves_from_level
tm_finalize
print_1D_tab
nb_lines
init_mat
get_filesize
parse_line
init_mat_mmap
init_mat_long
new_affinity_mat
tm_build_affinity_mat
tm_free_affinity_mat
tm_load_aff_mat
depth_first
nb_leaves
set_val
map_topology
tm_compute_mapping
update_comm_speed
fill_tab
   1 #include <fcntl.h>
   2 #include <sys/stat.h>
   3 #include <sys/mman.h>
   4 #include <sys/types.h>
   5 #include <unistd.h>
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9 #include <float.h>
  10 #include <ctype.h>
  11 #include <math.h>
  12 #include <assert.h>
  13 
  14 #include "tm_mt.h"
  15 #include "tm_mapping.h"
  16 #include "tm_timings.h"
  17 #include "tm_thread_pool.h"
  18 #include "tm_tree.h"
  19 
  20 #ifdef _WIN32
  21 #include <windows.h>
  22 #include <winbase.h>
  23 #endif
  24 
  25 #if defined(HAVE_LIBSCOTCH)
  26 #include <scotch.h>
  27 #endif  /* defined(HAVE_LIBSCOTCH) */
  28 
  29 #include <sys/mman.h>
  30 
  31 
  32 #define MIN(a,b) (a)<(b)?(a):(b)
  33 
  34 #define TEST_ERROR(n) do{ \
  35     if( (n) != 0 ){       \
  36        fprintf(stderr,"Error %d Line %d\n",n,__LINE__); \
  37        exit(-1);} \
  38   }while(0)
  39 
  40 #define LINE_SIZE (1000000)
  41 
  42 
  43 typedef struct {
  44   double val;
  45   int key1;
  46   int key2;
  47 } hash2_t;
  48 
  49 
  50 tm_affinity_mat_t * new_affinity_mat(double **mat, double *sum_row, int order, long int nnz);
  51 int compute_nb_leaves_from_level(int depth,tm_topology_t *topology);
  52 void depth_first(tm_tree_t *comm_tree, int *proc_list,int *i);
  53 int  fill_tab(int **new_tab,int *tab, int n, int start, int max_val, int shift);
  54 long int init_mat(char *filename,int N, double **mat, double *sum_row);
  55 void map_topology(tm_topology_t *topology,tm_tree_t *comm_tree, int level,
  56                   int *sigma, int nb_processes, int **k, int nb_compute_units);
  57 int nb_leaves(tm_tree_t *comm_tree);
  58 int nb_lines(char *filename);
  59 void print_1D_tab(int *tab,int N);
  60 tm_solution_t * tm_compute_mapping(tm_topology_t *topology,tm_tree_t *comm_tree);
  61 void tm_free_affinity_mat(tm_affinity_mat_t *aff_mat);
  62 tm_affinity_mat_t *tm_load_aff_mat(char *filename);
  63 void update_comm_speed(double **comm_speed,int old_size,int new_size);
  64 tm_affinity_mat_t * tm_build_affinity_mat(double **mat, int order);
  65 
  66 
  67 /* compute the number of leaves of any subtree starting froma node of depth depth*/
  68 int compute_nb_leaves_from_level(int depth,tm_topology_t *topology)
  69 {
  70   int res = 1;
  71 
  72   while(depth < topology->nb_levels-1)
  73     res *= topology->arity[depth++];
  74 
  75   return res;
  76 }
  77 
  78 void tm_finalize(){
  79   terminate_thread_pool();
  80   tm_mem_check();
  81 }
  82 
  83 
  84 
  85 void print_1D_tab(int *tab,int N)
  86 {
  87   int i;
  88   for (i = 0; i < N; i++) {
  89     printf("%d", tab[i]);
  90     if( i < (N-1) )
  91       printf(",");
  92   }
  93   printf("\n");
  94 }
  95 
  96 int nb_lines(char *filename)
  97 {
  98   FILE *pf = NULL;
  99   char line[LINE_SIZE];
 100   int N = 0;
 101 
 102   if(!(pf = fopen(filename,"r"))){
 103     if(tm_get_verbose_level() >= CRITICAL)
 104       fprintf(stderr,"Cannot open %s\n",filename);
 105     exit(-1);
 106   }
 107 
 108   while(fgets(line,LINE_SIZE,pf))
 109     N++;
 110 
 111   if(tm_get_verbose_level() >= DEBUG)
 112     printf("Number of lines of file %s = %d\n",filename,N);
 113 
 114   fclose(pf);
 115   return N;
 116 }
 117 
 118 
 119 
 120 long int  init_mat(char *filename,int N, double **mat, double *sum_row){
 121   FILE *pf = NULL;
 122   char *ptr= NULL;
 123   char line[LINE_SIZE];
 124   int i,j;
 125   unsigned int vl = tm_get_verbose_level();
 126   long int nnz = 0;
 127 
 128   if(!(pf=fopen(filename,"r"))){
 129     if(vl >= CRITICAL)
 130       fprintf(stderr,"Cannot open %s\n",filename);
 131     exit(-1);
 132   }
 133 
 134   j = -1;
 135   i = 0;
 136 
 137   while(fgets(line,LINE_SIZE,pf)){
 138     char *l = line;
 139     j = 0;
 140     sum_row[i] = 0;
 141     while((ptr=strtok(l," \t"))){
 142       l = NULL;
 143       if((ptr[0]!='\n')&&(!isspace(ptr[0]))&&(*ptr)){
 144         mat[i][j] = atof(ptr);
 145         if(mat[i][j]) nnz++;
 146         sum_row[i] += mat [i][j];
 147         if(mat[i][j]<0){
 148           if(vl >= WARNING)
 149             fprintf(stderr,"Warning: negative value in com matrix! mat[%d][%d]=%f\n",i,j,mat[i][j]);
 150         }
 151         j++;
 152       }
 153     }
 154     if( j != N){
 155       if(vl >= CRITICAL)
 156         fprintf(stderr,"Error at %d %d (%d!=%d). Too many columns for %s\n",i,j,j,N,filename);
 157       exit(-1);
 158     }
 159     i++;
 160   }
 161 
 162 
 163   if( i != N ){
 164     if(vl >= CRITICAL)
 165       fprintf(stderr,"Error at %d %d. Too many rows for %s\n",i,j,filename);
 166     exit(-1);
 167   }
 168 
 169   fclose (pf);
 170   return nnz;
 171 }
 172 
 173 
 174 static size_t get_filesize(char* filename) {
 175     struct stat st;
 176     stat(filename, &st);
 177     return st.st_size;
 178 }
 179 
 180 
 181 static char *parse_line(int i, double **mat, double *sum_row, int N, char *data, char *filename, long int *nnz){
 182   /* now parse the buffer byte per byte for the current line i until we reach '\n'*/
 183   unsigned int vl = tm_get_verbose_level();
 184   long val;
 185   sum_row[i] = 0;
 186   int j = 0;
 187   while(*data != '\n'){
 188     while(*data ==' ' || *data == '\t')
 189       data++;
 190     if(*data != '\n'){
 191       val = 0;
 192       while(*data !=' ' && *data != '\t' && *data != '\n'){
 193         val = val*10 + *data-'0';
 194         data++;
 195       }
 196       mat[i][j] = val;
 197       /* printf("mat[%d][%d] = %ld\n",i,j, val); */
 198       if (val){
 199         (*nnz)++; 
 200         sum_row[i] += val;
 201       }
 202       j++;
 203     }
 204   }
 205   if( j != N){
 206     if(vl >= CRITICAL)
 207       fprintf(stderr,"Error at %d %d (%d!=%d). Wrong number of columns line %d for file %s\n",i ,j ,j ,N ,i+1, filename);
 208     exit(-1);
 209   }
 210   data++;
 211   return data;
 212 }
 213 
 214 
 215 
 216 /* buffered read with mmap of teh file */
 217 static long int init_mat_mmap(char *filename,int N, double **mat, double *sum_row){
 218   int i;
 219   unsigned int vl = tm_get_verbose_level();
 220   size_t filesize = get_filesize(filename);
 221   int fd = open(filename, O_RDONLY, 0);
 222   long int nnz = 0;
 223 
 224   if(fd == -1){
 225     if(vl >= CRITICAL)
 226       fprintf(stderr,"Cannot open %s\n",filename);
 227     exit(-1);
 228   }
 229 
 230   char* data = (char*) mmap(NULL, filesize, PROT_READ, MAP_SHARED, fd, 0);
 231   
 232   if(data == MAP_FAILED){
 233     if(vl >= CRITICAL)
 234       fprintf(stderr,"Cannot mmap %s\n",filename);
 235     exit(-1);
 236   }
 237    
 238   i = 0;
 239   while(i<N){
 240     data = parse_line(i, mat, sum_row, N, data, filename, &nnz);
 241     i++;
 242   }
 243 
 244   munmap(data, filesize);
 245   /* fprintf(stderr,"DONE!\n"); */
 246   close (fd);
 247   return nnz;
 248 }
 249 
 250 
 251 
 252 
 253 static long int init_mat_long(char *filename,int N, double **mat, double *sum_row){
 254   int i;
 255   unsigned int vl = tm_get_verbose_level();
 256   char line[LINE_SIZE];
 257   FILE *pf;
 258   long int nnz = 0;
 259   
 260   if(!(pf=fopen(filename,"r"))){
 261     if(vl >= CRITICAL)
 262       fprintf(stderr,"Cannot open %s\n",filename);
 263     exit(-1);
 264   }
 265 
 266   i = 0;
 267   while(i<N){
 268     fgets(line,LINE_SIZE,pf);    
 269     parse_line(i, mat, sum_row, N, line, filename, &nnz);
 270     i++;
 271   }
 272 
 273 
 274   /* fprintf(stderr,"DONE!\n"); */
 275   fclose (pf);
 276   return nnz;
 277 }
 278 
 279 
 280 tm_affinity_mat_t * new_affinity_mat(double **mat, double *sum_row, int order, long int nnz){
 281   tm_affinity_mat_t * aff_mat;
 282 
 283   aff_mat = (tm_affinity_mat_t *) MALLOC(sizeof(tm_affinity_mat_t));
 284   aff_mat -> mat     = mat;
 285   aff_mat -> sum_row = sum_row;
 286   aff_mat -> order   = order;
 287   aff_mat -> nnz      = nnz;
 288 
 289   return aff_mat;
 290 }
 291 
 292 
 293 tm_affinity_mat_t * tm_build_affinity_mat(double **mat, int order){
 294   double *sum_row = NULL;
 295   int i,j;
 296   long int nnz = 0;
 297   sum_row = (double*)MALLOC(order*sizeof(double));
 298 
 299   for( i = 0 ; i < order ; i++){
 300     sum_row[i] = 0;
 301     for(j = 0 ; j < order ; j++){
 302       if(mat[i][j]){
 303         nnz++;
 304         sum_row[i] += mat [i][j];
 305       }
 306     }
 307   }
 308 
 309   return new_affinity_mat(mat, sum_row, order, nnz);
 310 }
 311 
 312 
 313 
 314 
 315 
 316 void tm_free_affinity_mat(tm_affinity_mat_t *aff_mat){
 317   int i;
 318   int n = aff_mat->order;
 319 
 320   for(i = 0 ; i < n ; i++)
 321     FREE(aff_mat->mat[i]);
 322 
 323   FREE(aff_mat->mat);
 324   FREE(aff_mat->sum_row);
 325   FREE(aff_mat);
 326 }
 327 
 328 
 329 tm_affinity_mat_t *tm_load_aff_mat(char *filename)
 330 {
 331   double **mat = NULL;
 332   double *sum_row = NULL;
 333   int i, order;
 334   long int nnz;
 335   
 336   if(tm_get_verbose_level() >= INFO)
 337     printf("Reading matrix file: %s\n",filename);
 338 
 339   order = nb_lines(filename);
 340 
 341   sum_row = (double*)MALLOC(order*sizeof(double));
 342   mat = (double**)MALLOC(order*sizeof(double*));
 343   for( i = 0 ; i < order ; i++)
 344     /* the last column stores the sum of the line*/
 345     mat[i] = (double*)MALLOC((order)*sizeof(double));
 346   /* on my mac  parsing large file is better done with fopen than mmap */
 347   #ifdef __MACH__ 
 348   if (get_filesize(filename) > 1024*1024*1014) {
 349     nnz = init_mat_long(filename,order, mat, sum_row); 
 350     if(tm_get_verbose_level() >= DEBUG)
 351       printf("New parser\n");
 352   }else{
 353     nnz = init_mat_mmap(filename,order, mat, sum_row);
 354     if(tm_get_verbose_level() >= DEBUG)
 355       printf("MMap parser\n");
 356   }
 357   #else
 358     nnz = init_mat_mmap(filename,order, mat, sum_row); 
 359     if(tm_get_verbose_level() >= DEBUG)
 360       printf("MMap parser\n");
 361  #endif
 362   
 363   /* TIC; */
 364   /* init_mat(filename,order, mat, sum_row); */
 365   /* double duration_fl = TOC; */
 366   /* printf("Old parser = %.3f\n",duration_fl); */
 367 
 368 
 369 
 370     if(tm_get_verbose_level() >= INFO)
 371     printf("Affinity matrix built from %s!\n",filename);
 372 
 373     return new_affinity_mat(mat, sum_row, order, nnz);
 374 
 375 
 376 }
 377 
 378 
 379 
 380 
 381 
 382 /* void map_tree(tm_tree_t* t1,tm_tree_t *t2) */
 383 /* { */
 384   /*  double x1,x2;
 385   if((!t1->left)&&(!t1->right)){
 386     printf ("%d -> %d\n",t1->id,t2->id);
 387     sigma[t2->id]=t1->id;
 388    return;
 389   }
 390   x1=t2->right->val/t1->right->val+t2->left->val/t1->left->val;
 391   x2=t2->left->val/t1->right->val+t2->right->val/t1->left->val;
 392   if(x1<x2){
 393     map_tree(t1->left,t2->left);
 394     map_tree(t1->right,t2->right);
 395   }else{
 396     map_tree(t1->right,t2->left);
 397     map_tree(t1->left,t2->right);
 398     }*/
 399 /* } */
 400 
 401 void depth_first(tm_tree_t *comm_tree, int *proc_list,int *i)
 402 {
 403   int j;
 404   if(!comm_tree->child){
 405     proc_list[(*i)++] = comm_tree->id;
 406     return;
 407   }
 408 
 409   for( j  = 0 ; j < comm_tree->arity ; j++ )
 410     depth_first(comm_tree->child[j],proc_list,i);
 411 }
 412 
 413 int nb_leaves(tm_tree_t *comm_tree)
 414 {
 415   int j,n=0;
 416 
 417   if(!comm_tree->child)
 418     return 1;
 419 
 420   for( j = 0 ; j < comm_tree->arity ; j++)
 421     n += nb_leaves(comm_tree->child[j]);
 422 
 423   return n;
 424 }
 425 
 426 /* find the first '-1 in the array of size n and put the value there*/
 427 static void set_val(int *tab, int val, int n){
 428   int i = 0;
 429 
 430   while (i < n ){
 431     if(tab[i] ==- 1){
 432       tab[i] = val;
 433       return;
 434     }
 435     i++;
 436   }
 437 
 438   if(tm_get_verbose_level() >= CRITICAL){
 439     fprintf(stderr,"Error while assigning value %d to k\n",val);
 440   }
 441 
 442   exit(-1);
 443 
 444 }
 445 /*Map topology to cores:
 446  sigma_i is such that  process i is mapped on core sigma_i
 447  k_i is such that core i exectutes process k_i
 448 
 449  size of sigma is the number of process "nb_processes"
 450  size of k is the number of cores/nodes "nb_compute_units"
 451 
 452  We must have numbe of process<=number of cores
 453 
 454  k_i =-1 if no process is mapped on core i
 455 */
 456 
 457 void map_topology(tm_topology_t *topology,tm_tree_t *comm_tree, int level,
 458                   int *sigma, int nb_processes, int **k, int nb_compute_units)
 459 {
 460   int *nodes_id = NULL;
 461   int *proc_list = NULL;
 462   int i,j,N,M,block_size;
 463 
 464   unsigned int vl = tm_get_verbose_level();
 465   M = nb_leaves(comm_tree);
 466   nodes_id = topology->node_id;
 467   N = topology->nb_nodes[level];
 468 
 469   if(vl >= INFO){
 470     printf("nb_leaves=%d\n",M);
 471     printf("level=%d, nodes_id=%p, N=%d\n",level,(void *)nodes_id,N);
 472     printf("N=%d,nb_compute_units=%d\n",N,nb_compute_units);
 473   }
 474 
 475   /* The number of node at level "level" in the tree should be equal to the number of processors*/
 476   assert(N==nb_compute_units*topology->oversub_fact);
 477 
 478   proc_list = (int*)MALLOC(sizeof(int)*M);
 479   i = 0;
 480   depth_first(comm_tree,proc_list,&i);
 481 
 482   block_size = M/N;
 483 
 484   if(k){/*if we need the k vector*/
 485     if(vl >= INFO)
 486       printf("M=%d, N=%d, BS=%d\n",M,N,block_size);
 487     for( i = 0 ; i < nb_processing_units(topology) ; i++ )
 488       for(j = 0 ; j < topology->oversub_fact ; j++){
 489         k[i][j] = -1;
 490     }
 491 
 492     for( i = 0 ; i < M ; i++ )
 493       if(proc_list[i] != -1){
 494         if(vl >= DEBUG)
 495           printf ("%d->%d\n",proc_list[i],nodes_id[i/block_size]);
 496 
 497         if( proc_list[i] < nb_processes ){
 498           sigma[proc_list[i]] = nodes_id[i/block_size];
 499           set_val(k[nodes_id[i/block_size]], proc_list[i], topology->oversub_fact);
 500         }
 501       }
 502   }else{
 503     if(vl >= INFO)
 504       printf("M=%d, N=%d, BS=%d\n",M,N,block_size);
 505     for( i = 0 ; i < M ; i++ )
 506       if(proc_list[i] != -1){
 507         if(vl >= DEBUG)
 508           printf ("%d->%d\n",proc_list[i],nodes_id[i/block_size]);
 509         if( proc_list[i] < nb_processes )
 510           sigma[proc_list[i]] = nodes_id[i/block_size];
 511       }
 512   }
 513 
 514   if((vl >= DEBUG) && (k)){
 515     printf("k: ");
 516     for( i = 0 ; i < nb_processing_units(topology) ; i++ ){
 517       printf("Procesing unit %d: ",i);
 518       for (j = 0 ; j<topology->oversub_fact; j++){
 519         if( k[i][j] == -1)
 520           break;
 521         printf("%d ",k[i][j]);
 522       }
 523       printf("\n");
 524     }
 525   }
 526 
 527   FREE(proc_list);
 528 }
 529 
 530 tm_solution_t * tm_compute_mapping(tm_topology_t *topology,tm_tree_t *comm_tree)
 531 {
 532   size_t i;
 533   tm_solution_t *solution;
 534   int *sigma, **k;
 535   size_t sigma_length  = comm_tree->nb_processes;
 536   size_t k_length      = nb_processing_units(topology);
 537 
 538   solution =  (tm_solution_t *)MALLOC(sizeof(tm_solution_t));
 539   sigma    =  (int*)  MALLOC(sizeof(int) * sigma_length);
 540   k        =  (int**) MALLOC(sizeof(int*) * k_length);
 541   for (i=0 ; i < k_length ; i++){
 542     k[i] =  (int*) MALLOC(sizeof(int) * topology->oversub_fact);
 543   }
 544 
 545   map_topology(topology, comm_tree, topology->nb_levels-1, sigma, sigma_length ,k, k_length);
 546 
 547   solution->sigma         = sigma;
 548   solution->sigma_length  = sigma_length;
 549   solution->k             = k;
 550   solution->k_length      = k_length;
 551   solution->oversub_fact  = topology->oversub_fact;
 552 
 553   return solution;
 554 }
 555 
 556 
 557 
 558 void update_comm_speed(double **comm_speed,int old_size,int new_size)
 559 {
 560   double *old_tab = NULL,*new_tab= NULL;
 561   int i;
 562   unsigned int vl = tm_get_verbose_level();
 563 
 564   if(vl >= DEBUG)
 565     printf("comm speed [%p]: ",(void *)*comm_speed);
 566 
 567   old_tab = *comm_speed;
 568   new_tab = (double*)MALLOC(sizeof(double)*new_size);
 569   *comm_speed = new_tab;
 570 
 571   for( i = 0 ; i < new_size ; i++ ){
 572     if( i < old_size)
 573       new_tab[i] = old_tab[i];
 574     else
 575       new_tab[i] = new_tab[i-1];
 576 
 577     if(vl >= DEBUG)
 578       printf("%f ",new_tab[i]);
 579   }
 580   if(vl >= DEBUG)
 581     printf("\n");
 582 }
 583 
 584 
 585 
 586 
 587 
 588 
 589 /*
 590    copy element of tab in *new_tab from start to end and shift negativeley them
 591    allocates *new_tab
 592 */
 593 int  fill_tab(int **new_tab,int *tab, int n, int start, int max_val, int shift)
 594 {
 595   int *res = NULL,i,j,end;
 596 
 597   if(!n){
 598     *new_tab = NULL;
 599     return 0;
 600   }
 601   end = start;
 602 
 603   /* find how many cell to copy*/
 604   while( end < n ){
 605     if(tab[end] >= max_val)
 606       break;
 607     end++;
 608   }
 609 
 610   /* if none return */
 611   if( start == end ){
 612     *new_tab = NULL;
 613     return end;
 614   }
 615 
 616   /* allocate the result*/
 617   res = (int*) MALLOC (sizeof(int)*(end-start));
 618 
 619   /* copy and shift*/
 620   j = 0;
 621   for( i = start ; i < end ; i++ ){
 622     res[j] = tab[i] - shift;
 623     j++;
 624   }
 625 
 626   /* set the pointer passed in parameter and return */
 627   *new_tab = res;
 628   return end;
 629 }
/* [<][>][^][v][top][bottom][index][help] */
root/ompi/mca/topo/treematch/treematch/tm_mapping.c

DEFINITIONS
