gs_smart_mapping_heuristics.c

Go to the documentation of this file.

#include "config.h"

#ifdef GS_SMART_GRIDSOLVE
#include <math.h>
#include "gs_smart_task_graph.h"
#include "gs_smart_mapping_graph.h"
#include "gs_smart_mapping_heuristics.h"
#include "gs_smart_mapping_matrix_func.h"

/*
 * The list of names of implemented mapping heuristics
 */

static int nb_mappers=5;
static char mapping_names[5][15] ={"ex_map", "basic_map", "random_map", "rwalk_map", "greedy_map"};

double
total_time(const struct timeval*, const struct timeval*);


/*
 * The name of the mapping heuristic called
 */
static char * mapper_type;


/*
 *  This function invokes the called mapping heuristic
 *  @param tg - (in) Task graph of a the mapped group of tasks
 *  @param netpm -- (in) Network performance model
 *  @param best_mg -- (out) Mapping solution generated by the mapping heuristic 
 *  @param mapper_num -- (in) The position of mapping solution to invoke in mapping_names array.
 */

int gs_smart_exec_mapper(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg, int mapper_num){
  LOGPRINTF("Mapping group of tasks with mapping heuristic %s\n", mapping_names[mapper_num]);
   gs_smart_mg * best_mg;
  if(mapper_num==0){
    if(gs_smart_ex_map(tg, netpm, &best_mg)<0){
        ERRPRINTF("SMART : Error performing exhaustive mapping heuristic\n");
        return -1;
    }
  }
  else if(mapper_num==1){
    if(gs_smart_basic_map(tg, netpm, &best_mg)<0){
        ERRPRINTF("SMART : Error performing basic mapping heuristic\n");
        return -1;
    }
  }
  else if(mapper_num==2){
    if(gs_smart_random_map(tg, netpm, &best_mg)<0){
        ERRPRINTF("SMART : Error performing random mapping heuristic\n");
        return -1;
    }
  }
  else if(mapper_num==3){
    if(gs_smart_rwalk_map(tg, netpm, &best_mg)<0){
        ERRPRINTF("SMART : Error performing random walk mapping heuristic\n");
        return -1;
    }
  }
  else if(mapper_num==4){
    if(gs_smart_greedy_map(tg, netpm, &best_mg)<0){
        ERRPRINTF("SMART : Error performing random walk mapping heuristic\n");
        return -1;
    }
  }
  *_best_mg=best_mg;
  return 0;
}







/*
 *  The exhaustive search mapping heuristic is an iterative mapping 
 *  heuristic.
 *  This mapping heuristic iterates through every possible mapping 
 *  solution and returns the mapping solution with fastest time.
 *
 *  This heuristic can be time-consuming when there are a large 
 *  number of solutions.  The number of solutions for a given 
 *  set of tasks and server is equal to num_server to the power
 *  of num_tasks, which can be a significant number.
 *  This can be expensive as it roughly takes one second to time 
 *  10,000 solutions.
 *
 *  @param tg - (in) Task graph of a the mapped group of tasks
 *  @param netpm -- (in) Network performance model
 *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
 *
 */



int gs_smart_ex_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){

  gs_smart_mg * this_mg;
  gs_smart_mg * best_mg=NULL;
  int ** mapping_matrix;
  int * mapping_vec;  
  int nb_rem_tasks, nb_servers;
  int i, j;
  int total_permutations, this_per;
  double best_time=0.0;
  double this_time=0.0;
  struct timeval t1, t2;
  double et;
  if(tg->nb_rem_nodes<=0){
    ERRPRINTF("SMART: Error doing exhaustive search, no remote nodes\n");
    return -1;
  }

  nb_servers=netpm->nb_nodes;
  nb_rem_tasks=tg->nb_rem_nodes;
  mapping_matrix = (int **)calloc( nb_servers, sizeof(int *));

  if(!mapping_matrix) return -1;
  
  for (i = 0; i <nb_servers; i++) {
    mapping_matrix[i] = (int *)calloc(nb_rem_tasks, sizeof(int));
    if(!mapping_matrix[i]) return -1;
  }

  for( i = 0; i < nb_servers; i++){
    for( j = 0; j < nb_rem_tasks; j++){
      mapping_matrix[i][j] = 0;
    }
  }

  mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
  if(!mapping_vec){
    ERRPRINTF("SMART: Error allocating to mapping vector\n");
    return -1;
  } 

  total_permutations=(int)(pow((double)nb_servers,(double)nb_rem_tasks));


  int num_valid_graphs=0;
  gettimeofday(&t1, 0);
 
  for(this_per=0;this_per<total_permutations;this_per++){
    this_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
    if(gs_smart_zero_mapping_matrix(mapping_matrix, nb_servers, nb_rem_tasks)<0){
      ERRPRINTF("SMART: Error resetting mapping matrix on mapping solution %d\n", this_per);
      return -1;
    }

    
    if(gs_smart_next_permutation(mapping_matrix, this_per, nb_servers, nb_rem_tasks)<0){
      ERRPRINTF("SMART: Error shifting matrix to next permuation on mapping solution %d\n", this_per);
      return -1;
    }
    if(gs_smart_matrix_to_vec(mapping_matrix, nb_servers, nb_rem_tasks, mapping_vec)<0){
      ERRPRINTF("SMART: Error converting mapping matrix to a vector\n");
      return -1;
    }
    int valid_graph;
    if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, this_mg, &valid_graph)<0){
      ERRPRINTF("SMART: Error generating mapping graph\n");
      return -1;
    }

   this_time=this_mg->total_time;
    if(valid_graph){ 
      if(num_valid_graphs==0){
        best_time=this_time;
        best_mg=this_mg;
      }
      else{
        if(this_time<best_time){
          best_time=this_time;
          if(gs_smart_free_mg(best_mg)<0){
            ERRPRINTF("SMART : Error freeing mapping graph\n");
            return -1;
          }
          best_mg=this_mg;
        }
        else{
          if(gs_smart_free_mg(this_mg)<0){
            ERRPRINTF("SMART : Error freeing mapping graph\n");
            return -1;
          }
        }

      }
      num_valid_graphs++;
     }
  }
  if(num_valid_graphs==0){
    ERRPRINTF("SMART : No mapping solutions found for this group of tasks\n");
    return -1;

  }
  if(gs_smart_mg_create_argument_file_names(best_mg)<0){
    ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
    return -1;
  }
  gettimeofday(&t2, 0);
  et = total_time(&t1,&t2);
  
  LOGPRINTF("It took exhaustive mapper %g seconds to generate mapping solution from %d solutions\n", et, total_permutations);
  *_best_mg=best_mg;
  return 0;
}







