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                         while( ! mapping_done )
 105                         {
 106                                 reduce = false ;
 107                                 atraiter = (ArrayList<GTask>) gr.getGraph().clone() ;
 108
 109                                 clList = sortClusters() ;
 110
 111                                 tri_dep() ;
 112
 113                                 int indice = -1 ;
 114                                 int nb_ok = 0 ;
 115                                 double places = 0 ;
 116                                 double dep = -1 ;
 117
 118                                 GTask tmp = null ;
 119                                 Cluster cl = null ;
 120
 121                                 boolean change_cluster = false ;
 122
 123
 124                                 while( nb_ok < gr.getNbGTask() )
 125                                 {
 126                                         if( places == 0 || change_cluster )
 127                                         {
 128                                                 if( change_cluster )
 129                                                 {
 130                                                         // Adding mapping
 131                                                         mp.addMapping( cl, mappees ) ;
 132                                                 }
 133
 134                                                 if( nb_ok < gr.getNbGTask() )
 135                                                 {
 136                                                         // Switching cluster
 137                                                         indice ++ ;
 138
 139                                                         if( indice == clList.size()  )
 140                                                         {
 141                                                                 System.out.println( "No more cluster !! Impossible to respect constrains !! " ) ;
 142                                                                 mp.initMapping() ;
 143                                                                 reduce = true ;
 144                                                         }
 145
 146                                                         cl = null ;
 147                                                         cl = clList.get( indice ) ;
 148                                                         places = cl.getNbGNode() ;
 149                                                         change_cluster = false ;
 150                                                         mappees = null ;
 151                                                         mappees = new ArrayList<GTask>() ;
 152                                                 }
 153                                         }
 154
 155                                         if( ( atraiter.size() + encours.size() ) <= places )
 156                                         {
 157
 158                                                 for( int i = 0 ; i < atraiter.size() ; i++ )
 159                                                 {
 160                                                         mappees.add( atraiter.get( i ) ) ;
 161                                                         nb_ok++ ;
 162                                                         places-- ;
 163                                                 }
 164
 165                                                 for( int i = 0 ; i < encours.size() ; i++ )
 166                                                 {
 167                                                         mappees.add( encours.get( i ) ) ;
 168                                                         nb_ok++ ;
 169                                                         places-- ;
 170                                                 }
 171
 172                                                 atraiter = null ;
 173                                                 encours = null ;
 174
 175                                                 atraiter = new ArrayList<GTask>() ;
 176                                                 encours = new ArrayList<GTask>() ;
 177
 178                                                 mp.addMapping( cl, mappees ) ;
 179
 180                                                 mapping_done = true ;
 181                                                 reduce = false ;
 182                                                 break ;
 183                                         }
 184
 185                                         if( encours.size() == 0 && atraiter.size() > 0 )
 186                                         {
 187                                                 encours.add( atraiter.remove(0) ) ;
 188                                         }
 189
 190                                         tmp = null ;
 191
 192                                         if( encours.size() > 0 )
 193                                         {
 194                                                 tmp = encours.get( 0 ) ;
 195                                         }
 196
 197                                         if( tmp != null )
 198                                         {
 199                                                 dep = calc_dep( tmp ) ;
 200
 201                                                 if( dep != -1 && 1 + ( dep * dep_min ) <= places && places > 0 )
 202                                                 {
 203                                                         places -- ;
 204                                                         nb_ok ++ ;
 205
 206                                                         ajoutDep( tmp ) ;
 207
 208                                                         mappees.add( tmp ) ;
 209                                                         fait.add( tmp ) ;
 210
 211                                                         atraiter.remove( tmp ) ;
 212                                                         encours.remove( tmp ) ;
 213                                                 } else {
 214                                                         change_cluster = true ;
 215                                                 }
 216
 217                                                 if( places == 0 )
 218                                                 {
 219                                                         change_cluster = true ;
 220                                                 }
 221
 222                                                 tmp = null ;
 223                                         }
 224                                 }
 225
 226                                 if( reduce )
 227                                 {
 228                                         mapping_done = false ;
 229
 230                                         System.out.println( "Reducing the minimum dependancies parameter..." ) ;
 231                                         dep_min = dep_min - 0.1 ;
 232                                         nb_ok = 0 ;
 233                                 }
 234
 235                         }
 236
 237
 238                 } else {
 239                         System.err.println( "\n\n!!! Mapping impossible ! There are more tasks than nodes !!!\n" ) ;
 240                 }
 241         }
 242
 243         private ArrayList<Cluster> sortClusters()
 244         {
 245                 ArrayList<Cluster> ret = new ArrayList<Cluster>() ;
 246
 247                 boolean ok ;
 248
 249                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 250                 {
 251                         ok = false ;
 252
 253                         if( ret.size() == 0 )
 254                         {
 255                                 ret.add( gl.getClusters().get( i ) ) ;
 256                         } else {
 257                                 for( int j = 0 ; j < ret.size() ; j++ )
 258                                 {
 259                                         if( gl.getClusters().get( i ).getNbFreeNodes() > ret.get( j ).getNbFreeNodes() )
 260                                         {
 261                                                 ret.add( j, gl.getClusters().get( i ) ) ;
 262                                                 ok = true ;
 263                                                 break ;
 264                                         }
 265                                 }
 266
 267                                 if( ! ok )
 268                                 {
 269                                         ret.add( gl.getClusters().get( i ) ) ;
 270                                 }
 271                         }
 272                 }
 273
 274                 return ret ;
 275         }
 276
 277
 278         /**
 279          *
 280          * @param _t
 281          */
 282         private void ajoutDep( GTask _t )
 283         {
 284                 if( _t != null )
 285                 {
 286                         GTask tmp = null ;
 287
 288                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
 289                         {
 290                                 tmp = _t.getDependencies().get( i ) ;
 291
 292                                 if( ! fait.contains( tmp ) && ! encours.contains( tmp )
 293                                                 && tmp.getNbDep() < _t.getNbDep() )
 294                                 {
 295                                         int j = 0 ;
 296                                         for( j = 0 ; j < encours.size() ; j++ )
 297                                         {
 298                                                 if( tmp.getNbDep() < encours.get( j ).getNbDep() )
 299                                                 {
 300                                                         encours.add( j, tmp ) ;
 301                                                         j = encours.size() + 10 ;
 302                                                 }
 303                                         }
 304
 305                                         if( j == encours.size() )
 306                                         {
 307                                                 encours.add( tmp ) ;
 308                                         }
 309
 310                                         atraiter.remove( tmp ) ;
 311
 312                                         tmp = null ;
 313                                 }
 314                         }
 315                 }
 316         }
 317
 318
 319         /**
 320          *
 321          * @param _t
 322          * @return
 323          */
 324         private double calc_dep( GTask _t )
 325         {
 326                 int dep = 0 ;
 327                 int ext = 0 ;
 328
 329                 double res = -1 ;
 330
 331                 if( _t != null )
 332                 {
 333                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
 334                         {
 335                                 if( ! fait.contains( _t.getDependencies().get( i ) ) )
 336                                 {
 337                                         dep ++ ;
 338                                 } else {
 339                                         if( ! mappees.contains( _t.getDependencies().get( i ) ) )
 340                                         {
 341                                                 ext++ ;
 342                                         }
 343                                 }
 344
 345                         }
 346
 347                         if( ( dep + ext ) < _t.getNbDep() * dep_min )
 348                         {
 349                                 res = 0 ;
 350                         } else {
 351                                 res = dep + ( ext * 0.5 ) ;
 352                         }
 353                 }
 354
 355                 return res ;
 356         }
 357
 358
 359
 360         /**
 361          *
 362          */
 363         @SuppressWarnings("unchecked")
 364         private void tri_dep()
 365         {
 366                 int nb_tache = gr.getNbGTask() ;
 367                 int nb_tri = 0 ;
 368                 int niveau = 0 ;
 369                 int niveau_fait = -1 ;
 370                 int temp = 0 ;
 371
 372                 ArrayList<GTask> tmp = new ArrayList<GTask>() ;
 373                 ArrayList<Integer> tab = new ArrayList<Integer>() ;
 374
 375                 while( nb_tri < nb_tache )
 376                 {
 377                         // Recherche du niveau en décroissant
 378                         for( int i = 0 ; i < nb_tache ; i++ )
 379                         {
 380                                 temp = atraiter.get(i).getNbDep() ;
 381
 382                                 if( niveau < temp )
 383                                 {
 384                                         if( niveau_fait != -1 )
 385                                         {
 386                                                 if( temp < niveau_fait )
 387                                                 {
 388                                                         niveau = temp ;
 389                                                 }
 390                                         } else {
 391                                                 niveau = temp ;
 392                                         }
 393                                 }
 394                         }
 395
 396                         // Searching task of the current level
 397                         for( int i = 0 ; i < nb_tache ; i++ )
 398                         {
 399                                 if( atraiter.get( i ).getNbDep() == niveau )
 400                                 {
 401                                         tmp.add( atraiter.get( i ) ) ;
 402                                         tab.add( atraiter.get( i ).getNum() ) ;
 403
 404                                         nb_tri ++ ;
 405                                 }
 406                         }
 407
 408                         niveau_fait = niveau ;
 409                         niveau = 0 ;
 410
 411                 }
 412
 413                 atraiter = (ArrayList<GTask>) tmp.clone() ;
 414         }
 415
 416
 417         @Override
 418         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 419         {
 420                 GNode ret = null ;
 421
 422                 /** If something has to be done **/
 423                 if( _dead != null )
 424                 {
 425                         ArrayList<GNode> ac = new ArrayList<GNode>() ;
 426                         GNode tmp = null ;
 427
 428                         /** Searching if clusters have some free nodes **/
 429                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 430                         {
 431                                 if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
 432                                 {
 433                                         tmp = null ;
 434                                         tmp = gl.getClusters().get( i ).nextGNode() ;
 435
 436                                         if( tmp != null )
 437                                         {
 438                                                 ac.add( tmp ) ;
 439                                         }
 440                                 }
 441                         }
 442
 443                         /** If there some nodes in clusters **/
 444                         if( ac.size() > 0 )
 445                         {
 446                                 double dist = -1, best = -1 ;
 447                                 int bestNode = -1 ;
 448
 449                                 /** Searching the replacing node with the lower distance
 450                                  * between it and the failed node
 451                                  */
 452                                 for( int i = 0 ; i < ac.size() ; i++ )
 453                                 {
 454                                         dist = gl.getDistance( _dead, ac.get( i ) ) ;
 455
 456                                         if( best == -1 )
 457                                         {
 458                                                 best = dist ;
 459                                                 bestNode = i ;
 460                                         } else {
 461                                                 if( dist < best )
 462                                                 {
 463                                                         best = dist ;
 464                                                         bestNode = i ;
 465                                                 }
 466                                         }
 467                                 }
 468
 469                                 /** Is there any node candidate ? **/
 470                                 if( bestNode != -1 )
 471                                 {
 472                                         ret = ac.get( bestNode ) ;
 473
 474                                         ret.setMapped( true ) ;
 475                                 }
 476                         }
 477                 }
 478
 479                 return ret ;
 480         }
 481
 482
 483         @Override
 484         public GNode getOtherGNode( ArrayList<GNode> _ag )
 485         {
 486                 GNode ret = null ;
 487
 488                 int free[] = new int[ gl.getNbCluster() ] ;
 489
 490                 /** Searching if clusters have some free nodes **/
 491                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 492                 {
 493                         free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ;
 494                 }
 495
 496                 /** Returning a node from the cluster which has the most
 497                  * available nodes
 498                  */
 499                 int most = -1, max = 0 ;
 500
 501                 for( int i = 0 ; i < free.length ; i++ )
 502                 {
 503                         if( free[ i ] > max )
 504                         {
 505                                 max = free[ i ] ;
 506                                 most = i ;
 507                         }
 508                 }
 509
 510                 /** Is there any cluster candidate ? **/
 511                 if( most != -1 )
 512                 {
 513                         ret = gl.getClusters().get( most ).nextGNode() ;
 514                 }
 515
 516                 return ret ;
 517         }
 518
 519
 520         @Override
 521         public boolean setParams(Object[] _params) {
 522                 return true ;
 523         }
 524
 525 }
 526
 527 /** La programmation est un art, respectons ceux qui la pratiquent !! **/