+package and.Mapping ;
+
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Random;
+
+
+/**
+ * Implementation of the Fault Tolerant AIAC Quick Quality Map (FT-AIAC-QM) algorithm
+ * @author Sébastien Miquée
+ * @version 1.0
+ */
+public class FT_AIAC_QM extends Algo
+{
+ private static final long serialVersionUID = 1L;
+
+
+ private ArrayList<GTask2> atraiter ;
+ private ArrayList<GNode> archi ;
+ private double f ; // search factor
+
+
+ /**
+ * Default constructor.
+ */
+ public FT_AIAC_QM()
+ {
+ super() ;
+ name = "AIAC-QM" ;
+ }
+
+
+ /**
+ * Constructor
+ * @param _gr Application graph to be mapped on
+ * @param _gd Grid graph
+ * @param _f Search factor
+ */
+ public FT_AIAC_QM( Graph _gr, Grid _gd, double _f )
+ {
+ super( _gr, _gd ) ;
+
+ f = _f ;
+ name = "AIAC-QM" ;
+ }
+
+ /**
+ *
+ * @return
+ */
+ private ArrayList<GNode> sortInitGNode()
+ {
+ ArrayList<GNode> grn = null ;
+
+ if( gl != null )
+ {
+ grn = new ArrayList<GNode>() ;
+
+ ArrayList<GNode> tmp = gl.getGNodes() ;
+
+ grn.add( tmp.get( 0 ) ) ;
+
+ boolean ok ;
+
+ for( int i = 1 ; i < tmp.size() ; i++ )
+ {
+ ok = false ;
+
+ for( int j = 0 ; j < grn.size() ; j++ )
+ {
+ if( tmp.get( i ).getPower() > grn.get( j ).getPower() )
+ {
+ grn.add( j, tmp.get( i ) ) ;
+ ok = true ;
+ break ;
+ }
+ }
+
+ if( ok == false )
+ {
+ grn.add( tmp.get( i ) ) ;
+ }
+ }
+ }
+
+ return grn ;
+ }
+
+
+ private ArrayList<GTask2> listToGTask2( Graph _gr )
+ {
+ ArrayList<GTask2> gr2 = null ;
+
+ if( _gr != null )
+ {
+ gr2 = new ArrayList<GTask2>() ;
+
+ for( int i = 0 ; i < _gr.getNbGTask() ; i++ )
+ {
+ gr2.add( new GTask2( _gr.getGraph().get( i ) ) ) ;
+ }
+ }
+
+ return gr2 ;
+ }
+
+
+ @Override
+ public void map()
+ {
+ /* If the mapping is possible ... */
+ if( gr.getNbGTask() <= gl.getNbGNode() )
+ {
+ atraiter = listToGTask2( gr ) ;
+ archi = sortInitGNode() ;
+
+ /** Local Variables **/
+ GNode nc = null ;
+ double yc = -1 ;
+ GNode nb = null ;
+ double yb = -1 ;
+ GNode nr = null ;
+ double yr = -1 ;
+ double ynb = -1 ;
+
+
+ System.out.println( "**********************************************" ) ;
+ System.out.println( "* Launching the FT-AIAC-QM Mapping algorithm *" ) ;
+ System.out.println( "**********************************************\n\n" ) ;
+
+ /** Initial values **/
+ int r = 1 ; // Number of rounds
+ int n = gr.getNbGTask() ; // Number of tasks
+
+ /** Initial mapping **/
+ initMapping() ;
+
+ /** Main loop **/
+ while( isOneMoveable() )
+ {
+ for( int ti = 0 ; ti < atraiter.size() ; ti++ )
+ {
+ if( atraiter.get( ti ).isMoveable() )
+ {
+ nc = atraiter.get( ti ).getMapedOn() ;
+ yc = atraiter.get( ti ).getExecTime() ;
+ nb = nc ;
+ yb = yc ;
+
+ /** Search a node to map on **/
+ for( int k = 0 ; k < ( f * n / r ) ; k++ )
+ {
+ nr = selectRandomGNode( n, r ) ;
+ yr = execTimeOn( atraiter.get( ti ).clone(), nr ) ;
+
+ if( yr < yb )
+ {
+ nb = nr ;
+ yb = yr ;
+ }
+ }
+
+ /** Research of the neighbours' nodes **/
+ ArrayList<GNode> neighbours = researchNeighbours( atraiter.get( ti ), 1 ) ;
+
+ for( int ni = 0 ; ni < neighbours.size() ; ni++ )
+ {
+ ynb = execTimeOn( atraiter.get( ti ).clone(), neighbours.get( ni ) ) ;
+
+ if( ynb < yb )
+ {
+ nb = neighbours.get( ni ) ;
+ yb = ynb ;
+ }
+ }
+
+
+ /** Mapping of the task **/
+ if( ! nb.equals( nc ) )
+ {
+ GTask2 t_ = taskOn( nb ) ;
+ if( t_ != null && t_.isMoveable() )
+ {
+ t_.setGNode( null ) ;
+ }
+
+ atraiter.get( ti ).setGNode( nb ) ;
+
+ updateExecTimeNeighbours( atraiter.get( ti ) ) ;
+ }
+ }
+
+ /** The task is fixed on this node **/
+ atraiter.get( ti ).setMoveable( false ) ;
+
+ /** If all tasks have been considered **/
+ if( ti == atraiter.size() - 1 )
+ {
+ r++ ;
+ }
+ }
+ }
+
+ /** Save the Mapping **/
+ for( int i = 0 ; i < atraiter.size() ; i++ )
+ {
+ mp.addMapping( new Association( atraiter.get( i ).getMapedOn(), atraiter.get( i ).getGTask() ) ) ;
+ }
+
+ } else {
+ System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
+ }
+ }
+
+ /**
+ *
+ * @param _nb
+ * @return
+ */
+ private GTask2 taskOn( GNode _nb )
+ {
+ for( int i = 0 ; i < atraiter.size() ; i++ )
+ {
+ if( atraiter.get( i ).getMapedOn().equals( _nb ) )
+ {
+ return atraiter.get( i ) ;
+ }
+ }
+
+ return null;
+ }
+
+ /**
+ *
+ * @param _g
+ * @param _deep
+ * @return
+ */
+ private ArrayList<GNode> researchNeighbours( GTask2 _g, double _deep)
+ {
+ ArrayList<GNode> nb = new ArrayList<GNode>() ;
+ ArrayList<GTask2> neighbours = new ArrayList<GTask2>() ;
+
+ for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
+ {
+ neighbours.add( atraiter.get( _g.getGTask().getDependencies().get( i ).getNum() ) ) ;
+ }
+
+ for( int i = 0 ; i < archi.size() ; i++ )
+ {
+ for( int j = 0 ; j < neighbours.size() ; j++ )
+ {
+ GNode tmp = neighbours.get( j ).getMapedOn() ;
+
+ if( gl.getDistance( tmp, archi.get( i ) ) <= _deep && ! nb.contains( tmp ) )
+ {
+ nb.add( tmp ) ;
+ }
+ }
+ }
+
+ return nb ;
+ }
+
+
+ /**
+ * Initialization of the mapping. Each task is mapped on computing
+ * nodes in order of their rank.
+ */
+ private void initMapping()
+ {
+ for( int i = 0 ; i < atraiter.size() ; i++ )
+ {
+ atraiter.get( i ).setGNode( archi.get( i ) ) ;
+ }
+ }
+
+
+ /**
+ *
+ * @param _g
+ * @param _n
+ * @return
+ */
+ private double execTimeOn( GTask2 _g, GNode _n )
+ {
+ _g.setGNode( _n ) ;
+
+ return calcExecTime( _g ) ;
+ }
+
+ /**
+ *
+ * @param _n
+ * @param _r
+ * @return
+ */
+ private GNode selectRandomGNode( int _n, int _r )
+ {
+ GNode g = null ;
+
+ Random rand = new Random() ;
+
+ g = archi.get( rand.nextInt( _n / _r ) ) ;
+
+ while( isTaskNotMoveableOn( g ) )
+ {
+ g = archi.get( rand.nextInt( _n / _r ) ) ;
+ }
+
+ return g ;
+ }
+
+
+ /**
+ *
+ * @param _g
+ * @return
+ */
+ private boolean isTaskNotMoveableOn( GNode _g )
+ {
+ for( int i = 0 ; i < atraiter.size() ; i++ )
+ {
+ if( atraiter.get( i ).getMapedOn().equals( _g ) && ! atraiter.get( i ).isMoveable() )
+ {
+ return true ;
+ }
+ }
+
+ return false ;
+ }
+
+
+ /**
+ *
+ * @return
+ */
+ private boolean isOneMoveable()
+ {
+ if( atraiter != null && atraiter.size() > 0 )
+ {
+ for( int i = 0 ; i < atraiter.size() ; i++ )
+ {
+ if( atraiter.get( i ).isMoveable() )
+ {
+ return true ;
+ }
+ }
+ }
+
+ return false ;
+ }
+
+
+ /**
+ *
+ * @param _g
+ * @return
+ */
+ private double calcExecTime( GTask2 _g )
+ {
+ double w = -1 ;
+
+ if( _g != null )
+ {
+ // Weight of computation
+ w = ( _g.getGTask().getWeight() / _g.mappedOn.getPower() ) ;
+
+ // Weight of communications
+ int tab[] = new int[ _g.getGTask().getNbDep() ] ;
+ for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
+ {
+ tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
+ }
+
+ for( int i = 0 ; i < tab.length ; i++ )
+ {
+ double tmp = gl.getDistance( _g.getMapedOn(), atraiter.get( tab[i] ).getMapedOn() ) ;
+
+ if( tmp >= 0 )
+ {
+ w += tmp ;
+ }
+ }
+ }
+
+ return w ;
+ }
+
+
+ /**
+ *
+ * @param _g
+ */
+ private void updateExecTime( GTask2 _g )
+ {
+ double w = calcExecTime( _g ) ;
+
+ if( w >= 0 )
+ {
+ if( w > _g.getExecTime() )
+ {
+ _g.setMoveable( true ) ;
+ }
+
+ _g.setExecTime( w ) ;
+ }
+ }
+
+
+ /**
+ *
+ * @param _g
+ */
+ private void updateExecTimeNeighbours( GTask2 _g )
+ {
+ int tab[] = new int[ _g.getGTask().getNbDep() ] ;
+ for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
+ {
+ tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
+ }
+
+ for( int i = 0 ; i < tab.length ; i++ )
+ {
+ updateExecTime( atraiter.get( tab[i] ) ) ;
+ }
+ }
+
+
+
+ /** Intern class **/
+ /**
+ * Temporary class.
+ */
+ private class GTask2 implements Serializable
+ {
+ private static final long serialVersionUID = 1L;
+
+ private GTask g ;
+ private boolean moveable ;
+ private double execTime ;
+ private GNode mappedOn ;
+
+ public GTask2()
+ {
+ g = null ;
+ moveable = false ;
+ execTime = -1 ;
+ mappedOn = null ;
+ }
+
+ public GTask2( GTask _g )
+ {
+ g = _g ;
+ moveable = false ;
+ execTime = -1 ;
+ mappedOn = null ;
+ }
+
+ public boolean isMoveable()
+ {
+ return moveable ;
+ }
+
+ public void setMoveable( boolean b )
+ {
+ moveable = b ;
+ }
+
+ public void setGNode( GNode _g )
+ {
+ mappedOn = _g ;
+ }
+
+
+ public GTask getGTask()
+ {
+ return g ;
+ }
+
+
+ public double getExecTime()
+ {
+ return execTime ;
+ }
+
+
+ public void setExecTime( double _d )
+ {
+ execTime = _d ;
+ }
+
+ public GNode getMapedOn()
+ {
+ return mappedOn ;
+ }
+
+
+ public GTask2 clone()
+ {
+ GTask2 g_new = new GTask2() ;
+ g_new.execTime = this.execTime ;
+ g_new.g = this.g ;
+ g_new.mappedOn = this.mappedOn ;
+ g_new.moveable = this.moveable ;
+
+ return g_new ;
+ }
+ }
+
+
+
+ @Override
+ public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
+ {
+ GNode ret = null ;
+
+ /** If something has to be done **/
+ if( _dead != null )
+ {
+ ArrayList<GNode> ac = new ArrayList<GNode>() ;
+ GNode tmp = null ;
+
+ /** Searching if clusters have some free nodes **/
+ for( int i = 0 ; i < gl.getNbCluster() ; i++ )
+ {
+ if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
+ {
+ tmp = gl.getClusters().get( i ).nextGNode() ;
+
+ if( tmp != null )
+ {
+ ac.add( tmp ) ;
+ }
+ }
+ }
+
+ /** If there some nodes in clusters **/
+ if( ac.size() > 0 )
+ {
+ double power = -1, best = -1 ;
+ int bestNode = -1 ;
+
+ /** Searching the replacing node with the higher
+ * computing power
+ */
+ for( int i = 0 ; i < ac.size() ; i++ )
+ {
+ power = ac.get( i ).getPower() ;
+
+ if( best == -1 )
+ {
+ best = power ;
+ bestNode = i ;
+ } else {
+ if( power > best )
+ {
+ best = power ;
+ bestNode = i ;
+ }
+ }
+ }
+
+ /** Is there any node candidate ? **/
+ if( bestNode != -1 )
+ {
+ ret = ac.get( bestNode ) ;
+ }
+ }
+
+ nb_fault++ ;
+ }
+
+ return ret ;
+ }
+
+
+ @Override
+ public GNode getOtherGNode( ArrayList<GNode> _ag )
+ {
+ GNode ret = null ;
+
+ int free[] = new int[ gl.getNbCluster() ] ;
+
+ /** Searching if clusters have some free nodes **/
+ for( int i = 0 ; i < gl.getNbCluster() ; i++ )
+ {
+ free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ;
+ }
+
+ /** Returning a node from the cluster which has the most
+ * available nodes
+ */
+ int most = -1, max = 0 ;
+
+ for( int i = 0 ; i < free.length ; i++ )
+ {
+ if( free[ i ] > max )
+ {
+ max = free[ i ] ;
+ most = i ;
+ }
+ }
+
+ /** Is there any cluster candidate ? **/
+ if( most != -1 )
+ {
+ ret = gl.getClusters().get( most ).nextGNode() ;
+ }
+
+
+ return ret ;
+ }
+}
+
+
+
+/** La programmation est un art, respectons ceux qui la pratiquent !! **/