/*
 *  The basic mapping heuristic is a non-iterative mapping heuristic.
 *  It maps each task one at a time. It finds the fastest smart enabled
 *  server that can execute each task.  When a nonblocking task gets 
 *  assigned to a server, the server's workload is increased. 
 *  This provides a basic method for load balancing non-blocking tasks.
 *  If there are no smart servers that can execute a specific task
 *  then this task will be assigned a server that is not smart enabled.
 *  Once the tasks have been assigned to servers, the mapping graph is
 *  generated with the best communication scheme, based on the dependencies
 *  between tasks and whether the servers assigned are smart servers or not.
 *
 *  This is a basic heuristic which generates a mapping solution quickly 
 *  and provides speed up due to direct communication between servers.
 *  However since it maps tasks individually it does not fully exploit the 
 *  potential of mapping tasks collectively such as improved load balancing
 *  of computation.
 *
 *  @param tg - (in) Task graph of a the mapped group of tasks
 *  @param netpm -- (in) Network performance model
 *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
 *
 */

int gs_smart_basic_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){
  gs_smart_mg * best_mg;
  gs_smart_tg_task_node * task_node;
  gs_smart_tg_remote_task_node * tg_rem_task_node;
  gs_server_t * server;
  int * mapping_vec;  
  int i, j, nb_rem_tasks, rem_task_cnt;
  int nbl_task_called;
  double this_time, best_time;
  int valid_assignment;
  int found_mapping;
  int nb_valid_mappings_timed;
  int valid_graph;
  int best_server_id=0;
  nb_rem_tasks=tg->nb_rem_nodes;
  best_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
  mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
 
  rem_task_cnt=0;
  nbl_task_called=0;
  for(i=0;i<tg->nb_nodes;i++){
    task_node=tg->task_nodes[i];
    if(task_node->node_type==GS_SMART_TG_REM_TASK_NODE){
      tg_rem_task_node=task_node->tg_rem_task_node;

      nb_valid_mappings_timed=0;
      best_time=0.0;
      /*
       * find fastest smart server
       */
      for(j=0;j<netpm->nb_nodes;j++){
        server=netpm->netpm_nodes[j]->server;
        if(server->smart){
          if(gs_smart_check_if_valid_assignment(tg_rem_task_node,
                                   server, &valid_assignment)<0){
            ERRPRINTF("SMART : Error checking if a valid assignment\n");
            return -1;
          }
          
          if((valid_assignment) && (nb_valid_mappings_timed==0)){
              best_server_id=j;
              if(gs_smart_time_tg_task_node(tg_rem_task_node, server, &best_time)<0){
                ERRPRINTF("SMART : Error timing task graph task node\n");
                return -1;
              }
              nb_valid_mappings_timed++;
            }
            else if ((valid_assignment) && (nb_valid_mappings_timed>0)){
              if(gs_smart_time_tg_task_node(tg_rem_task_node, server, &this_time)<0){
                ERRPRINTF("SMART : Error timing task graph task node\n");
                return -1;
              }
              if(this_time<best_time){
                best_server_id=j;
                best_time=this_time;
              }
              nb_valid_mappings_timed++;
            }
            
          } 
        }
        
       /*
        * if no smart servers find fastest standard server
        */

        if(nb_valid_mappings_timed==0){
          found_mapping=0;
            for(j=0;j<netpm->nb_nodes;j++){
              server=netpm->netpm_nodes[j]->server;
              if(!server->smart){
                if(gs_smart_check_if_valid_assignment(tg_rem_task_node,
                                     server, &valid_assignment)<0){
                  ERRPRINTF("SMART : Error checking if a valid assignment\n");
                  return -1;
                }
                if((valid_assignment) && (nb_valid_mappings_timed==0)){
                  best_server_id=j;
                  if(gs_smart_time_tg_task_node(tg_rem_task_node, server, &best_time)<0){
                    ERRPRINTF("SMART : Error timing task graph task node\n");
                    return -1;
                  }
                  nb_valid_mappings_timed++;
                }
                else if ((valid_assignment) && (nb_valid_mappings_timed>0)){
                  if(gs_smart_time_tg_task_node(tg_rem_task_node, server, &this_time)<0){
                    ERRPRINTF("SMART : Error timing task graph task node\n");
                    return -1;
                  }
                  if(this_time<best_time){
                    best_server_id=j;
                    best_time=this_time;
                  }
                  nb_valid_mappings_timed++;
                }
              } 
            }
        } 
        if(nb_valid_mappings_timed==0){
          ERRPRINTF("SMART: Error no valid mappings found for task %d %s\n", i, tg_rem_task_node->problem->name);
          return -1;
        }


        /*
         * if its a blocking task reset the task workloads of all the servers
         */ 
        
        if(tg_rem_task_node->blocking==1){ 
          for(j=0;j<netpm->nb_nodes;j++){
            netpm->netpm_nodes[j]->server->task_workload=0;
          }
        }
        /*
         * if its a non-blocking task bump up the task workload of assigned server
         */ 
        else if(tg_rem_task_node->blocking==0){
          netpm->netpm_nodes[best_server_id]->server->task_workload =(server->task_workload+ (10000*best_time));
        }

      
      mapping_vec[rem_task_cnt]=best_server_id; 
      rem_task_cnt++;
    }

  }
  
  if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, best_mg, &valid_graph)<0){
    ERRPRINTF("SMART: Error generating mapping graph\n");
    return -1;
  }
  if(gs_smart_mg_create_argument_file_names(best_mg)<0){
    ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
    return -1;
  }


  if(!valid_graph){
    ERRPRINTF("SMART : The mapping graph generated is invalid!\n");
    return -1;
  }
  *_best_mg=best_mg;
  return 0;
}







