src/and/Mapping/Maheve.java

   1 package and.Mapping;
   2
   3 import java.util.ArrayList;
   4
   5
   6
   7 public class Maheve extends Algo
   8 {
   9         private static final long serialVersionUID = 1L;
  10
  11         private static int minNode ;
  12         private static int nbSave ;
  13
  14         private double hd ;
  15         private ArrayList<Cluster> sortedCluster = null ;
  16         private ArrayList<GTask> tasks = null ;
  17
  18
  19         /**
  20          * Empty default constructor.
  21          */
  22         public Maheve()
  23         {
  24                 super() ;
  25                 name = "MAHEVE_2" ;
  26                 minNode = 5 ;
  27                 nbSave = 2 ;
  28                 sortedCluster = new ArrayList<Cluster>() ;
  29         }
  30
  31
  32         /**
  33          * Constructor of this algorithm, which takes into parameter
  34          * the application graph, the grid architecture, and the correction
  35          * parameter which indicates the threshold of the heterogeneity degree.
  36          * @param _gr The application graph
  37          * @param _gl The grid architecture
  38          * @param _threshold The heterogeneity threshold
  39          */
  40         public Maheve( Graph _gr, Grid _gl )
  41         {
  42                 super( _gr, _gl ) ;
  43
  44                 hd = 0 ;
  45                 sortedCluster = new ArrayList<Cluster>() ;
  46                 tasks = new ArrayList<GTask>() ;
  47                 name = "MAHEVE_2" ;
  48         }
  49
  50
  51         /**
  52          * Setter for the amount of nodes to preserve on each cluster
  53          * for the fault tolerance (should be 0 in an environment without fault).
  54          * @param _nbSave The amount of nodes to preserve
  55          */
  56         public void setNbSave( int _nbSave )
  57         {
  58                 if( _nbSave >= 0 )
  59                 {
  60                         nbSave = _nbSave ;
  61                 }
  62         }
  63
  64
  65         /**
  66          * Getter to retrieving the amount of nodes preserved for fault tolerance.
  67          * @return The amount of preserved nodes
  68          */
  69         public int getNbSave()
  70         {
  71                 return nbSave ;
  72         }
  73
  74
  75         /**
  76          * Setter for the minimum amount of nodes which should be present in
  77          * a cluster to consider this latter in the mapping process.
  78          * @param _minNode The minimum amount of nodes a cluster should have to be
  79          * considered
  80          */
  81         public void setMinNode( int _minNode )
  82         {
  83                 if( _minNode >= 0 )
  84                 {
  85                         minNode = _minNode ;
  86                 }
  87         }
  88
  89
  90         /**
  91          * Getter to retrieve the minimum amount of nodes a cluster should have
  92          * to be considered in the mapping process.
  93          * @return The minimum amount of nodes a cluster should have to be
  94          * considered
  95          */
  96         public int getMinNode()
  97         {
  98                 return minNode ;
  99         }
 100
 101
 102         @Override
 103         public void map() {
 104                 /** If the mapping is possible ... **/
 105                 if( ( gr != null ) && ( gr.getNbGTask() <= gl.getNbGNode() ) )
 106                 {
 107                         System.out.println( "******************************************" ) ;
 108                         System.out.println( "* Launching the MAHEVE Mapping algorithm *" ) ;
 109                         System.out.println( "******************************************\n\n" ) ;
 110
 111                         /** Local variables **/
 112                         ArrayList<GNode> used = null ;
 113
 114                         /** Initialization of heterogeneity degree **/
 115                         hd = gl.getHeterogenityDegre() ;
 116
 117
 118                         /** Ordering clusters according to their real power **/
 119                         updateSortedClusters() ;
 120
 121                         /** Searching the corresponding nodes **/
 122                         used = searchNodes( gr.getNbGTask() ) ;
 123
 124                         if( used == null || used.size() == 0 )
 125                         {
 126                                 System.err.println( "No node returned!" ) ;
 127                                 return ;
 128                         }
 129
 130
 131                         /** Ordering tasks **/
 132                         orderTasks() ;
 133
 134                         if( tasks == null || tasks.size() == 0 )
 135                         {
 136                                 System.err.println( "Unable to retrieve tasks to be mapped on!" ) ;
 137                                 return ;
 138                         }
 139
 140
 141                         /** Save the Mapping **/
 142                         for( int i = 0 ; i < tasks.size() ; i++ )
 143                         {
 144                                 mp.addMapping( new Association( used.get( i ), tasks.get( i ) ) ) ;
 145                         }
 146
 147                 } else {
 148                         System.err.println( "\n\n!!! Unable to map application!\n\n" ) ;
 149                         return ;
 150                 }
 151         }
 152
 153
 154         private void orderTasks()
 155         {
 156                 ArrayList<GTask> l1 = sortTasks() ;
 157
 158                 ArrayList<Integer> st = new ArrayList<Integer>() ;
 159
 160                 if( l1 != null && l1.size() > 0 )
 161                 {
 162                         ArrayList<GTask> l2 = new ArrayList<GTask>() ;
 163                         ArrayList<GTask> tmp = new ArrayList<GTask>() ;
 164
 165                         while( l1.size() > 0 )
 166                         {
 167                                 if( l2.size() == 0 )
 168                                 {
 169                                         l2.add( l1.get( 0 ) ) ;
 170                                         st.add( l1.get( 0 ).getNum() ) ;
 171                                 }
 172
 173                                 while( l2.size() > 0 )
 174                                 {
 175                                         l1.remove( l2.get( 0 ) ) ;
 176                                         tmp = addTask( l2.remove( 0 ), l1, st ) ;
 177
 178                                         for( int i = 0 ; i < tmp.size() ; i++ )
 179                                         {
 180                                                 l2.add( tmp.get( i ) ) ;
 181                                                 st.add( tmp.get( i ).getNum() ) ;
 182                                         }
 183                                 }
 184                         }
 185                 }
 186         }
 187
 188
 189         private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar,
 190                                                                          ArrayList<Integer> _st )
 191         {
 192
 193                 ArrayList<GTask> ret = null ;
 194
 195                 if( _gt != null && _ar != null )
 196                 {
 197                         ret = new ArrayList<GTask>() ;
 198
 199                         // ** Adding the task in the main list ** //
 200                         tasks.add( _gt ) ;
 201
 202                         // ** Searching its dependencies ** //
 203                         int nbDep = (int) (_gt.getNbDep() * (1.0 - hd)) ;
 204                         int cmpt = 0 ;
 205                         int num = 0 ;
 206
 207                         ArrayList<Integer> dep = new ArrayList<Integer>() ;
 208
 209                         // ** Retrieving dependencies and eliminating tasks already treated
 210                         // ** or in instance to be treated. **//
 211                         for( int i = 0 ; i < _gt.getDependencies().size() ; i++ )
 212                         {
 213                                 if( ! _st.contains( _gt.getDependencies().get( i ).getNum() ) )
 214                                 {
 215                                         dep.add( _gt.getDependencies().get( i ).getNum() ) ;
 216                                 }
 217                         }
 218
 219
 220                         // ** Searching dependencies in sorted tasks list ** //
 221                         for( int i = 0 ; i < _ar.size() ; i++ )
 222                         {
 223                                 num = _ar.get( i ).getNum() ;
 224
 225                                 if( dep.contains( num ) )
 226                                 {
 227 //                              for( int j = 0 ; j < dep.size() ; j++ )
 228 //                              {
 229 //                                      if( num == dep.get( j ) )
 230 //                                      {
 231                                                 ret.add( _ar.remove( i ) ) ;
 232                                                 cmpt++ ;
 233 //                                              dep.remove( j ) ;
 234 //                                              break ;
 235 //                                      }
 236                                 }
 237
 238                                 if( cmpt == nbDep )
 239                                 {
 240                                         break ;
 241                                 }
 242                         }
 243                 }
 244
 245                 return ret;
 246         }
 247
 248
 249         private ArrayList<GTask> sortTasks()
 250         {
 251                 ArrayList<GTask> ret = null ;
 252
 253                 ArrayList<GTask> tmp = gr.getGraph() ;
 254
 255                 if( tmp != null && tmp.size() > 0 )
 256                 {
 257                         ret = new ArrayList<GTask>() ;
 258
 259                         ArrayList<Double> mt = new ArrayList<Double>() ;
 260
 261                         double W, D, MT ;
 262                         boolean ok = false ;
 263
 264                         for( int i = 0 ; i < tmp.size() ; i++ )
 265                         {
 266                                 W = tmp.get( i ).getWeight() ;
 267                                 D = tmp.get( i ).getNbDep() ;
 268
 269                                 ok = false ;
 270
 271                                 MT = Math.pow( W, hd ) * Math.pow( D, ( 1.0 - hd) ) ;
 272
 273                                 if( ret.size() == 0 )
 274                                 {
 275                                         ret.add( tmp.get( i ) ) ;
 276                                         mt.add( MT ) ;
 277                                 } else {
 278                                         for( int j = 0 ; j < ret.size() ; j++ )
 279                                         {
 280                                                 if( MT > mt.get( j ) )
 281                                                 {
 282                                                         ret.add( j, tmp.get( i ) ) ;
 283                                                         mt.add( j, MT ) ;
 284
 285                                                         ok = true ;
 286                                                         break ;
 287                                                 }
 288                                         }
 289
 290                                         if( ! ok )
 291                                         {
 292                                                 ret.add( tmp.get( i ) ) ;
 293                                                 mt.add( MT ) ;
 294                                         }
 295                                 }
 296                         }
 297                 }
 298
 299                 return ret ;
 300         }
 301
 302
 303         private ArrayList<GNode> searchNodes( int _nbTask )
 304         {
 305                 ArrayList<GNode> ret = null ;
 306
 307                 if( _nbTask > 0 )
 308                 {
 309                         ret = new ArrayList<GNode>() ;
 310                         int nbFound = 0 ;
 311                         int max = 0 ;
 312                         GNode g = null ;
 313                         boolean changeParameter = false ;
 314
 315                         while( nbFound < _nbTask )
 316                         {
 317                                 int i = 0 ;
 318
 319                                 for( i = 0 ; i < sortedCluster.size() ; i++ )
 320                                 {
 321                                         /** If there is enough nodes ... **/
 322                                         if( sortedCluster.get( i ).getNbFreeNodes() >= minNode )
 323                                         {
 324                                                 max = 0 ;
 325                                                 sortedCluster.get( i ).initMoreGNode() ;
 326
 327                                                 max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ;
 328
 329                                                 for( int j = 0 ; j < max ; j++ )
 330                                                 {
 331                                                         g = sortedCluster.get( i ).moreGNode() ;
 332                                                         ret.add( g ) ;
 333
 334                                                         nbFound ++ ;
 335
 336                                                         if( nbFound >= _nbTask )
 337                                                                 break ;
 338                                                 }
 339                                         }
 340
 341                                         if( nbFound >= _nbTask )
 342                                                 break ;
 343                                 }
 344
 345                                 if( i == sortedCluster.size() && nbFound < _nbTask )
 346                                 {
 347                                         changeParameter = true ;
 348                                         minNode-- ;
 349                                 }
 350                         }
 351
 352                         if( changeParameter )
 353                         {
 354                                 System.err.println( "The parameter \"minNode\" has been reduced " +
 355                                                 "to allow the mapping process to be done." ) ;
 356                         }
 357                 }
 358
 359                 return ret ;
 360         }
 361
 362
 363         /**
 364          * Sort clusters according to the heterogeneity degree of the platform and
 365          * the eventual application's threshold.
 366          */
 367         private void updateSortedClusters()
 368         {
 369                 if( gl != null )
 370                 {
 371                         /** Purging the local list **/
 372                         sortedCluster = null ;
 373                         sortedCluster = new ArrayList<Cluster>() ;
 374
 375                         ArrayList<Double> calcMark = new ArrayList<Double>() ;
 376
 377                         double hd_g = gl.getHeterogenityDegre() ;
 378
 379                         /* Correction of hd */
 380                         hd =  calcNewHd( hd_g ) ;
 381
 382                         System.out.println("Corrected hd value: " + hd + " (" + hd_g + ")" ) ;
 383
 384                         /** Sorting clusters **/
 385                         ArrayList<Cluster> tmp = gl.getClusters() ;
 386
 387                         boolean ok ;
 388
 389                         double calcLoc = 0 ;
 390                         double normN ;
 391                         double normP ;
 392
 393                         double Nm = 0, Pm = 0 ;
 394
 395                         for( int i = 0 ; i < tmp.size() ; i++ )
 396                         {
 397                                 Nm += tmp.get( i ).getNbFreeNodes() ;
 398                                 Pm += tmp.get( i ).getAvgAvailablePower() ;
 399                         }
 400
 401                         for( int i = 0 ; i < tmp.size() ; i++ )
 402                         {
 403                                 normN = tmp.get( i ).getNbFreeNodes() * 100 / Nm ;
 404                                 normP = tmp.get( i ).getAvgAvailablePower() * 100 / Pm ;
 405
 406                                 /** The magic formula :P **/
 407                                 calcLoc = Math.pow( (normP * hd), 2) +
 408                                                   Math.pow( (normN * (1 - hd)), 2 ) ;
 409
 410                                 ok = false ;
 411
 412                                 if( sortedCluster.size() == 0 )
 413                                 {
 414                                         sortedCluster.add( tmp.get( i ) ) ;
 415                                         calcMark.add( calcLoc ) ;
 416                                 } else {
 417
 418                                         for( int j = 0 ; j < sortedCluster.size() ; j++ )
 419                                         {
 420                                                 if( calcLoc > calcMark.get( j ) )
 421                                                 {
 422                                                         sortedCluster.add( j, tmp.get( i ) ) ;
 423                                                         calcMark.add( j, calcLoc ) ;
 424                                                         ok = true ;
 425                                                         break ;
 426                                                 }
 427                                         }
 428
 429                                         if( ! ok )
 430                                         {
 431                                                 sortedCluster.add( tmp.get( i ) ) ;
 432                                                 calcMark.add( calcLoc ) ;
 433                                         }
 434                                 }
 435                         }
 436                 }
 437         }
 438
 439
 440         /**
 441          * Compute the new value of hd, by taking care of the application
 442          * and execution architecture characteristics.
 443          * @param hd_g Original heterogeneity degree
 444          * @return The new (corrected) heterogeneity degree
 445          */
 446         private double calcNewHd( double hd_g )
 447         {
 448                 /* Variables */
 449                 double nhd = 0 ;
 450
 451                 double nbTask = gr.getNbGTask() ;
 452                 double nbDep = gr.getMaxDep() ;
 453                 double maxNodes = gl.getMaxClusterNode() ;
 454
 455                 /* Computation */
 456                 nhd = hd_g / ( 10 * ( (nbDep / nbTask) + (nbDep / maxNodes) ) ) ;
 457
 458                 return nhd ;
 459         }
 460
 461
 462         @Override
 463         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 464         {
 465                 GNode ret = null ;
 466
 467                 /** If something has to be done **/
 468                 if( _dead != null )
 469                 {
 470                         boolean ok = false ;
 471                         /** Any place on the same cluster ? **/
 472                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 473                         {
 474                                 Cluster cl = null ;
 475
 476                                 int id = gl.getClusterOfNode( _dead ) ;
 477
 478                                 if( id != -1 )
 479                                 {
 480                                         cl = gl.getClusters().get(id) ;
 481
 482                                         if( cl.getNbFreeNodes() > 0 )
 483                                         {
 484                                                 ret = cl.nextGNode() ;
 485                                                 ok = true ;
 486                                         }
 487                                 } else {
 488                                         System.err.println( "Cluster not found!" ) ;
 489                                 }
 490                         }
 491
 492                         /** If there is no more place, try other clusters **/
 493                         if( ! ok )
 494                         {
 495                                 updateSortedClusters() ;
 496
 497                                 for( int i = 0 ; i < sortedCluster.size() ; i++ )
 498                                 {
 499                                         if( sortedCluster.get( i ).getNbFreeNodes() > 0 )
 500                                         {
 501                                                 ret = sortedCluster.get( i ).nextGNode() ;
 502                                                 ok = true ;
 503                                                 break ;
 504                                         }
 505                                 }
 506                         }
 507
 508                         nb_fault++ ;
 509                 }
 510
 511                 return ret ;
 512         }
 513
 514
 515         @Override
 516         public GNode getOtherGNode( ArrayList<GNode> _ag )
 517         {
 518                 GNode ret = null ;
 519
 520                 /** Searching the cluster which has the more free nodes **/
 521                 int pos = -1, max = 0, cur = 0 ;
 522                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 523                 {
 524                         cur = gl.getClusters().get( i ).getNbFreeNodes() ;
 525                         if( cur > max)
 526                         {
 527                                 pos = i ;
 528                                 max = cur ;
 529                         }
 530                 }
 531
 532                 ret = gl.getClusters().get( pos ).nextGNode() ;
 533
 534                 return ret ;
 535         }
 536
 537
 538         @Override
 539         public boolean setParams(Object[] _params) {
 540                 return true ;
 541         }
 542
 543 }
 544
 545 /** La programmation est un art, respectons ceux qui la pratiquent !! **/