From: Sébastien Miquée Date: Fri, 7 May 2010 08:51:55 +0000 (+0200) Subject: New stable version with the add of the Maheve algorithm. X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/mapping.git/commitdiff_plain/732a7291d1f84c7c95026129b8550b84f69337e5 New stable version with the add of the Maheve algorithm. - Adding the new efficient MAHEVE mapping algorithm. - Correction of some bugs. - Adding minor functionalities. - Cleaning code. --- diff --git a/src/and/Mapping/Algo.java b/src/and/Mapping/Algo.java index 142b8a6..ab4a895 100644 --- a/src/and/Mapping/Algo.java +++ b/src/and/Mapping/Algo.java @@ -17,6 +17,8 @@ public abstract class Algo implements Serializable protected Grid gl ; protected Mapping mp ; protected String ids ; + protected String name ; + protected int nb_fault ; /** @@ -28,6 +30,8 @@ public abstract class Algo implements Serializable gl = new Grid() ; mp = new Mapping() ; ids = "" ; + name = "" ; + nb_fault = 0 ; } @@ -42,6 +46,8 @@ public abstract class Algo implements Serializable gl = _gl ; mp = new Mapping() ; ids = "" ; + name = "" ; + nb_fault = 0 ; } @@ -105,10 +111,33 @@ public abstract class Algo implements Serializable */ 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 @@ -120,21 +149,26 @@ public abstract class Algo implements Serializable /** - * 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 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 !! **/ diff --git a/src/and/Mapping/Architecture.java b/src/and/Mapping/Architecture.java index 91e45a9..530c9da 100644 --- a/src/and/Mapping/Architecture.java +++ b/src/and/Mapping/Architecture.java @@ -1,5 +1,6 @@ package and.Mapping ; +import java.io.Serializable; import java.util.ArrayList; @@ -8,8 +9,10 @@ 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 archi ; private int nbNodes ; private int nbClusters ; diff --git a/src/and/Mapping/Association.java b/src/and/Mapping/Association.java index 7d24134..ab8ebdc 100644 --- a/src/and/Mapping/Association.java +++ b/src/and/Mapping/Association.java @@ -94,10 +94,18 @@ public class Association implements Serializable /** * 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 ; + } } diff --git a/src/and/Mapping/Cluster.java b/src/and/Mapping/Cluster.java index 4d59d3d..712f17c 100644 --- a/src/and/Mapping/Cluster.java +++ b/src/and/Mapping/Cluster.java @@ -14,12 +14,11 @@ public class Cluster implements Serializable { private static final long serialVersionUID = 1L; -// private int nb_node ; private String name ; private ArrayList nodes ; private ArrayList freenodes ; private String site ; -// private int indice ; + private int moreNode ; /** @@ -27,56 +26,14 @@ public class Cluster implements Serializable */ public Cluster() { -// nb_node = 0 ; name = "" ; nodes = new ArrayList() ; freenodes = new ArrayList() ; 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() ; -// freenodes = new ArrayList() ; -// 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() ; -// 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 @@ -98,8 +55,6 @@ public class Cluster implements Serializable _n.setInCluster( true ) ; nodes.add( _n ) ; -// nb_node++ ; - if( ! _n.getMapped() ) { freenodes.add( _n ) ; @@ -134,7 +89,6 @@ public class Cluster implements Serializable */ public int getNbGNode() { -// return nb_node ; return nodes.size() ; } @@ -184,29 +138,14 @@ public class Cluster implements Serializable 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 ) ; @@ -214,6 +153,30 @@ public class Cluster implements Serializable 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 ; + } /** @@ -222,18 +185,40 @@ public class Cluster implements Serializable */ 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!" ) ; } } @@ -255,7 +240,15 @@ public class Cluster implements Serializable 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 ) ) ; @@ -279,29 +272,19 @@ public class Cluster implements Serializable /** * 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 ; diff --git a/src/and/Mapping/DefaultMapping.java b/src/and/Mapping/DefaultMapping.java index 2f096b8..3de90b1 100644 --- a/src/and/Mapping/DefaultMapping.java +++ b/src/and/Mapping/DefaultMapping.java @@ -2,6 +2,7 @@ package and.Mapping ; import java.util.ArrayList; +import java.util.Random; /** @@ -23,6 +24,7 @@ public class DefaultMapping extends Algo public DefaultMapping() { super() ; + name = "DefaultMapping" ; } @@ -35,6 +37,7 @@ public class DefaultMapping extends Algo { super( _gr, _gd ) ; archi = _gnodes ; + name = "DefaultMapping" ; } @@ -60,9 +63,6 @@ public class DefaultMapping extends Algo } else { System.err.println( "\n\n!!! Unable to map application !\n\n" ) ; } - - /** Update in cluster the status of nodes **/ - updateGrid() ; } @@ -71,7 +71,7 @@ public class DefaultMapping extends Algo { GNode ret = null ; - if( _dead != null ) + if( _dead != null && _ag != null ) { int pos = 0 ; pos = mp.getIdOfAssociation( _dead ) ; @@ -84,18 +84,17 @@ public class DefaultMapping extends Algo 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 ; } @@ -106,7 +105,7 @@ public class DefaultMapping extends Algo /** Returning the first node in the list **/ if( _ag.size() > 0 ) { - return _ag.get( 1 ) ; + return _ag.get( 0 ) ; } return null ; diff --git a/src/and/Mapping/FT_AIAC_QM.java b/src/and/Mapping/FT_AIAC_QM.java new file mode 100644 index 0000000..a7e87c6 --- /dev/null +++ b/src/and/Mapping/FT_AIAC_QM.java @@ -0,0 +1,619 @@ +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 atraiter ; + private ArrayList 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 sortInitGNode() + { + ArrayList grn = null ; + + if( gl != null ) + { + grn = new ArrayList() ; + + ArrayList 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 listToGTask2( Graph _gr ) + { + ArrayList gr2 = null ; + + if( _gr != null ) + { + gr2 = new ArrayList() ; + + 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 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 researchNeighbours( GTask2 _g, double _deep) + { + ArrayList nb = new ArrayList() ; + ArrayList neighbours = new ArrayList() ; + + 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 _ag ) + { + GNode ret = null ; + + /** If something has to be done **/ + if( _dead != null ) + { + ArrayList ac = new ArrayList() ; + 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 _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 !! **/ diff --git a/src/and/Mapping/FT_FEC.java b/src/and/Mapping/FT_FEC.java new file mode 100644 index 0000000..28f78f8 --- /dev/null +++ b/src/and/Mapping/FT_FEC.java @@ -0,0 +1,521 @@ +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 atraiter ; + private ArrayList encours ; + private ArrayList fait ; + private ArrayList clList ; + private double dep_min ; + ArrayList mappees ; + + + /** + * Default constructor. + */ + public FT_FEC() + { + super() ; + + atraiter = new ArrayList() ; + encours = new ArrayList() ; + fait = new ArrayList() ; + clList = new ArrayList() ; + 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() ; + encours = new ArrayList() ; + fait = new ArrayList() ; + clList = new ArrayList() ; + 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() ; + encours = new ArrayList() ; + fait = new ArrayList() ; + clList = new ArrayList() ; + 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) 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() ; + } + } + + 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() ; + encours = new ArrayList() ; + + 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 sortClusters() + { + ArrayList ret = new ArrayList() ; + + 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 tmp = new ArrayList() ; + ArrayList tab = new ArrayList() ; + + 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) tmp.clone() ; + } + + + @Override + public GNode replaceNode( GNode _dead, ArrayList _ag ) + { + GNode ret = null ; + + /** If something has to be done **/ + if( _dead != null ) + { + ArrayList ac = new ArrayList() ; + 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 _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 !! **/ diff --git a/src/and/Mapping/GNode.java b/src/and/Mapping/GNode.java index b76d0c1..e7d5f94 100644 --- a/src/and/Mapping/GNode.java +++ b/src/and/Mapping/GNode.java @@ -23,6 +23,7 @@ public class GNode implements Serializable private boolean inCluster ; private String cluster ; private String site ; + private String ip ; /** @@ -293,6 +294,26 @@ public class GNode implements Serializable 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 !! **/ diff --git a/src/and/Mapping/Graph.java b/src/and/Mapping/Graph.java index 79efb2f..8f255cd 100644 --- a/src/and/Mapping/Graph.java +++ b/src/and/Mapping/Graph.java @@ -17,7 +17,6 @@ public class Graph implements Serializable private ArrayList graph ; -// private int nb_task ; private int nb_dep_total ; @@ -27,7 +26,6 @@ public class Graph implements Serializable public Graph() { graph = new ArrayList() ; -// nb_task = 0 ; nb_dep_total = 0 ; } @@ -39,7 +37,6 @@ public class Graph implements Serializable public int getNbGTask() { return graph.size() ; -// return nb_task ; } @@ -70,7 +67,6 @@ public class Graph implements Serializable { graph.add( _lt.get( i ).getNum(), _lt.get( i ) ) ; nb_dep_total += _lt.get( i ).getNbDep() ; -// nb_task ++ ; } } } diff --git a/src/and/Mapping/Grid.java b/src/and/Mapping/Grid.java index 3501a2d..57345cd 100644 --- a/src/and/Mapping/Grid.java +++ b/src/and/Mapping/Grid.java @@ -14,9 +14,6 @@ public class Grid implements Serializable { private static final long serialVersionUID = 1L; - -// private int nb_cluster ; -// private int nb_node ; private ArrayList clusters ; private ArrayList gnodesList; private boolean gnodesList_done; @@ -27,8 +24,6 @@ public class Grid implements Serializable */ public Grid() { -// nb_cluster = 0 ; -// nb_node = 0 ; clusters = new ArrayList() ; gnodesList = new ArrayList() ; gnodesList_done = false ; @@ -49,8 +44,6 @@ public class Grid implements Serializable { gnodesList.add( c.getGNodes().get( i ) ) ; } -// nb_cluster++ ; -// nb_node += c.getNbGNode() ; } } @@ -68,9 +61,7 @@ public class Grid implements Serializable 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++ ) { @@ -88,7 +79,6 @@ public class Grid implements Serializable public int getNbCluster() { return clusters.size() ; -// return nb_cluster ; } @@ -99,7 +89,6 @@ public class Grid implements Serializable public int getNbGNode() { return gnodesList.size() ; -// return nb_node ; } @@ -113,18 +102,6 @@ public class Grid implements Serializable } -// /** -// * 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 @@ -157,8 +134,6 @@ public class Grid implements Serializable } } - // - if( cluster1.compareTo( cluster2 ) == 0 ) { d = 1 ; @@ -227,8 +202,7 @@ public class Grid implements Serializable _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 { @@ -260,10 +234,8 @@ public class Grid implements Serializable _gnodes.get( i ).setCluster( cluster ) ; nClust.addGNode( _gnodes.get( i ) ) ; -// nb_cluster++ ; clusters.add( nClust ) ; -// nb_node++ ; gnodesList.add( _gnodes.get( i ) ) ; } } @@ -274,34 +246,92 @@ public class Grid implements Serializable /** - * 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() ) { @@ -309,9 +339,11 @@ public class Grid implements Serializable break ; } } + + } else { + System.err.println( "(Grid) The GNode to be deleted is null!" ) ; } - -// nb_node-- ; + gnodesList_done = false ; } @@ -326,7 +358,14 @@ public class Grid implements Serializable 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++ ) @@ -346,20 +385,26 @@ public class Grid implements Serializable * @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 ; } /** @@ -402,7 +447,13 @@ public class Grid implements Serializable 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 ; @@ -445,7 +496,14 @@ public class Grid implements Serializable { 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" ) ; + } } } } @@ -466,6 +524,47 @@ public class Grid implements Serializable 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 ; + } } diff --git a/src/and/Mapping/Maheve.java b/src/and/Mapping/Maheve.java new file mode 100644 index 0000000..4a24142 --- /dev/null +++ b/src/and/Mapping/Maheve.java @@ -0,0 +1,421 @@ +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 sortedCluster = null ; + private ArrayList tasks = null ; + + + /** + * Empty default constructor. + */ + public Maheve() + { + super() ; + name = "MAHEVE_2" ; + sortedCluster = new ArrayList() ; + } + + + /** + * 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() ; + tasks = new ArrayList() ; + 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 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 l1 = sortTasks() ; + + if( l1 != null && l1.size() > 0 ) + { + ArrayList l2 = new ArrayList() ; + ArrayList tmp = new ArrayList() ; + + 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 addTask(GTask _gt, ArrayList _ar) + { + + ArrayList ret = null ; + + if( _gt != null && _ar != null ) + { + ret = new ArrayList() ; + + // ** 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 dep = new ArrayList() ; + + 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 sortTasks() + { + ArrayList ret = null ; + + ArrayList tmp = gr.getGraph() ; + + if( tmp != null && tmp.size() > 0 ) + { + ret = new ArrayList() ; + + ArrayList mt = new ArrayList() ; + + 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 searchNodes( int _nbTask ) + { + ArrayList ret = null ; + + if( _nbTask > 0 ) + { + ret = new ArrayList() ; + 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() ; + + ArrayList calcMark = new ArrayList() ; + + hd = gl.getHeterogenityDegre() ; + + /** Sorting clusters **/ + ArrayList 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 _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 _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 !! **/ diff --git a/src/and/Mapping/Mapping.java b/src/and/Mapping/Mapping.java index 9429df4..e8320c4 100644 --- a/src/and/Mapping/Mapping.java +++ b/src/and/Mapping/Mapping.java @@ -16,6 +16,7 @@ public class Mapping implements Serializable /* Two kinds of Mapping, according to algorithms' goal */ private ArrayList mapping ; private ArrayList mapping2 ; + private ArrayList other ; private int type ; // 0 : mapping task/node ; 1 : mapping tasks/cluster @@ -26,6 +27,7 @@ public class Mapping implements Serializable { mapping = new ArrayList() ; mapping2 = new ArrayList() ; + other = new ArrayList() ; type = -1 ; } @@ -37,6 +39,7 @@ public class Mapping implements Serializable { mapping = new ArrayList() ; mapping2 = new ArrayList() ; + other = new ArrayList() ; type = -1 ; } @@ -62,7 +65,7 @@ public class Mapping implements Serializable 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 ) ) ) ; @@ -100,14 +103,78 @@ public class Mapping implements Serializable { 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 @@ -139,59 +206,30 @@ public class Mapping implements Serializable public ArrayList getMappedGNodes() { ArrayList ar = new ArrayList() ; - + if( mapping.size() != 0 ) { -// if( type == 0 ) -// { -// ArrayList tmp = (ArrayList) 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 tmp = (ArrayList) 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 ar = getMappedGNodes() ; @@ -203,7 +241,7 @@ public class Mapping implements Serializable System.out.println() ; } - if( type == 1 ) + if( type_print == 1 ) { for( int i = 0 ; i < mapping2.size() ; i++ ) { @@ -257,6 +295,59 @@ public class Mapping implements Serializable } + /** + * 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 diff --git a/src/and/Mapping/Simple.java b/src/and/Mapping/Simple.java index 3092a99..403b008 100644 --- a/src/and/Mapping/Simple.java +++ b/src/and/Mapping/Simple.java @@ -5,7 +5,7 @@ import java.util.ArrayList; /** - * Implementation of Simple Mapping algorithm + * Implementation of the Simple Mapping algorithm (no fault tolerance mechanism) * @author Sébastien Miquée * @version 1.0 */ @@ -23,6 +23,7 @@ public class Simple extends Algo public Simple() { super() ; + name = "Simple" ; } @@ -34,6 +35,8 @@ public class Simple extends Algo public Simple( Graph _gr, Grid _gd ) { super( _gr, _gd ) ; + + name = "Simple" ; } /** @@ -48,7 +51,7 @@ public class Simple extends Algo { grn = new ArrayList() ; - // Tri des clusters suivant leur taille + // Sorting clusters according to their "size" ArrayList cl = gl.getClusters() ; ArrayList cl2 = new ArrayList() ; @@ -113,8 +116,6 @@ public class Simple extends Algo System.err.println( "\n\n!!! Unable to map application !\n\n" ) ; } - /** Update in cluster the status of nodes **/ - updateGrid() ; } @@ -142,12 +143,11 @@ public class Simple extends Algo } 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 ; } diff --git a/src/and/Mapping/Utils.java b/src/and/Mapping/Utils.java index a5ec4d2..068789d 100644 --- a/src/and/Mapping/Utils.java +++ b/src/and/Mapping/Utils.java @@ -69,7 +69,19 @@ public class Utils 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 ) ; @@ -77,6 +89,9 @@ public class Utils 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 ; @@ -194,7 +209,7 @@ public class Utils 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( "" ) ) @@ -244,7 +259,7 @@ public class Utils 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( "" ) ) @@ -295,7 +310,7 @@ public class Utils 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( "" ) ) @@ -346,7 +361,7 @@ public class Utils 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 = "" ; @@ -394,7 +409,7 @@ public class Utils 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 = "" ; @@ -442,7 +457,7 @@ public class Utils 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 = "" ;