/*
 *  This mapping heuristic randomly traverses the solution space and
 *  returns the fastest solution within that solution space.
 *  The number of solutions timed is max_solutions.
 *
 *  @param tg - (in) Task graph of a the mapped group of tasks
 *  @param netpm -- (in) Network performance model
 *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
 *
 */





int gs_smart_rwalk_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){

  gs_smart_mg * this_mg;
  gs_smart_mg * best_mg=NULL;
  int ** mapping_matrix;
  int * mapping_vec;  
  int nb_rem_tasks, nb_servers;
  int i, j;
  int total_permutations;
  double best_time=0.0;
  double this_time=0.0;
  int solution_num;
  int max_solutions=10000;
  int valid_graph=0;
  int sol_num=0;
  int num_valid_graphs=0;
  struct timeval t1, t2;
  double et;
  if(tg->nb_rem_nodes<=0){
    ERRPRINTF("SMART: Error doing exhaustive search, no remote nodes\n");
    return -1;
  }

  nb_servers=netpm->nb_nodes;
  nb_rem_tasks=tg->nb_rem_nodes;
  mapping_matrix = (int **)calloc( nb_servers, sizeof(int *));

  if(!mapping_matrix) return -1;
  
  for (i = 0; i <nb_servers; i++) {
    mapping_matrix[i] = (int *)calloc(nb_rem_tasks, sizeof(int));
    if(!mapping_matrix[i]) return -1;
  }

  for( i = 0; i < nb_servers; i++){
    for( j = 0; j < nb_rem_tasks; j++){
      mapping_matrix[i][j] = 0;
    }
  }

  mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
  if(!mapping_vec){
    ERRPRINTF("SMART: Error allocating to mapping vector\n");
    return -1;
  } 

  total_permutations=(int)(pow((double)nb_servers,(double)nb_rem_tasks));

  LOGPRINTF("Total number of possible solutions %d\n", total_permutations);
  LOGPRINTF("Number of solutions timed =  %d\n", max_solutions);
  num_valid_graphs=0;
  gettimeofday(&t1, 0);
  while((sol_num<max_solutions) && (sol_num<total_permutations)){
    this_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
    srand((unsigned)time(0)); 
    solution_num=(rand()%total_permutations);
    if(gs_smart_zero_mapping_matrix(mapping_matrix, nb_servers, nb_rem_tasks)<0){
      ERRPRINTF("SMART: Error resetting mapping matrix on mapping solution\n");
      return -1;
    }
    if(gs_smart_next_permutation(mapping_matrix, solution_num, nb_servers, nb_rem_tasks)<0){
      ERRPRINTF("SMART: Error shifting matrix to next permuation on mapping solution\n");
      return -1;
    }
    if(gs_smart_matrix_to_vec(mapping_matrix, nb_servers, nb_rem_tasks, mapping_vec)<0){
      ERRPRINTF("SMART: Error converting mapping matrix to a vector\n");
      return -1;
    }
    if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, this_mg, &valid_graph)<0){
      ERRPRINTF("SMART: Error generating mapping graph\n");
      return -1;
    }
    if(!valid_graph){
      if(gs_smart_free_mg(this_mg)<0){
        ERRPRINTF("SMART : Error freeing mapping graph\n");
        return -1;
      }
    }
    else{

      this_time=this_mg->total_time;
      if(valid_graph){ 
        if(num_valid_graphs==0){
          best_time=this_time;
          best_mg=this_mg;
        }
        else{
          if(this_time<best_time){
            best_time=this_time;
            if(gs_smart_free_mg(best_mg)<0){
              ERRPRINTF("SMART : Error freeing mapping graph\n");
              return -1;
            }
            best_mg=this_mg;
          }
          
          else{
            if(gs_smart_free_mg(this_mg)<0){
              ERRPRINTF("SMART : Error freeing mapping graph\n");
              return -1;
            }
          }
        }
        num_valid_graphs++;
       }
     }
    sol_num++;
  }
  if(num_valid_graphs==0){
    ERRPRINTF("SMART: Could not find a valid graph\n");
    return -1;
  }
  if(gs_smart_mg_create_argument_file_names(best_mg)<0){
    ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
    return -1;
  }
  gettimeofday(&t2, 0);
  et = total_time(&t1,&t2);
  
  LOGPRINTF("It took random walk mapper %g seconds to generate mapping solution\n", et);
 

  *_best_mg=best_mg;

  return 0;

}








