gs_smart_mapping_heuristics.c

Go to the documentation of this file.
00001 
00017 #include "config.h"
00018 
00019 #ifdef GS_SMART_GRIDSOLVE
00020 #include <math.h>
00021 #include "gs_smart_task_graph.h"
00022 #include "gs_smart_mapping_graph.h"
00023 #include "gs_smart_mapping_heuristics.h"
00024 #include "gs_smart_mapping_matrix_func.h"
00025 
00026 /*
00027  * The list of names of implemented mapping heuristics
00028  */
00029 
00030 static int nb_mappers=5;
00031 static char mapping_names[5][15] ={"ex_map", "basic_map", "random_map", "rwalk_map", "greedy_map"};
00032 
00033 double
00034 total_time(const struct timeval*, const struct timeval*);
00035 
00036 
00037 /*
00038  * The name of the mapping heuristic called
00039  */
00040 static char * mapper_type;
00041 
00042 
00043 /*
00044  *  This function invokes the called mapping heuristic
00045  *  @param tg - (in) Task graph of a the mapped group of tasks
00046  *  @param netpm -- (in) Network performance model
00047  *  @param best_mg -- (out) Mapping solution generated by the mapping heuristic 
00048  *  @param mapper_num -- (in) The position of mapping solution to invoke in mapping_names array.
00049  */
00050 
00051 int gs_smart_exec_mapper(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg, int mapper_num){
00052   LOGPRINTF("Mapping group of tasks with mapping heuristic %s\n", mapping_names[mapper_num]);
00053    gs_smart_mg * best_mg;
00054   if(mapper_num==0){
00055     if(gs_smart_ex_map(tg, netpm, &best_mg)<0){
00056         ERRPRINTF("SMART : Error performing exhaustive mapping heuristic\n");
00057         return -1;
00058     }
00059   }
00060   else if(mapper_num==1){
00061     if(gs_smart_basic_map(tg, netpm, &best_mg)<0){
00062         ERRPRINTF("SMART : Error performing basic mapping heuristic\n");
00063         return -1;
00064     }
00065   }
00066   else if(mapper_num==2){
00067     if(gs_smart_random_map(tg, netpm, &best_mg)<0){
00068         ERRPRINTF("SMART : Error performing random mapping heuristic\n");
00069         return -1;
00070     }
00071   }
00072   else if(mapper_num==3){
00073     if(gs_smart_rwalk_map(tg, netpm, &best_mg)<0){
00074         ERRPRINTF("SMART : Error performing random walk mapping heuristic\n");
00075         return -1;
00076     }
00077   }
00078   else if(mapper_num==4){
00079     if(gs_smart_greedy_map(tg, netpm, &best_mg)<0){
00080         ERRPRINTF("SMART : Error performing random walk mapping heuristic\n");
00081         return -1;
00082     }
00083   }
00084   *_best_mg=best_mg;
00085   return 0;
00086 }
00087 
00088 
00089 
00090 
00091 
00092 
00093 
00094 /*
00095  *  The exhaustive search mapping heuristic is an iterative mapping 
00096  *  heuristic.
00097  *  This mapping heuristic iterates through every possible mapping 
00098  *  solution and returns the mapping solution with fastest time.
00099  *
00100  *  This heuristic can be time-consuming when there are a large 
00101  *  number of solutions.  The number of solutions for a given 
00102  *  set of tasks and server is equal to num_server to the power
00103  *  of num_tasks, which can be a significant number.
00104  *  This can be expensive as it roughly takes one second to time 
00105  *  10,000 solutions.
00106  *
00107  *  @param tg - (in) Task graph of a the mapped group of tasks
00108  *  @param netpm -- (in) Network performance model
00109  *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
00110  *
00111  */
00112 
00113 
00114 
00115 int gs_smart_ex_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){
00116 
00117   gs_smart_mg * this_mg;
00118   gs_smart_mg * best_mg=NULL;
00119   int ** mapping_matrix;
00120   int * mapping_vec;  
00121   int nb_rem_tasks, nb_servers;
00122   int i, j;
00123   int total_permutations, this_per;
00124   double best_time=0.0;
00125   double this_time=0.0;
00126   struct timeval t1, t2;
00127   double et;
00128   if(tg->nb_rem_nodes<=0){
00129     ERRPRINTF("SMART: Error doing exhaustive search, no remote nodes\n");
00130     return -1;
00131   }
00132 
00133   nb_servers=netpm->nb_nodes;
00134   nb_rem_tasks=tg->nb_rem_nodes;
00135   mapping_matrix = (int **)calloc( nb_servers, sizeof(int *));
00136 
00137   if(!mapping_matrix) return -1;
00138   
00139   for (i = 0; i <nb_servers; i++) {
00140     mapping_matrix[i] = (int *)calloc(nb_rem_tasks, sizeof(int));
00141     if(!mapping_matrix[i]) return -1;
00142   }
00143 
00144   for( i = 0; i < nb_servers; i++){
00145     for( j = 0; j < nb_rem_tasks; j++){
00146       mapping_matrix[i][j] = 0;
00147     }
00148   }
00149 
00150   mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
00151   if(!mapping_vec){
00152     ERRPRINTF("SMART: Error allocating to mapping vector\n");
00153     return -1;
00154   } 
00155 
00156   total_permutations=(int)(pow((double)nb_servers,(double)nb_rem_tasks));
00157 
00158 
00159   int num_valid_graphs=0;
00160   gettimeofday(&t1, 0);
00161  
00162   for(this_per=0;this_per<total_permutations;this_per++){
00163     this_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
00164     if(gs_smart_zero_mapping_matrix(mapping_matrix, nb_servers, nb_rem_tasks)<0){
00165       ERRPRINTF("SMART: Error resetting mapping matrix on mapping solution %d\n", this_per);
00166       return -1;
00167     }
00168 
00169     
00170     if(gs_smart_next_permutation(mapping_matrix, this_per, nb_servers, nb_rem_tasks)<0){
00171       ERRPRINTF("SMART: Error shifting matrix to next permuation on mapping solution %d\n", this_per);
00172       return -1;
00173     }
00174     if(gs_smart_matrix_to_vec(mapping_matrix, nb_servers, nb_rem_tasks, mapping_vec)<0){
00175       ERRPRINTF("SMART: Error converting mapping matrix to a vector\n");
00176       return -1;
00177     }
00178     int valid_graph;
00179     if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, this_mg, &valid_graph)<0){
00180       ERRPRINTF("SMART: Error generating mapping graph\n");
00181       return -1;
00182     }
00183 
00184    this_time=this_mg->total_time;
00185     if(valid_graph){ 
00186       if(num_valid_graphs==0){
00187         best_time=this_time;
00188         best_mg=this_mg;
00189       }
00190       else{
00191         if(this_time<best_time){
00192           best_time=this_time;
00193           if(gs_smart_free_mg(best_mg)<0){
00194             ERRPRINTF("SMART : Error freeing mapping graph\n");
00195             return -1;
00196           }
00197           best_mg=this_mg;
00198         }
00199         else{
00200           if(gs_smart_free_mg(this_mg)<0){
00201             ERRPRINTF("SMART : Error freeing mapping graph\n");
00202             return -1;
00203           }
00204         }
00205 
00206       }
00207       num_valid_graphs++;
00208      }
00209   }
00210   if(num_valid_graphs==0){
00211     ERRPRINTF("SMART : No mapping solutions found for this group of tasks\n");
00212     return -1;
00213 
00214   }
00215   if(gs_smart_mg_create_argument_file_names(best_mg)<0){
00216     ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
00217     return -1;
00218   }
00219   gettimeofday(&t2, 0);
00220   et = total_time(&t1,&t2);
00221   
00222   LOGPRINTF("It took exhaustive mapper %g seconds to generate mapping solution from %d solutions\n", et, total_permutations);
00223   *_best_mg=best_mg;
00224   return 0;
00225 }
00226 
00227 
00228 
00229 
00230 
00231 
00232 
00233 /*
00234  *  The basic mapping heuristic is a non-iterative mapping heuristic.
00235  *  It maps each task one at a time. It finds the fastest smart enabled
00236  *  server that can execute each task.  When a nonblocking task gets 
00237  *  assigned to a server, the server's workload is increased. 
00238  *  This provides a basic method for load balancing non-blocking tasks.
00239  *  If there are no smart servers that can execute a specific task
00240  *  then this task will be assigned a server that is not smart enabled.
00241  *  Once the tasks have been assigned to servers, the mapping graph is
00242  *  generated with the best communication scheme, based on the dependencies
00243  *  between tasks and whether the servers assigned are smart servers or not.
00244  *
00245  *  This is a basic heuristic which generates a mapping solution quickly 
00246  *  and provides speed up due to direct communication between servers.
00247  *  However since it maps tasks individually it does not fully exploit the 
00248  *  potential of mapping tasks collectively such as improved load balancing
00249  *  of computation.
00250  *
00251  *  @param tg - (in) Task graph of a the mapped group of tasks
00252  *  @param netpm -- (in) Network performance model
00253  *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
00254  *
00255  */
00256 
00257 int gs_smart_basic_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){
00258   gs_smart_mg * best_mg;
00259   gs_smart_tg_task_node * task_node;
00260   gs_smart_tg_remote_task_node * tg_rem_task_node;
00261   gs_server_t * server;
00262   int * mapping_vec;  
00263   int i, j, nb_rem_tasks, rem_task_cnt;
00264   int nbl_task_called;
00265   double this_time, best_time;
00266   int valid_assignment;
00267   int found_mapping;
00268   int nb_valid_mappings_timed;
00269   int valid_graph;
00270   int best_server_id=0;
00271   nb_rem_tasks=tg->nb_rem_nodes;
00272   best_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
00273   mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
00274  
00275   rem_task_cnt=0;
00276   nbl_task_called=0;
00277   for(i=0;i<tg->nb_nodes;i++){
00278     task_node=tg->task_nodes[i];
00279     if(task_node->node_type==GS_SMART_TG_REM_TASK_NODE){
00280       tg_rem_task_node=task_node->tg_rem_task_node;
00281 
00282       nb_valid_mappings_timed=0;
00283       best_time=0.0;
00284       /*
00285        * find fastest smart server
00286        */
00287       for(j=0;j<netpm->nb_nodes;j++){
00288         server=netpm->netpm_nodes[j]->server;
00289         if(server->smart){
00290           if(gs_smart_check_if_valid_assignment(tg_rem_task_node,
00291                                    server, &valid_assignment)<0){
00292             ERRPRINTF("SMART : Error checking if a valid assignment\n");
00293             return -1;
00294           }
00295           
00296           if((valid_assignment) && (nb_valid_mappings_timed==0)){
00297               best_server_id=j;
00298               if(gs_smart_time_tg_task_node(tg_rem_task_node, server, &best_time)<0){
00299                 ERRPRINTF("SMART : Error timing task graph task node\n");
00300                 return -1;
00301               }
00302               nb_valid_mappings_timed++;
00303             }
00304             else if ((valid_assignment) && (nb_valid_mappings_timed>0)){
00305               if(gs_smart_time_tg_task_node(tg_rem_task_node, server, &this_time)<0){
00306                 ERRPRINTF("SMART : Error timing task graph task node\n");
00307                 return -1;
00308               }
00309               if(this_time<best_time){
00310                 best_server_id=j;
00311                 best_time=this_time;
00312               }
00313               nb_valid_mappings_timed++;
00314             }
00315             
00316           } 
00317         }
00318         
00319        /*
00320         * if no smart servers find fastest standard server
00321         */
00322 
00323         if(nb_valid_mappings_timed==0){
00324           found_mapping=0;
00325             for(j=0;j<netpm->nb_nodes;j++){
00326               server=netpm->netpm_nodes[j]->server;
00327               if(!server->smart){
00328                 if(gs_smart_check_if_valid_assignment(tg_rem_task_node,
00329                                      server, &valid_assignment)<0){
00330                   ERRPRINTF("SMART : Error checking if a valid assignment\n");
00331                   return -1;
00332                 }
00333                 if((valid_assignment) && (nb_valid_mappings_timed==0)){
00334                   best_server_id=j;
00335                   if(gs_smart_time_tg_task_node(tg_rem_task_node, server, &best_time)<0){
00336                     ERRPRINTF("SMART : Error timing task graph task node\n");
00337                     return -1;
00338                   }
00339                   nb_valid_mappings_timed++;
00340                 }
00341                 else if ((valid_assignment) && (nb_valid_mappings_timed>0)){
00342                   if(gs_smart_time_tg_task_node(tg_rem_task_node, server, &this_time)<0){
00343                     ERRPRINTF("SMART : Error timing task graph task node\n");
00344                     return -1;
00345                   }
00346                   if(this_time<best_time){
00347                     best_server_id=j;
00348                     best_time=this_time;
00349                   }
00350                   nb_valid_mappings_timed++;
00351                 }
00352               } 
00353             }
00354         } 
00355         if(nb_valid_mappings_timed==0){
00356           ERRPRINTF("SMART: Error no valid mappings found for task %d %s\n", i, tg_rem_task_node->problem->name);
00357           return -1;
00358         }
00359 
00360 
00361         /*
00362          * if its a blocking task reset the task workloads of all the servers
00363          */ 
00364         
00365         if(tg_rem_task_node->blocking==1){ 
00366           for(j=0;j<netpm->nb_nodes;j++){
00367             netpm->netpm_nodes[j]->server->task_workload=0;
00368           }
00369         }
00370         /*
00371          * if its a non-blocking task bump up the task workload of assigned server
00372          */ 
00373         else if(tg_rem_task_node->blocking==0){
00374           netpm->netpm_nodes[best_server_id]->server->task_workload =(server->task_workload+ (10000*best_time));
00375         }
00376 
00377       
00378       mapping_vec[rem_task_cnt]=best_server_id; 
00379       rem_task_cnt++;
00380     }
00381 
00382   }
00383   
00384   if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, best_mg, &valid_graph)<0){
00385     ERRPRINTF("SMART: Error generating mapping graph\n");
00386     return -1;
00387   }
00388   if(gs_smart_mg_create_argument_file_names(best_mg)<0){
00389     ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
00390     return -1;
00391   }
00392 
00393 
00394   if(!valid_graph){
00395     ERRPRINTF("SMART : The mapping graph generated is invalid!\n");
00396     return -1;
00397   }
00398   *_best_mg=best_mg;
00399   return 0;
00400 }
00401 
00402 
00403 
00404 
00405 
00406 
00407 
00408 /*
00409  *  This mapping heuristic randomly traverses the solution space and
00410  *  returns the fastest solution within that solution space.
00411  *  The number of solutions timed is max_solutions.
00412  *
00413  *  @param tg - (in) Task graph of a the mapped group of tasks
00414  *  @param netpm -- (in) Network performance model
00415  *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
00416  *
00417  */
00418 
00419 
00420 
00421 
00422 
00423 int gs_smart_rwalk_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){
00424 
00425   gs_smart_mg * this_mg;
00426   gs_smart_mg * best_mg=NULL;
00427   int ** mapping_matrix;
00428   int * mapping_vec;  
00429   int nb_rem_tasks, nb_servers;
00430   int i, j;
00431   int total_permutations;
00432   double best_time=0.0;
00433   double this_time=0.0;
00434   int solution_num;
00435   int max_solutions=10000;
00436   int valid_graph=0;
00437   int sol_num=0;
00438   int num_valid_graphs=0;
00439   struct timeval t1, t2;
00440   double et;
00441   if(tg->nb_rem_nodes<=0){
00442     ERRPRINTF("SMART: Error doing exhaustive search, no remote nodes\n");
00443     return -1;
00444   }
00445 
00446   nb_servers=netpm->nb_nodes;
00447   nb_rem_tasks=tg->nb_rem_nodes;
00448   mapping_matrix = (int **)calloc( nb_servers, sizeof(int *));
00449 
00450   if(!mapping_matrix) return -1;
00451   
00452   for (i = 0; i <nb_servers; i++) {
00453     mapping_matrix[i] = (int *)calloc(nb_rem_tasks, sizeof(int));
00454     if(!mapping_matrix[i]) return -1;
00455   }
00456 
00457   for( i = 0; i < nb_servers; i++){
00458     for( j = 0; j < nb_rem_tasks; j++){
00459       mapping_matrix[i][j] = 0;
00460     }
00461   }
00462 
00463   mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
00464   if(!mapping_vec){
00465     ERRPRINTF("SMART: Error allocating to mapping vector\n");
00466     return -1;
00467   } 
00468 
00469   total_permutations=(int)(pow((double)nb_servers,(double)nb_rem_tasks));
00470 
00471   LOGPRINTF("Total number of possible solutions %d\n", total_permutations);
00472   LOGPRINTF("Number of solutions timed =  %d\n", max_solutions);
00473   num_valid_graphs=0;
00474   gettimeofday(&t1, 0);
00475   while((sol_num<max_solutions) && (sol_num<total_permutations)){
00476     this_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
00477     srand((unsigned)time(0)); 
00478     solution_num=(rand()%total_permutations);
00479     if(gs_smart_zero_mapping_matrix(mapping_matrix, nb_servers, nb_rem_tasks)<0){
00480       ERRPRINTF("SMART: Error resetting mapping matrix on mapping solution\n");
00481       return -1;
00482     }
00483     if(gs_smart_next_permutation(mapping_matrix, solution_num, nb_servers, nb_rem_tasks)<0){
00484       ERRPRINTF("SMART: Error shifting matrix to next permuation on mapping solution\n");
00485       return -1;
00486     }
00487     if(gs_smart_matrix_to_vec(mapping_matrix, nb_servers, nb_rem_tasks, mapping_vec)<0){
00488       ERRPRINTF("SMART: Error converting mapping matrix to a vector\n");
00489       return -1;
00490     }
00491     if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, this_mg, &valid_graph)<0){
00492       ERRPRINTF("SMART: Error generating mapping graph\n");
00493       return -1;
00494     }
00495     if(!valid_graph){
00496       if(gs_smart_free_mg(this_mg)<0){
00497         ERRPRINTF("SMART : Error freeing mapping graph\n");
00498         return -1;
00499       }
00500     }
00501     else{
00502 
00503       this_time=this_mg->total_time;
00504       if(valid_graph){ 
00505         if(num_valid_graphs==0){
00506           best_time=this_time;
00507           best_mg=this_mg;
00508         }
00509         else{
00510           if(this_time<best_time){
00511             best_time=this_time;
00512             if(gs_smart_free_mg(best_mg)<0){
00513               ERRPRINTF("SMART : Error freeing mapping graph\n");
00514               return -1;
00515             }
00516             best_mg=this_mg;
00517           }
00518           
00519           else{
00520             if(gs_smart_free_mg(this_mg)<0){
00521               ERRPRINTF("SMART : Error freeing mapping graph\n");
00522               return -1;
00523             }
00524           }
00525         }
00526         num_valid_graphs++;
00527        }
00528      }
00529     sol_num++;
00530   }
00531   if(num_valid_graphs==0){
00532     ERRPRINTF("SMART: Could not find a valid graph\n");
00533     return -1;
00534   }
00535   if(gs_smart_mg_create_argument_file_names(best_mg)<0){
00536     ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
00537     return -1;
00538   }
00539   gettimeofday(&t2, 0);
00540   et = total_time(&t1,&t2);
00541   
00542   LOGPRINTF("It took random walk mapper %g seconds to generate mapping solution\n", et);
00543  
00544 
00545   *_best_mg=best_mg;
00546 
00547   return 0;
00548 
00549 }
00550 
00551 
00552 
00553 
00554 
00555 
00556 
00557 
00558 /*
00559  *  This mapping heuristic is a non-iterative heuristic.
00560  *  It randomly chooses one solution. This mapping solution
00561  *  should only be used for testing.
00562  *
00563  *  @param tg - (in) Task graph of a the mapped group of tasks
00564  *  @param netpm -- (in) Network performance model
00565  *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
00566  *
00567  */
00568 
00569 
00570 
00571 int gs_smart_random_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){
00572 
00573   gs_smart_mg * this_mg;
00574   gs_smart_mg * best_mg=NULL;
00575   int ** mapping_matrix;
00576   int * mapping_vec;  
00577   int nb_rem_tasks, nb_servers;
00578   int i, j;
00579   int total_permutations;
00580   int solution_num;
00581   int max_solutions=10000;
00582   int valid_graph=0;
00583   int sol_num=0;
00584 
00585   this_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
00586   if(tg->nb_rem_nodes<=0){
00587     ERRPRINTF("SMART: Error doing exhaustive search, no remote nodes\n");
00588     return -1;
00589   }
00590 
00591   nb_servers=netpm->nb_nodes;
00592   nb_rem_tasks=tg->nb_rem_nodes;
00593   mapping_matrix = (int **)calloc( nb_servers, sizeof(int *));
00594 
00595   if(!mapping_matrix) return -1;
00596   
00597   for (i = 0; i <nb_servers; i++) {
00598     mapping_matrix[i] = (int *)calloc(nb_rem_tasks, sizeof(int));
00599     if(!mapping_matrix[i]) return -1;
00600   }
00601 
00602   for( i = 0; i < nb_servers; i++){
00603     for( j = 0; j < nb_rem_tasks; j++){
00604       mapping_matrix[i][j] = 0;
00605     }
00606   }
00607 
00608   mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
00609   if(!mapping_vec){
00610     ERRPRINTF("SMART: Error allocating to mapping vector\n");
00611     return -1;
00612   } 
00613 
00614   total_permutations=(int)(pow((double)nb_servers,(double)nb_rem_tasks));
00615 
00616   while((!valid_graph) && (sol_num<max_solutions)){
00617     srand((unsigned)time(0)); 
00618     solution_num=(rand()%total_permutations);
00619     if(gs_smart_zero_mapping_matrix(mapping_matrix, nb_servers, nb_rem_tasks)<0){
00620       ERRPRINTF("SMART: Error resetting mapping matrix on mapping solution\n");
00621       return -1;
00622     }
00623     if(gs_smart_next_permutation(mapping_matrix, solution_num, nb_servers, nb_rem_tasks)<0){
00624       ERRPRINTF("SMART: Error shifting matrix to next permuation on mapping solution\n");
00625       return -1;
00626     }
00627     if(gs_smart_matrix_to_vec(mapping_matrix, nb_servers, nb_rem_tasks, mapping_vec)<0){
00628       ERRPRINTF("SMART: Error converting mapping matrix to a vector\n");
00629       return -1;
00630     }
00631     if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, this_mg, &valid_graph)<0){
00632       ERRPRINTF("SMART: Error generating mapping graph\n");
00633       return -1;
00634     }
00635     if(!valid_graph){
00636 /*
00637       if(gs_smart_free_mg(this_mg)<0){
00638         ERRPRINTF("SMART : Error freeing mapping graph\n");
00639         return -1;
00640       }
00641 */
00642     }
00643     sol_num++;
00644   }
00645   if(!valid_graph){
00646     ERRPRINTF("SMART: Could not find a valid graph\n");
00647     return -1;
00648   }
00649   if(gs_smart_mg_create_argument_file_names(this_mg)<0){
00650     ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
00651     return -1;
00652   }
00653    best_mg=this_mg;
00654   *_best_mg=best_mg;
00655 
00656   return 0;
00657 
00658 }
00659 
00660 
00661 
00662 
00663 /*
00664  * This function sets the mapping heuristic which will be
00665  * invoked.
00666  *
00667  * @param _mapper_type -- the name of the mapper to invoke
00668  */
00669 
00670 
00671 int gs_smart_set_mapper_type(char * _mapper_type){
00672 
00673   int i;
00674   if(!_mapper_type) return -1;
00675   for(i=0;i<nb_mappers;i++){
00676     if(strcmp(_mapper_type, mapping_names[i])==0){
00677       mapper_type=_mapper_type;
00678       return 0;
00679     }
00680   }
00681   return -1;
00682 }
00683 
00684 
00685 
00686 
00687 /*
00688  * This function gets the mapping heuristic which will be
00689  * invoked.
00690  *
00691  * @param _mapper_type -- the name of the mapper which will be invoked
00692  */
00693 
00694 
00695 int gs_smart_get_mapper_type(char ** _mapper_type){
00696   if(!mapper_type) return -1;
00697   *_mapper_type=mapper_type;
00698   return 0;
00699 }
00700 
00701 /*
00702  * This function returns the number of implemented mapping heuristic.
00703  */
00704 
00705 int gs_smart_get_nb_mappers(){
00706   return nb_mappers;
00707 }
00708 
00709 
00710 /*
00711  * This function returns the mapping heuristic name.
00712  *
00713  * @param number -- the position of the mapping heuristic in mapping_names array
00714  */
00715 char * gs_smart_get_mapping_name(int number){
00716   return  mapping_names[number];
00717 }
00718 
00719 
00720 /*
00721  * This function checks if the called mapping heuristic exists 
00722  * and has been implemented.
00723  *
00724  * @param mapper_type -- the name of the mapping heuristic to check
00725  */
00726 
00727 
00728 int gs_smart_check_if_mapper_exists(char * mapper_type){
00729   int i;
00730   for(i=0;i<nb_mappers;i++){
00731     if(strcmp(mapping_names[i], mapper_type)==0){
00732       return 0;
00733     }
00734   }
00735   return -1;
00736 }
00737 
00738 
00739 
00740 int gs_smart_find_fastest_server(gs_smart_tg_remote_task_node * tg_rem_task_node, 
00741                   gs_smart_netpm * netpm, double *_best_time, int * _best_server_id){
00742 
00743 
00744   int i;
00745   gs_server_t * server;
00746   int valid_assignment;
00747   int nb_valid_mappings_timed=0;
00748   int best_server_id=0;
00749   double this_time, best_time;
00750   int found_mapping;
00751   
00752   /*
00753    * find fastest smart server
00754    */
00755   for(i=0;i<netpm->nb_nodes;i++){
00756     server=netpm->netpm_nodes[i]->server;
00757     if(server->smart){
00758       if(gs_smart_check_if_valid_assignment(tg_rem_task_node,
00759                                  server, &valid_assignment)<0){
00760         ERRPRINTF("SMART : Error checking if a valid assignment\n");
00761         return -1;
00762       } 
00763           
00764       if((valid_assignment) && (nb_valid_mappings_timed==0)){
00765         best_server_id=i;
00766         if(gs_smart_time_tg_task_node_with_c_comm(tg_rem_task_node, server, &best_time)<0){
00767           ERRPRINTF("SMART : Error timing task graph task node\n");
00768           return -1;
00769         }
00770         nb_valid_mappings_timed++;
00771       }
00772       else if ((valid_assignment) && (nb_valid_mappings_timed>0)){
00773         if(gs_smart_time_tg_task_node_with_c_comm(tg_rem_task_node, server, &this_time)<0){
00774           ERRPRINTF("SMART : Error timing task graph task node\n");
00775           return -1;
00776         }
00777         if(this_time<best_time){
00778           best_server_id=i;
00779           best_time=this_time;
00780         }
00781         nb_valid_mappings_timed++;
00782       }
00783     } 
00784   }
00785         
00786   /*
00787    * if no smart servers find fastest standard server
00788    */
00789 
00790   if(nb_valid_mappings_timed==0){
00791     found_mapping=0;
00792     for(i=0;i<netpm->nb_nodes;i++){
00793       server=netpm->netpm_nodes[i]->server;
00794       if(!server->smart){
00795         if(gs_smart_check_if_valid_assignment(tg_rem_task_node,
00796                                  server, &valid_assignment)<0){
00797           ERRPRINTF("SMART : Error checking if a valid assignment\n");
00798           return -1;
00799         }
00800         if((valid_assignment) && (nb_valid_mappings_timed==0)){
00801           best_server_id=i;
00802           if(gs_smart_time_tg_task_node_with_c_comm(tg_rem_task_node, server, &best_time)<0){
00803             ERRPRINTF("SMART : Error timing task graph task node\n");
00804             return -1;
00805           }
00806           nb_valid_mappings_timed++;
00807         }
00808         else if ((valid_assignment) && (nb_valid_mappings_timed>0)){
00809           if(gs_smart_time_tg_task_node_with_c_comm(tg_rem_task_node, server, &this_time)<0){
00810             ERRPRINTF("SMART : Error timing task graph task node\n");
00811             return -1;
00812           }
00813           if(this_time<best_time){
00814             best_server_id=i;
00815             best_time=this_time;
00816           }
00817           nb_valid_mappings_timed++;
00818         }
00819       } 
00820     }
00821   } 
00822   if(nb_valid_mappings_timed==0){
00823     ERRPRINTF("SMART: Error no valid mappings found for task %d %s\n", i, tg_rem_task_node->problem->name);
00824     return -1;
00825   }
00826 
00827   *_best_server_id=best_server_id;
00828   *_best_time=best_time;
00829   return 0;
00830 }
00831 
00832 
00833 
00834 
00835 int gs_smart_get_netpm_link_pos(gs_smart_netpm * netpm, int src_server_id, 
00836                                       int dest_server_id, int * _link_pos){
00837 
00838 
00839   int i;
00840   int link_pos=0;
00841   gs_smart_netpm_node * netpm_node;
00842   for(i=0;i<netpm->nb_nodes ;i++){
00843     netpm_node=netpm->netpm_nodes[i];
00844 
00845     if((netpm_node->server->smart) && (netpm_node->id!=src_server_id)){
00846       link_pos++;
00847     }
00848     if(netpm_node->id==dest_server_id){
00849       break;
00850     }
00851   }
00852   *_link_pos=link_pos;
00853   return 0;
00854 }
00855 
00856 
00857 /*
00858  *
00859  *
00860  *
00861  */
00862 
00863 
00864 
00865 
00866 int gs_smart_greedy_back_link_comm_score(gs_smart_tg * tg, gs_smart_netpm * netpm,  int task_pos, int assn_server_pos, 
00867                                                  int * mapping_vec, double * score){
00868 
00869 
00870   gs_smart_tg_dep_link * tg_bk_link;
00871   gs_smart_tg_task_node * tg_dep_node;
00872   gs_smart_tg_remote_task_node * tg_dep_rem_node;
00873   gs_smart_netpm_link * dep_link;
00874   gs_smart_tg_remote_task_node * tg_rem_node;
00875   gs_smart_netpm_node * netpm_this_server;
00876   gs_smart_netpm_node * netpm_dep_server;
00877   gs_smart_tg_client_node * next_client_node;
00878 
00879   int byte_size=0;
00880   double comm_score, total_score=0.0, bw=0.0;
00881   int  m_vec_dep_pos, dep_server_pos;
00882   int i;
00883       
00884   netpm_this_server=netpm->netpm_nodes[assn_server_pos];
00885   tg_rem_node=tg->task_nodes[task_pos]->tg_rem_task_node;
00886 
00887   /*
00888    * For each back link from this mapped remote task node
00889    * calculate its comm score and add to total score.
00890    * If a dependency is determined to be broken, if either a
00891    * source task or dest task are standard servers then
00892    * calculate the cost of bridge communication.
00893    */ 
00894 
00895   for(i=0;i<tg_rem_node->nb_node_bkwd_links;i++){
00896     tg_bk_link=tg_rem_node->tg_node_bkwrd_link[i];
00897     tg_dep_node=tg_bk_link->obj_node_ptr->tg_obj_bkwrd_link->task_node_ptr;
00898     byte_size=tg_bk_link->obj_node_ptr->byte_size;
00899  
00900     /*
00901      * if this back link of the task node points back 
00902      * to the client then calculate the comm score between mapped server
00903      * to client
00904      */ 
00905     if(tg_dep_node->node_type==GS_SMART_TG_CLIENT_NODE){
00906       bw=netpm_this_server->netpm_links[0]->bw;
00907       comm_score=(double)((byte_size/bw));
00908       total_score=total_score+comm_score;
00909     }
00910     /*
00911      * else if the back link of the task node points back 
00912      * to the another task node then calculate the comm score between mapped 
00913      * server of this destination task to the mapped server of the 
00914      * source task.
00915      */  
00916     else{
00917       tg_dep_rem_node=tg_dep_node->tg_rem_task_node;
00918       m_vec_dep_pos=(tg_dep_node->id/2)-1;
00919       /*
00920        * if the back link points back to a node
00921        * which has previously been mapped to a server.
00922        * In this case the mapping vec element which corresponds to that 
00923        * task node has been given a value which is not -1;
00924        */ 
00925       if(mapping_vec[m_vec_dep_pos]!=-1){
00926         dep_server_pos=mapping_vec[m_vec_dep_pos];
00927         netpm_dep_server=netpm->netpm_nodes[dep_server_pos];
00928        
00929         /*
00930          * If either the dest task node (this) is mapped to a standard server or 
00931          * the source task node (dep) is mapped to standard server then the 
00932          * dependencies between these tasks will be broken.
00933          * Therefore we need to calculate the comm score to transfer bytesize 
00934          * from source node to client. And then from client to
00935          * dest task node(i.e. bridge communication). 
00936          * As opposed to just calculate from source to destination.
00937          */  
00938         if( (!netpm_this_server->server->smart) || (!netpm_dep_server->server->smart) ){
00939           bw=netpm_this_server->netpm_links[0]->bw;
00940           comm_score=(double)((byte_size/bw));
00941           total_score=total_score+comm_score;
00942           bw=netpm_dep_server->netpm_links[0]->bw;
00943           comm_score=(double)((byte_size/bw));
00944           total_score=total_score+comm_score;
00945         } 
00946         /*
00947          * Else just calculate the comm score for direct communication or caching.
00948          */ 
00949         else{
00950           /*
00951            * if the server mapped to source task is the same as server
00952            * mapped to destination task then calculate the score for
00953            * caching the arg.
00954            */ 
00955           if(dep_server_pos==assn_server_pos){
00956             comm_score=(double)((double)(byte_size/(double)100000000));
00957             total_score=total_score+comm_score;
00958           }
00959           /*
00960            * if the server mapped to source task is different to the server
00961            * mapped to destination task then calculate the score for
00962            * direct communication.
00963            */ 
00964           else{
00965             /*
00966              * First determine the network link (dep )which connects the source server 
00967              * to destintation server. 
00968              */ 
00969             int link_pos;
00970             if(gs_smart_get_netpm_link_pos(netpm, assn_server_pos,
00971                                       dep_server_pos, &link_pos)<0){
00972               ERRPRINTF("SMART: Error getting network pm link position\n");
00973               return -1;
00974 
00975             }
00976 
00977  
00978             /* 
00979              * Then calculate the comm score and
00980              * add it to the total score.
00981              */
00982              dep_link=netpm->netpm_nodes[assn_server_pos]->netpm_links[link_pos];
00983              bw=dep_link->bw;
00984              comm_score=(double)((byte_size/bw)); 
00985              total_score=total_score+comm_score;
00986           }
00987         }
00988       }
00989     }
00990   }
00991 //  netpm_this_server=netpm->netpm_nodes[assn_server_pos];
00992   /*
00993    * If the server mapped to this task is not a smart server
00994    * then add the communication cost of sending out back to client
00995    */ 
00996 
00997   if( (!netpm_this_server->server->smart)){
00998     bw=netpm_this_server->netpm_links[0]->bw;
00999     comm_score=(double)((byte_size/bw));
01000     total_score=total_score+comm_score;
01001   }
01002 
01003   /*
01004    * In additionthe communication cost of the back links from the next 
01005    * client node back to this task node are calculated and added total
01006    * score. 
01007    */ 
01008   next_client_node=tg->task_nodes[task_pos+1]->tg_client_node; 
01009   for(i=0;i<next_client_node->nb_node_bkwd_links;i++){
01010     tg_bk_link=next_client_node->tg_node_bkwrd_link[i];
01011     byte_size=tg_bk_link->obj_node_ptr->byte_size;
01012     bw=netpm_this_server->netpm_links[0]->bw;
01013     comm_score=(double)((byte_size/bw));
01014     total_score=total_score+comm_score;
01015   }
01016  
01017   *score=total_score;
01018   return 0;
01019 }
01020 /*
01021  * 
01022  *
01023  *
01024  */
01025 
01026 
01027 int gs_smart_greedy_get_score(gs_smart_tg * tg, gs_smart_netpm * netpm, 
01028                  int *mapping_vec, double * comp_scores, int m_vec_pos, 
01029                  double * _comp_score, double * score){
01030 
01031   int i;
01032   int task_pos;
01033   gs_smart_tg_remote_task_node * tg_rem_node;
01034   gs_smart_tg_task_node *tg_node;
01035   gs_smart_netpm_node * netpm_this_server;
01036   int assn_server_pos;
01037   double total_score=0, comp_score, comm_score;
01038 
01039   /*
01040    *
01041    *
01042    */
01043   double back_link_score=0 ;
01044   double total_comp_score=0 ;
01045   for(i=0;i<tg->nb_rem_nodes;i++){
01046     assn_server_pos=mapping_vec[i];
01047     task_pos=(i+1)*2;
01048 
01049     if(mapping_vec[i]!=-1){
01050       netpm_this_server=netpm->netpm_nodes[assn_server_pos];
01051       tg_node=tg->task_nodes[task_pos];
01052       tg_rem_node=tg_node->tg_rem_task_node;
01053       /*
01054        * gs_smart_greedy_time_back_links
01055        */
01056       if(gs_smart_greedy_back_link_comm_score(tg,netpm, task_pos,assn_server_pos, mapping_vec, &comm_score)<0){
01057         ERRPRINTF("SMART: Error getting the score for back links\n");
01058         return -1;
01059       }
01060       back_link_score=comm_score+back_link_score;
01061 
01062       total_score=comm_score+total_score;
01063 
01064       if(i==m_vec_pos){
01065         if(gs_smart_time_tg_task_node(tg_rem_node, netpm_this_server->server, &comp_score)<0){
01066           ERRPRINTF("SMART : Error gs_smart_time_tg_task_node\n");
01067           return -1;
01068         }
01069         comp_scores[i]=comp_score;
01070         total_comp_score=total_comp_score+comp_score;
01071         total_score=total_score+comp_score;
01072       }
01073       else{
01074         comp_score=comp_scores[i]; 
01075         total_comp_score=total_comp_score+comp_score;
01076         total_score=total_score+comp_score;
01077      }
01078     }
01079   }
01080 /*
01081   LOGPRINTF("ASSIGNING TASK %d TO SERVER %s\n", m_vec_pos, netpm->netpm_nodes[mapping_vec[m_vec_pos]]->server->hostname);
01082   LOGPRINTF("TOTAL BACK LINK SCORE =%f\n", back_link_score);
01083   LOGPRINTF("TOTAL COMP SCORE =%f\n", total_comp_score);
01084   LOGPRINTF("TOTAL OVERALL SCORE =%f\n", total_score);
01085 */
01086   *_comp_score=comp_score;
01087   *score=total_score;
01088   return 0;
01089 }
01090 
01091 
01092 int gs_smart_greedy_best_server(gs_smart_tg * tg, gs_smart_netpm * netpm, 
01093                                 int * mapping_vec, double * comp_scores, 
01094                                 int m_vec_pos, double * _comp_score, 
01095                                 int *_nb_valid_assign){
01096 
01097   gs_smart_tg_remote_task_node * tg_rem_task_node;
01098   gs_smart_tg_task_node *tg_node;
01099   gs_server_t * mapped_server;
01100 
01101   int i=0;
01102   double this_score, best_score=0;
01103   int best_pos=0;
01104 
01105   /*
01106    * position in task graph of the task currently getting assigned
01107    */ 
01108   int task_pos;  
01109 
01110   double this_comp_score, best_comp_score=0;
01111   int nb_valid_assign=0;
01112   int valid_assignment;
01113   int server_pos;
01114   task_pos=(m_vec_pos+1)*2;
01115   tg_node=tg->task_nodes[task_pos];
01116   tg_rem_task_node=tg_node->tg_rem_task_node;
01117   for(i=0;i<netpm->nb_nodes;i++){
01118     mapping_vec[m_vec_pos]=i;
01119     server_pos=mapping_vec[m_vec_pos];
01120     mapped_server=netpm->netpm_nodes[server_pos]->server;
01121  
01122     if(gs_smart_check_if_valid_assignment(tg_rem_task_node, mapped_server, &valid_assignment)<0){
01123       ERRPRINTF("SMART : Error checking if it is a valid assignment\n");
01124       return -1;
01125     }
01126     if(valid_assignment==-1){
01127       break;
01128     }
01129 
01130     nb_valid_assign++;
01131 
01132     if(gs_smart_greedy_get_score(tg, netpm, mapping_vec, comp_scores, m_vec_pos, &this_comp_score, &this_score)<0){
01133       ERRPRINTF("SMART : Error gs_smart_greedy_get_score\n");
01134       return -1;
01135     }
01136 
01137 
01138     if(i==0){
01139       best_comp_score=this_comp_score;
01140       best_score=this_score;
01141       best_pos=i;
01142     }
01143     else{
01144       if(this_score<best_score){
01145         best_comp_score=this_comp_score;
01146         best_score=this_score;
01147         best_pos=i;
01148       }
01149     }
01150   }
01151   *_comp_score=best_comp_score; 
01152   *_nb_valid_assign=nb_valid_assign;
01153   mapping_vec[m_vec_pos]=best_pos;
01154   return 0;
01155 
01156 }
01157 
01158 
01159 
01160 
01161 
01162 int gs_smart_rank_group_tasks(gs_smart_tg * tg, int start_i, int end_i, int nb_nbl_group , int * ranked_tasks){
01163   gs_smart_tg_task_node * task_node;
01164   gs_smart_tg_remote_task_node * tg_rem_task_node=NULL;
01165   gs_smart_tg_remote_task_node * tg_ranked_task_node;
01166   int i, j, k;
01167 
01168   for(i=start_i; i<=end_i; i++){
01169     task_node=tg->task_nodes[i];
01170     if(task_node->node_type==GS_SMART_TG_REM_TASK_NODE){
01171       tg_rem_task_node=task_node->tg_rem_task_node;
01172       for(j=0;j<nb_nbl_group;j++){
01173         if(ranked_tasks[j]==0){
01174           ranked_tasks[j]=i;
01175           break;
01176         }
01177         else{
01178           int task_pos=ranked_tasks[j];
01179           tg_ranked_task_node=tg->task_nodes[task_pos]->tg_rem_task_node;
01180           int tmp_task_pos_1, tmp_task_pos_2;
01181           if(tg_rem_task_node->nb_flops > tg_ranked_task_node->nb_flops){
01182             tmp_task_pos_1=ranked_tasks[j];                
01183             ranked_tasks[j]=i;
01184             for(k=j+1;k<nb_nbl_group;k++){
01185               if(ranked_tasks[k]==0){
01186                 ranked_tasks[k]=tmp_task_pos_1;
01187                 break;
01188               }
01189               else{
01190                 tmp_task_pos_2=ranked_tasks[k];
01191                 ranked_tasks[k]=tmp_task_pos_1;
01192                 tmp_task_pos_1=tmp_task_pos_2;    
01193               }              
01194             }
01195           }
01196           else if(tg_rem_task_node->nb_flops == tg_ranked_task_node->nb_flops){
01197             tmp_task_pos_1=ranked_tasks[j];                
01198             ranked_tasks[j]=i;
01199             for(k=j+1;k<nb_nbl_group;k++){
01200               if(ranked_tasks[k]==0){
01201                 ranked_tasks[k]=tmp_task_pos_1;
01202                 break;
01203               }
01204               else{
01205                 tmp_task_pos_2=ranked_tasks[k];
01206                 ranked_tasks[k]=tmp_task_pos_1;
01207                 tmp_task_pos_1=tmp_task_pos_2;    
01208               }              
01209             }
01210           }
01211 
01212         }
01213       }     
01214     }              
01215   }
01216 
01217 
01218 
01219 
01220   return 0;
01221 }
01222 
01223 
01224 /*
01225  *
01226  *
01227  */
01228 
01229 
01230 
01231 int gs_smart_map_greedy_group(gs_smart_tg * tg, gs_smart_netpm * netpm, 
01232        int start_i, int end_i, int nb_nbl_group , int rem_task_cnt, int * mapping_vec){
01233 
01234   gs_smart_tg_task_node * task_node;
01235   gs_smart_tg_remote_task_node * tg_rem_task_node=NULL;
01236   gs_server_t * mapped_server;
01237 
01238 
01239   int nb_valid_assign;
01240 
01241   /*
01242    * array stores the rank of each task
01243    * the rank indicates its relative computation load in the group
01244    */ 
01245   int * ranked_tasks;
01246 
01247   /*
01248    *  stores computational score of each previously mapped task in group 
01249    */ 
01250   double * comp_scores;
01251 
01252 
01253   double comp_score;
01254   int best_server_id=0, i, m_vec_pos;
01255 
01256   /*
01257    * keeps track of the task graph position of the current task being mapped 
01258    */
01259   int task_pos; 
01260 
01261 
01262   comp_scores= (double *)calloc(tg->nb_rem_nodes, sizeof(double));
01263   ranked_tasks = (int *)calloc(nb_nbl_group, sizeof(int));
01264 
01265   /*
01266    * This function returns a vector which ranks each task in the group
01267    * according to their computation load.
01268    */ 
01269 
01270   if(gs_smart_rank_group_tasks(tg, start_i, end_i, nb_nbl_group , ranked_tasks)<0){
01271     ERRPRINTF("SMART : Error ranking group of tasks\n");
01272     return -1;
01273   }
01274 
01275 
01276   for(i=0;i<nb_nbl_group;i++){
01277     task_pos=ranked_tasks[i];
01278     m_vec_pos=(rem_task_cnt+nb_nbl_group)-1-i;
01279     task_node=tg->task_nodes[task_pos];
01280     tg_rem_task_node=task_node->tg_rem_task_node;
01281     if(gs_smart_greedy_best_server(tg, netpm, mapping_vec, comp_scores, m_vec_pos, &comp_score, &nb_valid_assign)<0){
01282       ERRPRINTF("SMART : Error gs_smart_greedy_best_server\n");
01283       return -1;
01284     }
01285     if(nb_valid_assign<1){
01286       ERRPRINTF("SMART : Error, nndle->o valid assignments were found for task %s\n",tg_rem_task_node->problem->name);
01287       ERRPRINTF("SMART : No servers in the network could execute this task\n");
01288       return -1;
01289     }
01290 
01291     best_server_id=mapping_vec[m_vec_pos];
01292     mapped_server=netpm->netpm_nodes[best_server_id]->server;
01293     mapped_server->task_workload =(mapped_server->task_workload+(10000*comp_score) );
01294   }
01295 
01296   for(i=0;i<netpm->nb_nodes;i++){
01297     netpm->netpm_nodes[i]->server->task_workload=0;
01298   }
01299   return 0;
01300 }
01301 /*
01302  *  The basic mapping heuristic is a non-iterative mapping heuristic.
01303  *  It maps each task one at a time. It finds the fastest smart enabled
01304  *  server that can execute each task.  When a nonblocking task gets 
01305  *  assigned to a server, the server's workload is increased. 
01306  *  This provides a basic method for load balancing non-blocking tasks.
01307  *  If there are no smart servers that can execute a specific task
01308  *  then this task will be assigned a server that is not smart enabled.
01309  *  Once the tasks have been assigned to servers, the mapping graph is
01310  *  generated with the best communication scheme, based on the dependencies
01311  *  between tasks and whether the servers assigned are smart servers or not.
01312  *
01313  *  This is a basic heuristic which generates a mapping solution quickly 
01314  *  and provides speed up due to direct communication between servers.
01315  *  However since it maps tasks individually it does not fully exploit the 
01316  *  potential of mapping tasks collectively such as improved load balancing
01317  *  of computation.
01318  *
01319  *  @param tg - (in) Task graph of a the mapped group of tasks
01320  *  @param netpm -- (in) Network performance model
01321  *  @param best_mg -- (out) Mapping solution generated by mapping heuristic 
01322  *
01323  */
01324 
01325 int gs_smart_greedy_map(gs_smart_tg * tg, gs_smart_netpm * netpm, gs_smart_mg ** _best_mg){
01326   gs_smart_mg * best_mg;
01327   gs_smart_tg_task_node * task_node;
01328   gs_smart_tg_remote_task_node * tg_rem_task_node;
01329   int * mapping_vec;  
01330   int i, nb_rem_tasks, rem_task_cnt;
01331   int nbl_task_called;
01332   double est_time;
01333   int valid_graph;
01334   int best_server_id=0;
01335   int * assigned_tasks;
01336 
01337   int start_i=0, end_i=0;
01338   nb_rem_tasks=tg->nb_rem_nodes;
01339   best_mg = (gs_smart_mg * )calloc(1, sizeof(gs_smart_mg));
01340   mapping_vec = (int *)calloc(nb_rem_tasks, sizeof(int));
01341   assigned_tasks = (int *)calloc(nb_rem_tasks, sizeof(int));
01342 
01343   
01344   for(i=0;i<nb_rem_tasks;i++){
01345     mapping_vec[i]=-1;
01346   }
01347  
01348   rem_task_cnt=0;
01349   nbl_task_called=0;
01350 
01351   nbl_task_called=0;
01352   rem_task_cnt=0;
01353   i=0;
01354   task_node=tg->task_nodes[i];
01355   int nb_nbl_group=0;
01356   start_i=i;
01357   while(i<tg->nb_nodes){
01358     task_node=tg->task_nodes[i];
01359     if(task_node->node_type==GS_SMART_TG_REM_TASK_NODE){
01360       tg_rem_task_node=task_node->tg_rem_task_node;
01361       if(tg_rem_task_node->blocking){
01362         end_i=i;
01363         if(nb_nbl_group==0){
01364           if( gs_smart_find_fastest_server(tg_rem_task_node,netpm, 
01365                                               &est_time, &best_server_id)<0){
01366             ERRPRINTF("SMART : Error finding fastest server\n");
01367             return -1;
01368           }
01369           mapping_vec[rem_task_cnt]=best_server_id;
01370           rem_task_cnt++;
01371         }
01372         else{
01373           if(gs_smart_map_greedy_group(tg, netpm, start_i, end_i, nb_nbl_group,
01374                                                     rem_task_cnt, mapping_vec)){
01375             ERRPRINTF("Error mapping greedy group\n");
01376             return -1;
01377           }
01378           rem_task_cnt=rem_task_cnt+nb_nbl_group;
01379           if( gs_smart_find_fastest_server(tg_rem_task_node,netpm, 
01380                                                  &est_time, &best_server_id)<0){
01381             ERRPRINTF("SMART : Error finding fastest server\n");
01382             return -1;
01383           }
01384           mapping_vec[rem_task_cnt]=best_server_id;
01385           rem_task_cnt++;
01386 
01387         }
01388         nb_nbl_group=0;
01389         start_i=end_i;
01390       }
01391       else{
01392         nb_nbl_group++;
01393       }
01394       end_i=i;
01395     }
01396     i++;
01397   }
01398   if(nb_nbl_group>0){
01399     start_i=start_i+2;
01400     if(gs_smart_map_greedy_group(tg, netpm, start_i, end_i, nb_nbl_group,
01401                                                     rem_task_cnt, mapping_vec)){
01402       ERRPRINTF("Error mapping greedy group\n");
01403       return -1;
01404     }
01405   }
01406   rem_task_cnt=rem_task_cnt+nb_nbl_group;
01407 
01408 /*
01409   mapping_vec[0]=2;
01410   mapping_vec[1]=2;
01411   mapping_vec[2]=2;
01412   mapping_vec[3]=2;
01413   mapping_vec[4]=2;
01414 */
01415   if(gs_smart_generate_mapping_graph(tg, netpm, mapping_vec, best_mg, &valid_graph)<0){
01416     ERRPRINTF("SMART: Error generating mapping graph\n");
01417     return -1;
01418   }
01419   if(gs_smart_mg_create_argument_file_names(best_mg)<0){
01420     ERRPRINTF("SMART : Error creating mapping graph argument file names\n");
01421     return -1;
01422   }
01423 
01424   if(!valid_graph){
01425     ERRPRINTF("SMART : The mapping graph generated is invalid!\n");
01426     return -1;
01427   }
01428   *_best_mg=best_mg;
01429   return 0;
01430 }
01431 
01432 
01433 
01434 
01435 
01436 
01437 
01438 
01439 
01440 
01441 
01442 double
01443 total_time(const struct timeval* t0, const struct timeval* t1)
01444 {
01445   double ret = t1->tv_sec - t0->tv_sec;
01446   double uret = t1->tv_usec - t0->tv_usec;
01447   return ret + uret / 1E6;
01448 }
01449 
01450 
01451 
01452 
01453 
01454 
01455 
01456 
01457 
01458 
01459 #endif