--- /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 !! **/