/*
 *  This mapping heuristic is a non-iterative heuristic.
 *  It randomly chooses one solution. This mapping solution
 *  should only be used for testing.
 *
 *  @param tg - (in) Task graph of a the mapped group of tasks
 *  @param netpm -- (in) Network performance model
 *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
 *
 */



int gs_smart_random_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){

  gs_smart_mg * this_mg;
  gs_smart_mg * best_mg=NULL;
  int ** mapping_matrix;
  int * mapping_vec;  
  int nb_rem_tasks, nb_servers;
  int i, j;
  int total_permutations;
  int solution_num;
  int max_solutions=10000;
  int valid_graph=0;
  int sol_num=0;

  this_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
  if(tg->nb_rem_nodes<=0){
    ERRPRINTF("SMART: Error doing exhaustive search, no remote nodes\n");
    return -1;
  }

  nb_servers=netpm->nb_nodes;
  nb_rem_tasks=tg->nb_rem_nodes;
  mapping_matrix = (int **)calloc( nb_servers, sizeof(int *));

  if(!mapping_matrix) return -1;
  
  for (i = 0; i <nb_servers; i++) {
    mapping_matrix[i] = (int *)calloc(nb_rem_tasks, sizeof(int));
    if(!mapping_matrix[i]) return -1;
  }

  for( i = 0; i < nb_servers; i++){
    for( j = 0; j < nb_rem_tasks; j++){
      mapping_matrix[i][j] = 0;
    }
  }

  mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
  if(!mapping_vec){
    ERRPRINTF("SMART: Error allocating to mapping vector\n");
    return -1;
  } 

  total_permutations=(int)(pow((double)nb_servers,(double)nb_rem_tasks));

  while((!valid_graph) && (sol_num<max_solutions)){
    srand((unsigned)time(0)); 
    solution_num=(rand()%total_permutations);
    if(gs_smart_zero_mapping_matrix(mapping_matrix, nb_servers, nb_rem_tasks)<0){
      ERRPRINTF("SMART: Error resetting mapping matrix on mapping solution\n");
      return -1;
    }
    if(gs_smart_next_permutation(mapping_matrix, solution_num, nb_servers, nb_rem_tasks)<0){
      ERRPRINTF("SMART: Error shifting matrix to next permuation on mapping solution\n");
      return -1;
    }
    if(gs_smart_matrix_to_vec(mapping_matrix, nb_servers, nb_rem_tasks, mapping_vec)<0){
      ERRPRINTF("SMART: Error converting mapping matrix to a vector\n");
      return -1;
    }
    if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, this_mg, &valid_graph)<0){
      ERRPRINTF("SMART: Error generating mapping graph\n");
      return -1;
    }
    if(!valid_graph){
/*
      if(gs_smart_free_mg(this_mg)<0){
        ERRPRINTF("SMART : Error freeing mapping graph\n");
        return -1;
      }
*/
    }
    sol_num++;
  }
  if(!valid_graph){
    ERRPRINTF("SMART: Could not find a valid graph\n");
    return -1;
  }
  if(gs_smart_mg_create_argument_file_names(this_mg)<0){
    ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
    return -1;
  }
   best_mg=this_mg;
  *_best_mg=best_mg;

  return 0;

}




/*
 * This function sets the mapping heuristic which will be
 * invoked.
 *
 * @param _mapper_type -- the name of the mapper to invoke
 */


int gs_smart_set_mapper_type(char * _mapper_type){

  int i;
  if(!_mapper_type) return -1;
  for(i=0;i<nb_mappers;i++){
    if(strcmp(_mapper_type, mapping_names[i])==0){
      mapper_type=_mapper_type;
      return 0;
    }
  }
  return -1;
}




/*
 * This function gets the mapping heuristic which will be
 * invoked.
 *
 * @param _mapper_type -- the name of the mapper which will be invoked
 */


int gs_smart_get_mapper_type(char ** _mapper_type){
  if(!mapper_type) return -1;
  *_mapper_type=mapper_type;
  return 0;
}

/*
 * This function returns the number of implemented mapping heuristic.
 */

int gs_smart_get_nb_mappers(){
  return nb_mappers;
}


/*
 * This function returns the mapping heuristic name.
 *
 * @param number -- the position of the mapping heuristic in mapping_names array
 */
char * gs_smart_get_mapping_name(int number){
  return  mapping_names[number];
}


/*
 * This function checks if the called mapping heuristic exists 
 * and has been implemented.
 *
 * @param mapper_type -- the name of the mapping heuristic to check
 */


int gs_smart_check_if_mapper_exists(char * mapper_type){
  int i;
  for(i=0;i<nb_mappers;i++){
    if(strcmp(mapping_names[i], mapper_type)==0){
      return 0;
    }
  }
  return -1;
}



