src/and/Mapping/FT_AIAC_QM.java

   1 package and.Mapping ;
   2
   3
   4 import java.io.Serializable;
   5 import java.util.ArrayList;
   6 import java.util.Random;
   7
   8
   9 /**
  10  * Implementation of the Fault Tolerant AIAC Quick Quality Map (FT-AIAC-QM) algorithm
  11  * @author S&eacute;bastien Miqu&eacute;e
  12  * @version 1.0
  13  */
  14 public class FT_AIAC_QM extends Algo
  15 {
  16         private static final long serialVersionUID = 1L;
  17
  18
  19         private ArrayList<GTask2> atraiter ;
  20         private ArrayList<GNode> archi ;
  21         private double f ; // search factor
  22
  23
  24         /**
  25          * Default constructor.
  26          */
  27         public FT_AIAC_QM()
  28         {
  29                 super() ;
  30                 name = "AIAC-QM" ;
  31         }
  32
  33
  34         /**
  35          * Constructor
  36          * @param _gr Application graph to be mapped on
  37          * @param _gd Grid graph
  38          * @param _f Search factor
  39          */
  40         public FT_AIAC_QM( Graph _gr, Grid _gd, double _f )
  41         {
  42                 super( _gr, _gd ) ;
  43
  44                 f = _f ;
  45                 name = "AIAC-QM" ;
  46         }
  47
  48         /**
  49          *
  50          * @return
  51          */
  52         private ArrayList<GNode> sortInitGNode()
  53         {
  54                 ArrayList<GNode> grn = null ;
  55
  56                 if( gl != null )
  57                 {
  58                         grn = new ArrayList<GNode>() ;
  59
  60                         ArrayList<GNode> tmp = gl.getGNodes() ;
  61
  62                         grn.add( tmp.get( 0 ) ) ;
  63
  64                         boolean ok ;
  65
  66                         for( int i = 1 ; i < tmp.size() ; i++ )
  67                         {
  68                                 ok = false ;
  69
  70                                 for( int j = 0 ; j < grn.size() ; j++ )
  71                                 {
  72                                         if( tmp.get( i ).getPower() > grn.get( j ).getPower() )
  73                                         {
  74                                                 grn.add( j, tmp.get( i ) ) ;
  75                                                 ok = true ;
  76                                                 break ;
  77                                         }
  78                                 }
  79
  80                                 if( ok == false )
  81                                 {
  82                                         grn.add( tmp.get( i ) ) ;
  83                                 }
  84                         }
  85                 }
  86
  87                 return grn ;
  88         }
  89
  90
  91         private ArrayList<GTask2> listToGTask2( Graph _gr )
  92         {
  93                 ArrayList<GTask2> gr2 = null ;
  94
  95                 if( _gr != null )
  96                 {
  97                         gr2 = new ArrayList<GTask2>() ;
  98
  99                         for( int i = 0 ; i < _gr.getNbGTask() ; i++ )
 100                         {
 101                                 gr2.add( new GTask2( _gr.getGraph().get( i ) ) ) ;
 102                         }
 103                 }
 104
 105                 return gr2 ;
 106         }
 107
 108
 109         @Override
 110         public void map()
 111         {
 112                 /* If the mapping is possible ... */
 113                 if( gr.getNbGTask() <= gl.getNbGNode() )
 114                 {
 115                         atraiter = listToGTask2( gr ) ;
 116                         archi = sortInitGNode() ;
 117
 118                         /** Local Variables **/
 119                         GNode nc = null ;
 120                         double yc = -1 ;
 121                         GNode nb = null ;
 122                         double yb = -1 ;
 123                         GNode nr = null ;
 124                         double yr = -1 ;
 125                         double ynb = -1 ;
 126
 127
 128                         System.out.println( "**********************************************" ) ;
 129                         System.out.println( "* Launching the FT-AIAC-QM Mapping algorithm *" ) ;
 130                         System.out.println( "**********************************************\n\n" ) ;
 131
 132                         /** Initial values **/
 133                         int r = 1 ; // Number of rounds
 134                         int n = gr.getNbGTask() ; // Number of tasks
 135
 136                         /** Initial mapping **/
 137                         initMapping() ;
 138
 139
 140                         /** Main loop **/
 141                         while( isOneMoveable() )
 142                         {
 143                                 for( int ti = 0 ; ti < atraiter.size() ; ti++ )
 144                                 {
 145                                         if( atraiter.get( ti ).isMoveable() )
 146                                         {
 147                                                 nc = atraiter.get( ti ).getMapedOn() ;
 148                                                 yc = atraiter.get( ti ).getExecTime() ;
 149                                                 nb = nc ;
 150                                                 yb = yc ;
 151
 152                                                 /** Search a node to map on **/
 153                                                 for( int k = 0 ; k < ( f * n / r ) ; k++ )
 154                                                 {
 155                                                         nr = selectRandomGNode( n, r ) ;
 156                                                         yr = execTimeOn( atraiter.get( ti ).clone(), nr ) ;
 157
 158                                                         if( yr < yb )
 159                                                         {
 160                                                                 nb = nr ;
 161                                                                 yb = yr ;
 162                                                         }
 163                                                 }
 164
 165                                                 /** Research of the neighbours' nodes **/
 166                                                 ArrayList<GNode> neighbours = researchNeighbours( atraiter.get( ti ), 1 ) ;
 167
 168                                                 for( int ni = 0 ; ni < neighbours.size() ; ni++ )
 169                                                 {
 170                                                         ynb = execTimeOn( atraiter.get( ti ).clone(), neighbours.get( ni ) ) ;
 171
 172                                                         if( ynb < yb )
 173                                                         {
 174                                                                 nb = neighbours.get( ni ) ;
 175                                                                 yb = ynb ;
 176                                                         }
 177                                                 }
 178
 179
 180                                                 /** Mapping of the task **/
 181                                                 if( ! nb.equals( nc ) )
 182                                                 {
 183                                                         GTask2 t_ = taskOn( nb ) ;
 184                                                         if( t_ != null && t_.isMoveable() )
 185                                                         {
 186                                                                 t_.setGNode( null ) ;
 187                                                         }
 188
 189                                                         atraiter.get( ti ).setGNode( nb ) ;
 190
 191                                                         updateExecTimeNeighbours( atraiter.get( ti ) ) ;
 192                                                 }
 193                                         }
 194
 195                                         /** The task is fixed on this node **/
 196                                         atraiter.get( ti ).setMoveable( false ) ;
 197
 198                                         /** If all tasks have been considered **/
 199                                         if( ti == atraiter.size() - 1 )
 200                                         {
 201                                                 r++ ;
 202                                         }
 203                                 }
 204                         }
 205
 206                         /** Save the Mapping **/
 207                         for( int i = 0 ; i < atraiter.size() ; i++ )
 208                         {
 209                                 mp.addMapping( atraiter.get( i ).getMapedOn(), atraiter.get( i ).getGTask() ) ;
 210                         }
 211
 212                 } else {
 213                         System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
 214                 }
 215         }
 216
 217         /**
 218          *
 219          * @param _nb
 220          * @return
 221          */
 222         private GTask2 taskOn( GNode _nb )
 223         {
 224                 for( int i = 0 ; i < atraiter.size() ; i++ )
 225                 {
 226                         if( atraiter.get( i ).getMapedOn().equals( _nb ) )
 227                         {
 228                                 return atraiter.get( i ) ;
 229                         }
 230                 }
 231
 232                 return null;
 233         }
 234
 235         /**
 236          *
 237          * @param _g
 238          * @param _deep
 239          * @return
 240          */
 241         private ArrayList<GNode> researchNeighbours( GTask2 _g, double _deep)
 242         {
 243                 ArrayList<GNode> nb = new ArrayList<GNode>() ;
 244                 ArrayList<GTask2> neighbours = new ArrayList<GTask2>() ;
 245
 246                 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
 247                 {
 248                         neighbours.add( atraiter.get( _g.getGTask().getDependencies().get( i ).getNum() ) ) ;
 249                 }
 250
 251                 for( int i = 0 ; i < archi.size() ; i++ )
 252                 {
 253                         for( int j = 0 ; j < neighbours.size() ; j++ )
 254                         {
 255                                 GNode tmp = neighbours.get( j ).getMapedOn() ;
 256
 257                                 if( gl.getDistance( tmp, archi.get( i ) ) <= _deep && ! nb.contains( tmp ) )
 258                                 {
 259                                         nb.add( tmp ) ;
 260                                 }
 261                         }
 262                 }
 263
 264                 return nb ;
 265         }
 266
 267
 268         /**
 269          * Initialization of the mapping. Each task is mapped on computing
 270          * nodes in order of their rank.
 271          */
 272         private void initMapping()
 273         {
 274                 for( int i = 0 ; i < atraiter.size() ; i++ )
 275                 {
 276                         atraiter.get( i ).setGNode( archi.get( i ) ) ;
 277                 }
 278         }
 279
 280
 281         /**
 282          *
 283          * @param _g
 284          * @param _n
 285          * @return
 286          */
 287         private double execTimeOn( GTask2 _g, GNode _n )
 288         {
 289                 _g.setGNode( _n ) ;
 290
 291                 return calcExecTime( _g ) ;
 292         }
 293
 294         /**
 295          *
 296          * @param _n
 297          * @param _r
 298          * @return
 299          */
 300         private GNode selectRandomGNode( int _n, int _r )
 301         {
 302                 GNode g = null ;
 303
 304                 Random rand = new Random() ;
 305
 306                 g = archi.get( rand.nextInt( _n / _r ) ) ;
 307
 308                 while( isTaskNotMoveableOn( g ) )
 309                 {
 310                         g = archi.get( rand.nextInt( _n / _r ) ) ;
 311                 }
 312
 313                 return g ;
 314         }
 315
 316
 317         /**
 318          *
 319          * @param _g
 320          * @return
 321          */
 322         private boolean isTaskNotMoveableOn( GNode _g )
 323         {
 324                 for( int i = 0 ; i < atraiter.size() ; i++ )
 325                 {
 326                         if( atraiter.get( i ).getMapedOn().equals( _g ) && ! atraiter.get( i ).isMoveable() )
 327                         {
 328                                 return true ;
 329                         }
 330                 }
 331
 332                 return false ;
 333         }
 334
 335
 336         /**
 337          *
 338          * @return
 339          */
 340         private boolean isOneMoveable()
 341         {
 342                 if( atraiter != null && atraiter.size() > 0 )
 343                 {
 344                         for( int i = 0 ; i < atraiter.size() ; i++ )
 345                         {
 346                                 if( atraiter.get( i ).isMoveable() )
 347                                 {
 348                                         return true ;
 349                                 }
 350                         }
 351                 }
 352
 353                 return false ;
 354         }
 355
 356
 357         /**
 358          *
 359          * @param _g
 360          * @return
 361          */
 362         private double calcExecTime( GTask2 _g )
 363         {
 364                 double w = -1 ;
 365
 366                 if( _g != null )
 367                 {
 368                         // Weight of computation
 369                         w = ( _g.getGTask().getWeight() / _g.mappedOn.getPower() ) ;
 370
 371                         // Weight of communications
 372                         int tab[] = new int[ _g.getGTask().getNbDep() ] ;
 373                         for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
 374                         {
 375                                 tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
 376                         }
 377
 378                         for( int i = 0 ; i < tab.length ; i++ )
 379                         {
 380                                 double tmp = gl.getDistance( _g.getMapedOn(), atraiter.get( tab[i] ).getMapedOn() ) ;
 381
 382                                 if( tmp >= 0 )
 383                                 {
 384                                         w += tmp ;
 385                                 }
 386                         }
 387                 }
 388
 389                 return w ;
 390         }
 391
 392
 393         /**
 394          *
 395          * @param _g
 396          */
 397         private void updateExecTime( GTask2 _g )
 398         {
 399                 double w = calcExecTime( _g ) ;
 400
 401                 if( w >= 0 )
 402                 {
 403                         if( w > _g.getExecTime() )
 404                         {
 405                                 _g.setMoveable( true ) ;
 406                         }
 407
 408                         _g.setExecTime( w ) ;
 409                 }
 410         }
 411
 412
 413         /**
 414          *
 415          * @param _g
 416          */
 417         private void updateExecTimeNeighbours( GTask2 _g )
 418         {
 419                 int tab[] = new int[ _g.getGTask().getNbDep() ] ;
 420                 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
 421                 {
 422                         tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
 423                 }
 424
 425                 for( int i = 0 ; i < tab.length ; i++ )
 426                 {
 427                         updateExecTime( atraiter.get( tab[i] ) ) ;
 428                 }
 429         }
 430
 431
 432
 433         /** Intern class **/
 434         /**
 435          * Temporary class.
 436          */
 437         private class GTask2 implements Serializable
 438         {
 439                 private static final long serialVersionUID = 1L;
 440
 441                 private GTask g ;
 442                 private boolean moveable ;
 443                 private double execTime ;
 444                 private GNode mappedOn ;
 445
 446                 public GTask2()
 447                 {
 448                         g = null ;
 449                         moveable = false ;
 450                         execTime = -1 ;
 451                         mappedOn = null ;
 452                 }
 453
 454                 public GTask2( GTask _g )
 455                 {
 456                         g = _g ;
 457                         moveable = false ;
 458                         execTime = -1 ;
 459                         mappedOn = null ;
 460                 }
 461
 462                 public boolean isMoveable()
 463                 {
 464                         return moveable ;
 465                 }
 466
 467                 public void setMoveable( boolean b )
 468                 {
 469                         moveable = b ;
 470                 }
 471
 472                 public void setGNode( GNode _g )
 473                 {
 474                         mappedOn = _g ;
 475                 }
 476
 477
 478                 public GTask getGTask()
 479                 {
 480                         return g ;
 481                 }
 482
 483
 484                 public double getExecTime()
 485                 {
 486                         return execTime ;
 487                 }
 488
 489
 490                 public void setExecTime( double _d )
 491                 {
 492                         execTime = _d ;
 493                 }
 494
 495                 public GNode getMapedOn()
 496                 {
 497                         return mappedOn ;
 498                 }
 499
 500
 501                 public GTask2 clone()
 502                 {
 503                         GTask2 g_new = new GTask2() ;
 504                         g_new.execTime = this.execTime ;
 505                         g_new.g = this.g ;
 506                         g_new.mappedOn = this.mappedOn ;
 507                         g_new.moveable = this.moveable ;
 508
 509                         return g_new ;
 510                 }
 511         }
 512
 513
 514
 515         @Override
 516         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 517         {
 518                 GNode ret = null ;
 519
 520                 /** If something has to be done **/
 521                 if( _dead != null )
 522                 {
 523                         ArrayList<GNode> ac = new ArrayList<GNode>() ;
 524                         GNode tmp = null ;
 525
 526                         /** Searching if clusters have some free nodes **/
 527                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 528                         {
 529                                 if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
 530                                 {
 531                                         tmp = gl.getClusters().get( i ).nextGNode() ;
 532
 533                                         if( tmp != null )
 534                                         {
 535                                                 ac.add( tmp ) ;
 536                                         }
 537                                 }
 538                         }
 539
 540                         /** If there some nodes in clusters **/
 541                         if( ac.size() > 0 )
 542                         {
 543                                 double power = -1, best = -1 ;
 544                                 int bestNode = -1 ;
 545
 546                                 /** Searching the replacing node with the higher
 547                                  * computing power
 548                                  */
 549                                 for( int i = 0 ; i < ac.size() ; i++ )
 550                                 {
 551                                         power = ac.get( i ).getPower() ;
 552
 553                                         if( best == -1 )
 554                                         {
 555                                                 best = power ;
 556                                                 bestNode = i ;
 557                                         } else {
 558                                                 if( power > best )
 559                                                 {
 560                                                         best = power ;
 561                                                         bestNode = i ;
 562                                                 }
 563                                         }
 564                                 }
 565
 566                                 /** Is there any node candidate ? **/
 567                                 if( bestNode != -1 )
 568                                 {
 569                                         ret = ac.get( bestNode ) ;
 570                                 }
 571                         }
 572
 573                         nb_fault++ ;
 574                 }
 575
 576                 return ret ;
 577         }
 578
 579
 580         @Override
 581         public GNode getOtherGNode( ArrayList<GNode> _ag )
 582         {
 583                 GNode ret = null ;
 584
 585                 int free[] = new int[ gl.getNbCluster() ] ;
 586
 587                 /** Searching if clusters have some free nodes **/
 588                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 589                 {
 590                         free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ;
 591                 }
 592
 593                 /** Returning a node from the cluster which has the most
 594                  * available nodes
 595                  */
 596                 int most = -1, max = 0 ;
 597
 598                 for( int i = 0 ; i < free.length ; i++ )
 599                 {
 600                         if( free[ i ] > max )
 601                         {
 602                                 max = free[ i ] ;
 603                                 most = i ;
 604                         }
 605                 }
 606
 607                 /** Is there any cluster candidate ? **/
 608                 if( most != -1 )
 609                 {
 610                         ret = gl.getClusters().get( most ).nextGNode() ;
 611                 }
 612
 613
 614                 return ret ;
 615         }
 616
 617
 618         @Override
 619         public boolean setParams(Object[] _params) {
 620                 return true ;
 621         }
 622 }
 623
 624
 625
 626 /** La programmation est un art, respectons ceux qui la pratiquent !! **/