src/and/Mapping/FT_FEC.java

   1 package and.Mapping ;
   2
   3
   4 import java.util.ArrayList;
   5
   6
   7
   8
   9 /**
  10  * Mapping algorithm based on the Edge-Cut principles
  11  * @author S&eacute;bastien Miqu&eacute;e
  12  *
  13  */
  14 public class FT_FEC extends Algo
  15 {
  16         private static final long serialVersionUID = 1L;
  17
  18
  19         private ArrayList<GTask> atraiter ;
  20         private ArrayList<GTask> encours ;
  21         private ArrayList<GTask> fait ;
  22         private ArrayList<Cluster> clList ;
  23         private double dep_min ;
  24         ArrayList<GTask> mappees ;
  25
  26
  27         /**
  28          * Default constructor.
  29          */
  30         public FT_FEC()
  31         {
  32                 super() ;
  33
  34                 atraiter = new ArrayList<GTask>() ;
  35                 encours = new ArrayList<GTask>() ;
  36                 fait = new ArrayList<GTask>() ;
  37                 clList = new ArrayList<Cluster>() ;
  38                 dep_min = 0 ;
  39                 mappees = null ;
  40         }
  41
  42
  43         /**
  44          * Constructor.
  45          * @param _gr Application graph to be mapped on
  46          * @param _gl Grid graph
  47          */
  48         public FT_FEC( Graph _gr, Grid _gl )
  49         {
  50                 super( _gr, _gl ) ;
  51
  52                 atraiter = new ArrayList<GTask>() ;
  53                 encours = new ArrayList<GTask>() ;
  54                 fait = new ArrayList<GTask>() ;
  55                 clList = new ArrayList<Cluster>() ;
  56                 dep_min = 0 ;
  57                 mappees = null ;
  58         }
  59
  60
  61         /**
  62          * Constructor.
  63          * @param _gr Application graph to be mapped on
  64          * @param _gl Grid graph
  65          * @param _dep_min Minimum amount of local dependencies
  66          */
  67         public FT_FEC( Graph _gr, Grid _gl, double _dep_min )
  68         {
  69                 super( _gr, _gl ) ;
  70
  71                 atraiter = new ArrayList<GTask>() ;
  72                 encours = new ArrayList<GTask>() ;
  73                 fait = new ArrayList<GTask>() ;
  74                 clList = new ArrayList<Cluster>() ;
  75                 dep_min = _dep_min ;
  76                 mappees = null ;
  77         }
  78
  79
  80         @SuppressWarnings("unchecked")
  81         @Override
  82         public void map()
  83         {
  84                 System.out.println( "*********************************" ) ;
  85                 System.out.println( "* Launching the FT-F-EC Mapping *" ) ;
  86                 System.out.println( "*********************************\n\n" ) ;
  87
  88                 /* If the mapping is possible ... */
  89                 if( gr.getNbGTask() <= gl.getNbGNode() )
  90                 {
  91                         boolean mapping_done =false ;
  92                         boolean reduce = false ;
  93
  94                         if( dep_min > 1.0 )
  95                         {
  96                                 dep_min = 1.0 ;
  97                         }
  98
  99                         if( dep_min < 0 )
 100                         {
 101                                 dep_min = 0 ;
 102                         }
 103
 104                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 105                         {
 106                                 gl.getClusters().get( i ).initMoreGNode() ;
 107                         }
 108
 109
 110                         while( ! mapping_done )
 111                         {
 112                                 reduce = false ;
 113                                 atraiter = (ArrayList<GTask>) gr.getGraph().clone() ;
 114
 115                                 clList = sortClusters() ;
 116
 117                                 tri_dep() ;
 118
 119                                 int indice = -1 ;
 120                                 int nb_ok = 0 ;
 121                                 double places = 0 ;
 122                                 double dep = -1 ;
 123
 124                                 GTask tmp = null ;
 125                                 Cluster cl = null ;
 126
 127                                 boolean change_cluster = false ;
 128
 129
 130                                 while( nb_ok < gr.getNbGTask() )
 131                                 {
 132                                         if( places == 0 || change_cluster )
 133                                         {
 134                                                 if( change_cluster )
 135                                                 {
 136                                                         // Adding mapping
 137                                                         mp.addMapping( cl, mappees ) ;
 138                                                 }
 139
 140                                                 if( nb_ok < gr.getNbGTask() )
 141                                                 {
 142                                                         // Switching cluster
 143                                                         indice ++ ;
 144
 145                                                         if( indice == clList.size()  )
 146                                                         {
 147                                                                 System.out.println( "No more cluster !! Impossible to respect constrains !! " ) ;
 148                                                                 mp.initMapping() ;
 149                                                                 reduce = true ;
 150                                                         }
 151
 152                                                         cl = null ;
 153                                                         cl = clList.get( indice ) ;
 154                                                         places = cl.getNbGNode() ;
 155                                                         change_cluster = false ;
 156                                                         mappees = null ;
 157                                                         mappees = new ArrayList<GTask>() ;
 158                                                 }
 159                                         }
 160
 161                                         if( ( atraiter.size() + encours.size() ) <= places )
 162                                         {
 163
 164                                                 for( int i = 0 ; i < atraiter.size() ; i++ )
 165                                                 {
 166                                                         mappees.add( atraiter.get( i ) ) ;
 167                                                         nb_ok++ ;
 168                                                         places-- ;
 169                                                 }
 170
 171                                                 for( int i = 0 ; i < encours.size() ; i++ )
 172                                                 {
 173                                                         mappees.add( encours.get( i ) ) ;
 174                                                         nb_ok++ ;
 175                                                         places-- ;
 176                                                 }
 177
 178                                                 atraiter = null ;
 179                                                 encours = null ;
 180
 181                                                 atraiter = new ArrayList<GTask>() ;
 182                                                 encours = new ArrayList<GTask>() ;
 183
 184                                                 mp.addMapping( cl, mappees ) ;
 185
 186                                                 mapping_done = true ;
 187                                                 reduce = false ;
 188                                                 break ;
 189                                         }
 190
 191                                         if( encours.size() == 0 && atraiter.size() > 0 )
 192                                         {
 193                                                 encours.add( atraiter.remove(0) ) ;
 194                                         }
 195
 196                                         tmp = null ;
 197
 198                                         if( encours.size() > 0 )
 199                                         {
 200                                                 tmp = encours.get( 0 ) ;
 201                                         }
 202
 203                                         if( tmp != null )
 204                                         {
 205                                                 dep = calc_dep( tmp ) ;
 206
 207                                                 if( dep != -1 && 1 + ( dep * dep_min ) <= places && places > 0 )
 208                                                 {
 209                                                         places -- ;
 210                                                         nb_ok ++ ;
 211
 212                                                         ajoutDep( tmp ) ;
 213
 214                                                         mappees.add( tmp ) ;
 215                                                         fait.add( tmp ) ;
 216
 217                                                         atraiter.remove( tmp ) ;
 218                                                         encours.remove( tmp ) ;
 219                                                 } else {
 220                                                         change_cluster = true ;
 221                                                 }
 222
 223                                                 if( places == 0 )
 224                                                 {
 225                                                         change_cluster = true ;
 226                                                 }
 227
 228                                                 tmp = null ;
 229                                         }
 230                                 }
 231
 232                                 if( reduce )
 233                                 {
 234                                         mapping_done = false ;
 235
 236                                         System.out.println( "Reducing the minimum dependancies parameter..." ) ;
 237                                         dep_min = dep_min - 0.1 ;
 238                                         nb_ok = 0 ;
 239                                 }
 240
 241                         }
 242
 243
 244                 } else {
 245                         System.err.println( "\n\n!!! Mapping impossible ! There are more tasks than nodes !!!\n" ) ;
 246                 }
 247         }
 248
 249         private ArrayList<Cluster> sortClusters()
 250         {
 251                 ArrayList<Cluster> ret = new ArrayList<Cluster>() ;
 252
 253                 boolean ok ;
 254
 255                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 256                 {
 257                         ok = false ;
 258
 259                         if( ret.size() == 0 )
 260                         {
 261                                 ret.add( gl.getClusters().get( i ) ) ;
 262                         } else {
 263                                 for( int j = 0 ; j < ret.size() ; j++ )
 264                                 {
 265                                         if( gl.getClusters().get( i ).getNbFreeNodes() > ret.get( j ).getNbFreeNodes() )
 266                                         {
 267                                                 ret.add( j, gl.getClusters().get( i ) ) ;
 268                                                 ok = true ;
 269                                                 break ;
 270                                         }
 271                                 }
 272
 273                                 if( ! ok )
 274                                 {
 275                                         ret.add( gl.getClusters().get( i ) ) ;
 276                                 }
 277                         }
 278                 }
 279
 280                 return ret ;
 281         }
 282
 283
 284         /**
 285          *
 286          * @param _t
 287          */
 288         private void ajoutDep( GTask _t )
 289         {
 290                 if( _t != null )
 291                 {
 292                         GTask tmp = null ;
 293
 294                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
 295                         {
 296                                 tmp = _t.getDependencies().get( i ) ;
 297
 298                                 if( ! fait.contains( tmp ) && ! encours.contains( tmp )
 299                                                 && tmp.getNbDep() < _t.getNbDep() )
 300                                 {
 301                                         int j = 0 ;
 302                                         for( j = 0 ; j < encours.size() ; j++ )
 303                                         {
 304                                                 if( tmp.getNbDep() < encours.get( j ).getNbDep() )
 305                                                 {
 306                                                         encours.add( j, tmp ) ;
 307                                                         j = encours.size() + 10 ;
 308                                                 }
 309                                         }
 310
 311                                         if( j == encours.size() )
 312                                         {
 313                                                 encours.add( tmp ) ;
 314                                         }
 315
 316                                         atraiter.remove( tmp ) ;
 317
 318                                         tmp = null ;
 319                                 }
 320                         }
 321                 }
 322         }
 323
 324
 325         /**
 326          *
 327          * @param _t
 328          * @return
 329          */
 330         private double calc_dep( GTask _t )
 331         {
 332                 int dep = 0 ;
 333                 int ext = 0 ;
 334
 335                 double res = -1 ;
 336
 337                 if( _t != null )
 338                 {
 339                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
 340                         {
 341                                 if( ! fait.contains( _t.getDependencies().get( i ) ) )
 342                                 {
 343                                         dep ++ ;
 344                                 } else {
 345                                         if( ! mappees.contains( _t.getDependencies().get( i ) ) )
 346                                         {
 347                                                 ext++ ;
 348                                         }
 349                                 }
 350
 351                         }
 352
 353                         if( ( dep + ext ) < _t.getNbDep() * dep_min )
 354                         {
 355                                 res = 0 ;
 356                         } else {
 357                                 res = dep + ( ext * 0.5 ) ;
 358                         }
 359                 }
 360
 361                 return res ;
 362         }
 363
 364
 365
 366         /**
 367          *
 368          */
 369         @SuppressWarnings("unchecked")
 370         private void tri_dep()
 371         {
 372                 int nb_tache = gr.getNbGTask() ;
 373                 int nb_tri = 0 ;
 374                 int niveau = 0 ;
 375                 int niveau_fait = -1 ;
 376                 int temp = 0 ;
 377
 378                 ArrayList<GTask> tmp = new ArrayList<GTask>() ;
 379                 ArrayList<Integer> tab = new ArrayList<Integer>() ;
 380
 381                 while( nb_tri < nb_tache )
 382                 {
 383                         // Recherche du niveau en décroissant
 384                         for( int i = 0 ; i < nb_tache ; i++ )
 385                         {
 386                                 temp = atraiter.get(i).getNbDep() ;
 387
 388                                 if( niveau < temp )
 389                                 {
 390                                         if( niveau_fait != -1 )
 391                                         {
 392                                                 if( temp < niveau_fait )
 393                                                 {
 394                                                         niveau = temp ;
 395                                                 }
 396                                         } else {
 397                                                 niveau = temp ;
 398                                         }
 399                                 }
 400                         }
 401
 402                         // Searching task of the current level
 403                         for( int i = 0 ; i < nb_tache ; i++ )
 404                         {
 405                                 if( atraiter.get( i ).getNbDep() == niveau )
 406                                 {
 407                                         tmp.add( atraiter.get( i ) ) ;
 408                                         tab.add( atraiter.get( i ).getNum() ) ;
 409
 410                                         nb_tri ++ ;
 411                                 }
 412                         }
 413
 414                         niveau_fait = niveau ;
 415                         niveau = 0 ;
 416
 417                 }
 418
 419                 atraiter = (ArrayList<GTask>) tmp.clone() ;
 420         }
 421
 422
 423         @Override
 424         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 425         {
 426                 GNode ret = null ;
 427
 428                 /** If something has to be done **/
 429                 if( _dead != null )
 430                 {
 431                         ArrayList<GNode> ac = new ArrayList<GNode>() ;
 432                         GNode tmp = null ;
 433
 434                         /** Searching if clusters have some free nodes **/
 435                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 436                         {
 437                                 if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
 438                                 {
 439                                         tmp = null ;
 440                                         tmp = gl.getClusters().get( i ).nextGNode() ;
 441
 442                                         if( tmp != null )
 443                                         {
 444                                                 ac.add( tmp ) ;
 445                                         }
 446                                 }
 447                         }
 448
 449                         /** If there some nodes in clusters **/
 450                         if( ac.size() > 0 )
 451                         {
 452                                 double dist = -1, best = -1 ;
 453                                 int bestNode = -1 ;
 454
 455                                 /** Searching the replacing node with the lower distance
 456                                  * between it and the failed node
 457                                  */
 458                                 for( int i = 0 ; i < ac.size() ; i++ )
 459                                 {
 460                                         dist = gl.getDistance( _dead, ac.get( i ) ) ;
 461
 462                                         if( best == -1 )
 463                                         {
 464                                                 best = dist ;
 465                                                 bestNode = i ;
 466                                         } else {
 467                                                 if( dist < best )
 468                                                 {
 469                                                         best = dist ;
 470                                                         bestNode = i ;
 471                                                 }
 472                                         }
 473                                 }
 474
 475                                 /** Is there any node candidate ? **/
 476                                 if( bestNode != -1 )
 477                                 {
 478                                         ret = ac.get( bestNode ) ;
 479
 480                                         ret.setMapped( true ) ;
 481                                 }
 482                         }
 483                 }
 484
 485                 return ret ;
 486         }
 487
 488
 489         @Override
 490         public GNode getOtherGNode( ArrayList<GNode> _ag )
 491         {
 492                 GNode ret = null ;
 493
 494                 int free[] = new int[ gl.getNbCluster() ] ;
 495
 496                 /** Searching if clusters have some free nodes **/
 497                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 498                 {
 499                         free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ;
 500                 }
 501
 502                 /** Returning a node from the cluster which has the most
 503                  * available nodes
 504                  */
 505                 int most = -1, max = 0 ;
 506
 507                 for( int i = 0 ; i < free.length ; i++ )
 508                 {
 509                         if( free[ i ] > max )
 510                         {
 511                                 max = free[ i ] ;
 512                                 most = i ;
 513                         }
 514                 }
 515
 516                 /** Is there any cluster candidate ? **/
 517                 if( most != -1 )
 518                 {
 519                         ret = gl.getClusters().get( most ).nextGNode() ;
 520                 }
 521
 522                 return ret ;
 523         }
 524
 525
 526         @Override
 527         public boolean setParams(Object[] _params) {
 528                 return true ;
 529         }
 530
 531 }
 532
 533 /** La programmation est un art, respectons ceux qui la pratiquent !! **/