int gs_smart_find_fastest_server(gs_smart_tg_remote_task_node * tg_rem_task_node, 
                  gs_smart_netpm * netpm, double *_best_time, int * _best_server_id){


  int i;
  gs_server_t * server;
  int valid_assignment;
  int nb_valid_mappings_timed=0;
  int best_server_id=0;
  double this_time, best_time;
  int found_mapping;
  
  /*
   * find fastest smart server
   */
  for(i=0;i<netpm->nb_nodes;i++){
    server=netpm->netpm_nodes[i]->server;
    if(server->smart){
      if(gs_smart_check_if_valid_assignment(tg_rem_task_node,
                                 server, &valid_assignment)<0){
        ERRPRINTF("SMART : Error checking if a valid assignment\n");
        return -1;
      } 
          
      if((valid_assignment) && (nb_valid_mappings_timed==0)){
        best_server_id=i;
        if(gs_smart_time_tg_task_node_with_c_comm(tg_rem_task_node, server, &best_time)<0){
          ERRPRINTF("SMART : Error timing task graph task node\n");
          return -1;
        }
        nb_valid_mappings_timed++;
      }
      else if ((valid_assignment) && (nb_valid_mappings_timed>0)){
        if(gs_smart_time_tg_task_node_with_c_comm(tg_rem_task_node, server, &this_time)<0){
          ERRPRINTF("SMART : Error timing task graph task node\n");
          return -1;
        }
        if(this_time<best_time){
          best_server_id=i;
          best_time=this_time;
        }
        nb_valid_mappings_timed++;
      }
    } 
  }
        
  /*
   * if no smart servers find fastest standard server
   */

  if(nb_valid_mappings_timed==0){
    found_mapping=0;
    for(i=0;i<netpm->nb_nodes;i++){
      server=netpm->netpm_nodes[i]->server;
      if(!server->smart){
        if(gs_smart_check_if_valid_assignment(tg_rem_task_node,
                                 server, &valid_assignment)<0){
          ERRPRINTF("SMART : Error checking if a valid assignment\n");
          return -1;
        }
        if((valid_assignment) && (nb_valid_mappings_timed==0)){
          best_server_id=i;
          if(gs_smart_time_tg_task_node_with_c_comm(tg_rem_task_node, server, &best_time)<0){
            ERRPRINTF("SMART : Error timing task graph task node\n");
            return -1;
          }
          nb_valid_mappings_timed++;
        }
        else if ((valid_assignment) && (nb_valid_mappings_timed>0)){
          if(gs_smart_time_tg_task_node_with_c_comm(tg_rem_task_node, server, &this_time)<0){
            ERRPRINTF("SMART : Error timing task graph task node\n");
            return -1;
          }
          if(this_time<best_time){
            best_server_id=i;
            best_time=this_time;
          }
          nb_valid_mappings_timed++;
        }
      } 
    }
  } 
  if(nb_valid_mappings_timed==0){
    ERRPRINTF("SMART: Error no valid mappings found for task %d %s\n", i, tg_rem_task_node->problem->name);
    return -1;
  }

  *_best_server_id=best_server_id;
  *_best_time=best_time;
  return 0;
}




int gs_smart_get_netpm_link_pos(gs_smart_netpm * netpm, int src_server_id, 
                                      int dest_server_id, int * _link_pos){


  int i;
  int link_pos=0;
  gs_smart_netpm_node * netpm_node;
  for(i=0;i<netpm->nb_nodes ;i++){
    netpm_node=netpm->netpm_nodes[i];

    if((netpm_node->server->smart) && (netpm_node->id!=src_server_id)){
      link_pos++;
    }
    if(netpm_node->id==dest_server_id){
      break;
    }
  }
  *_link_pos=link_pos;
  return 0;
}


/*
 *
 *
 *
 */




