src/and/Mapping/Maheve.java

   1 package and.Mapping;
   2
   3 import java.util.ArrayList;
   4
   5
   6
   7 public class Maheve extends Algo
   8 {
   9         private static final long serialVersionUID = 1L;
  10
  11         private static final int minNode = 5 ;
  12         private static final int nbSave = 2 ;
  13
  14         private double hd ;
  15         private ArrayList<Cluster> sortedCluster = null ;
  16         private ArrayList<GTask> tasks = null ;
  17
  18
  19         /**
  20          * Empty default constructor.
  21          */
  22         public Maheve()
  23         {
  24                 super() ;
  25                 name = "MAHEVE_2" ;
  26                 sortedCluster = new ArrayList<Cluster>() ;
  27         }
  28
  29
  30         /**
  31          * Constructor of this algorithm, which takes into parameter
  32          * the application graph, the grid architecture, and the correction
  33          * parameter which indicates the threshold of the heterogeneity degree.
  34          * @param _gr The application graph
  35          * @param _gl The grid architecture
  36          * @param _threshold The heterogeneity threshold
  37          */
  38         public Maheve( Graph _gr, Grid _gl )
  39         {
  40                 super( _gr, _gl ) ;
  41
  42                 hd = 0 ;
  43                 sortedCluster = new ArrayList<Cluster>() ;
  44                 tasks = new ArrayList<GTask>() ;
  45                 name = "MAHEVE_2" ;
  46         }
  47
  48
  49         @Override
  50         public void map() {
  51                 /** If the mapping is possible ... **/
  52                 if( ( gr != null ) && ( gr.getNbGTask() <= gl.getNbGNode() ) )
  53                 {
  54                         System.out.println( "******************************************" ) ;
  55                         System.out.println( "* Launching the MAHEVE Mapping algorithm *" ) ;
  56                         System.out.println( "******************************************\n\n" ) ;
  57
  58                         /** Local variables **/
  59                         ArrayList<GNode> used = null ;
  60
  61                         /** Initialization of heterogeneity degree **/
  62                         hd = gl.getHeterogenityDegre() ;
  63
  64
  65                         /** Ordering clusters according to their real power **/
  66                         updateSortedClusters() ;
  67
  68                         /** Searching the corresponding nodes **/
  69                         used = searchNodes( gr.getNbGTask() ) ;
  70
  71                         if( used == null || used.size() == 0 )
  72                         {
  73                                 System.err.println( "No node returned!" ) ;
  74                                 return ;
  75                         }
  76
  77
  78                         /** Ordering tasks **/
  79                         orderTasks() ;
  80
  81                         if( tasks == null || tasks.size() == 0 )
  82                         {
  83                                 System.err.println( "Unable to retrieve tasks to be mapped on!" ) ;
  84                                 return ;
  85                         }
  86
  87
  88                         /** Save the Mapping **/
  89                         for( int i = 0 ; i < tasks.size() ; i++ )
  90                         {
  91                                 mp.addMapping( new Association( used.get( i ), tasks.get( i ) ) ) ;
  92                         }
  93
  94                 } else {
  95                         System.err.println( "\n\n!!! Unable to map application!\n\n" ) ;
  96                         return ;
  97                 }
  98         }
  99
 100
 101         private void orderTasks()
 102         {
 103                 ArrayList<GTask> l1 = sortTasks() ;
 104
 105                 if( l1 != null && l1.size() > 0 )
 106                 {
 107                         ArrayList<GTask> l2 = new ArrayList<GTask>() ;
 108                         ArrayList<GTask> tmp = new ArrayList<GTask>() ;
 109
 110                         while( l1.size() > 0 )
 111                         {
 112                                 if( l2.size() == 0 )
 113                                 {
 114                                         l2.add( l1.get( 0 ) ) ;
 115                                 }
 116
 117                                 while( l2.size() > 0 )
 118                                 {
 119                                         l1.remove( l2.get( 0 ) ) ;
 120                                         tmp = addTask( l2.remove( 0 ), l1 ) ;
 121
 122                                         for( int i = 0 ; i < tmp.size() ; i++ )
 123                                         {
 124                                                 l2.add( tmp.get( i ) ) ;
 125                                         }
 126                                 }
 127                         }
 128                 }
 129         }
 130
 131
 132         private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar)
 133         {
 134
 135                 ArrayList<GTask> ret = null ;
 136
 137                 if( _gt != null && _ar != null )
 138                 {
 139                         ret = new ArrayList<GTask>() ;
 140
 141                         // ** Adding the task in the main list ** //
 142                         tasks.add( _gt ) ;
 143
 144                         // ** Searching its dependencies ** //
 145                         int nbDep = (int) (_gt.getNbDep() * (1.0 - hd)) ;
 146                         int cmpt = 0 ;
 147                         int num = 0 ;
 148
 149                         ArrayList<Integer> dep = new ArrayList<Integer>() ;
 150
 151                         for( int i = 0 ; i < _gt.getDependencies().size() ; i++ )
 152                         {
 153                                 dep.add( _gt.getDependencies().get( i ).getNum() ) ;
 154                         }
 155
 156                         for( int i = 0 ; i < _ar.size() ; i++ )
 157                         {
 158                                 num = _ar.get( i ).getNum() ;
 159
 160                                 for( int j = 0 ; j < dep.size() ; j++ )
 161                                 {
 162                                         if( num == dep.get( j ) )
 163                                         {
 164                                                 ret.add( _ar.remove( i ) ) ;
 165                                                 cmpt++ ;
 166                                                 dep.remove( j ) ;
 167                                                 break ;
 168                                         }
 169                                 }
 170
 171                                 if( cmpt == nbDep )
 172                                 {
 173                                         break ;
 174                                 }
 175                         }
 176                 }
 177
 178                 return ret;
 179         }
 180
 181
 182         private ArrayList<GTask> sortTasks()
 183         {
 184                 ArrayList<GTask> ret = null ;
 185
 186                 ArrayList<GTask> tmp = gr.getGraph() ;
 187
 188                 if( tmp != null && tmp.size() > 0 )
 189                 {
 190                         ret = new ArrayList<GTask>() ;
 191
 192                         ArrayList<Double> mt = new ArrayList<Double>() ;
 193
 194                         double W, D, MT ;
 195                         boolean ok = false ;
 196
 197                         for( int i = 0 ; i < tmp.size() ; i++ )
 198                         {
 199                                 W = tmp.get( i ).getWeight() ;
 200                                 D = tmp.get( i ).getNbDep() ;
 201
 202                                 ok = false ;
 203
 204                                 MT = Math.pow( W, hd ) * Math.pow( D, ( 1.0 - hd) ) ;
 205
 206                                 if( ret.size() == 0 )
 207                                 {
 208                                         ret.add( tmp.get( i ) ) ;
 209                                         mt.add( MT ) ;
 210                                 } else {
 211                                         for( int j = 0 ; j < ret.size() ; j++ )
 212                                         {
 213                                                 if( MT > mt.get( j ) )
 214                                                 {
 215                                                         ret.add( j, tmp.get( i ) ) ;
 216                                                         mt.add( j, MT ) ;
 217
 218                                                         ok = true ;
 219                                                         break ;
 220                                                 }
 221                                         }
 222
 223                                         if( ! ok )
 224                                         {
 225                                                 ret.add( tmp.get( i ) ) ;
 226                                                 mt.add( MT ) ;
 227                                         }
 228                                 }
 229                         }
 230                 }
 231
 232                 return ret ;
 233         }
 234
 235
 236         private ArrayList<GNode> searchNodes( int _nbTask )
 237         {
 238                 ArrayList<GNode> ret = null ;
 239
 240                 if( _nbTask > 0 )
 241                 {
 242                         ret = new ArrayList<GNode>() ;
 243                         int nbFound = 0 ;
 244                         int max = 0 ;
 245                         GNode g = null ;
 246
 247                         for( int i = 0 ; i < sortedCluster.size() ; i++ )
 248                         {
 249                                 /** If there is enough nodes ... **/
 250                                 if( sortedCluster.get( i ).getNbFreeNodes() >= minNode )
 251                                 {
 252                                         max = 0 ;
 253                                         sortedCluster.get( i ).initMoreGNode() ;
 254
 255                                         max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ;
 256
 257                                         for( int j = 0 ; j < max ; j++ )
 258                                         {
 259                                                 g = sortedCluster.get( i ).moreGNode() ;
 260                                                 ret.add( g ) ;
 261
 262                                                 nbFound ++ ;
 263
 264                                                 if( nbFound >= _nbTask )
 265                                                         break ;
 266                                         }
 267                                 }
 268
 269                                 if( nbFound >= _nbTask )
 270                                         break ;
 271                         }
 272                 }
 273
 274                 return ret ;
 275         }
 276
 277
 278         /**
 279          * Sort clusters according to the heterogeneity degree of the platform and
 280          * the eventual application's threshold.
 281          */
 282         private void updateSortedClusters()
 283         {
 284                 if( gl != null )
 285                 {
 286                         /** Purging the local list **/
 287                         sortedCluster = null ;
 288                         sortedCluster = new ArrayList<Cluster>() ;
 289
 290                         ArrayList<Double> calcMark = new ArrayList<Double>() ;
 291
 292                         hd = gl.getHeterogenityDegre() ;
 293
 294                         /** Sorting clusters **/
 295                         ArrayList<Cluster> tmp = gl.getClusters() ;
 296
 297                         boolean ok ;
 298
 299                         double calcLoc = 0 ;
 300                         double normN ;
 301                         double normP ;
 302
 303                         double Nm = 0, Pm = 0 ;
 304
 305                         for( int i = 0 ; i < tmp.size() ; i++ )
 306                         {
 307                                 Nm += tmp.get( i ).getNbFreeNodes() ;
 308                                 Pm += tmp.get( i ).getAvgAvailablePower() ;
 309                         }
 310
 311                         for( int i = 0 ; i < tmp.size() ; i++ )
 312                         {
 313                                 normN = tmp.get( i ).getNbFreeNodes() * 100 / Nm ;
 314                                 normP = tmp.get( i ).getAvgAvailablePower() * 100 / Pm ;
 315
 316                                 /** The magic formula :P **/
 317                                 calcLoc = Math.sqrt( Math.pow( (normP * hd), 2) +
 318                                                   Math.pow( (normN *(1 - hd)), 2 ) ) ;
 319
 320                                 ok = false ;
 321
 322                                 if( sortedCluster.size() == 0 )
 323                                 {
 324                                         sortedCluster.add( tmp.get( i ) ) ;
 325                                         calcMark.add( calcLoc ) ;
 326                                 } else {
 327
 328                                         for( int j = 0 ; j < sortedCluster.size() ; j++ )
 329                                         {
 330                                                 if( calcLoc > calcMark.get( j ) )
 331                                                 {
 332                                                         sortedCluster.add( j, tmp.get( i ) ) ;
 333                                                         calcMark.add( j, calcLoc ) ;
 334                                                         ok = true ;
 335                                                         break ;
 336                                                 }
 337                                         }
 338
 339                                         if( ! ok )
 340                                         {
 341                                                 sortedCluster.add( tmp.get( i ) ) ;
 342                                                 calcMark.add( calcLoc ) ;
 343                                         }
 344                                 }
 345                         }
 346                 }
 347         }
 348
 349
 350         @Override
 351         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 352         {
 353                 GNode ret = null ;
 354
 355                 /** If something has to be done **/
 356                 if( _dead != null )
 357                 {
 358                         boolean ok = false ;
 359                         /** Any place on the same cluster ? **/
 360                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 361                         {
 362                                 Cluster cl = null ;
 363
 364                                 int id = gl.getClusterOfNode( _dead ) ;
 365
 366                                 if( id != -1 )
 367                                 {
 368                                         cl = gl.getClusters().get(id) ;
 369
 370                                         if( cl.getNbFreeNodes() > 0 )
 371                                         {
 372                                                 ret = cl.nextGNode() ;
 373                                                 ok = true ;
 374                                         }
 375                                 } else {
 376                                         System.err.println( "Cluster not found!" ) ;
 377                                 }
 378                         }
 379
 380                         /** If there is no more place, try other clusters **/
 381                         if( ! ok )
 382                         {
 383                                 updateSortedClusters() ;
 384
 385                                 for( int i = 0 ; i < sortedCluster.size() ; i++ )
 386                                 {
 387                                         if( sortedCluster.get( i ).getNbFreeNodes() > 0 )
 388                                         {
 389                                                 ret = sortedCluster.get( i ).nextGNode() ;
 390                                                 ok = true ;
 391                                                 break ;
 392                                         }
 393                                 }
 394                         }
 395
 396                         nb_fault++ ;
 397                 }
 398
 399                 return ret ;
 400         }
 401
 402
 403         @Override
 404         public GNode getOtherGNode( ArrayList<GNode> _ag )
 405         {
 406                 GNode ret = null ;
 407
 408                 /** Searching the cluster which has the more free nodes **/
 409                 int pos = -1, max = 0, cur = 0 ;
 410                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 411                 {
 412                         cur = gl.getClusters().get( i ).getNbFreeNodes() ;
 413                         if( cur > max)
 414                         {
 415                                 pos = i ;
 416                                 max = cur ;
 417                         }
 418                 }
 419
 420                 ret = gl.getClusters().get( pos ).nextGNode() ;
 421
 422                 return ret ;
 423         }
 424
 425 }
 426
 427 /** La programmation est un art, respectons ceux qui la pratiquent !! **/