src/and/Mapping/LSM.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 LSM 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 Architecture archi ;
  23         private ArrayList<Architecture> liste_archi ;
  24         private double dep_min ;
  25         ArrayList<GTask> mappees ;
  26
  27
  28         /**
  29          * Default constructor.
  30          */
  31         public LSM()
  32         {
  33                 super() ;
  34
  35                 atraiter = new ArrayList<GTask>() ;
  36                 encours = new ArrayList<GTask>() ;
  37                 fait = new ArrayList<GTask>() ;
  38 //              archi = new Architecture() ;
  39                 liste_archi = new ArrayList<Architecture>() ;
  40                 dep_min = 0 ;
  41                 mappees = null ;
  42         }
  43
  44
  45         /**
  46          * Constructor.
  47          * @param _gr Application graph to be mapped on
  48          * @param _gl Grid graph
  49          */
  50         public LSM( Graph _gr, Grid _gl )
  51         {
  52                 super( _gr, _gl ) ;
  53
  54                 atraiter = new ArrayList<GTask>() ;
  55                 encours = new ArrayList<GTask>() ;
  56                 fait = new ArrayList<GTask>() ;
  57 //              archi = new Architecture() ;
  58                 liste_archi = new ArrayList<Architecture>() ;
  59                 dep_min = 0 ;
  60                 mappees = null ;
  61         }
  62
  63
  64         /**
  65          * Constructor.
  66          * @param _gr Application graph to be mapped on
  67          * @param _gl Grid graph
  68          * @param _dep_min Minimum amount of local dependencies
  69          */
  70         public LSM( Graph _gr, Grid _gl, double _dep_min )
  71         {
  72                 super( _gr, _gl ) ;
  73
  74                 atraiter = new ArrayList<GTask>() ;
  75                 encours = new ArrayList<GTask>() ;
  76                 fait = new ArrayList<GTask>() ;
  77 //              archi = new Architecture() ;
  78                 liste_archi = new ArrayList<Architecture>() ;
  79                 dep_min = _dep_min ;
  80                 mappees = null ;
  81         }
  82
  83
  84         @SuppressWarnings("unchecked")
  85         @Override
  86         public void map()
  87         {
  88                 System.out.println( "***********************************" ) ;
  89                 System.out.println( "* Launching the Edge-Cuts Mapping *" ) ;
  90                 System.out.println( "***********************************\n\n" ) ;
  91
  92                 /* Si le mapping est possible ... */
  93                 if( gr.getNbGTask() <= gl.getNbGNode() )
  94                 {
  95                         atraiter = (ArrayList<GTask>) gr.getGraph().clone() ;
  96
  97                         liste_archi = construireArchi( gl, gr.getNbGTask() ) ;
  98
  99                         tri_dep() ;
 100
 101                         int indice = -1 ;
 102                         int nb_ok = 0 ;
 103                         double places = 0 ;
 104                         double dep = -1 ;
 105
 106 //                      double moy = gr.getAverageDep() ;
 107                         GTask tmp = null ;
 108                         Cluster cl = null ;
 109
 110                         boolean change_cluster = false ;
 111
 112 //                      System.out.println("nb cluster : "+liste_archi.get(0).getNbClusters() );
 113
 114
 115                         while( nb_ok < gr.getNbGTask() )
 116                         {
 117                                 if( places == 0 || change_cluster )
 118                                 {
 119                                         if( change_cluster )
 120                                         {
 121                                                 // Ajout du mapping
 122                                                 mp.addMapping( cl, mappees ) ;
 123                                         }
 124
 125                                         if( nb_ok < gr.getNbGTask() )
 126                                         {
 127                                                 // Changement de cluster
 128                                                 indice ++ ;
 129
 130                                                 if( indice == liste_archi.get(0).getNbClusters() )
 131                                                 {
 132                                                         System.out.println( "No more cluster !! Impossible to respect constrains !! " ) ;
 133                                                         //System.exit( 2 ) ;
 134                                                         mp.initMapping() ;
 135                                                         return ;
 136                                                 }
 137
 138                                                 cl = null ;
 139                                                 cl = liste_archi.get(0).getArchi().get( indice ) ;
 140                                                 places = cl.getNbGNode() ;
 141                                                 change_cluster = false ;
 142                                                 mappees = null ;
 143                                                 mappees = new ArrayList<GTask>() ;
 144                                         }
 145                                 }
 146
 147                                 if( ( atraiter.size() + encours.size() ) <= places )
 148                                 {
 149                                         for( int i = 0 ; i < atraiter.size() ; i++ )
 150                                         {
 151                                                 mappees.add( atraiter.get( i ) ) ;
 152                                                 nb_ok++ ;
 153                                                 places-- ;
 154                                         }
 155
 156                                         for( int i = 0 ; i < encours.size() ; i++ )
 157                                         {
 158                                                 mappees.add( encours.get( i ) ) ;
 159                                                 nb_ok++ ;
 160                                                 places-- ;
 161                                         }
 162
 163                                         atraiter = null ;
 164                                         encours = null ;
 165
 166                                         atraiter = new ArrayList<GTask>() ;
 167                                         encours = new ArrayList<GTask>() ;
 168
 169                                         mp.addMapping( cl, mappees ) ;
 170                                 }
 171
 172                                 if( encours.size() == 0 && atraiter.size() > 0 )
 173                                 {
 174                                         encours.add( atraiter.get(0) ) ;
 175                                 }
 176
 177                                 if( encours.size() > 0 )
 178                                 {
 179                                         tmp = encours.get( 0 ) ;
 180                                 }
 181
 182
 183 //                              if( ( calc_dep( tmp )* dep_min * moy ) <= places && places > 0 )
 184                                 dep = calc_dep( tmp ) ;
 185
 186                                 if( dep != -1 && 1 + ( dep * dep_min ) <= places && places > 0 )
 187                                 {
 188                                         places -- ;
 189                                         nb_ok ++ ;
 190
 191                                         ajoutDep( tmp ) ;
 192
 193                                         mappees.add( tmp ) ;
 194                                         fait.add( tmp ) ;
 195
 196                                         atraiter.remove( tmp ) ;
 197                                         encours.remove( tmp ) ;
 198                                 } else {
 199                                         change_cluster = true ;
 200                                 }
 201
 202                                 if( places == 0 )
 203                                 {
 204                                         change_cluster = true ;
 205                                 }
 206
 207                                 tmp = null ;
 208
 209 //                              try {
 210 //                                      Thread.sleep( 1000 ) ;
 211 //                              } catch( InterruptedException e ) {
 212 //                                      e.printStackTrace() ;
 213 //                              }
 214 //
 215 //                              mp.affiche() ;
 216 //                              System.out.println( "reste : " + places + " sur " + cl.getNom() ) ;
 217 //                              System.out.println( "nb_ok = " +nb_ok);
 218 //                              System.out.println("etat : "+encours);
 219 //                              System.out.println("etat2 : "+mappees);
 220 //                              System.out.println( "etat3 : "+atraiter);
 221                         }
 222
 223
 224                 } else {
 225                         System.out.println( "\n\n!!! Mapping impossible ! There are more tasks than nodes !!!\n" ) ;
 226                 }
 227
 228                 /** Update in cluster the status of nodes **/
 229                 updateGrid() ;
 230         }
 231
 232         /**
 233          *
 234          * @param _t
 235          */
 236         private void ajoutDep( GTask _t )
 237         {
 238                 if( _t != null )
 239                 {
 240                         GTask tmp = null ;
 241
 242                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
 243                         {
 244                                 tmp = _t.getDependencies().get( i ) ;
 245
 246                                 if( ! fait.contains( tmp ) && ! encours.contains( tmp )
 247                                                 && tmp.getNbDep() < _t.getNbDep() )
 248                                 {
 249 //                                      System.out.println("haha => "+tmp.getNum() ) ;
 250                                         int j = 0 ;
 251                                         for( j = 0 ; j < encours.size() ; j++ )
 252                                         {
 253                                                 if( tmp.getNbDep() < encours.get( j ).getNbDep() )
 254                                                 {
 255                                                         encours.add( j, tmp ) ;
 256                                                         j = encours.size() + 10 ;
 257                                                 }
 258                                         }
 259
 260                                         if( j == encours.size() )
 261                                         {
 262                                                 encours.add( tmp ) ;
 263                                         }
 264
 265                                         atraiter.remove( tmp ) ;
 266
 267                                         tmp = null ;
 268                                 }
 269                         }
 270                 }
 271         }
 272
 273
 274         /**
 275          *
 276          * @param _t
 277          * @return
 278          */
 279         private double calc_dep( GTask _t )
 280         {
 281                 int dep = 0 ;
 282                 int ext = 0 ;
 283
 284                 double res = -1 ;
 285
 286                 if( _t != null )
 287                 {
 288                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
 289                         {
 290                                 if( ! fait.contains( _t.getDependencies().get( i ) ) )
 291                                 {
 292                                         dep ++ ;
 293                                 } else {
 294                                         if( ! mappees.contains( _t.getDependencies().get( i ) ) )
 295                                         {
 296                                                 ext++ ;
 297                                         }
 298                                 }
 299
 300                         }
 301
 302                         if( ( dep + ext ) < _t.getNbDep() * dep_min )
 303                         {
 304                                 res = 0 ;
 305                         } else {
 306                                 res = dep + ( ext * 0.5 ) ;
 307                         }
 308
 309 //                      System.out.println("dep de "+t.getNum()+" => " + res);
 310
 311                 }
 312
 313
 314                 return res ;
 315         }
 316
 317
 318         /**
 319          *
 320          * @param _gl
 321          * @param _nbGTask
 322          * @return
 323          */
 324         @SuppressWarnings("unchecked")
 325         private ArrayList<Architecture> construireArchi( Grid _gl, int _nbGTask )
 326         {
 327                 ArrayList<Architecture> ar = new ArrayList<Architecture>() ;
 328
 329                 ArrayList<Cluster> cl = (ArrayList<Cluster>) gl.getClusters().clone() ;
 330
 331
 332                 // Méthode à faire !
 333                 Architecture a = new Architecture() ;
 334
 335                 for( int i = 0 ; i < cl.size() ; i ++ )
 336                 {
 337                         a.addCluster( cl.get( i ) ) ;
 338                 }
 339
 340                 ar.add( a ) ;
 341
 342                 return ar ;
 343         }
 344
 345         /**
 346          *
 347          */
 348         @SuppressWarnings("unchecked")
 349         private void tri_dep()
 350         {
 351                 int nb_tache = gr.getNbGTask() ;
 352                 int nb_tri = 0 ;
 353                 int niveau = 0 ;
 354                 int niveau_fait = -1 ;
 355                 int temp = 0 ;
 356
 357                 ArrayList<GTask> tmp = new ArrayList<GTask>() ;
 358                 ArrayList<Integer> tab = new ArrayList<Integer>() ;
 359
 360                 while( nb_tri < nb_tache )
 361                 {
 362                         // Recherche du niveau en décroissant
 363                         for( int i = 0 ; i < nb_tache ; i++ )
 364                         {
 365                                 temp = atraiter.get(i).getNbDep() ;
 366
 367                                 if( niveau < temp )
 368                                 {
 369                                         if( niveau_fait != -1 )
 370                                         {
 371                                                 if( temp < niveau_fait )
 372                                                 {
 373                                                         niveau = temp ;
 374                                                 }
 375                                         } else {
 376                                                 niveau = temp ;
 377                                         }
 378                                 }
 379                         }
 380
 381                         // Recherche des taches du niveau courrant
 382                         for( int i = 0 ; i < nb_tache ; i++ )
 383                         {
 384                                 if( atraiter.get( i ).getNbDep() == niveau )
 385                                 {
 386                                         tmp.add( atraiter.get( i ) ) ;
 387                                         tab.add( atraiter.get( i ).getNum() ) ;
 388
 389                                         nb_tri ++ ;
 390                                 }
 391                         }
 392
 393                         niveau_fait = niveau ;
 394                         niveau = 0 ;
 395
 396                 }
 397
 398                 atraiter = (ArrayList<GTask>) tmp.clone() ;
 399
 400 //              for( int i = 0 ; i < nb_tache ; i++ )
 401 //              {
 402 //                      System.out.print( atraiter.get(i).getNum() +" " ) ;
 403 //              }
 404 //              System.out.println();
 405         }
 406
 407
 408         @Override
 409         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 410         {
 411                 GNode ret = null ;
 412
 413                 /** Updating the grid if there is any modification **/
 414                 if( _ag != null && _ag.size() != 0 )
 415                 {
 416                         gl.updateGrid( _ag ) ;
 417                 }
 418
 419                 /** If something has to be done **/
 420                 if( _dead != null )
 421                 {
 422                         ArrayList<GNode> ac = new ArrayList<GNode>() ;
 423
 424                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 425                         {
 426                                 if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
 427                                 {
 428                                         ac.add( gl.getClusters().get( i ).nextGNode() ) ;
 429                                 }
 430                         }
 431                 }
 432
 433                 /** Update in cluster the status of nodes **/
 434                 updateGrid() ;
 435
 436                 return ret ;
 437         }
 438
 439
 440         @Override
 441         public GNode getOtherGNode( ArrayList<GNode> _ag )
 442         {
 443
 444                 return null;
 445         }
 446
 447 }
 448
 449 /** La programmation est un art, respectons ceux qui la pratiquent !! **/