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
 229         /**
 230          *
 231          * @param _t
 232          */
 233         private void ajoutDep( GTask _t )
 234         {
 235                 if( _t != null )
 236                 {
 237                         GTask tmp = null ;
 238
 239                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
 240                         {
 241                                 tmp = _t.getDependencies().get( i ) ;
 242
 243                                 if( ! fait.contains( tmp ) && ! encours.contains( tmp )
 244                                                 && tmp.getNbDep() < _t.getNbDep() )
 245                                 {
 246 //                                      System.out.println("haha => "+tmp.getNum() ) ;
 247                                         int j = 0 ;
 248                                         for( j = 0 ; j < encours.size() ; j++ )
 249                                         {
 250                                                 if( tmp.getNbDep() < encours.get( j ).getNbDep() )
 251                                                 {
 252                                                         encours.add( j, tmp ) ;
 253                                                         j = encours.size() + 10 ;
 254                                                 }
 255                                         }
 256
 257                                         if( j == encours.size() )
 258                                         {
 259                                                 encours.add( tmp ) ;
 260                                         }
 261
 262                                         atraiter.remove( tmp ) ;
 263
 264                                         tmp = null ;
 265                                 }
 266                         }
 267                 }
 268         }
 269
 270
 271         /**
 272          *
 273          * @param _t
 274          * @return
 275          */
 276         private double calc_dep( GTask _t )
 277         {
 278                 int dep = 0 ;
 279                 int ext = 0 ;
 280
 281                 double res = -1 ;
 282
 283                 if( _t != null )
 284                 {
 285                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
 286                         {
 287                                 if( ! fait.contains( _t.getDependencies().get( i ) ) )
 288                                 {
 289                                         dep ++ ;
 290                                 } else {
 291                                         if( ! mappees.contains( _t.getDependencies().get( i ) ) )
 292                                         {
 293                                                 ext++ ;
 294                                         }
 295                                 }
 296
 297                         }
 298
 299                         if( ( dep + ext ) < _t.getNbDep() * dep_min )
 300                         {
 301                                 res = 0 ;
 302                         } else {
 303                                 res = dep + ( ext * 0.5 ) ;
 304                         }
 305
 306 //                      System.out.println("dep de "+t.getNum()+" => " + res);
 307
 308                 }
 309
 310
 311                 return res ;
 312         }
 313
 314
 315         /**
 316          *
 317          * @param _gl
 318          * @param _nbGTask
 319          * @return
 320          */
 321         @SuppressWarnings("unchecked")
 322         private ArrayList<Architecture> construireArchi( Grid _gl, int _nbGTask )
 323         {
 324                 ArrayList<Architecture> ar = new ArrayList<Architecture>() ;
 325
 326                 ArrayList<Cluster> cl = (ArrayList<Cluster>) gl.getClusters().clone() ;
 327
 328
 329                 // Méthode à faire !
 330                 Architecture a = new Architecture() ;
 331
 332                 for( int i = 0 ; i < cl.size() ; i ++ )
 333                 {
 334                         a.addCluster( cl.get( i ) ) ;
 335                 }
 336
 337                 ar.add( a ) ;
 338
 339                 return ar ;
 340         }
 341
 342         /**
 343          *
 344          */
 345         @SuppressWarnings("unchecked")
 346         private void tri_dep()
 347         {
 348                 int nb_tache = gr.getNbGTask() ;
 349                 int nb_tri = 0 ;
 350                 int niveau = 0 ;
 351                 int niveau_fait = -1 ;
 352                 int temp = 0 ;
 353
 354                 ArrayList<GTask> tmp = new ArrayList<GTask>() ;
 355                 ArrayList<Integer> tab = new ArrayList<Integer>() ;
 356
 357                 while( nb_tri < nb_tache )
 358                 {
 359                         // Recherche du niveau en décroissant
 360                         for( int i = 0 ; i < nb_tache ; i++ )
 361                         {
 362                                 temp = atraiter.get(i).getNbDep() ;
 363
 364                                 if( niveau < temp )
 365                                 {
 366                                         if( niveau_fait != -1 )
 367                                         {
 368                                                 if( temp < niveau_fait )
 369                                                 {
 370                                                         niveau = temp ;
 371                                                 }
 372                                         } else {
 373                                                 niveau = temp ;
 374                                         }
 375                                 }
 376                         }
 377
 378                         // Recherche des taches du niveau courrant
 379                         for( int i = 0 ; i < nb_tache ; i++ )
 380                         {
 381                                 if( atraiter.get( i ).getNbDep() == niveau )
 382                                 {
 383                                         tmp.add( atraiter.get( i ) ) ;
 384                                         tab.add( atraiter.get( i ).getNum() ) ;
 385
 386                                         nb_tri ++ ;
 387                                 }
 388                         }
 389
 390                         niveau_fait = niveau ;
 391                         niveau = 0 ;
 392
 393                 }
 394
 395                 atraiter = (ArrayList<GTask>) tmp.clone() ;
 396
 397 //              for( int i = 0 ; i < nb_tache ; i++ )
 398 //              {
 399 //                      System.out.print( atraiter.get(i).getNum() +" " ) ;
 400 //              }
 401 //              System.out.println();
 402         }
 403
 404
 405         @Override
 406         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 407         {
 408                 return null;
 409         }
 410
 411
 412         @Override
 413         public GNode getOtherGNode( ArrayList<GNode> _ag ) {
 414                 // TODO Auto-generated method stub
 415                 return null;
 416         }
 417
 418 }
 419
 420 /** La programmation est un art, respectons ceux qui la pratiquent !! **/