4 import java.io.Serializable;
5 import java.util.ArrayList;
6 import java.util.Random;
10 * Implementation of the Fault Tolerant AIAC Quick Quality Map (FT-AIAC-QM) algorithm
11 * @author Sébastien Miquée
14 public class FT_AIAC_QM extends Algo
16 private static final long serialVersionUID = 1L;
19 private ArrayList<GTask2> atraiter ;
20 private ArrayList<GNode> archi ;
21 private double f ; // search factor
25 * Default constructor.
36 * @param _gr Application graph to be mapped on
37 * @param _gd Grid graph
38 * @param _f Search factor
40 public FT_AIAC_QM( Graph _gr, Grid _gd, double _f )
52 private ArrayList<GNode> sortInitGNode()
54 ArrayList<GNode> grn = null ;
58 grn = new ArrayList<GNode>() ;
60 ArrayList<GNode> tmp = gl.getGNodes() ;
62 grn.add( tmp.get( 0 ) ) ;
66 for( int i = 1 ; i < tmp.size() ; i++ )
70 for( int j = 0 ; j < grn.size() ; j++ )
72 if( tmp.get( i ).getPower() > grn.get( j ).getPower() )
74 grn.add( j, tmp.get( i ) ) ;
82 grn.add( tmp.get( i ) ) ;
91 private ArrayList<GTask2> listToGTask2( Graph _gr )
93 ArrayList<GTask2> gr2 = null ;
97 gr2 = new ArrayList<GTask2>() ;
99 for( int i = 0 ; i < _gr.getNbGTask() ; i++ )
101 gr2.add( new GTask2( _gr.getGraph().get( i ) ) ) ;
112 /* If the mapping is possible ... */
113 if( gr.getNbGTask() <= gl.getNbGNode() )
115 atraiter = listToGTask2( gr ) ;
116 archi = sortInitGNode() ;
118 /** Local Variables **/
128 System.out.println( "**********************************************" ) ;
129 System.out.println( "* Launching the FT-AIAC-QM Mapping algorithm *" ) ;
130 System.out.println( "**********************************************\n\n" ) ;
132 /** Initial values **/
133 int r = 1 ; // Number of rounds
134 int n = gr.getNbGTask() ; // Number of tasks
136 /** Initial mapping **/
140 while( isOneMoveable() )
142 for( int ti = 0 ; ti < atraiter.size() ; ti++ )
144 if( atraiter.get( ti ).isMoveable() )
146 nc = atraiter.get( ti ).getMapedOn() ;
147 yc = atraiter.get( ti ).getExecTime() ;
151 /** Search a node to map on **/
152 for( int k = 0 ; k < ( f * n / r ) ; k++ )
154 nr = selectRandomGNode( n, r ) ;
155 yr = execTimeOn( atraiter.get( ti ).clone(), nr ) ;
164 /** Research of the neighbours' nodes **/
165 ArrayList<GNode> neighbours = researchNeighbours( atraiter.get( ti ), 1 ) ;
167 for( int ni = 0 ; ni < neighbours.size() ; ni++ )
169 ynb = execTimeOn( atraiter.get( ti ).clone(), neighbours.get( ni ) ) ;
173 nb = neighbours.get( ni ) ;
179 /** Mapping of the task **/
180 if( ! nb.equals( nc ) )
182 GTask2 t_ = taskOn( nb ) ;
183 if( t_ != null && t_.isMoveable() )
185 t_.setGNode( null ) ;
188 atraiter.get( ti ).setGNode( nb ) ;
190 updateExecTimeNeighbours( atraiter.get( ti ) ) ;
194 /** The task is fixed on this node **/
195 atraiter.get( ti ).setMoveable( false ) ;
197 /** If all tasks have been considered **/
198 if( ti == atraiter.size() - 1 )
205 /** Save the Mapping **/
206 for( int i = 0 ; i < atraiter.size() ; i++ )
208 mp.addMapping( new Association( atraiter.get( i ).getMapedOn(), atraiter.get( i ).getGTask() ) ) ;
212 System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
221 private GTask2 taskOn( GNode _nb )
223 for( int i = 0 ; i < atraiter.size() ; i++ )
225 if( atraiter.get( i ).getMapedOn().equals( _nb ) )
227 return atraiter.get( i ) ;
240 private ArrayList<GNode> researchNeighbours( GTask2 _g, double _deep)
242 ArrayList<GNode> nb = new ArrayList<GNode>() ;
243 ArrayList<GTask2> neighbours = new ArrayList<GTask2>() ;
245 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
247 neighbours.add( atraiter.get( _g.getGTask().getDependencies().get( i ).getNum() ) ) ;
250 for( int i = 0 ; i < archi.size() ; i++ )
252 for( int j = 0 ; j < neighbours.size() ; j++ )
254 GNode tmp = neighbours.get( j ).getMapedOn() ;
256 if( gl.getDistance( tmp, archi.get( i ) ) <= _deep && ! nb.contains( tmp ) )
268 * Initialization of the mapping. Each task is mapped on computing
269 * nodes in order of their rank.
271 private void initMapping()
273 for( int i = 0 ; i < atraiter.size() ; i++ )
275 atraiter.get( i ).setGNode( archi.get( i ) ) ;
286 private double execTimeOn( GTask2 _g, GNode _n )
290 return calcExecTime( _g ) ;
299 private GNode selectRandomGNode( int _n, int _r )
303 Random rand = new Random() ;
305 g = archi.get( rand.nextInt( _n / _r ) ) ;
307 while( isTaskNotMoveableOn( g ) )
309 g = archi.get( rand.nextInt( _n / _r ) ) ;
321 private boolean isTaskNotMoveableOn( GNode _g )
323 for( int i = 0 ; i < atraiter.size() ; i++ )
325 if( atraiter.get( i ).getMapedOn().equals( _g ) && ! atraiter.get( i ).isMoveable() )
339 private boolean isOneMoveable()
341 if( atraiter != null && atraiter.size() > 0 )
343 for( int i = 0 ; i < atraiter.size() ; i++ )
345 if( atraiter.get( i ).isMoveable() )
361 private double calcExecTime( GTask2 _g )
367 // Weight of computation
368 w = ( _g.getGTask().getWeight() / _g.mappedOn.getPower() ) ;
370 // Weight of communications
371 int tab[] = new int[ _g.getGTask().getNbDep() ] ;
372 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
374 tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
377 for( int i = 0 ; i < tab.length ; i++ )
379 double tmp = gl.getDistance( _g.getMapedOn(), atraiter.get( tab[i] ).getMapedOn() ) ;
396 private void updateExecTime( GTask2 _g )
398 double w = calcExecTime( _g ) ;
402 if( w > _g.getExecTime() )
404 _g.setMoveable( true ) ;
407 _g.setExecTime( w ) ;
416 private void updateExecTimeNeighbours( GTask2 _g )
418 int tab[] = new int[ _g.getGTask().getNbDep() ] ;
419 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
421 tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
424 for( int i = 0 ; i < tab.length ; i++ )
426 updateExecTime( atraiter.get( tab[i] ) ) ;
436 private class GTask2 implements Serializable
438 private static final long serialVersionUID = 1L;
441 private boolean moveable ;
442 private double execTime ;
443 private GNode mappedOn ;
453 public GTask2( GTask _g )
461 public boolean isMoveable()
466 public void setMoveable( boolean b )
471 public void setGNode( GNode _g )
477 public GTask getGTask()
483 public double getExecTime()
489 public void setExecTime( double _d )
494 public GNode getMapedOn()
500 public GTask2 clone()
502 GTask2 g_new = new GTask2() ;
503 g_new.execTime = this.execTime ;
505 g_new.mappedOn = this.mappedOn ;
506 g_new.moveable = this.moveable ;
515 public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
519 /** If something has to be done **/
522 ArrayList<GNode> ac = new ArrayList<GNode>() ;
525 /** Searching if clusters have some free nodes **/
526 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
528 if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
530 tmp = gl.getClusters().get( i ).nextGNode() ;
539 /** If there some nodes in clusters **/
542 double power = -1, best = -1 ;
545 /** Searching the replacing node with the higher
548 for( int i = 0 ; i < ac.size() ; i++ )
550 power = ac.get( i ).getPower() ;
565 /** Is there any node candidate ? **/
568 ret = ac.get( bestNode ) ;
580 public GNode getOtherGNode( ArrayList<GNode> _ag )
584 int free[] = new int[ gl.getNbCluster() ] ;
586 /** Searching if clusters have some free nodes **/
587 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
589 free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ;
592 /** Returning a node from the cluster which has the most
595 int most = -1, max = 0 ;
597 for( int i = 0 ; i < free.length ; i++ )
599 if( free[ i ] > max )
606 /** Is there any cluster candidate ? **/
609 ret = gl.getClusters().get( most ).nextGNode() ;
618 public boolean setParams(Object[] _params) {
625 /** La programmation est un art, respectons ceux qui la pratiquent !! **/