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
 254                                         max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ;
 255
 256                                         for( int j = 0 ; j < max ; j++ )
 257                                         {
 258                                                 g = sortedCluster.get( i ).nextGNode() ;
 259                                                 ret.add( g ) ;
 260                                                 sortedCluster.get( i ).setGNodeStatus( g, true ) ;
 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 locP ;
 301                         int N ;
 302                         double P ;
 303
 304                         for( int i = 0 ; i < tmp.size() ; i++ )
 305                         {
 306                                 N = tmp.get( i ).getNbFreeNodes() ;
 307                                 P = tmp.get( i ).getAvailablePower() ;
 308                                 locP = P / N ;
 309
 310                                 /** The magic formula :P **/
 311                                 calcLoc = Math.sqrt( locP * Math.pow((1.5 * hd + 0.3), 2) +
 312                                                  N * Math.pow((1.1 - hd), 2 ) ) ;
 313
 314                                 ok = false ;
 315
 316                                 if( sortedCluster.size() == 0 )
 317                                 {
 318                                         sortedCluster.add( tmp.get( i ) ) ;
 319                                         calcMark.add( calcLoc ) ;
 320                                 } else {
 321
 322                                         for( int j = 0 ; j < sortedCluster.size() ; j++ )
 323                                         {
 324                                                 if( calcLoc > calcMark.get( j ) )
 325                                                 {
 326                                                         sortedCluster.add( j, tmp.get( i ) ) ;
 327                                                         calcMark.add( j, calcLoc ) ;
 328                                                         ok = true ;
 329                                                         break ;
 330                                                 }
 331                                         }
 332
 333                                         if( ! ok )
 334                                         {
 335                                                 sortedCluster.add( tmp.get( i ) ) ;
 336                                                 calcMark.add( calcLoc ) ;
 337                                         }
 338                                 }
 339                         }
 340                 }
 341         }
 342
 343
 344         @Override
 345         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 346         {
 347                 GNode ret = null ;
 348
 349                 /** If something has to be done **/
 350                 if( _dead != null )
 351                 {
 352                         boolean ok = false ;
 353                         /** Any place on the same cluster ? **/
 354                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 355                         {
 356                                 Cluster cl = null ;
 357
 358                                 int id = gl.getClusterOfNode( _dead ) ;
 359
 360                                 if( id != -1 )
 361                                 {
 362                                         cl = gl.getClusters().get(id) ;
 363
 364                                         if( cl.getNbFreeNodes() > 0 )
 365                                         {
 366                                                 ret = cl.nextGNode() ;
 367                                                 ok = true ;
 368                                         }
 369                                 } else {
 370                                         System.err.println( "Cluster not found!" ) ;
 371                                 }
 372                         }
 373
 374                         /** If there is no more place, try other clusters **/
 375                         if( ! ok )
 376                         {
 377                                 updateSortedClusters() ;
 378
 379                                 for( int i = 0 ; i < sortedCluster.size() ; i++ )
 380                                 {
 381                                         if( sortedCluster.get( i ).getNbFreeNodes() > 0 )
 382                                         {
 383                                                 ret = sortedCluster.get( i ).nextGNode() ;
 384                                                 ok = true ;
 385                                                 break ;
 386                                         }
 387                                 }
 388                         }
 389
 390                         nb_fault++ ;
 391                 }
 392
 393                 return ret ;
 394         }
 395
 396
 397         @Override
 398         public GNode getOtherGNode( ArrayList<GNode> _ag )
 399         {
 400                 GNode ret = null ;
 401
 402                 /** Searching the cluster which has the more free nodes **/
 403                 int pos = -1, max = 0, cur = 0 ;
 404                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 405                 {
 406                         cur = gl.getClusters().get( i ).getNbFreeNodes() ;
 407                         if( cur > max)
 408                         {
 409                                 pos = i ;
 410                                 max = cur ;
 411                         }
 412                 }
 413
 414                 ret = gl.getClusters().get( pos ).nextGNode() ;
 415
 416                 return ret ;
 417         }
 418
 419 }
 420
 421 /** La programmation est un art, respectons ceux qui la pratiquent !! **/