src/and/Mapping/Maheve.java

   1 package and.Mapping;
   2
   3 import java.util.ArrayList;
   4 import java.util.Iterator;
   5
   6
   7
   8 public class Maheve extends Algo
   9 {
  10         private static final long serialVersionUID = 1L;
  11
  12         private static int minNode ;
  13         private static int nbSave ;
  14
  15         private double hd ;
  16         private ArrayList<Cluster> sortedCluster = null ;
  17         private ArrayList<GTask> tasks = null ;
  18
  19
  20         /**
  21          * Empty default constructor.
  22          */
  23         public Maheve()
  24         {
  25                 super() ;
  26                 name = "MAHEVE_3" ;
  27                 minNode = 5 ;
  28                 nbSave = 2 ;
  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_3" ;
  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.getNbFreenodes() ) )
 106                 {
 107                         System.out.println( "******************************************" ) ;
 108                         System.out.println( "* Launching the MAHEVE Mapping algorithm *" ) ;
 109                         System.out.println( "******************************************\n\n" ) ;
 110
 111                         /** Initialization of heterogeneity degree (hd) **/
 112                         double hd_g = gl.getHeterogenityDegre() ;
 113
 114                         /* Correction of hd */
 115                         // correction is function of the application and platform characteristics
 116                         hd = calcNewHd( hd_g ) ;
 117
 118                         System.out.println( "Corrected hd value: " + hd + " (" + hd_g + ")" ) ;
 119
 120
 121                         /** Ordering clusters according to their real power **/
 122                         updateSortedClusters() ;
 123
 124
 125                         /** Ordering tasks **/
 126                         orderTasks() ;
 127
 128                         if( tasks == null || tasks.size() == 0 )
 129                         {
 130                                 System.err.println( "Unable to retrieve tasks to be mapped on!" ) ;
 131                                 return ;
 132                         }
 133
 134                         /** Mapping of tasks on nodes/clusters **/
 135                         mapping() ;
 136
 137                 } else {
 138                         System.err.println( "\n\n!!! Unable to map application!\n\n" ) ;
 139                         return ;
 140                 }
 141         }
 142
 143
 144         private void mapping()
 145         {
 146                 int ind = 0 ;
 147                 boolean ok, change ;
 148                 int div = 1 ;
 149                 int nbDep ;
 150
 151                 ArrayList<Cluster> cl = new ArrayList<Cluster>() ;
 152
 153                 for( int i = 0 ; i < sortedCluster.size() ; i++ )
 154                 {
 155                         cl.add( sortedCluster.get( i ).clone() ) ;
 156                 }
 157
 158                 for( int i = 0 ; i < tasks.size() ; i++ )
 159                 {
 160                         ok = false ;
 161
 162                         while( ! ok )
 163                         {
 164                                 nbDep = (int) ( tasks.get( i ).getNbDep() * (1.0 - hd) / div ) + 1 ;
 165
 166                                 change = false ;
 167
 168                                 if( (cl.get( ind ).getNbFreeNodes() - nbSave) >= nbDep )
 169                                 {
 170                                         GNode gn = cl.get( ind ).getBetterFreeGNode() ;
 171                                         if( gn != null )
 172                                         {
 173                                                 cl.get( ind ).setGNodeStatus( gn, true ) ;
 174                                                 mp.addMapping( (gl.getCluster( cl.get( ind ).getName()).exists( gn )) , tasks.get( i ) ) ;
 175                                                 ok = true ;
 176                                         } else {
 177                                                 change = true ;
 178                                         }
 179                                 } else {
 180                                         change = true ;
 181                                 }
 182
 183                                 if( change )
 184                                 {
 185                                         ind++ ;
 186
 187                                         if( ind == cl.size() )
 188                                         {
 189                                                 ind = 0 ;
 190                                                 div++ ;
 191                                         }
 192                                 }
 193                         }
 194                 }
 195         }
 196
 197
 198         private void orderTasks()
 199         {
 200                 ArrayList<GTask> l1 = sortTasks() ;
 201
 202                 ArrayList<Integer> st = new ArrayList<Integer>() ;
 203
 204                 if( l1 != null && l1.size() > 0 )
 205                 {
 206                         ArrayList<GTask> l2 = new ArrayList<GTask>() ;
 207                         ArrayList<GTask> tmp = new ArrayList<GTask>() ;
 208
 209                         while( l1.size() > 0 )
 210                         {
 211                                 if( l2.size() == 0 )
 212                                 {
 213                                         l2.add( l1.get( 0 ) ) ;
 214                                         st.add( l1.get( 0 ).getNum() ) ;
 215                                 }
 216
 217                                 while( l2.size() > 0 )
 218                                 {
 219                                         l1.remove( l2.get( 0 ) ) ;
 220                                         tmp = addTask( l2.remove( 0 ), l1, st ) ;
 221
 222                                         for( int i = 0 ; i < tmp.size() ; i++ )
 223                                         {
 224                                                 l2.add( tmp.get( i ) ) ;
 225                                                 st.add( tmp.get( i ).getNum() ) ;
 226                                         }
 227                                 }
 228                         }
 229                 }
 230         }
 231
 232
 233         private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar,
 234                                                                          ArrayList<Integer> _st )
 235         {
 236
 237                 ArrayList<GTask> ret = null ;
 238
 239                 if( _gt != null && _ar != null )
 240                 {
 241                         ret = new ArrayList<GTask>() ;
 242
 243                         // ** Adding the task in the main list ** //
 244                         tasks.add( _gt ) ;
 245
 246                         // ** Searching its dependencies ** //
 247                         int nbDep = (int) ( _gt.getNbDep() * (1.0 - hd) + 1 ) ;
 248                         int cmpt = 0 ;
 249                         int num = 0 ;
 250
 251                         ArrayList<Integer> dep = new ArrayList<Integer>() ;
 252
 253                         // ** Retrieving dependencies and eliminating tasks already treated
 254                         // ** or in instance to be treated. **//
 255                         for( int i = 0 ; i < _gt.getDependencies().size() ; i++ )
 256                         {
 257                                 if( ! _st.contains( _gt.getDependencies().get( i ).getNum() ) )
 258                                 {
 259                                         dep.add( _gt.getDependencies().get( i ).getNum() ) ;
 260                                 }
 261                         }
 262
 263
 264                         // ** Searching dependencies in sorted tasks list ** //
 265                         Iterator<GTask> iter = _ar.iterator() ;
 266                         while( iter.hasNext() )
 267                         {
 268                                 GTask gt = iter.next() ;
 269                                 num = gt.getNum() ;
 270
 271                                 if( dep.contains( num ) )
 272                                 {
 273                                         ret.add( gt ) ;
 274                                         iter.remove() ;
 275                                         cmpt++ ;
 276                                 }
 277
 278                                 if( cmpt == nbDep )
 279                                 {
 280                                         break ;
 281                                 }
 282                         }
 283                 }
 284
 285                 return ret;
 286         }
 287
 288
 289         private ArrayList<GTask> sortTasks()
 290         {
 291                 ArrayList<GTask> ret = null ;
 292                 double maxW = 0, maxD = 0 ;
 293
 294                 ArrayList<GTask> tmp = gr.getGraph() ;
 295
 296                 maxD = gr.getMaxDep() ;
 297
 298                 for( int i = 0 ; i < gr.getNbGTask() ; i++ )
 299                 {
 300                         if( gr.getGraph().get( i ).getWeight() > maxW )
 301                         {
 302                                 maxW = gr.getGraph().get( i ).getWeight() ;
 303                         }
 304                 }
 305
 306                 if( tmp != null && tmp.size() > 0 )
 307                 {
 308                         ret = new ArrayList<GTask>() ;
 309
 310                         ArrayList<Double> mt = new ArrayList<Double>() ;
 311
 312                         double W, D, MT ;
 313                         boolean ok = false ;
 314
 315                         for( int i = 0 ; i < tmp.size() ; i++ )
 316                         {
 317                                 W = tmp.get( i ).getWeight() / maxW ;
 318                                 D = tmp.get( i ).getNbDep() / maxD ;
 319
 320                                 ok = false ;
 321
 322                                 MT = Math.pow( W, hd ) + Math.pow( D, ( 1.0 - hd) ) ;
 323
 324                                 if( ret.size() == 0 )
 325                                 {
 326                                         ret.add( tmp.get( i ) ) ;
 327                                         mt.add( MT ) ;
 328                                 } else {
 329                                         for( int j = 0 ; j < ret.size() ; j++ )
 330                                         {
 331                                                 if( MT > mt.get( j ) )
 332                                                 {
 333                                                         ret.add( j, tmp.get( i ) ) ;
 334                                                         mt.add( j, MT ) ;
 335
 336                                                         ok = true ;
 337                                                         break ;
 338                                                 }
 339                                         }
 340
 341                                         if( ! ok )
 342                                         {
 343                                                 ret.add( tmp.get( i ) ) ;
 344                                                 mt.add( MT ) ;
 345                                         }
 346                                 }
 347                         }
 348                 }
 349
 350                 return ret ;
 351         }
 352
 353
 354         /**
 355          * Sort clusters according to the heterogeneity degree of the platform and
 356          * the eventual application's threshold.
 357          */
 358         private void updateSortedClusters()
 359         {
 360                 if( gl != null )
 361                 {
 362                         /** Purging the local list **/
 363                         sortedCluster = null ;
 364                         sortedCluster = new ArrayList<Cluster>() ;
 365
 366
 367                         /** Sorting clusters **/
 368                         ArrayList<Cluster> tmp = gl.getClusters() ;
 369
 370                         double[] marks = new double[ tmp.size() ] ;
 371                         boolean ok ;
 372
 373                         double calcLoc = 0 ;
 374                         double normN ;
 375                         double normP ;
 376
 377                         double Nm = 0, Pm = 0 ;
 378
 379                         int i = 0 ;
 380
 381                         // Computing data
 382                         for( i = 0 ; i < tmp.size() ; i++ )
 383                         {
 384                                 Nm += tmp.get( i ).getNbFreeNodes() ;
 385                                 Pm += tmp.get( i ).getAvgAvailablePower() ;
 386                         }
 387
 388                         // Computing marks
 389                         for( i = 0 ; i < tmp.size() ; i++ )
 390                         {
 391                                 normN = tmp.get( i ).getNbFreeNodes() * 100 / Nm ;
 392                                 normP = tmp.get( i ).getAvgAvailablePower() * 100 / Pm ;
 393
 394                                 /** The magic formula :P **/
 395                                 calcLoc = Math.pow( normP, hd) +
 396                                                   Math.pow( normN, (1 - hd) ) ;
 397
 398                                 marks[ i ] = calcLoc ;
 399                         }
 400
 401                         // Taking into account the network latency
 402                         ArrayList<Couple> couples = new ArrayList<Couple>() ;
 403                         if( tmp.size() > 1 )
 404                         {
 405                                 for( i = 0 ; i < tmp.size() - 1 ; i++ )
 406                                 {
 407                                         for( int j = i+1 ; j < tmp.size() ; j++ )
 408                                         {
 409                                                 couples.add( new Couple( tmp.get( i ), marks[i],
 410                                                                                  tmp.get( j ), marks[j] ) ) ;
 411                                         }
 412                                 }
 413                         } else {
 414                                 couples.add( new Couple( tmp.get(0), marks[0], null, -1 ) ) ;
 415                         }
 416
 417
 418                         // Sorting couples
 419                         ArrayList<Couple> Scouples = new ArrayList<Couple>() ;
 420                         for( i = 0 ; i < couples.size() ; i++ )
 421                         {
 422                                 ok = false ;
 423
 424                                 if( Scouples.size() == 0 )
 425                                 {
 426                                         Scouples.add( couples.get( i ) ) ;
 427                                 } else {
 428
 429                                         for( int j = 0 ; j < Scouples.size() ; j++ )
 430                                         {
 431                                                 if( couples.get( i ).getCoupleMark() > Scouples.get( j ).getCoupleMark() )
 432                                                 {
 433                                                         Scouples.add( j, couples.get( i ) ) ;
 434                                                         ok = true ;
 435                                                         break ;
 436                                                 }
 437                                         }
 438
 439                                         if( ! ok )
 440                                         {
 441                                                 Scouples.add( couples.get( i ) ) ;
 442                                         }
 443                                 }
 444                         }
 445
 446                         // Extracting clusters
 447                         for( i = 0 ; i < Scouples.size() ; i++ )
 448                         {
 449                                 if( ! sortedCluster.contains( Scouples.get(i).getBetterCluster() ) )
 450                                 {
 451                                         sortedCluster.add( Scouples.get( i ).getBetterCluster() ) ;
 452                                 }
 453
 454                                 if( Scouples.get( i ).getOtherCluster() != null &&
 455                                         ! sortedCluster.contains( Scouples.get(i).getOtherCluster() ))
 456                                 {
 457                                         sortedCluster.add( Scouples.get( i ).getOtherCluster() ) ;
 458                                 }
 459                         }
 460
 461                         tmp = null ;
 462                         couples = null ;
 463                         Scouples = null ;
 464                 }
 465         }
 466
 467
 468         /**
 469          * Compute the new value of hd, by taking care of the application
 470          * and execution architecture characteristics.
 471          * @param hd_g Original heterogeneity degree
 472          * @return The new (corrected) heterogeneity degree
 473          */
 474         private double calcNewHd( double hd_g )
 475         {
 476                 /* Variables */
 477                 double nhd = 0 ;
 478
 479                 double nbTask = gr.getNbGTask() ;
 480                 double avgNodesCluster = gl.getAvgClusterNode() ;
 481                 double nbAvgDep = gr.getAverageDep() ;
 482
 483                 /* Computation */
 484                 double correc_appli = 1 - ((nbTask / nbAvgDep +1) / nbTask) ;
 485                 double correc_archi = 1 - (( avgNodesCluster / (nbAvgDep + 1) ) / avgNodesCluster) ;
 486                 System.out.println( correc_appli + "  " +correc_archi ) ;
 487
 488                 nhd = hd_g + (correc_appli - 0.5) + (correc_archi - 0.5) ;
 489
 490                 if( nhd >= 1 ) nhd = 0.99 ;
 491                 if( nhd <= 0 ) nhd = 0.01 ;
 492
 493
 494                 return nhd ;
 495         }
 496
 497
 498         @Override
 499         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 500         {
 501                 GNode ret = null ;
 502
 503                 /** If something has to be done **/
 504                 if( _dead != null )
 505                 {
 506                         boolean ok = false ;
 507                         /** Any place on the same cluster ? **/
 508                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 509                         {
 510                                 Cluster cl = null ;
 511
 512                                 int id = gl.getClusterOfNode( _dead ) ;
 513
 514                                 if( id != -1 )
 515                                 {
 516                                         cl = gl.getClusters().get(id) ;
 517
 518                                         if( cl.getNbFreeNodes() > 0 )
 519                                         {
 520                                                 ret = cl.nextGNode() ;
 521                                                 ok = true ;
 522                                         }
 523                                 } else {
 524                                         System.err.println( "Cluster not found!" ) ;
 525                                 }
 526                         }
 527
 528                         /** If there is no more place, try other clusters **/
 529                         if( ! ok )
 530                         {
 531                                 updateSortedClusters() ;
 532
 533                                 for( int i = 0 ; i < sortedCluster.size() ; i++ )
 534                                 {
 535                                         if( sortedCluster.get( i ).getNbFreeNodes() > 0 )
 536                                         {
 537                                                 ret = sortedCluster.get( i ).nextGNode() ;
 538                                                 ok = true ;
 539                                                 break ;
 540                                         }
 541                                 }
 542                         }
 543
 544                         if( ! ok )
 545                         {
 546                                 System.err.println( "No repalacing node found! No left places on any cluster!" ) ;
 547                         }
 548
 549                         nb_fault++ ;
 550                 }
 551
 552                 return ret ;
 553         }
 554
 555
 556         @Override
 557         public GNode getOtherGNode( ArrayList<GNode> _ag )
 558         {
 559                 GNode ret = null ;
 560
 561                 /** Searching the cluster which has the more free nodes **/
 562                 int pos = -1, max = 0, cur = 0 ;
 563                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 564                 {
 565                         cur = gl.getClusters().get( i ).getNbFreeNodes() ;
 566                         if( cur > max)
 567                         {
 568                                 pos = i ;
 569                                 max = cur ;
 570                         }
 571                 }
 572
 573                 ret = gl.getClusters().get( pos ).nextGNode() ;
 574
 575                 return ret ;
 576         }
 577
 578
 579         @Override
 580         public boolean setParams(Object[] _params) {
 581                 return true ;
 582         }
 583
 584
 585         private class Couple
 586         {
 587                 Cluster c1, c2 ;
 588                 double m1, m2 ;
 589                 boolean single ;
 590
 591                 Couple( Cluster _c1, double _m1, Cluster _c2, double _m2 )
 592                 {
 593                         c1 = _c1 ; m1 = _m1 ;
 594                         c2 = _c2 ; m2 = _m2 ;
 595
 596                         if( _c2 == null )
 597                         {
 598                                 single = true ;
 599                         } else {
 600                                 single = false ;
 601                         }
 602                 }
 603
 604                 protected double getCoupleMark()
 605                 {
 606                         double d = -1 ;
 607                         int i = 0 ;
 608                         GNode g1, g2 ;
 609
 610                         while( d == -1 )
 611                         {
 612                                 g1 = c1.getGNodes().get( i ) ;
 613                                 g2 = c2.getGNodes().get( i ) ;
 614
 615                                 if( g1 == null || g2 == null )
 616                                 {
 617                                         System.err.println( "There is no more node in at least one cluster" ) ;
 618                                         return 100000.0 ;
 619                                 }
 620
 621                                 d = Math.pow(gl.getDistance( g1, g2 ), (1- hd)) ;
 622                                 i++ ;
 623                         }
 624
 625                         return ( m1 + m2 ) / d ;
 626                 }
 627
 628                 protected Cluster getBetterCluster()
 629                 {
 630                         if( single )
 631                         {
 632                                 return c1 ;
 633                         }
 634
 635                         if( m1 > m2 )
 636                         {
 637                                 return c1 ;
 638                         } else {
 639                                 return c2 ;
 640                         }
 641                 }
 642
 643                 protected Cluster getOtherCluster()
 644                 {
 645                         if( single )
 646                         {
 647                                 return null ;
 648                         }
 649
 650                         if( m1 > m2 )
 651                         {
 652                                 return c2 ;
 653                         } else {
 654                                 return c1 ;
 655                         }
 656                 }
 657         }
 658
 659 }
 660
 661 /** La programmation est un art, respectons ceux qui la pratiquent !! **/