int gs_smart_greedy_back_link_comm_score(gs_smart_tg * tg, gs_smart_netpm * netpm,  int task_pos, int assn_server_pos, 
                                                 int * mapping_vec, double * score){


  gs_smart_tg_dep_link * tg_bk_link;
  gs_smart_tg_task_node * tg_dep_node;
  gs_smart_tg_remote_task_node * tg_dep_rem_node;
  gs_smart_netpm_link * dep_link;
  gs_smart_tg_remote_task_node * tg_rem_node;
  gs_smart_netpm_node * netpm_this_server;
  gs_smart_netpm_node * netpm_dep_server;
  gs_smart_tg_client_node * next_client_node;

  int byte_size=0;
  double comm_score, total_score=0.0, bw=0.0;
  int  m_vec_dep_pos, dep_server_pos;
  int i;
      
  netpm_this_server=netpm->netpm_nodes[assn_server_pos];
  tg_rem_node=tg->task_nodes[task_pos]->tg_rem_task_node;

  /*
   * For each back link from this mapped remote task node
   * calculate its comm score and add to total score.
   * If a dependency is determined to be broken, if either a
   * source task or dest task are standard servers then
   * calculate the cost of bridge communication.
   */ 

  for(i=0;i<tg_rem_node->nb_node_bkwd_links;i++){
    tg_bk_link=tg_rem_node->tg_node_bkwrd_link[i];
    tg_dep_node=tg_bk_link->obj_node_ptr->tg_obj_bkwrd_link->task_node_ptr;
    byte_size=tg_bk_link->obj_node_ptr->byte_size;
 
    /*
     * if this back link of the task node points back 
     * to the client then calculate the comm score between mapped server
     * to client
     */ 
    if(tg_dep_node->node_type==GS_SMART_TG_CLIENT_NODE){
      bw=netpm_this_server->netpm_links[0]->bw;
      comm_score=(double)((byte_size/bw));
      total_score=total_score+comm_score;
    }
    /*
     * else if the back link of the task node points back 
     * to the another task node then calculate the comm score between mapped 
     * server of this destination task to the mapped server of the 
     * source task.
     */  
    else{
      tg_dep_rem_node=tg_dep_node->tg_rem_task_node;
      m_vec_dep_pos=(tg_dep_node->id/2)-1;
      /*
       * if the back link points back to a node
       * which has previously been mapped to a server.
       * In this case the mapping vec element which corresponds to that 
       * task node has been given a value which is not -1;
       */ 
      if(mapping_vec[m_vec_dep_pos]!=-1){
        dep_server_pos=mapping_vec[m_vec_dep_pos];
        netpm_dep_server=netpm->netpm_nodes[dep_server_pos];
       
        /*
         * If either the dest task node (this) is mapped to a standard server or 
         * the source task node (dep) is mapped to standard server then the 
         * dependencies between these tasks will be broken.
         * Therefore we need to calculate the comm score to transfer bytesize 
         * from source node to client. And then from client to
         * dest task node(i.e. bridge communication). 
         * As opposed to just calculate from source to destination.
         */  
        if( (!netpm_this_server->server->smart) || (!netpm_dep_server->server->smart) ){
          bw=netpm_this_server->netpm_links[0]->bw;
          comm_score=(double)((byte_size/bw));
          total_score=total_score+comm_score;
          bw=netpm_dep_server->netpm_links[0]->bw;
          comm_score=(double)((byte_size/bw));
          total_score=total_score+comm_score;
        } 
        /*
         * Else just calculate the comm score for direct communication or caching.
         */ 
        else{
          /*
           * if the server mapped to source task is the same as server
           * mapped to destination task then calculate the score for
           * caching the arg.
           */ 
          if(dep_server_pos==assn_server_pos){
            comm_score=(double)((double)(byte_size/(double)100000000));
            total_score=total_score+comm_score;
          }
          /*
           * if the server mapped to source task is different to the server
           * mapped to destination task then calculate the score for
           * direct communication.
           */ 
          else{
            /*
             * First determine the network link (dep )which connects the source server 
             * to destintation server. 
             */ 
            int link_pos;
            if(gs_smart_get_netpm_link_pos(netpm, assn_server_pos,
                                      dep_server_pos, &link_pos)<0){
              ERRPRINTF("SMART: Error getting network pm link position\n");
              return -1;

            }

 
            /* 
             * Then calculate the comm score and
             * add it to the total score.
             */
             dep_link=netpm->netpm_nodes[assn_server_pos]->netpm_links[link_pos];
             bw=dep_link->bw;
             comm_score=(double)((byte_size/bw)); 
             total_score=total_score+comm_score;
          }
        }
      }
    }
  }
//  netpm_this_server=netpm->netpm_nodes[assn_server_pos];
  /*
   * If the server mapped to this task is not a smart server
   * then add the communication cost of sending out back to client
   */ 

  if( (!netpm_this_server->server->smart)){
    bw=netpm_this_server->netpm_links[0]->bw;
    comm_score=(double)((byte_size/bw));
    total_score=total_score+comm_score;
  }

  /*
   * In additionthe communication cost of the back links from the next 
   * client node back to this task node are calculated and added total
   * score. 
   */ 
  next_client_node=tg->task_nodes[task_pos+1]->tg_client_node; 
  for(i=0;i<next_client_node->nb_node_bkwd_links;i++){
    tg_bk_link=next_client_node->tg_node_bkwrd_link[i];
    byte_size=tg_bk_link->obj_node_ptr->byte_size;
    bw=netpm_this_server->netpm_links[0]->bw;
    comm_score=(double)((byte_size/bw));
    total_score=total_score+comm_score;
  }
 
  *score=total_score;
  return 0;
}
/*
 * 
 *
 *
 */


int gs_smart_greedy_get_score(gs_smart_tg * tg, gs_smart_netpm * netpm, 
                 int *mapping_vec, double * comp_scores, int m_vec_pos, 
                 double * _comp_score, double * score){

  int i;
  int task_pos;
  gs_smart_tg_remote_task_node * tg_rem_node;
  gs_smart_tg_task_node *tg_node;
  gs_smart_netpm_node * netpm_this_server;
  int assn_server_pos;
  double total_score=0, comp_score, comm_score;

  /*
   *
   *
   */
  double back_link_score=0 ;
  double total_comp_score=0 ;
  for(i=0;i<tg->nb_rem_nodes;i++){
    assn_server_pos=mapping_vec[i];
    task_pos=(i+1)*2;

    if(mapping_vec[i]!=-1){
      netpm_this_server=netpm->netpm_nodes[assn_server_pos];
      tg_node=tg->task_nodes[task_pos];
      tg_rem_node=tg_node->tg_rem_task_node;
      /*
       * gs_smart_greedy_time_back_links
       */
      if(gs_smart_greedy_back_link_comm_score(tg,netpm, task_pos,assn_server_pos, mapping_vec, &comm_score)<0){
        ERRPRINTF("SMART: Error getting the score for back links\n");
        return -1;
      }
      back_link_score=comm_score+back_link_score;

      total_score=comm_score+total_score;

      if(i==m_vec_pos){
        if(gs_smart_time_tg_task_node(tg_rem_node, netpm_this_server->server, &comp_score)<0){
          ERRPRINTF("SMART : Error gs_smart_time_tg_task_node\n");
          return -1;
        }
        comp_scores[i]=comp_score;
        total_comp_score=total_comp_score+comp_score;
        total_score=total_score+comp_score;
      }
      else{
        comp_score=comp_scores[i]; 
        total_comp_score=total_comp_score+comp_score;
        total_score=total_score+comp_score;
     }
    }
  }
/*
  LOGPRINTF("ASSIGNING TASK %d TO SERVER %s\n", m_vec_pos, netpm->netpm_nodes[mapping_vec[m_vec_pos]]->server->hostname);
  LOGPRINTF("TOTAL BACK LINK SCORE =%f\n", back_link_score);
  LOGPRINTF("TOTAL COMP SCORE =%f\n", total_comp_score);
  LOGPRINTF("TOTAL OVERALL SCORE =%f\n", total_score);
*/
  *_comp_score=comp_score;
  *score=total_score;
  return 0;
}


