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                 ArrayList<Integer> st = new ArrayList<Integer>() ;
 106
 107                 if( l1 != null && l1.size() > 0 )
 108                 {
 109                         ArrayList<GTask> l2 = new ArrayList<GTask>() ;
 110                         ArrayList<GTask> tmp = new ArrayList<GTask>() ;
 111
 112                         while( l1.size() > 0 )
 113                         {
 114                                 if( l2.size() == 0 )
 115                                 {
 116                                         l2.add( l1.get( 0 ) ) ;
 117                                         st.add( l1.get( 0 ).getNum() ) ;
 118                                 }
 119
 120                                 while( l2.size() > 0 )
 121                                 {
 122                                         l1.remove( l2.get( 0 ) ) ;
 123                                         tmp = addTask( l2.remove( 0 ), l1, st ) ;
 124
 125                                         for( int i = 0 ; i < tmp.size() ; i++ )
 126                                         {
 127                                                 l2.add( tmp.get( i ) ) ;
 128                                                 st.add( tmp.get( i ).getNum() ) ;
 129                                         }
 130                                 }
 131                         }
 132                 }
 133         }
 134
 135
 136         private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar,
 137                                                                          ArrayList<Integer> _st )
 138         {
 139
 140                 ArrayList<GTask> ret = null ;
 141
 142                 if( _gt != null && _ar != null )
 143                 {
 144                         ret = new ArrayList<GTask>() ;
 145
 146                         // ** Adding the task in the main list ** //
 147                         tasks.add( _gt ) ;
 148
 149                         // ** Searching its dependencies ** //
 150                         int nbDep = (int) (_gt.getNbDep() * (1.0 - hd)) ;
 151                         int cmpt = 0 ;
 152                         int num = 0 ;
 153
 154                         ArrayList<Integer> dep = new ArrayList<Integer>() ;
 155
 156                         // ** Retrieving dependencies and eliminating tasks already treated
 157                         // ** or in instance to be treated. **//
 158                         for( int i = 0 ; i < _gt.getDependencies().size() ; i++ )
 159                         {
 160                                 if( ! _st.contains( _gt.getDependencies().get( i ).getNum() ) )
 161                                 {
 162                                         dep.add( _gt.getDependencies().get( i ).getNum() ) ;
 163                                 }
 164                         }
 165
 166
 167                         // ** Searching dependencies in sorted tasks list ** //
 168                         for( int i = 0 ; i < _ar.size() ; i++ )
 169                         {
 170                                 num = _ar.get( i ).getNum() ;
 171
 172                                 if( dep.contains( num ) )
 173                                 {
 174 //                              for( int j = 0 ; j < dep.size() ; j++ )
 175 //                              {
 176 //                                      if( num == dep.get( j ) )
 177 //                                      {
 178                                                 ret.add( _ar.remove( i ) ) ;
 179                                                 cmpt++ ;
 180 //                                              dep.remove( j ) ;
 181 //                                              break ;
 182 //                                      }
 183                                 }
 184
 185                                 if( cmpt == nbDep )
 186                                 {
 187                                         break ;
 188                                 }
 189                         }
 190                 }
 191
 192                 return ret;
 193         }
 194
 195
 196         private ArrayList<GTask> sortTasks()
 197         {
 198                 ArrayList<GTask> ret = null ;
 199
 200                 ArrayList<GTask> tmp = gr.getGraph() ;
 201
 202                 if( tmp != null && tmp.size() > 0 )
 203                 {
 204                         ret = new ArrayList<GTask>() ;
 205
 206                         ArrayList<Double> mt = new ArrayList<Double>() ;
 207
 208                         double W, D, MT ;
 209                         boolean ok = false ;
 210
 211                         for( int i = 0 ; i < tmp.size() ; i++ )
 212                         {
 213                                 W = tmp.get( i ).getWeight() ;
 214                                 D = tmp.get( i ).getNbDep() ;
 215
 216                                 ok = false ;
 217
 218                                 MT = Math.pow( W, hd ) * Math.pow( D, ( 1.0 - hd) ) ;
 219
 220                                 if( ret.size() == 0 )
 221                                 {
 222                                         ret.add( tmp.get( i ) ) ;
 223                                         mt.add( MT ) ;
 224                                 } else {
 225                                         for( int j = 0 ; j < ret.size() ; j++ )
 226                                         {
 227                                                 if( MT > mt.get( j ) )
 228                                                 {
 229                                                         ret.add( j, tmp.get( i ) ) ;
 230                                                         mt.add( j, MT ) ;
 231
 232                                                         ok = true ;
 233                                                         break ;
 234                                                 }
 235                                         }
 236
 237                                         if( ! ok )
 238                                         {
 239                                                 ret.add( tmp.get( i ) ) ;
 240                                                 mt.add( MT ) ;
 241                                         }
 242                                 }
 243                         }
 244                 }
 245
 246                 return ret ;
 247         }
 248
 249
 250         private ArrayList<GNode> searchNodes( int _nbTask )
 251         {
 252                 ArrayList<GNode> ret = null ;
 253
 254                 if( _nbTask > 0 )
 255                 {
 256                         ret = new ArrayList<GNode>() ;
 257                         int nbFound = 0 ;
 258                         int max = 0 ;
 259                         GNode g = null ;
 260
 261                         for( int i = 0 ; i < sortedCluster.size() ; i++ )
 262                         {
 263                                 /** If there is enough nodes ... **/
 264                                 if( sortedCluster.get( i ).getNbFreeNodes() >= minNode )
 265                                 {
 266                                         max = 0 ;
 267                                         sortedCluster.get( i ).initMoreGNode() ;
 268
 269                                         max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ;
 270
 271                                         for( int j = 0 ; j < max ; j++ )
 272                                         {
 273                                                 g = sortedCluster.get( i ).moreGNode() ;
 274                                                 ret.add( g ) ;
 275
 276                                                 nbFound ++ ;
 277
 278                                                 if( nbFound >= _nbTask )
 279                                                         break ;
 280                                         }
 281                                 }
 282
 283                                 if( nbFound >= _nbTask )
 284                                         break ;
 285                         }
 286                 }
 287
 288                 return ret ;
 289         }
 290
 291
 292         /**
 293          * Sort clusters according to the heterogeneity degree of the platform and
 294          * the eventual application's threshold.
 295          */
 296         private void updateSortedClusters()
 297         {
 298                 if( gl != null )
 299                 {
 300                         /** Purging the local list **/
 301                         sortedCluster = null ;
 302                         sortedCluster = new ArrayList<Cluster>() ;
 303
 304                         ArrayList<Double> calcMark = new ArrayList<Double>() ;
 305
 306                         hd = gl.getHeterogenityDegre() ;
 307
 308                         /** Sorting clusters **/
 309                         ArrayList<Cluster> tmp = gl.getClusters() ;
 310
 311                         boolean ok ;
 312
 313                         double calcLoc = 0 ;
 314                         double normN ;
 315                         double normP ;
 316
 317                         double Nm = 0, Pm = 0 ;
 318
 319                         for( int i = 0 ; i < tmp.size() ; i++ )
 320                         {
 321                                 Nm += tmp.get( i ).getNbFreeNodes() ;
 322                                 Pm += tmp.get( i ).getAvgAvailablePower() ;
 323                         }
 324
 325                         for( int i = 0 ; i < tmp.size() ; i++ )
 326                         {
 327                                 normN = tmp.get( i ).getNbFreeNodes() * 100 / Nm ;
 328                                 normP = tmp.get( i ).getAvgAvailablePower() * 100 / Pm ;
 329
 330                                 /** The magic formula :P **/
 331                                 calcLoc = Math.sqrt( Math.pow( (normP * hd), 2) +
 332                                                   Math.pow( (normN *(1 - hd)), 2 ) ) ;
 333
 334                                 ok = false ;
 335
 336                                 if( sortedCluster.size() == 0 )
 337                                 {
 338                                         sortedCluster.add( tmp.get( i ) ) ;
 339                                         calcMark.add( calcLoc ) ;
 340                                 } else {
 341
 342                                         for( int j = 0 ; j < sortedCluster.size() ; j++ )
 343                                         {
 344                                                 if( calcLoc > calcMark.get( j ) )
 345                                                 {
 346                                                         sortedCluster.add( j, tmp.get( i ) ) ;
 347                                                         calcMark.add( j, calcLoc ) ;
 348                                                         ok = true ;
 349                                                         break ;
 350                                                 }
 351                                         }
 352
 353                                         if( ! ok )
 354                                         {
 355                                                 sortedCluster.add( tmp.get( i ) ) ;
 356                                                 calcMark.add( calcLoc ) ;
 357                                         }
 358                                 }
 359                         }
 360                 }
 361         }
 362
 363
 364         @Override
 365         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
 366         {
 367                 GNode ret = null ;
 368
 369                 /** If something has to be done **/
 370                 if( _dead != null )
 371                 {
 372                         boolean ok = false ;
 373                         /** Any place on the same cluster ? **/
 374                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 375                         {
 376                                 Cluster cl = null ;
 377
 378                                 int id = gl.getClusterOfNode( _dead ) ;
 379
 380                                 if( id != -1 )
 381                                 {
 382                                         cl = gl.getClusters().get(id) ;
 383
 384                                         if( cl.getNbFreeNodes() > 0 )
 385                                         {
 386                                                 ret = cl.nextGNode() ;
 387                                                 ok = true ;
 388                                         }
 389                                 } else {
 390                                         System.err.println( "Cluster not found!" ) ;
 391                                 }
 392                         }
 393
 394                         /** If there is no more place, try other clusters **/
 395                         if( ! ok )
 396                         {
 397                                 updateSortedClusters() ;
 398
 399                                 for( int i = 0 ; i < sortedCluster.size() ; i++ )
 400                                 {
 401                                         if( sortedCluster.get( i ).getNbFreeNodes() > 0 )
 402                                         {
 403                                                 ret = sortedCluster.get( i ).nextGNode() ;
 404                                                 ok = true ;
 405                                                 break ;
 406                                         }
 407                                 }
 408                         }
 409
 410                         nb_fault++ ;
 411                 }
 412
 413                 return ret ;
 414         }
 415
 416
 417         @Override
 418         public GNode getOtherGNode( ArrayList<GNode> _ag )
 419         {
 420                 GNode ret = null ;
 421
 422                 /** Searching the cluster which has the more free nodes **/
 423                 int pos = -1, max = 0, cur = 0 ;
 424                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
 425                 {
 426                         cur = gl.getClusters().get( i ).getNbFreeNodes() ;
 427                         if( cur > max)
 428                         {
 429                                 pos = i ;
 430                                 max = cur ;
 431                         }
 432                 }
 433
 434                 ret = gl.getClusters().get( pos ).nextGNode() ;
 435
 436                 return ret ;
 437         }
 438
 439 }
 440
 441 /** La programmation est un art, respectons ceux qui la pratiquent !! **/