- Adding the new efficient MAHEVE mapping algorithm.
- Correction of some bugs.
- Adding minor functionalities.
- Cleaning code.
protected Grid gl ;
protected Mapping mp ;
protected String ids ;
+ protected String name ;
+ protected int nb_fault ;
/**
gl = new Grid() ;
mp = new Mapping() ;
ids = "" ;
+ name = "" ;
+ nb_fault = 0 ;
}
gl = _gl ;
mp = new Mapping() ;
ids = "" ;
+ name = "" ;
+ nb_fault = 0 ;
}
*/
public void setIdS( String _s )
{
- ids = _s ;
+ if( _s != null )
+ {
+ ids = _s ;
+ }
}
+ /**
+ * Set the algorithms parameters when this one is instanciated
+ * by a class load mechanism.
+ * @param _params
+ * @return
+ */
+ public boolean setParams( Object[] _params )
+ {
+ if( _params.length >= 2 )
+ {
+ gr = (Graph) _params[0] ;
+ gl = (Grid) _params[1];
+ } else {
+ System.err.println( "Not enough parameters!" ) ;
+ return false ;
+ }
+
+ return true ;
+ }
+
/**
* Return the string identifier of the algorithm.
* @return The algorithm's identifier
/**
- * Update the grid status after having done the mapping.
+ * Set the name of the mapping algorithm.
+ * @param _n The new name
*/
- public void updateGrid()
+ public void setName( String _n )
{
- if( mp.getMappedGNodes().size() > 0 )
+ if( _n != null )
{
- ArrayList<GNode> temp = mp.getMappedGNodes() ;
- for( int i = 0 ; i < temp.size() ; i++ )
- {
- gl.getClusterOfNode( temp.get( i ) ).setGNodeStatus( temp.get( i ), true ) ;
-
- gl.setMappedStatus( temp.get( i ), true ) ;
- }
+ name = _n ;
}
}
+
+
+ /**
+ * Return the name of the mapping algorithm.
+ * @return The algorithm's name
+ */
+ public String getName()
+ {
+ return name ;
+ }
}
/** La programmation est un art, respectons ceux qui la pratiquent !! **/
package and.Mapping ;
+import java.io.Serializable;
import java.util.ArrayList;
* @author Sébastien Miquée
*
*/
-public class Architecture
+public class Architecture implements Serializable
{
+ private static final long serialVersionUID = 1L;
+
private ArrayList<Cluster> archi ;
private int nbNodes ;
private int nbClusters ;
/**
* Replace the GNode of the association.
* @param _g The replacing GNode
+ * @return The state of the replacement
*/
- public void setGNode( GNode _g )
+ public boolean setGNode( GNode _g )
{
- g = _g ;
+ if( _g != null )
+ {
+ g = _g ;
+ return true ;
+ } else {
+ System.err.println( "(Association) The new GNode is null!" ) ;
+ return false ;
+ }
}
{
private static final long serialVersionUID = 1L;
-// private int nb_node ;
private String name ;
private ArrayList<GNode> nodes ;
private ArrayList<GNode> freenodes ;
private String site ;
-// private int indice ;
+ private int moreNode ;
/**
*/
public Cluster()
{
-// nb_node = 0 ;
name = "" ;
nodes = new ArrayList<GNode>() ;
freenodes = new ArrayList<GNode>() ;
site = "" ;
-// indice = 0 ;
+ moreNode = 0 ;
}
-// /**
-// * Constructor.
-// * @param _nb The amount of computing nodes in the cluster
-// */
-// public Cluster( int _nb )
-// {
-// nb_node = _nb ;
-// name = "" ;
-// nodes = new ArrayList<GNode>() ;
-// freenodes = new ArrayList<GNode>() ;
-// site = "" ;
-//// indice = 0 ;
-//
-//
-// for( int i = 0 ; i < nb_node ; i++ )
-// {
-// nodes.add( new GNode() ) ;
-// }
-// }
-
-
-// /**
-// * Constructor.
-// * @param _nb The amount of computing nodes in the cluster
-// * @param _name Cluster's name
-// */
-// public Cluster( int _nb, String _name )
-// {
-//// nb_node = _nb ;
-// name = _name ;
-// nodes = new ArrayList<GNode>() ;
-// site = "" ;
-//// indice = 0 ;
-//
-// for( int i = 0 ; i < nb_node ; i++ )
-// {
-// nodes.add( new GNode() ) ;
-// }
-// }
-
-
/**
* Set the name of the cluster.
* @param _name Cluster's name
_n.setInCluster( true ) ;
nodes.add( _n ) ;
-// nb_node++ ;
-
if( ! _n.getMapped() )
{
freenodes.add( _n ) ;
*/
public int getNbGNode()
{
-// return nb_node ;
return nodes.size() ;
}
return pos ;
}
-// /**
-// * Initialization of indice variable.
-// */
-// public void initIndice()
-// {
-// indice = 0 ;
-// }
-
-
/**
- * Return the next computing node in the cluster,
- * according to the indice variable.
+ * Return the next available computing node in the cluster.
* @return The next node in the cluster
*/
public GNode nextGNode()
{
GNode ret = null ;
-// if( indice < nb_node )
-// {
-// ret = nodes.get( indice ) ;
-// indice++ ;
-// }
if( freenodes.size() > 0 )
{
ret = freenodes.get( 0 ) ;
return ret ;
}
+
+
+ /**
+ * Return the next available computing node in the cluster,
+ * according to the moreNode iterator.
+ * @return The next node in the cluster
+ */
+ public GNode moreGNode()
+ {
+ GNode ret = null ;
+
+ if( freenodes.size() > 0 )
+ {
+ if( moreNode >= freenodes.size() )
+ {
+ moreNode = 0 ;
+ }
+
+ ret = freenodes.get( moreNode ) ;
+ moreNode++ ;
+ }
+
+ return ret ;
+ }
/**
*/
public void removeGNode( GNode _dead )
{
- if( _dead != null && _dead.getCluster().equals( name ) && _dead.getSite().equals( site ) )
+ if( _dead != null )
{
- for( int i = 0 ; i < nodes.size() ; i++ )
+ if( _dead.getCluster().equals( name ) && _dead.getSite().equals( site ) )
{
- if( _dead.getId() == nodes.get( i ).getId() )
+ int i = 0 ;
+ for( i = 0 ; i < nodes.size() ; i++ )
{
- freenodes.remove( nodes.remove( i ) ) ;
-// nb_node-- ;
-
- break ;
+ if( _dead.getId() == nodes.get( i ).getId() )
+ {
+ nodes.remove( i ) ;
+
+ int j = 0 ;
+ for( j = 0 ; j < freenodes.size() ; j++ )
+ {
+ if( freenodes.get(j).getId() == _dead.getId() )
+ {
+ freenodes.remove( j ) ;
+ break ;
+ }
+ }
+
+ break ;
+ }
}
+
+ if( i > nodes.size() )
+ {
+ System.err.println( "(Cluster) The GNode was not found in the list!" );
+ }
+ } else {
+ System.err.println( "(Cluster) The GNode to be deleted is not mine!" ) ;
}
+ } else {
+ System.err.println( "(Cluster) The GNode to be deleted is null!" ) ;
}
}
if( _status )
{
- freenodes.remove( nodes.get(i) ) ;
+ for( int j = 0 ; j < freenodes.size() ; j++ )
+ {
+ if( freenodes.get(j).getId() == nodes.get(i).getId() )
+ {
+ freenodes.remove( j ) ;
+ break ;
+ }
+ }
+
} else {
if( ! freenodes.contains( nodes.get( i ) ) )
freenodes.add( nodes.get( i ) ) ;
/**
* Compute and return the real available computing power of the cluster,
* including the heterogeneity degree of the platform.
- * @param _het The heterogeneity degree of the platform
* @return The real available computing power
*/
- public double getAvailablePower( double _het )
+ public double getAvailablePower()
{
double ret = 0 ;
/** If there is some available nodes **/
if( freenodes.size() > 0 )
- {
- double het = _het ;
- double totalPower = 0 ;
-
- if( het == 0 )
- het = 0.00001 ;
-
+ {
for( int i = 0 ; i < freenodes.size() ; i++ )
{
- totalPower += freenodes.get( i ).getPower() ;
+ ret += freenodes.get( i ).getPower() ;
}
-
- ret = Math.pow( ( totalPower / freenodes.size() ), ( 2 * het) ) *
- ( freenodes.size() / ( het * het) ) ;
}
return ret ;
import java.util.ArrayList;
+import java.util.Random;
/**
public DefaultMapping()
{
super() ;
+ name = "DefaultMapping" ;
}
{
super( _gr, _gd ) ;
archi = _gnodes ;
+ name = "DefaultMapping" ;
}
} else {
System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
}
-
- /** Update in cluster the status of nodes **/
- updateGrid() ;
}
{
GNode ret = null ;
- if( _dead != null )
+ if( _dead != null && _ag != null )
{
int pos = 0 ;
pos = mp.getIdOfAssociation( _dead ) ;
if( _ag.size() > 0 )
{
- ret = _ag.get( 0 ) ;
-
+ Random r = new Random() ;
+ ret = _ag.get( r.nextInt( _ag.size() ) ) ;
} else {
System.err.println( "Not enought available nodes in gnodes to replace one !" ) ;
return null ;
- }
+ }
+
+ nb_fault++ ;
}
- /** Update in cluster the status of nodes **/
- updateGrid() ;
-
return ret ;
}
/** Returning the first node in the list **/
if( _ag.size() > 0 )
{
- return _ag.get( 1 ) ;
+ return _ag.get( 0 ) ;
}
return null ;
--- /dev/null
+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 !! **/
--- /dev/null
+package and.Mapping ;
+
+
+import java.util.ArrayList;
+
+
+
+
+/**
+ * Mapping algorithm based on the Edge-Cut principles
+ * @author Sébastien Miquée
+ *
+ */
+public class FT_FEC extends Algo
+{
+ private static final long serialVersionUID = 1L;
+
+
+ private ArrayList<GTask> atraiter ;
+ private ArrayList<GTask> encours ;
+ private ArrayList<GTask> fait ;
+ private ArrayList<Cluster> clList ;
+ private double dep_min ;
+ ArrayList<GTask> mappees ;
+
+
+ /**
+ * Default constructor.
+ */
+ public FT_FEC()
+ {
+ super() ;
+
+ atraiter = new ArrayList<GTask>() ;
+ encours = new ArrayList<GTask>() ;
+ fait = new ArrayList<GTask>() ;
+ clList = new ArrayList<Cluster>() ;
+ dep_min = 0 ;
+ mappees = null ;
+ }
+
+
+ /**
+ * Constructor.
+ * @param _gr Application graph to be mapped on
+ * @param _gl Grid graph
+ */
+ public FT_FEC( Graph _gr, Grid _gl )
+ {
+ super( _gr, _gl ) ;
+
+ atraiter = new ArrayList<GTask>() ;
+ encours = new ArrayList<GTask>() ;
+ fait = new ArrayList<GTask>() ;
+ clList = new ArrayList<Cluster>() ;
+ dep_min = 0 ;
+ mappees = null ;
+ }
+
+
+ /**
+ * Constructor.
+ * @param _gr Application graph to be mapped on
+ * @param _gl Grid graph
+ * @param _dep_min Minimum amount of local dependencies
+ */
+ public FT_FEC( Graph _gr, Grid _gl, double _dep_min )
+ {
+ super( _gr, _gl ) ;
+
+ atraiter = new ArrayList<GTask>() ;
+ encours = new ArrayList<GTask>() ;
+ fait = new ArrayList<GTask>() ;
+ clList = new ArrayList<Cluster>() ;
+ dep_min = _dep_min ;
+ mappees = null ;
+ }
+
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void map()
+ {
+ System.out.println( "*********************************" ) ;
+ System.out.println( "* Launching the FT-F-EC Mapping *" ) ;
+ System.out.println( "*********************************\n\n" ) ;
+
+ /* If the mapping is possible ... */
+ if( gr.getNbGTask() <= gl.getNbGNode() )
+ {
+ boolean mapping_done =false ;
+ boolean reduce = false ;
+
+ if( dep_min > 1.0 )
+ {
+ dep_min = 1.0 ;
+ }
+
+ if( dep_min < 0 )
+ {
+ dep_min = 0 ;
+ }
+
+ while( ! mapping_done )
+ {
+ reduce = false ;
+ atraiter = (ArrayList<GTask>) gr.getGraph().clone() ;
+
+ clList = sortClusters() ;
+
+ tri_dep() ;
+
+ int indice = -1 ;
+ int nb_ok = 0 ;
+ double places = 0 ;
+ double dep = -1 ;
+
+ GTask tmp = null ;
+ Cluster cl = null ;
+
+ boolean change_cluster = false ;
+
+
+ while( nb_ok < gr.getNbGTask() )
+ {
+ if( places == 0 || change_cluster )
+ {
+ if( change_cluster )
+ {
+ // Adding mapping
+ mp.addMapping( cl, mappees ) ;
+ }
+
+ if( nb_ok < gr.getNbGTask() )
+ {
+ // Switching cluster
+ indice ++ ;
+
+ if( indice == clList.size() )
+ {
+ System.out.println( "No more cluster !! Impossible to respect constrains !! " ) ;
+ mp.initMapping() ;
+ reduce = true ;
+ }
+
+ cl = null ;
+ cl = clList.get( indice ) ;
+ places = cl.getNbGNode() ;
+ change_cluster = false ;
+ mappees = null ;
+ mappees = new ArrayList<GTask>() ;
+ }
+ }
+
+ if( ( atraiter.size() + encours.size() ) <= places )
+ {
+
+ for( int i = 0 ; i < atraiter.size() ; i++ )
+ {
+ mappees.add( atraiter.get( i ) ) ;
+ nb_ok++ ;
+ places-- ;
+ }
+
+ for( int i = 0 ; i < encours.size() ; i++ )
+ {
+ mappees.add( encours.get( i ) ) ;
+ nb_ok++ ;
+ places-- ;
+ }
+
+ atraiter = null ;
+ encours = null ;
+
+ atraiter = new ArrayList<GTask>() ;
+ encours = new ArrayList<GTask>() ;
+
+ mp.addMapping( cl, mappees ) ;
+
+ mapping_done = true ;
+ reduce = false ;
+ break ;
+ }
+
+ if( encours.size() == 0 && atraiter.size() > 0 )
+ {
+ encours.add( atraiter.remove(0) ) ;
+ }
+
+ tmp = null ;
+
+ if( encours.size() > 0 )
+ {
+ tmp = encours.get( 0 ) ;
+ }
+
+ if( tmp != null )
+ {
+ dep = calc_dep( tmp ) ;
+
+ if( dep != -1 && 1 + ( dep * dep_min ) <= places && places > 0 )
+ {
+ places -- ;
+ nb_ok ++ ;
+
+ ajoutDep( tmp ) ;
+
+ mappees.add( tmp ) ;
+ fait.add( tmp ) ;
+
+ atraiter.remove( tmp ) ;
+ encours.remove( tmp ) ;
+ } else {
+ change_cluster = true ;
+ }
+
+ if( places == 0 )
+ {
+ change_cluster = true ;
+ }
+
+ tmp = null ;
+ }
+ }
+
+ if( reduce )
+ {
+ mapping_done = false ;
+
+ System.out.println( "Reducing the minimum dependancies parameter..." ) ;
+ dep_min = dep_min - 0.1 ;
+ nb_ok = 0 ;
+ }
+
+ }
+
+
+ } else {
+ System.err.println( "\n\n!!! Mapping impossible ! There are more tasks than nodes !!!\n" ) ;
+ }
+ }
+
+ private ArrayList<Cluster> sortClusters()
+ {
+ ArrayList<Cluster> ret = new ArrayList<Cluster>() ;
+
+ boolean ok ;
+
+ for( int i = 0 ; i < gl.getNbCluster() ; i++ )
+ {
+ ok = false ;
+
+ if( ret.size() == 0 )
+ {
+ ret.add( gl.getClusters().get( i ) ) ;
+ } else {
+ for( int j = 0 ; j < ret.size() ; j++ )
+ {
+ if( gl.getClusters().get( i ).getNbFreeNodes() > ret.get( j ).getNbFreeNodes() )
+ {
+ ret.add( j, gl.getClusters().get( i ) ) ;
+ ok = true ;
+ break ;
+ }
+ }
+
+ if( ! ok )
+ {
+ ret.add( gl.getClusters().get( i ) ) ;
+ }
+ }
+ }
+
+ return ret ;
+ }
+
+
+ /**
+ *
+ * @param _t
+ */
+ private void ajoutDep( GTask _t )
+ {
+ if( _t != null )
+ {
+ GTask tmp = null ;
+
+ for( int i = 0 ; i < _t.getNbDep() ; i++ )
+ {
+ tmp = _t.getDependencies().get( i ) ;
+
+ if( ! fait.contains( tmp ) && ! encours.contains( tmp )
+ && tmp.getNbDep() < _t.getNbDep() )
+ {
+ int j = 0 ;
+ for( j = 0 ; j < encours.size() ; j++ )
+ {
+ if( tmp.getNbDep() < encours.get( j ).getNbDep() )
+ {
+ encours.add( j, tmp ) ;
+ j = encours.size() + 10 ;
+ }
+ }
+
+ if( j == encours.size() )
+ {
+ encours.add( tmp ) ;
+ }
+
+ atraiter.remove( tmp ) ;
+
+ tmp = null ;
+ }
+ }
+ }
+ }
+
+
+ /**
+ *
+ * @param _t
+ * @return
+ */
+ private double calc_dep( GTask _t )
+ {
+ int dep = 0 ;
+ int ext = 0 ;
+
+ double res = -1 ;
+
+ if( _t != null )
+ {
+ for( int i = 0 ; i < _t.getNbDep() ; i++ )
+ {
+ if( ! fait.contains( _t.getDependencies().get( i ) ) )
+ {
+ dep ++ ;
+ } else {
+ if( ! mappees.contains( _t.getDependencies().get( i ) ) )
+ {
+ ext++ ;
+ }
+ }
+
+ }
+
+ if( ( dep + ext ) < _t.getNbDep() * dep_min )
+ {
+ res = 0 ;
+ } else {
+ res = dep + ( ext * 0.5 ) ;
+ }
+ }
+
+ return res ;
+ }
+
+
+
+ /**
+ *
+ */
+ @SuppressWarnings("unchecked")
+ private void tri_dep()
+ {
+ int nb_tache = gr.getNbGTask() ;
+ int nb_tri = 0 ;
+ int niveau = 0 ;
+ int niveau_fait = -1 ;
+ int temp = 0 ;
+
+ ArrayList<GTask> tmp = new ArrayList<GTask>() ;
+ ArrayList<Integer> tab = new ArrayList<Integer>() ;
+
+ while( nb_tri < nb_tache )
+ {
+ // Recherche du niveau en décroissant
+ for( int i = 0 ; i < nb_tache ; i++ )
+ {
+ temp = atraiter.get(i).getNbDep() ;
+
+ if( niveau < temp )
+ {
+ if( niveau_fait != -1 )
+ {
+ if( temp < niveau_fait )
+ {
+ niveau = temp ;
+ }
+ } else {
+ niveau = temp ;
+ }
+ }
+ }
+
+ // Searching task of the current level
+ for( int i = 0 ; i < nb_tache ; i++ )
+ {
+ if( atraiter.get( i ).getNbDep() == niveau )
+ {
+ tmp.add( atraiter.get( i ) ) ;
+ tab.add( atraiter.get( i ).getNum() ) ;
+
+ nb_tri ++ ;
+ }
+ }
+
+ niveau_fait = niveau ;
+ niveau = 0 ;
+
+ }
+
+ atraiter = (ArrayList<GTask>) tmp.clone() ;
+ }
+
+
+ @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 = null ;
+ tmp = gl.getClusters().get( i ).nextGNode() ;
+
+ if( tmp != null )
+ {
+ ac.add( tmp ) ;
+ }
+ }
+ }
+
+ /** If there some nodes in clusters **/
+ if( ac.size() > 0 )
+ {
+ double dist = -1, best = -1 ;
+ int bestNode = -1 ;
+
+ /** Searching the replacing node with the lower distance
+ * between it and the failed node
+ */
+ for( int i = 0 ; i < ac.size() ; i++ )
+ {
+ dist = gl.getDistance( _dead, ac.get( i ) ) ;
+
+ if( best == -1 )
+ {
+ best = dist ;
+ bestNode = i ;
+ } else {
+ if( dist < best )
+ {
+ best = dist ;
+ bestNode = i ;
+ }
+ }
+ }
+
+ /** Is there any node candidate ? **/
+ if( bestNode != -1 )
+ {
+ ret = ac.get( bestNode ) ;
+
+ ret.setMapped( true ) ;
+ }
+ }
+ }
+
+ 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 !! **/
private boolean inCluster ;
private String cluster ;
private String site ;
+ private String ip ;
/**
return name ;
}
+
+ /**
+ * Return the IP address of the GNode.
+ * @return The IP address
+ */
+ public String getIP()
+ {
+ return ip ;
+ }
+
+
+ /**
+ * Set the IP address of the GNode.
+ * @param _ip The IP address
+ */
+ public void setIP( String _ip )
+ {
+ ip = _ip ;
+ }
+
}
/** La programmation est un art, respectons ceux qui la pratiquent !! **/
private ArrayList<GTask> graph ;
-// private int nb_task ;
private int nb_dep_total ;
public Graph()
{
graph = new ArrayList<GTask>() ;
-// nb_task = 0 ;
nb_dep_total = 0 ;
}
public int getNbGTask()
{
return graph.size() ;
-// return nb_task ;
}
{
graph.add( _lt.get( i ).getNum(), _lt.get( i ) ) ;
nb_dep_total += _lt.get( i ).getNbDep() ;
-// nb_task ++ ;
}
}
}
{
private static final long serialVersionUID = 1L;
-
-// private int nb_cluster ;
-// private int nb_node ;
private ArrayList<Cluster> clusters ;
private ArrayList<GNode> gnodesList;
private boolean gnodesList_done;
*/
public Grid()
{
-// nb_cluster = 0 ;
-// nb_node = 0 ;
clusters = new ArrayList<Cluster>() ;
gnodesList = new ArrayList<GNode>() ;
gnodesList_done = false ;
{
gnodesList.add( c.getGNodes().get( i ) ) ;
}
-// nb_cluster++ ;
-// nb_node += c.getNbGNode() ;
}
}
for( int i = 0 ; i < al.size() ; i++ )
{
clusters.add( al.get( i ) ) ;
-// nb_cluster++ ;
nbCLusterNodes = al.get( i ).getNbGNode() ;
-// nb_node += nbCLusterNodes ;
for( int j = 0 ; j < nbCLusterNodes ; j++ )
{
public int getNbCluster()
{
return clusters.size() ;
-// return nb_cluster ;
}
public int getNbGNode()
{
return gnodesList.size() ;
-// return nb_node ;
}
}
-// /**
-// * Initialization of clusters.
-// */
-// public void initClusters()
-// {
-// for( int i = 0 ; i < nb_cluster ; i++ )
-// {
-// clusters.get( i ).initIndice() ;
-// }
-// }
-
-
/**
* Compute and return the distance between two clusters.
* @param _g1 First cluster
}
}
- //
-
if( cluster1.compareTo( cluster2 ) == 0 )
{
d = 1 ;
_gnodes.get( i ).setInCluster( true ) ;
_gnodes.get( i ).setMapped( false ) ;
- clusters.get( i ).addGNode( _gnodes.get( j ) ) ;
-// nb_node++ ;
+ clusters.get( j ).addGNode( _gnodes.get( i ) ) ;
gnodesList.add( _gnodes.get( i ) ) ;
} else {
_gnodes.get( i ).setCluster( cluster ) ;
nClust.addGNode( _gnodes.get( i ) ) ;
-// nb_cluster++ ;
clusters.add( nClust ) ;
-// nb_node++ ;
gnodesList.add( _gnodes.get( i ) ) ;
}
}
/**
- * Remove a computing node from the grid.
- * @param _dead The node to be removed
+ * Upgrade the grid with a new node.
+ * @param _g The new node
*/
- public void removeGNode( GNode _dead )
+ public void addGNode( GNode _g )
{
- if( _dead != null )
+ if( _g != null )
{
- if( _dead.getMapped() )
+ /** Searching the cluster in which the node should be added **/
+ int j = 0 ;
+ for( j = 0; j < clusters.size(); j++ )
{
- String site = "", cluster = "" ;
-
- site = _dead.getSite() ;
- cluster = _dead.getCluster() ;
-
- /** Removing GNode from its cluster **/
- for( int j = 0 ; j < clusters.size() ; j++ )
+ if( _g.getCluster().equalsIgnoreCase( clusters.get( j ).getName() ) )
{
- if( clusters.get( j ).getName().equals( cluster ) && clusters.get( j ).getSite().equals( site ))
+ int pos = clusters.get( j ).isIn( _g ) ;
+
+ if( pos == -1 )
{
- clusters.get( j ).removeGNode( _dead ) ;
-
- break ;
+ _g.setSite( clusters.get( j ).getSite() ) ;
+ _g.setInCluster( true ) ;
+ _g.setMapped( false ) ;
+
+ clusters.get( j ).addGNode( _g ) ;
+ gnodesList.add( _g ) ;
+
+ } else {
+ clusters.get( j ).removeGNode( _g ) ;
+ clusters.get( j ).addGNode( _g ) ;
}
+
+ break ;
}
}
+
+ /** The cluster was not found, so it is a new one **/
+ if( j == clusters.size() )
+ {
+ String site = "", cluster = "" ;
+ Cluster nClust = new Cluster() ;
+
+ String names[] = Utils.decodeG5Knames( _g.getName() ) ;
+
+ cluster = names[ 1 ] ;
+ site = names[ 2 ] ;
+
+ System.out.println("** (Grid) Creation of cluster: "+cluster);
+
+ nClust.setName( cluster ) ;
+ nClust.setSite( site ) ;
+
+ _g.setInCluster( true ) ;
+ _g.setMapped( false ) ;
+ _g.setSite( site ) ;
+ _g.setCluster( cluster ) ;
+
+ nClust.addGNode( _g ) ;
+
+ clusters.add( nClust ) ;
+ gnodesList.add( _g ) ;
+ }
+ }
+ gnodesList_done = false ;
+ }
+
+
+ /**
+ * Remove a computing node from the grid.
+ * @param _dead The node to be removed
+ */
+ public void removeGNode( GNode _dead )
+ {
+ if( _dead != null )
+ {
+ /** Removing GNode from its cluster **/
+ int id = getClusterOfNode( _dead ) ;
+
+ if( id != -1 )
+ {
+ clusters.get( id ).removeGNode( _dead ) ;
+ } else {
+ System.err.println( "(Grid) Cluster of dead node not found!" ) ;
+ }
+
/** Removing the dead node from the global list **/
- for( int i = 0 ; i < gnodesList.size() ; i++ )
+ int i = 0 ;
+ for( i = 0 ; i < gnodesList.size() ; i++ )
{
if( _dead.getId() == gnodesList.get( i ).getId() )
{
break ;
}
}
+
+ } else {
+ System.err.println( "(Grid) The GNode to be deleted is null!" ) ;
}
-
-// nb_node-- ;
+
gnodesList_done = false ;
}
if( _g != null )
{
/** Change in the cluster **/
- getClusterOfNode( _g ).setGNodeStatus( _g, _status ) ;
+ int id = getClusterOfNode( _g ) ;
+
+ if( id != -1 )
+ {
+ clusters.get(id).setGNodeStatus( _g, _status ) ;
+ } else {
+ System.err.println( "(Grid) Cluster "+_g.getCluster()+" not found!" ) ;
+ }
/** Change in local list **/
for( int i = 0 ; i < gnodesList.size() ; i++ )
* @param _g A node
* @return The cluster containing the node
*/
- public Cluster getClusterOfNode( GNode _g )
+ public int getClusterOfNode( GNode _g )
{
+ int ret = -1 ;
+
if( _g != null )
{
for( int i = 0 ; i < clusters.size() ; i++ )
{
if( _g.getCluster().equalsIgnoreCase( clusters.get( i ).getName() ) )
{
- return clusters.get( i ) ;
+ if( _g.getSite().equalsIgnoreCase( clusters.get( i ).getSite() ) )
+ {
+ ret = i ;
+ break ;
+ }
}
}
}
- return null ;
+ return ret ;
}
/**
std = Math.sqrt( temp ) ;
/** Computation of the relative standard deviation **/
- hd = 100 * std / average ;
+ hd = std / average ;
+
+ /** Correction of the maximum value **/
+ if( hd > 1 )
+ {
+ hd = 1 ;
+ }
return hd ;
{
setMappedStatus( _ag.get( i ), false ) ;
- getClusterOfNode( _ag.get( i ) ).setGNodeStatus( _ag.get( i ), false ) ;
+ int id = getClusterOfNode( _ag.get( i ) ) ;
+
+ if( id != -1 )
+ {
+ clusters.get(id).setGNodeStatus( _ag.get( i ), false ) ;
+ } else {
+ System.err.println( "Cluster not found" ) ;
+ }
}
}
}
System.out.println();
}
+
+
+ /**
+ * Return the average power of the grid, by computing the average for
+ * eac cluster.
+ * @return The average power of the grid
+ */
+ public double getAvgFreePower()
+ {
+ double ret = 0 ;
+ int nb = 0 ;
+
+ if( clusters != null && clusters.size() > 0 )
+ {
+ for( int i = 0 ; i < clusters.size() ; i++ )
+ {
+ nb++ ;
+
+ ret += clusters.get( i ).getAvailablePower() / clusters.get( i ).getNbFreeNodes() ;
+ }
+
+ ret = ret / nb ;
+
+ }
+
+ return ret ;
+ }
+
+
+ /**
+ * Return the amount of freenodes available in the whole grid.
+ * @return The amount of available nodes
+ */
+ public int getNbFreenodes()
+ {
+ int ret = 0 ;
+
+ for( int i = 0 ; i < clusters.size() ; i++ )
+ ret += clusters.get(i).getNbFreeNodes() ;
+ return ret ;
+ }
}
--- /dev/null
+package and.Mapping;
+
+import java.util.ArrayList;
+
+
+
+public class Maheve extends Algo
+{
+ private static final long serialVersionUID = 1L;
+
+ private static final int minNode = 5 ;
+ private static final int nbSave = 2 ;
+
+ private double hd ;
+ private ArrayList<Cluster> sortedCluster = null ;
+ private ArrayList<GTask> tasks = null ;
+
+
+ /**
+ * Empty default constructor.
+ */
+ public Maheve()
+ {
+ super() ;
+ name = "MAHEVE_2" ;
+ sortedCluster = new ArrayList<Cluster>() ;
+ }
+
+
+ /**
+ * Constructor of this algorithm, which takes into parameter
+ * the application graph, the grid architecture, and the correction
+ * parameter which indicates the threshold of the heterogeneity degree.
+ * @param _gr The application graph
+ * @param _gl The grid architecture
+ * @param _threshold The heterogeneity threshold
+ */
+ public Maheve( Graph _gr, Grid _gl )
+ {
+ super( _gr, _gl ) ;
+
+ hd = 0 ;
+ sortedCluster = new ArrayList<Cluster>() ;
+ tasks = new ArrayList<GTask>() ;
+ name = "MAHEVE_2" ;
+ }
+
+
+ @Override
+ public void map() {
+ /** If the mapping is possible ... **/
+ if( ( gr != null ) && ( gr.getNbGTask() <= gl.getNbGNode() ) )
+ {
+ System.out.println( "******************************************" ) ;
+ System.out.println( "* Launching the MAHEVE Mapping algorithm *" ) ;
+ System.out.println( "******************************************\n\n" ) ;
+
+ /** Local variables **/
+ ArrayList<GNode> used = null ;
+
+ /** Initialization of heterogeneity degree **/
+ hd = gl.getHeterogenityDegre() ;
+
+
+ /** Ordering clusters according to their real power **/
+ updateSortedClusters() ;
+
+ /** Searching the corresponding nodes **/
+ used = searchNodes( gr.getNbGTask() ) ;
+
+ if( used == null || used.size() == 0 )
+ {
+ System.err.println( "No node returned!" ) ;
+ return ;
+ }
+
+
+ /** Ordering tasks **/
+ orderTasks() ;
+
+ if( tasks == null || tasks.size() == 0 )
+ {
+ System.err.println( "Unable to retrieve tasks to be mapped on!" ) ;
+ return ;
+ }
+
+
+ /** Save the Mapping **/
+ for( int i = 0 ; i < tasks.size() ; i++ )
+ {
+ mp.addMapping( new Association( used.get( i ), tasks.get( i ) ) ) ;
+ }
+
+ } else {
+ System.err.println( "\n\n!!! Unable to map application!\n\n" ) ;
+ return ;
+ }
+ }
+
+
+ private void orderTasks()
+ {
+ ArrayList<GTask> l1 = sortTasks() ;
+
+ if( l1 != null && l1.size() > 0 )
+ {
+ ArrayList<GTask> l2 = new ArrayList<GTask>() ;
+ ArrayList<GTask> tmp = new ArrayList<GTask>() ;
+
+ while( l1.size() > 0 )
+ {
+ if( l2.size() == 0 )
+ {
+ l2.add( l1.get( 0 ) ) ;
+ }
+
+ while( l2.size() > 0 )
+ {
+ l1.remove( l2.get( 0 ) ) ;
+ tmp = addTask( l2.remove( 0 ), l1 ) ;
+
+ for( int i = 0 ; i < tmp.size() ; i++ )
+ {
+ l2.add( tmp.get( i ) ) ;
+ }
+ }
+ }
+ }
+ }
+
+
+ private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar)
+ {
+
+ ArrayList<GTask> ret = null ;
+
+ if( _gt != null && _ar != null )
+ {
+ ret = new ArrayList<GTask>() ;
+
+ // ** Adding the task in the main list ** //
+ tasks.add( _gt ) ;
+
+ // ** Searching its dependencies ** //
+ int nbDep = (int) (_gt.getNbDep() * (1.0 - hd)) ;
+ int cmpt = 0 ;
+ int num = 0 ;
+
+ ArrayList<Integer> dep = new ArrayList<Integer>() ;
+
+ for( int i = 0 ; i < _gt.getDependencies().size() ; i++ )
+ {
+ dep.add( _gt.getDependencies().get( i ).getNum() ) ;
+ }
+
+ for( int i = 0 ; i < _ar.size() ; i++ )
+ {
+ num = _ar.get( i ).getNum() ;
+
+ for( int j = 0 ; j < dep.size() ; j++ )
+ {
+ if( num == dep.get( j ) )
+ {
+ ret.add( _ar.remove( i ) ) ;
+ cmpt++ ;
+ dep.remove( j ) ;
+ break ;
+ }
+ }
+
+ if( cmpt == nbDep )
+ {
+ break ;
+ }
+ }
+ }
+
+ return ret;
+ }
+
+
+ private ArrayList<GTask> sortTasks()
+ {
+ ArrayList<GTask> ret = null ;
+
+ ArrayList<GTask> tmp = gr.getGraph() ;
+
+ if( tmp != null && tmp.size() > 0 )
+ {
+ ret = new ArrayList<GTask>() ;
+
+ ArrayList<Double> mt = new ArrayList<Double>() ;
+
+ double W, D, MT ;
+ boolean ok = false ;
+
+ for( int i = 0 ; i < tmp.size() ; i++ )
+ {
+ W = tmp.get( i ).getWeight() ;
+ D = tmp.get( i ).getNbDep() ;
+
+ ok = false ;
+
+ MT = Math.pow( W, hd ) * Math.pow( D, ( 1.0 - hd) ) ;
+
+ if( ret.size() == 0 )
+ {
+ ret.add( tmp.get( i ) ) ;
+ mt.add( MT ) ;
+ } else {
+ for( int j = 0 ; j < ret.size() ; j++ )
+ {
+ if( MT > mt.get( j ) )
+ {
+ ret.add( j, tmp.get( i ) ) ;
+ mt.add( j, MT ) ;
+
+ ok = true ;
+ break ;
+ }
+ }
+
+ if( ! ok )
+ {
+ ret.add( tmp.get( i ) ) ;
+ mt.add( MT ) ;
+ }
+ }
+ }
+ }
+
+ return ret ;
+ }
+
+
+ private ArrayList<GNode> searchNodes( int _nbTask )
+ {
+ ArrayList<GNode> ret = null ;
+
+ if( _nbTask > 0 )
+ {
+ ret = new ArrayList<GNode>() ;
+ int nbFound = 0 ;
+ int max = 0 ;
+ GNode g = null ;
+
+ for( int i = 0 ; i < sortedCluster.size() ; i++ )
+ {
+ /** If there is enough nodes ... **/
+ if( sortedCluster.get( i ).getNbFreeNodes() >= minNode )
+ {
+ max = 0 ;
+
+ max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ;
+
+ for( int j = 0 ; j < max ; j++ )
+ {
+ g = sortedCluster.get( i ).nextGNode() ;
+ ret.add( g ) ;
+ sortedCluster.get( i ).setGNodeStatus( g, true ) ;
+
+ nbFound ++ ;
+
+ if( nbFound >= _nbTask )
+ break ;
+ }
+ }
+
+ if( nbFound >= _nbTask )
+ break ;
+ }
+ }
+
+ return ret ;
+ }
+
+
+ /**
+ * Sort clusters according to the heterogeneity degree of the platform and
+ * the eventual application's threshold.
+ */
+ private void updateSortedClusters()
+ {
+ if( gl != null )
+ {
+ /** Purging the local list **/
+ sortedCluster = null ;
+ sortedCluster = new ArrayList<Cluster>() ;
+
+ ArrayList<Double> calcMark = new ArrayList<Double>() ;
+
+ hd = gl.getHeterogenityDegre() ;
+
+ /** Sorting clusters **/
+ ArrayList<Cluster> tmp = gl.getClusters() ;
+
+ boolean ok ;
+
+ double calcLoc = 0 ;
+ double locP ;
+ int N ;
+ double P ;
+
+ for( int i = 0 ; i < tmp.size() ; i++ )
+ {
+ N = tmp.get( i ).getNbFreeNodes() ;
+ P = tmp.get( i ).getAvailablePower() ;
+ locP = P / N ;
+
+ /** The magic formula :P **/
+ calcLoc = Math.sqrt( locP * Math.pow((1.5 * hd + 0.3), 2) +
+ N * Math.pow((1.1 - hd), 2 ) ) ;
+
+ ok = false ;
+
+ if( sortedCluster.size() == 0 )
+ {
+ sortedCluster.add( tmp.get( i ) ) ;
+ calcMark.add( calcLoc ) ;
+ } else {
+
+ for( int j = 0 ; j < sortedCluster.size() ; j++ )
+ {
+ if( calcLoc > calcMark.get( j ) )
+ {
+ sortedCluster.add( j, tmp.get( i ) ) ;
+ calcMark.add( j, calcLoc ) ;
+ ok = true ;
+ break ;
+ }
+ }
+
+ if( ! ok )
+ {
+ sortedCluster.add( tmp.get( i ) ) ;
+ calcMark.add( calcLoc ) ;
+ }
+ }
+ }
+ }
+ }
+
+
+ @Override
+ public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
+ {
+ GNode ret = null ;
+
+ /** If something has to be done **/
+ if( _dead != null )
+ {
+ boolean ok = false ;
+ /** Any place on the same cluster ? **/
+ for( int i = 0 ; i < gl.getNbCluster() ; i++ )
+ {
+ Cluster cl = null ;
+
+ int id = gl.getClusterOfNode( _dead ) ;
+
+ if( id != -1 )
+ {
+ cl = gl.getClusters().get(id) ;
+
+ if( cl.getNbFreeNodes() > 0 )
+ {
+ ret = cl.nextGNode() ;
+ ok = true ;
+ }
+ } else {
+ System.err.println( "Cluster not found!" ) ;
+ }
+ }
+
+ /** If there is no more place, try other clusters **/
+ if( ! ok )
+ {
+ updateSortedClusters() ;
+
+ for( int i = 0 ; i < sortedCluster.size() ; i++ )
+ {
+ if( sortedCluster.get( i ).getNbFreeNodes() > 0 )
+ {
+ ret = sortedCluster.get( i ).nextGNode() ;
+ ok = true ;
+ break ;
+ }
+ }
+ }
+
+ nb_fault++ ;
+ }
+
+ return ret ;
+ }
+
+
+ @Override
+ public GNode getOtherGNode( ArrayList<GNode> _ag )
+ {
+ GNode ret = null ;
+
+ /** Searching the cluster which has the more free nodes **/
+ int pos = -1, max = 0, cur = 0 ;
+ for( int i = 0 ; i < gl.getNbCluster() ; i++ )
+ {
+ cur = gl.getClusters().get( i ).getNbFreeNodes() ;
+ if( cur > max)
+ {
+ pos = i ;
+ max = cur ;
+ }
+ }
+
+ ret = gl.getClusters().get( pos ).nextGNode() ;
+
+ return ret ;
+ }
+
+}
+
+/** La programmation est un art, respectons ceux qui la pratiquent !! **/
/* Two kinds of Mapping, according to algorithms' goal */
private ArrayList<Association> mapping ;
private ArrayList<Association> mapping2 ;
+ private ArrayList<GNode> other ;
private int type ; // 0 : mapping task/node ; 1 : mapping tasks/cluster
{
mapping = new ArrayList<Association>() ;
mapping2 = new ArrayList<Association>() ;
+ other = new ArrayList<GNode>() ;
type = -1 ;
}
{
mapping = new ArrayList<Association>() ;
mapping2 = new ArrayList<Association>() ;
+ other = new ArrayList<GNode>() ;
type = -1 ;
}
GNode tmp = null ;
for( int i = 0 ; i < at.size() ; i++ )
{
- tmp = c.nextGNode() ;
+ tmp = c.moreGNode() ;
if( tmp != null )
{
insertMapping( new Association( tmp, at.get( i ) ) ) ;
{
if( _a != null && _a.getGNode() != null && _a.getGTask() != null )
{
-// int ind = _a.getGTask().getNum() ;
-//
-// mapping.add( ind - 1, _a ) ;
mapping.add( _a ) ;
}
}
+ /**
+ * Determine if a node is used as an other node in the mapping.
+ * @param _g The node to search
+ * @return The position of the node
+ */
+ private int searchOther( GNode _g )
+ {
+ int pos = -1 ;
+
+ if( _g != null )
+ {
+ for( int i = 0 ; i < other.size() ; i++ )
+ {
+ if( _g.getId() == other.get( i ).getId() )
+ {
+ pos = i ;
+ break ;
+ }
+ }
+ }
+
+ return pos ;
+ }
+
+
+ /**
+ * Add a new node in the other nodes list.
+ * @param _g The other node
+ */
+ public void addOtherNode( GNode _g )
+ {
+ if( _g != null )
+ {
+ int pos = searchOther( _g ) ;
+
+ if( pos != -1 )
+ {
+ other.add( _g ) ;
+ } else {
+ System.out.println( "This node already exist in OtherNodes! " +
+ "I replace it" ) ;
+ other.set( pos, _g ) ;
+ }
+ }
+ }
+
+
+ /**
+ * Remove a node in the other nodes list.
+ * @param _g The node to be removed
+ */
+ public void removeOtherNode( GNode _g )
+ {
+ if( _g != null )
+ {
+ int pos = searchOther( _g ) ;
+
+ if( pos != -1 )
+ {
+ other.remove( pos ) ;
+ } else {
+ System.err.println( "This node does not exist in OtherNodes!" ) ;
+ }
+ }
+ }
+
+
/**
* Remove a failed node from the mapping.
* @param _deadNode The failed node
public ArrayList<GNode> getMappedGNodes()
{
ArrayList<GNode> ar = new ArrayList<GNode>() ;
-
+
if( mapping.size() != 0 )
{
-// if( type == 0 )
-// {
-// ArrayList<Association> tmp = (ArrayList<Association>) mapping.clone() ;
-
- for( int i = 0 ; i < mapping.size() ; i++ )
- {
-// for( int j = 0 ; j < tmp.size() ; j++ )
-// {
-// if( tmp.get( j ).getGTask().getNum() == i )
-// {
- ar.add( mapping.get( i ).getGNode() ) ;
-// tmp.remove( j ) ;
-// j = tmp.size() + 2 ;
-// }
-// }
- }
-// }
-//
-// if( type == 1 )
-// {
-// ArrayList<Association> tmp = (ArrayList<Association>) mapping2.clone() ;
-//
-// for( int i = 0 ; i < mapping2.size() ; i++ )
-// {
-// for( int j = 0 ; j < tmp.size() ; j++ )
-// {
-// if( tmp.get( j ).getGTask().getNum() == i )
-// {
-// ar.add( tmp.get( j ).getGNode() ) ;
-// tmp.remove( j ) ;
-// j = tmp.size() + 2 ;
-// }
-// }
-// }
-// }
+ for( int i = 0 ; i < mapping.size() ; i++ )
+ {
+ ar.add( mapping.get( i ).getGNode() ) ;
+ }
}
-
+
return ar ;
}
-
+
/**
* Print the status of the mapping done, according to its type.
*/
- public void print()
+ public void print( int _type )
{
+ int type_print = _type ;
+
System.out.println();
System.out.println( "\t=> Mapping done:\n" ) ;
- if( type == 0 )
+ if( type_print == 0 )
{
ArrayList<GNode> ar = getMappedGNodes() ;
System.out.println() ;
}
- if( type == 1 )
+ if( type_print == 1 )
{
for( int i = 0 ; i < mapping2.size() ; i++ )
{
}
+ /**
+ * Return the association of the given position.
+ * @param _id The position of the Association
+ * @return The Association requested
+ */
+ public Association getAssociation( int _id )
+ {
+ if( _id >= 0 && _id < mapping.size() )
+ {
+ return mapping.get( _id ) ;
+ } else {
+ return null ;
+ }
+ }
+
+
+ /**
+ * Remove the association of the given position.
+ * @param _id The position of the Association
+ * @return The Association removed
+ */
+ public Association removeAssociation( int _id )
+ {
+ if( _id >= 0 && _id < mapping.size() )
+ {
+ return mapping.remove( _id ) ;
+ } else {
+ return null ;
+ }
+ }
+
+ /**
+ * Return the position of the association containing
+ * the GTask of a specified rank.
+ * @param _taskRank The rank of the task
+ * @return The position of the association
+ */
+ public int getIdOfAssociation( int _taskRank )
+ {
+ int ret = -1 ;
+
+ for( int i = 0 ; i < mapping.size() ; i++ )
+ {
+ if( mapping.get( i ).getGTask().getNum() == _taskRank )
+ {
+ ret = i ;
+ break ;
+ }
+ }
+
+ return ret ;
+ }
+
/**
* Return the amount of external tasks dependencies, in cluster point of view.
* @return The amount of external dependencies
/**
- * Implementation of Simple Mapping algorithm
+ * Implementation of the Simple Mapping algorithm (no fault tolerance mechanism)
* @author Sébastien Miquée
* @version 1.0
*/
public Simple()
{
super() ;
+ name = "Simple" ;
}
public Simple( Graph _gr, Grid _gd )
{
super( _gr, _gd ) ;
+
+ name = "Simple" ;
}
/**
{
grn = new ArrayList<GNode>() ;
- // Tri des clusters suivant leur taille
+ // Sorting clusters according to their "size"
ArrayList<Cluster> cl = gl.getClusters() ;
ArrayList<Cluster> cl2 = new ArrayList<Cluster>() ;
System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
}
- /** Update in cluster the status of nodes **/
- updateGrid() ;
}
} else {
System.err.println( "Not enought available nodes in gnodes to replace one !" ) ;
return null ;
- }
+ }
+
+ nb_fault++ ;
}
- /** Update in cluster the status of nodes **/
- updateGrid() ;
-
return ret ;
}
e.printStackTrace();
System.exit( 1 ) ;
}
+
+ /* Host IP */
+ String ip = null ;
+ try {
+ InetAddress addr = InetAddress.getLocalHost() ;
+ ip = addr.getHostAddress() ;
+ } catch( final Exception e ) {
+ System.err.println( "Unalbe to retrieve host's name !" ) ;
+ e.printStackTrace();
+ System.exit( 1 ) ;
+ }
+ String names[] = decodeG5Knames( name ) ;
/* Updating node information */
n.setFrequency( frequency ) ;
n.setMemory( memory ) ;
n.setNb_cores( nbCore ) ;
n.setName( name ) ;
+ n.setCluster( names[1] ) ;
+ n.setSite( names[2] ) ;
+ n.setIP( ip ) ;
n.setMapped( false ) ;
return n ;
if ( ! _file.endsWith( ".xml" ) )
{
- _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+ _file = _file + ".xml"; // Adding xml extension to file
}
if( ! _file.equals( "" ) )
if ( ! _file.endsWith( ".xml" ) )
{
- _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+ _file = _file + ".xml"; // Adding xml extension to file
}
if( ! _file.equals( "" ) )
if ( ! _file.endsWith( ".xml" ) )
{
- _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+ _file = _file + ".xml"; // Adding xml extension to file
}
if( ! _file.equals( "" ) )
if ( ! _file.endsWith( ".xml" ) )
{
- _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+ _file = _file + ".xml"; // Adding xml extension to file
}
String path = "" ;
if ( ! _file.endsWith( ".xml" ) )
{
- _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+ _file = _file + ".xml"; // Adding xml extension to file
}
String path = "" ;
if ( ! _file.endsWith( ".xml" ) )
{
- _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+ _file = _file + ".xml"; // Adding xml extension to file
}
String path = "" ;