int gs_smart_greedy_best_server(gs_smart_tg * tg, gs_smart_netpm * netpm, 
                                int * mapping_vec, double * comp_scores, 
                                int m_vec_pos, double * _comp_score, 
                                int *_nb_valid_assign){

  gs_smart_tg_remote_task_node * tg_rem_task_node;
  gs_smart_tg_task_node *tg_node;
  gs_server_t * mapped_server;

  int i=0;
  double this_score, best_score=0;
  int best_pos=0;

  /*
   * position in task graph of the task currently getting assigned
   */ 
  int task_pos;  

  double this_comp_score, best_comp_score=0;
  int nb_valid_assign=0;
  int valid_assignment;
  int server_pos;
  task_pos=(m_vec_pos+1)*2;
  tg_node=tg->task_nodes[task_pos];
  tg_rem_task_node=tg_node->tg_rem_task_node;
  for(i=0;i<netpm->nb_nodes;i++){
    mapping_vec[m_vec_pos]=i;
    server_pos=mapping_vec[m_vec_pos];
    mapped_server=netpm->netpm_nodes[server_pos]->server;
 
    if(gs_smart_check_if_valid_assignment(tg_rem_task_node, mapped_server, &valid_assignment)<0){
      ERRPRINTF("SMART : Error checking if it is a valid assignment\n");
      return -1;
    }
    if(valid_assignment==-1){
      break;
    }

    nb_valid_assign++;

    if(gs_smart_greedy_get_score(tg, netpm, mapping_vec, comp_scores, m_vec_pos, &this_comp_score, &this_score)<0){
      ERRPRINTF("SMART : Error gs_smart_greedy_get_score\n");
      return -1;
    }


    if(i==0){
      best_comp_score=this_comp_score;
      best_score=this_score;
      best_pos=i;
    }
    else{
      if(this_score<best_score){
        best_comp_score=this_comp_score;
        best_score=this_score;
        best_pos=i;
      }
    }
  }
  *_comp_score=best_comp_score; 
  *_nb_valid_assign=nb_valid_assign;
  mapping_vec[m_vec_pos]=best_pos;
  return 0;

}





int gs_smart_rank_group_tasks(gs_smart_tg * tg, int start_i, int end_i, int nb_nbl_group , int * ranked_tasks){
  gs_smart_tg_task_node * task_node;
  gs_smart_tg_remote_task_node * tg_rem_task_node=NULL;
  gs_smart_tg_remote_task_node * tg_ranked_task_node;
  int i, j, k;

  for(i=start_i; i<=end_i; i++){
    task_node=tg->task_nodes[i];
    if(task_node->node_type==GS_SMART_TG_REM_TASK_NODE){
      tg_rem_task_node=task_node->tg_rem_task_node;
      for(j=0;j<nb_nbl_group;j++){
        if(ranked_tasks[j]==0){
          ranked_tasks[j]=i;
          break;
        }
        else{
          int task_pos=ranked_tasks[j];
          tg_ranked_task_node=tg->task_nodes[task_pos]->tg_rem_task_node;
          int tmp_task_pos_1, tmp_task_pos_2;
          if(tg_rem_task_node->nb_flops > tg_ranked_task_node->nb_flops){
            tmp_task_pos_1=ranked_tasks[j];                
            ranked_tasks[j]=i;
            for(k=j+1;k<nb_nbl_group;k++){
              if(ranked_tasks[k]==0){
                ranked_tasks[k]=tmp_task_pos_1;
                break;
              }
              else{
                tmp_task_pos_2=ranked_tasks[k];
                ranked_tasks[k]=tmp_task_pos_1;
                tmp_task_pos_1=tmp_task_pos_2;    
              }              
            }
          }
          else if(tg_rem_task_node->nb_flops == tg_ranked_task_node->nb_flops){
            tmp_task_pos_1=ranked_tasks[j];                
            ranked_tasks[j]=i;
            for(k=j+1;k<nb_nbl_group;k++){
              if(ranked_tasks[k]==0){
                ranked_tasks[k]=tmp_task_pos_1;
                break;
              }
              else{
                tmp_task_pos_2=ranked_tasks[k];
                ranked_tasks[k]=tmp_task_pos_1;
                tmp_task_pos_1=tmp_task_pos_2;    
              }              
            }
          }

        }
      }     
    }              
  }




  return 0;
}


/*
 *
 *
 */



