src/and/Mapping/Mapping.java

   1 package and.Mapping ;
   2
   3 import java.io.Serializable;
   4 import java.util.ArrayList;
   5
   6
   7 /**
   8  * Class representing the tasks mapping on clusters and/or nodes
   9  * @author S&eacute;bastien Miqu&eacute;e
  10  *
  11  */
  12 public class Mapping implements Serializable
  13 {
  14         private static final long serialVersionUID = 1L;
  15
  16         /* Two kinds of Mapping, according to algorithms' goal */
  17         private ArrayList<Association> mapping ;
  18         private ArrayList<Association> mapping2 ;
  19         private ArrayList<GNode> other ;
  20         private int type ; // 0 : mapping task/node ; 1 : mapping tasks/cluster
  21         private Grid gd ;
  22
  23
  24         /**
  25          * Default constructor
  26          */
  27         public Mapping()
  28         {
  29                 mapping = new ArrayList<Association>() ;
  30                 mapping2 = new ArrayList<Association>() ;
  31                 other = new ArrayList<GNode>() ;
  32                 type = -1 ;
  33                 gd = null ;
  34         }
  35
  36
  37         /**
  38          * Initialization of the Mapping variables
  39          */
  40         public void initMapping()
  41         {
  42                 mapping = new ArrayList<Association>() ;
  43                 mapping2 = new ArrayList<Association>() ;
  44                 other = new ArrayList<GNode>() ;
  45                 type = -1 ;
  46                 gd = null ;
  47         }
  48
  49
  50         /**
  51          * Set the grid in which the mapping is done.
  52          * @param _gd The grid
  53          */
  54         public void setGrid( Grid _gd )
  55         {
  56                 gd = _gd ;
  57         }
  58
  59
  60         /**
  61          * Add in the mapping an association between a cluster and tasks set.
  62          * @param c Cluster of the association
  63          * @param at Tasks set to be associated
  64          */
  65         public void addMapping( Cluster c, ArrayList<GTask> at )
  66         {
  67                 mapping2.add( new Association( c, at ) ) ;
  68
  69                 if( type == 1 || type == -1 )
  70                 {
  71                         type = 1 ;
  72                 } else {
  73                         System.err.println( "Mapping type mismatch !" ) ;
  74                         System.exit( 1 ) ;
  75                 }
  76
  77                 /** For the usage of algorithms which map groups of tasks on cluster **/
  78                 GNode tmp = null ;
  79                 c.initMoreGNode() ;
  80                 for( int i = 0 ; i < at.size() ; i++ )
  81                 {
  82                         tmp = c.moreGNode() ;
  83                         if( tmp != null )
  84                         {
  85                                 insertMapping( new Association( tmp, at.get( i ) ), false ) ;
  86                         } else {
  87                                 System.err.println( "Error during reception of the next GNode !" ) ;
  88                                 break ;
  89                         }
  90                 }
  91         }
  92
  93
  94         /**
  95          * Add a mapping association between a task and a node
  96          * in the general mapping.
  97          * @param _gn The node on which the task is mapped
  98          * @param _gt The task mapped on the node
  99          */
 100         public void addMapping( GNode _gn, GTask _gt )
 101         {
 102                 if( type == 0 || type == -1 )
 103                 {
 104                         type = 0 ;
 105                 } else {
 106                         System.err.println( "Mapping type mismatch !" ) ;
 107                         System.exit( 1 ) ;
 108                 }
 109
 110                 insertMapping( new Association( _gn, _gt ), true ) ;
 111         }
 112
 113
 114         /**
 115          * Insert the association at the right place.
 116          * @param _a The association to be inserted
 117          */
 118         public void insertMapping( Association _a, boolean _other )
 119         {
 120                 if( _a != null && _a.getGNode() != null && _a.getGTask() != null )
 121                 {
 122                         mapping.add( _a ) ;
 123
 124                         if( _other )
 125                         {
 126                                 updateMapping2( _a ) ;
 127                         }
 128                 }
 129         }
 130
 131
 132         private void updateMapping2( Association _a )
 133         {
 134                 boolean ok = false ;
 135
 136                 for( int i = 0 ; i < mapping2.size() ; i++ )
 137                 {
 138                         if( mapping2.get( i ).getCluster().getName().equalsIgnoreCase( _a.getGNode().getClusterName() ) )
 139                         {
 140                                 mapping2.get( i ).getGtasks().add( _a.getGTask() ) ;
 141
 142                                 ok = true ;
 143                                 break ;
 144                         }
 145                 }
 146
 147                 if( !ok )
 148                 {
 149                         Cluster cl = _a.getGNode().getCluster() ;
 150                         ArrayList<GTask> gr = new ArrayList<GTask>() ;
 151                         gr.add( _a.getGTask() ) ;
 152                         mapping2.add( new Association( cl, gr ) ) ;
 153                 }
 154         }
 155
 156
 157         /**
 158          * Determine if a node is used as an other node in the mapping.
 159          * @param _g The node to search
 160          * @return The position of the node
 161          */
 162         private int searchOther( GNode _g )
 163         {
 164                 int pos = -1 ;
 165
 166                 if( _g != null )
 167                 {
 168                         for( int i = 0 ; i < other.size() ; i++ )
 169                         {
 170                                 if( _g.getId() == other.get( i ).getId() )
 171                                 {
 172                                         pos = i ;
 173                                         break ;
 174                                 }
 175                         }
 176                 }
 177
 178                 return pos ;
 179         }
 180
 181
 182         /**
 183          * Add a new node in the other nodes list.
 184          * @param _g The other node
 185          */
 186         public void addOtherNode( GNode _g )
 187         {
 188                 if( _g != null )
 189                 {
 190                         int pos = searchOther( _g ) ;
 191
 192                         if( pos != -1 )
 193                         {
 194                                 other.add( _g ) ;
 195                         } else {
 196                                 System.out.println( "This node already exist in OtherNodes! " +
 197                                                 "I replace it" ) ;
 198                                 other.set( pos, _g ) ;
 199                         }
 200                 }
 201         }
 202
 203
 204         /**
 205          * Remove a node in the other nodes list.
 206          * @param _g The node to be removed
 207          */
 208         public void removeOtherNode( GNode _g )
 209         {
 210                 if( _g != null )
 211                 {
 212                         int pos = searchOther( _g ) ;
 213
 214                         if( pos != -1 )
 215                         {
 216                                 other.remove( pos ) ;
 217                         } else {
 218                                 System.err.println( "This node does not exist in OtherNodes!" ) ;
 219                         }
 220                 }
 221         }
 222
 223
 224         /**
 225          * Remove a failed node from the mapping.
 226          * @param _deadNode The failed node
 227          * @return The task associated with the failed node
 228          */
 229         public GTask removeGNode( GNode _deadNode )
 230         {
 231                 GTask gt = null ;
 232
 233                 for( int i = 0 ; i < mapping.size() ; i++ )
 234                 {
 235                         if( mapping.get( i ).getGNode().getId() == _deadNode.getId() )
 236                         {
 237                                 gt = mapping.get( i ).getGTask() ;
 238                                 mapping.remove( i ) ;
 239                                 break ;
 240                         }
 241                 }
 242
 243                 return gt ;
 244         }
 245
 246
 247         /**
 248          * Return the list of GNodes on which tasks are mapped, in order
 249          * of the task number.
 250          * @return The ordered list, according to the GTasks id, of GNodes involved in the mapping
 251          */
 252         public ArrayList<GNode> getMappedGNodes()
 253         {
 254                 ArrayList<GNode> ar = new ArrayList<GNode>() ;
 255
 256                 if( mapping.size() != 0 )
 257                 {
 258                         ArrayList<Association> mp = organizeMapping() ;
 259
 260                         for( int i = 0 ; i < mp.size() ; i++ )
 261                         {
 262                                 ar.add( mp.get( i ).getGNode() ) ;
 263                         }
 264                 }
 265
 266                 return ar ;
 267         }
 268
 269
 270         private ArrayList<Association> organizeMapping()
 271         {
 272                 ArrayList<Association> ret = null ;
 273
 274                 if( mapping.size() > 0 )
 275                 {
 276                         ret = new ArrayList<Association>( mapping.size() ) ;
 277                         for( int i = 0 ; i < mapping.size() ; i++ )
 278                                 ret.add( null ) ;
 279
 280                         for( int i = 0 ; i < mapping.size() ; i++ )
 281                         {
 282                                 ret.set( mapping.get( i ).getGTask().getNum(), mapping.get( i ) ) ;
 283                         }
 284                 } else {
 285                         System.out.println( "No mapping..." ) ;
 286                 }
 287
 288                 return ret ;
 289         }
 290
 291
 292         /**
 293          * Print the status of the mapping done, according to its type.
 294          */
 295         public void print( int _type )
 296         {
 297                 int type_print = _type ;
 298
 299                 System.out.println();
 300                 System.out.println( "\t=> Mapping done:\n" ) ;
 301
 302                 if( type_print == 0 )
 303                 {
 304                         ArrayList<GNode> ar = getMappedGNodes() ;
 305
 306                         for( int i = 0 ; i < ar.size() ; i++ )
 307                         {
 308                                 System.out.println( "Task " + i + " on  " + ar.get( i ).getName() ) ;
 309                         }
 310
 311                         System.out.println() ;
 312                 }
 313
 314                 if( type_print == 1 )
 315                 {
 316                         for( int i = 0 ; i < mapping2.size() ; i++ )
 317                         {
 318                                 System.out.print( "\t\tCluster \"" + mapping2.get( i ).getCluster().getName() + "\" => { ") ;
 319                                 for( int j = 0 ; j < mapping2.get( i ).getGtasks().size() ; j++ )
 320                                 {
 321                                         System.out.print( mapping2.get( i ).getGtasks().get( j ).getNum() ) ;
 322
 323                                         if( j != mapping2.get( i ).getGtasks().size() - 1 )
 324                                         {
 325                                                 System.out.print( ", " ) ;
 326                                         }
 327                                 }
 328                                 System.out.println( " } " ) ;
 329                                 System.out.println() ;
 330                         }
 331                 }
 332         }
 333
 334
 335         /**
 336          * Return the mapping done.
 337          * @return The mapping
 338          */
 339         public ArrayList<Association> getMapping()
 340         {
 341                 return mapping ;
 342         }
 343
 344
 345         /**
 346          * Return the position of the association containing
 347          * the GNode _g.
 348          * @param _g The GNode to be search
 349          * @return The position of the association
 350          */
 351         public int getIdOfAssociation( GNode _g )
 352         {
 353                 int ret = -1 ;
 354
 355                 for( int i = 0 ; i < mapping.size() ; i++ )
 356                 {
 357                         if( mapping.get( i ).getGNode().getId() == _g.getId() )
 358                         {
 359                                 ret = i ;
 360                                 break ;
 361                         }
 362                 }
 363
 364                 return ret ;
 365         }
 366
 367
 368         /**
 369          * Return the association of the given position.
 370          * @param _id The position of the Association
 371          * @return The Association requested
 372          */
 373         public Association getAssociation( int _id )
 374         {
 375                 if( _id >= 0 && _id < mapping.size() )
 376                 {
 377                         return mapping.get( _id ) ;
 378                 } else {
 379                         return null ;
 380                 }
 381         }
 382
 383
 384         /**
 385          * Remove the association of the given position.
 386          * @param _id The position of the Association
 387          * @return The Association removed
 388          */
 389         public Association removeAssociation( int _id )
 390         {
 391                 if( _id >= 0 && _id < mapping.size() )
 392                 {
 393                         return mapping.remove( _id ) ;
 394                 } else {
 395                         return null ;
 396                 }
 397         }
 398
 399         /**
 400          * Return the position of the association containing
 401          * the GTask of a specified rank.
 402          * @param _taskRank The rank of the task
 403          * @return The position of the association
 404          */
 405         public int getIdOfAssociation( int _taskRank )
 406         {
 407                 int ret = -1 ;
 408
 409                 for( int i = 0 ; i < mapping.size() ; i++ )
 410                 {
 411                         if( mapping.get( i ).getGTask().getNum() == _taskRank )
 412                         {
 413                                 ret = i ;
 414                                 break ;
 415                         }
 416                 }
 417
 418                 return ret ;
 419         }
 420
 421         /**
 422          * Return the amount of external tasks dependencies, in cluster point of view.
 423          * @return The amount of external dependencies
 424          */
 425         public int calcDepExt()
 426         {
 427                 int depExt = 0 ;
 428
 429                 ArrayList<Association> mp = organizeMapping() ;
 430
 431                 for( int i = 0 ; i < mp.size() ; i++ )
 432                 {
 433                         ArrayList<Integer> dids = mp.get( i ).getGTask().getDependenciesIds() ;
 434
 435                         for( int j = 0 ; j < dids.size() ; j++ )
 436                         {
 437                                 if( ! mp.get( i ).getGNode().getSiteName().equalsIgnoreCase(
 438                                                 mp.get( dids.get(j) ).getGNode().getSiteName() ) )
 439                                 {
 440                                         depExt++ ;
 441                                 }
 442                         }
 443                 }
 444
 445                 return ( depExt / 2 ) ;
 446         }
 447
 448
 449         /**
 450          * ** TO BE MODIFIED !!!
 451          * @return
 452          */
 453         public double calcAsyncMark()
 454         {
 455                 double mark = 0 ;
 456
 457                 ArrayList<Double> comput = new ArrayList<Double>() ;
 458                 ArrayList<Double> comput2 = new ArrayList<Double>() ;
 459                 double max_time = 0 ;
 460
 461                 ArrayList<Association> mp = organizeMapping() ;
 462
 463                 /** Initialization **/
 464                 for( int i = 0 ; i < mp.size() ; i++ )
 465                 {
 466                         Double calc = new Double( mp.get( i ).getGTask().getWeight() /
 467                                         mp.get( i ).getGNode().getPower() ) ;
 468
 469                         comput.add( calc ) ;
 470                         comput2.add( new Double ( -1 ) ) ;
 471
 472                         if( calc > max_time )
 473                         {
 474                                 max_time = calc ;
 475                         }
 476                 }
 477
 478                 /** Normalization **/
 479                 for( int i = 0 ; i < mp.size() ; i++ )
 480                 {
 481                         comput.set( i, comput.get( i ) / max_time ) ;
 482                 }
 483
 484
 485                 for( int k = 0 ; k < 2 ; k++ )
 486                 for( int i = 0 ; i < mp.size() ; i++ )
 487                 {
 488                         ArrayList<Integer> tmp = mp.get(i).getGTask().getDependenciesIds() ;
 489
 490                         double calc = 0 ;
 491                         double valv ;
 492
 493                         for( int j = 0 ; j < tmp.size() ; j++ )
 494                         {
 495                                 if( comput2.get( j ) != -1  )
 496                                 {
 497                                         valv = comput2.get( j ) ;
 498                                 } else {
 499                                         valv = comput.get( j ) ;
 500                                 }
 501
 502                                 calc += ( valv + ( gd.getDistance( mp.get( i ).getGNode(), mp.get( j ).getGNode() )
 503                                                                 / gd.getMaxDistance() ) ) ;
 504                         }
 505
 506                         comput2.set( i, comput.get( i ) * calc ) ;
 507                 }
 508
 509                 mark = -1 ;
 510                 for( int i = 0 ; i < comput2.size() ; i++ )
 511                 {
 512                         if( mark < comput2.get( i ) )
 513                         {
 514                                 mark = comput2.get( i ) ;
 515                         }
 516                 }
 517
 518                 return mark ;
 519         }
 520
 521 }
 522
 523 /** La programmation est un art, respectons ceux qui la pratiquent !! **/