src/and/Mapping/QM.java

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