int gs_smart_map_greedy_group(gs_smart_tg * tg, gs_smart_netpm * netpm, 
       int start_i, int end_i, int nb_nbl_group , int rem_task_cnt, int * mapping_vec){

  gs_smart_tg_task_node * task_node;
  gs_smart_tg_remote_task_node * tg_rem_task_node=NULL;
  gs_server_t * mapped_server;


  int nb_valid_assign;

  /*
   * array stores the rank of each task
   * the rank indicates its relative computation load in the group
   */ 
  int * ranked_tasks;

  /*
   *  stores computational score of each previously mapped task in group 
   */ 
  double * comp_scores;


  double comp_score;
  int best_server_id=0, i, m_vec_pos;

  /*
   * keeps track of the task graph position of the current task being mapped 
   */
  int task_pos; 


  comp_scores= (double *)calloc(tg->nb_rem_nodes, sizeof(double));
  ranked_tasks = (int *)calloc(nb_nbl_group, sizeof(int));

  /*
   * This function returns a vector which ranks each task in the group
   * according to their computation load.
   */ 

  if(gs_smart_rank_group_tasks(tg, start_i, end_i, nb_nbl_group , ranked_tasks)<0){
    ERRPRINTF("SMART : Error ranking group of tasks\n");
    return -1;
  }


  for(i=0;i<nb_nbl_group;i++){
    task_pos=ranked_tasks[i];
    m_vec_pos=(rem_task_cnt+nb_nbl_group)-1-i;
    task_node=tg->task_nodes[task_pos];
    tg_rem_task_node=task_node->tg_rem_task_node;
    if(gs_smart_greedy_best_server(tg, netpm, mapping_vec, comp_scores, m_vec_pos, &comp_score, &nb_valid_assign)<0){
      ERRPRINTF("SMART : Error gs_smart_greedy_best_server\n");
      return -1;
    }
    if(nb_valid_assign<1){
      ERRPRINTF("SMART : Error, nndle->o valid assignments were found for task %s\n",tg_rem_task_node->problem->name);
      ERRPRINTF("SMART : No servers in the network could execute this task\n");
      return -1;
    }

    best_server_id=mapping_vec[m_vec_pos];
    mapped_server=netpm->netpm_nodes[best_server_id]->server;
    mapped_server->task_workload =(mapped_server->task_workload+(10000*comp_score) );
  }

  for(i=0;i<netpm->nb_nodes;i++){
    netpm->netpm_nodes[i]->server->task_workload=0;
  }
  return 0;
}
/*
 *  The basic mapping heuristic is a non-iterative mapping heuristic.
 *  It maps each task one at a time. It finds the fastest smart enabled
 *  server that can execute each task.  When a nonblocking task gets 
 *  assigned to a server, the server's workload is increased. 
 *  This provides a basic method for load balancing non-blocking tasks.
 *  If there are no smart servers that can execute a specific task
 *  then this task will be assigned a server that is not smart enabled.
 *  Once the tasks have been assigned to servers, the mapping graph is
 *  generated with the best communication scheme, based on the dependencies
 *  between tasks and whether the servers assigned are smart servers or not.
 *
 *  This is a basic heuristic which generates a mapping solution quickly 
 *  and provides speed up due to direct communication between servers.
 *  However since it maps tasks individually it does not fully exploit the 
 *  potential of mapping tasks collectively such as improved load balancing
 *  of computation.
 *
 *  @param tg - (in) Task graph of a the mapped group of tasks
 *  @param netpm -- (in) Network performance model
 *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
 *
 */

int gs_smart_greedy_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){
  gs_smart_mg * best_mg;
  gs_smart_tg_task_node * task_node;
  gs_smart_tg_remote_task_node * tg_rem_task_node;
  int * mapping_vec;  
  int i, nb_rem_tasks, rem_task_cnt;
  int nbl_task_called;
  double est_time;
  int valid_graph;
  int best_server_id=0;
  int * assigned_tasks;

  int start_i=0, end_i=0;
  nb_rem_tasks=tg->nb_rem_nodes;
  best_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
  mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
  assigned_tasks = (int *)calloc(nb_rem_tasks, sizeof(int));

  
  for(i=0;i<nb_rem_tasks;i++){
    mapping_vec[i]=-1;
  }
 
  rem_task_cnt=0;
  nbl_task_called=0;

  nbl_task_called=0;
  rem_task_cnt=0;
  i=0;
  task_node=tg->task_nodes[i];
  int nb_nbl_group=0;
  start_i=i;
  while(i<tg->nb_nodes){
    task_node=tg->task_nodes[i];
    if(task_node->node_type==GS_SMART_TG_REM_TASK_NODE){
      tg_rem_task_node=task_node->tg_rem_task_node;
      if(tg_rem_task_node->blocking){
        end_i=i;
        if(nb_nbl_group==0){
          if( gs_smart_find_fastest_server(tg_rem_task_node,netpm, 
                                              &est_time, &best_server_id)<0){
            ERRPRINTF("SMART : Error finding fastest server\n");
            return -1;
          }
          mapping_vec[rem_task_cnt]=best_server_id;
          rem_task_cnt++;
        }
        else{
          if(gs_smart_map_greedy_group(tg, netpm, start_i, end_i, nb_nbl_group,
                                                    rem_task_cnt, mapping_vec)){
            ERRPRINTF("Error mapping greedy group\n");
            return -1;
          }
          rem_task_cnt=rem_task_cnt+nb_nbl_group;
          if( gs_smart_find_fastest_server(tg_rem_task_node,netpm, 
                                                 &est_time, &best_server_id)<0){
            ERRPRINTF("SMART : Error finding fastest server\n");
            return -1;
          }
          mapping_vec[rem_task_cnt]=best_server_id;
          rem_task_cnt++;

        }
        nb_nbl_group=0;
        start_i=end_i;
      }
      else{
        nb_nbl_group++;
      }
      end_i=i;
    }
    i++;
  }
  if(nb_nbl_group>0){
    start_i=start_i+2;
    if(gs_smart_map_greedy_group(tg, netpm, start_i, end_i, nb_nbl_group,
                                                    rem_task_cnt, mapping_vec)){
      ERRPRINTF("Error mapping greedy group\n");
      return -1;
    }
  }
  rem_task_cnt=rem_task_cnt+nb_nbl_group;

/*
  mapping_vec[0]=2;
  mapping_vec[1]=2;
  mapping_vec[2]=2;
  mapping_vec[3]=2;
  mapping_vec[4]=2;
*/
  if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, best_mg, &valid_graph)<0){
    ERRPRINTF("SMART: Error generating mapping graph\n");
    return -1;
  }
  if(gs_smart_mg_create_argument_file_names(best_mg)<0){
    ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
    return -1;
  }

  if(!valid_graph){
    ERRPRINTF("SMART : The mapping graph generated is invalid!\n");
    return -1;
  }
  *_best_mg=best_mg;
  return 0;
}











double
total_time(const struct timeval* t0, const struct timeval* t1)
{
  double ret = t1->tv_sec - t0->tv_sec;
  double uret = t1->tv_usec - t0->tv_usec;
  return ret + uret / 1E6;
}










#endif