From: Sébastien Miquée Date: Tue, 7 Jun 2011 07:59:01 +0000 (+0200) Subject: New version of MAHEVE plus corrections. X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/mapping.git/commitdiff_plain New version of MAHEVE plus corrections. - New version of MAHEVE: performance enhancement. - Adding some functionalities in the library for the new version of MAHEVE and to enhance library performance. --- diff --git a/Makefile b/Makefile index ba63f69..578d223 100644 --- a/Makefile +++ b/Makefile @@ -31,7 +31,7 @@ javadoc:cleanDoc @echo @echo "## Generating Javadoc ..." @echo - javadoc -d ./$(JAVADOC) ./$(SRC)/$(PACKAGE)/*.java + javadoc -windowtitle "Mapping Library" -d ./$(JAVADOC) ./$(SRC)/$(PACKAGE)/*.java clean: diff --git a/src/and/Mapping/Algo.java b/src/and/Mapping/Algo.java index f1974a0..f5c3ff6 100644 --- a/src/and/Mapping/Algo.java +++ b/src/and/Mapping/Algo.java @@ -48,6 +48,7 @@ public abstract class Algo implements Serializable ids = "" ; name = "" ; nb_fault = 0 ; + mp.setGrid( _gl ) ; } diff --git a/src/and/Mapping/Association.java b/src/and/Mapping/Association.java index ab8ebdc..d7d4d6a 100644 --- a/src/and/Mapping/Association.java +++ b/src/and/Mapping/Association.java @@ -66,7 +66,7 @@ public class Association implements Serializable * Return the associated tasks list. * @return The associated tasks list */ - public ArrayList getGtask() + public ArrayList getGtasks() { return at ; } diff --git a/src/and/Mapping/Cluster.java b/src/and/Mapping/Cluster.java index 588c26e..69323eb 100644 --- a/src/and/Mapping/Cluster.java +++ b/src/and/Mapping/Cluster.java @@ -50,7 +50,7 @@ public class Cluster implements Serializable */ public void addGNode( GNode _n ) { - if( _n != null ) + if( _n != null && _n.getClusterName().equalsIgnoreCase( name ) ) { _n.setInCluster( true ) ; nodes.add( _n ) ; @@ -73,6 +73,16 @@ public class Cluster implements Serializable } + /** + * Return the list of free computing nodes which are in the cluster. + * @return The list of free nodes + */ + public ArrayList getFreeGNodes() + { + return freenodes ; + } + + /** * Return cluster's name. * @return Cluster's name @@ -114,7 +124,8 @@ public class Cluster implements Serializable /** - * Test if a computing node is in the cluster. + * Test if a computing node is in the cluster, and return its position (if + * it exists). * @param _g The node to be tested * @return The position of the node */ @@ -130,14 +141,36 @@ public class Cluster implements Serializable { pos = i ; break ; - } - + } } } return pos ; } + + /** + * Test if a computing node is in the cluster, and return it (if + * it exists). + * @param _g The node to be tested + * @return The position of the node + */ + public GNode exists( GNode _g ) + { + if( _g != null ) + { + for( int i = 0 ; i < nodes.size() ; i ++ ) + { + if( nodes.get( i ).getId() == _g.getId() ) + { + return nodes.get( i ) ; + } + } + } + + return null ; + } + /** * Return the next available computing node in the cluster. * @return The next node in the cluster @@ -196,7 +229,8 @@ public class Cluster implements Serializable { if( _dead != null ) { - if( _dead.getCluster().equals( name ) && _dead.getSite().equals( site ) ) + if( _dead.getClusterName().equalsIgnoreCase( name ) + && _dead.getSiteName().equalsIgnoreCase( site ) ) { int i = 0 ; for( i = 0 ; i < nodes.size() ; i++ ) @@ -376,6 +410,68 @@ public class Cluster implements Serializable } } + + /** + * Replace a node in the cluster (in case of a reconnection for example). + * @param _g The node to be replaced + */ + public void replaceGNode( GNode _g ) + { + if( _g != null ) + { + removeGNode( _g ) ; + addGNode( _g ) ; + } + } + + + /** + * Search and return the better (most powerful) available node + * of the cluster. + * @return The best available node + */ + public GNode getBetterFreeGNode() + { + GNode ret = null ; + + if( freenodes.size() > 0 ) + { + ret = freenodes.get( 0 ) ; + } + + for( int i = 1 ; i < freenodes.size() ; i++ ) + { + if( freenodes.get( i ).getPower() > ret.getPower() ) + { + ret = freenodes.get( i ) ; + } + } + + return ret ; + } + + + /** + * Construct and return a copy of the current Cluster. + * @return A copy of the cluster + */ + public Cluster clone() + { + Cluster copy = new Cluster() ; + + copy.setName( name ) ; + copy.setSite( site ) ; + + for( int i = 0 ; i < nodes.size() ; i++ ) + { + GNode newgn = (GNode) nodes.get( i ).clone() ; + newgn.setCluster( copy ) ; + copy.addGNode( newgn ) ; + } + + return copy ; + } + } /** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/DefaultMapping.java b/src/and/Mapping/DefaultMapping.java index f322659..5aa64e5 100644 --- a/src/and/Mapping/DefaultMapping.java +++ b/src/and/Mapping/DefaultMapping.java @@ -33,10 +33,9 @@ public class DefaultMapping extends Algo * @param _gr Tasks graph to be mapped * @param _gd Grid graph */ - public DefaultMapping( Graph _gr, Grid _gd, ArrayList _gnodes ) + public DefaultMapping( Graph _gr, Grid _gd ) { super( _gr, _gd ) ; - archi = _gnodes ; name = "DefaultMapping" ; } @@ -49,6 +48,8 @@ public class DefaultMapping extends Algo if( gr.getNbGTask() <= gl.getNbGNode() ) { atraiter = gr.getGraph() ; + archi = gl.getFreeGNodes() ; + System.out.println( "*******************************************" ) ; System.out.println( "* Launching the Default Mapping algorithm *" ) ; @@ -57,7 +58,9 @@ public class DefaultMapping extends Algo /** Save the Mapping **/ for( int i = 0 ; i < atraiter.size() ; i++ ) { - mp.addMapping( new Association( archi.get( i ), atraiter.get( i ) ) ) ; + Random r = new Random() ; + int ret = r.nextInt( archi.size() ) ; + mp.addMapping( archi.remove( ret ), atraiter.get( i ) ) ; } } else { diff --git a/src/and/Mapping/FT_AIAC_QM.java b/src/and/Mapping/FT_AIAC_QM.java index d0a2861..013bb76 100644 --- a/src/and/Mapping/FT_AIAC_QM.java +++ b/src/and/Mapping/FT_AIAC_QM.java @@ -136,6 +136,7 @@ public class FT_AIAC_QM extends Algo /** Initial mapping **/ initMapping() ; + /** Main loop **/ while( isOneMoveable() ) { @@ -205,7 +206,7 @@ public class FT_AIAC_QM extends Algo /** Save the Mapping **/ for( int i = 0 ; i < atraiter.size() ; i++ ) { - mp.addMapping( new Association( atraiter.get( i ).getMapedOn(), atraiter.get( i ).getGTask() ) ) ; + mp.addMapping( atraiter.get( i ).getMapedOn(), atraiter.get( i ).getGTask() ) ; } } else { diff --git a/src/and/Mapping/FT_FEC.java b/src/and/Mapping/FT_FEC.java index b9e216a..9f0616f 100644 --- a/src/and/Mapping/FT_FEC.java +++ b/src/and/Mapping/FT_FEC.java @@ -100,6 +100,12 @@ public class FT_FEC extends Algo { dep_min = 0 ; } + + for( int i = 0 ; i < gl.getNbCluster() ; i++ ) + { + gl.getClusters().get( i ).initMoreGNode() ; + } + while( ! mapping_done ) { diff --git a/src/and/Mapping/GNode.java b/src/and/Mapping/GNode.java index 3e79f03..dab3ac0 100644 --- a/src/and/Mapping/GNode.java +++ b/src/and/Mapping/GNode.java @@ -21,9 +21,10 @@ public class GNode implements Serializable private long id ; private boolean mapped ; private boolean inCluster ; - private String cluster ; - private String site ; + private String clusterName ; + private String siteName ; private String ip ; + private Cluster cluster ; /** @@ -32,8 +33,8 @@ public class GNode implements Serializable public GNode() { name = "" ; - cluster = "" ; - site = "" ; + clusterName = "" ; + siteName = "" ; nb_cores = 0 ; frequency = 0 ; mflops = 0 ; @@ -42,6 +43,18 @@ public class GNode implements Serializable id = -1 ; mapped = false ; inCluster = false ; + cluster = null ; + } + + + public void setCluster( Cluster _cl ) + { + cluster = _cl ; + } + + public Cluster getCluster() + { + return cluster ; } @@ -49,9 +62,9 @@ public class GNode implements Serializable * Set the cluster's name in which the computing node is. * @param _c The name of the cluster containing the node */ - public void setCluster( String _c ) + public void setClusterName( String _cn ) { - cluster = _c ; + clusterName = _cn ; } @@ -59,9 +72,9 @@ public class GNode implements Serializable * Return the cluster's name in which the node is. * @return The cluster's name */ - public String getCluster() + public String getClusterName() { - return cluster ; + return clusterName ; } @@ -69,9 +82,9 @@ public class GNode implements Serializable * Set the site's name in which the computing node is. * @param _s The site's name */ - public void setSite( String _s ) + public void setSiteName( String _s ) { - site = _s ; + siteName = _s ; } @@ -79,9 +92,9 @@ public class GNode implements Serializable * Return the name of the site in which the computing node is. * @return The site's name */ - public String getSite() + public String getSiteName() { - return site ; + return siteName ; } @@ -313,6 +326,31 @@ public class GNode implements Serializable ip = _ip ; } + + /** + * Construct and return a copy of the current GNode. + * @return A copy of this node + */ + public GNode clone() + { + GNode copy = new GNode() ; + + copy.setName( name ) ; + copy.setNb_cores( nb_cores ) ; + copy.setFrequency( frequency ) ; + copy.setMFlops( mflops ) ; + copy.setMemory( memory ) ; + copy.setNode( node ) ; + copy.setId( id ) ; + copy.setMapped( mapped ) ; + copy.setInCluster( inCluster ) ; + copy.setClusterName( clusterName ) ; + copy.setSiteName( siteName ) ; + copy.setIP( ip ) ; + + return copy ; + } + } /** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/GTask.java b/src/and/Mapping/GTask.java index 8dd430b..fb3ad01 100644 --- a/src/and/Mapping/GTask.java +++ b/src/and/Mapping/GTask.java @@ -111,7 +111,7 @@ public class GTask implements Serializable /** - * Return the task's dependencies list. + * Return the task dependencies list. * @return The dependencies list */ public ArrayList getDependencies() @@ -120,6 +120,23 @@ public class GTask implements Serializable } + /** + * Return the ids of the dependences of the task in a list. + * @return The ids list + */ + public ArrayList getDependenciesIds() + { + ArrayList ret = new ArrayList() ; + + for( int i = 0 ; i < dependencies.size() ; i++ ) + { + ret.add( new Integer( dependencies.get( i ).getNum() ) ) ; + } + + return ret; + } + + /** * Return the task's number. * @return The task's number diff --git a/src/and/Mapping/Grid.java b/src/and/Mapping/Grid.java index 2451b95..902e40f 100644 --- a/src/and/Mapping/Grid.java +++ b/src/and/Mapping/Grid.java @@ -102,6 +102,27 @@ public class Grid implements Serializable } + /** + * Search a cluster of the given name, and return it if it exists. + * @param _name The name of the cluster + * @return The cluster + */ + public Cluster getCluster( String _name ) + { + for( int i = 0 ; i < clusters.size() ; i++ ) + { + if( clusters.get( i ).getName().equalsIgnoreCase( _name ) ) + { + return clusters.get( i ) ; + } + } + + System.err.println( "The cluster \"" + _name + "\" does not exist!" ) ; + + return null ; + } + + /** * Compute and return the distance between two clusters. * @param _g1 First cluster @@ -110,37 +131,27 @@ public class Grid implements Serializable */ public double getDistance( GNode _g1, GNode _g2 ) { - double d = 0 ; - - if( _g1.equals( _g2 ) ) + if( _g1 == null || _g2 == null ) { - return d ; + return -1 ; } + double d = 0 ; + String cluster1 = "c1", cluster2 = "c2", site1 = "s1", site2 = "s2" ; - for( int i = 0 ; i < clusters.size() ; i++ ) - { - if( clusters.get( i ).isIn( _g1 ) != -1 ) - { - cluster1 = clusters.get( i ).getName() ; - site1 = clusters.get( i ).getSite() ; - } - - if( clusters.get( i ).isIn( _g2 ) != -1 ) - { - cluster2 = clusters.get( i ).getName() ; - site2 = clusters.get( i ).getSite() ; - } - } + cluster1 = _g1.getClusterName() ; + site1 = _g1.getSiteName() ; + cluster2 = _g2.getClusterName() ; + site2 = _g2.getSiteName() ; - if( cluster1.compareTo( cluster2 ) == 0 ) + if( cluster1.equalsIgnoreCase( cluster2 ) ) { d = 10 ; } else { - if( site1.compareTo( site2 ) == 0 ) + if( site1.equalsIgnoreCase( site2 ) ) { - d = 20 ; + d = 15 ; } else { d = 30 ; } @@ -177,6 +188,28 @@ public class Grid implements Serializable } + /** + * Return the list of free computing nodes in the grid. + * @return The list of free computing nodes + */ + public ArrayList getFreeGNodes() + { + ArrayList ret = new ArrayList() ; + + for( int i = 0 ; i < clusters.size() ; i++ ) + { + ArrayList ar = clusters.get( i ).getFreeGNodes() ; + + for( int j = 0 ; j < ar.size() ; j++ ) + { + ret.add( ar.get( j ) ) ; + } + } + + return ret ; + } + + /** * Upgrade the grid with new nodes. * @param _gnodes The list of new nodes @@ -189,16 +222,18 @@ public class Grid implements Serializable { /** Searching the cluster in which the node should be added **/ int j = 0 ; - for( j = 0; j < clusters.size(); j++ ) + boolean ok = false ; + + for( j = 0 ; j < clusters.size() ; j++ ) { - if( _gnodes.get( i ).getCluster().equalsIgnoreCase( clusters.get( j ).getName() ) ) + if( _gnodes.get( i ).getClusterName().equalsIgnoreCase( clusters.get( j ).getName() ) + && _gnodes.get( i ).getSiteName().equalsIgnoreCase( clusters.get( j ).getSite() ) ) { int pos = clusters.get( j ).isIn( _gnodes.get( i ) ) ; if( pos == -1 ) { - _gnodes.get( i ).setCluster( clusters.get( j ).getName() ) ; - _gnodes.get( i ).setSite( clusters.get( j ).getSite() ) ; + _gnodes.get( i ).setCluster( clusters.get( j ) ) ; _gnodes.get( i ).setInCluster( true ) ; _gnodes.get( i ).setMapped( false ) ; @@ -209,29 +244,28 @@ public class Grid implements Serializable clusters.get( j ).setGNodeStatus( _gnodes.get( i ), _gnodes.get( i ).getMapped() ) ; } + ok = true ; break ; } } /** The cluster was not found, so it is a new one **/ - if( j == clusters.size() ) + if( ! ok ) { String site = "", cluster = "" ; Cluster nClust = new Cluster() ; + + cluster = _gnodes.get( i ).getClusterName() ; // names[ 1 ] ; + site = _gnodes.get( i ).getSiteName() ; // names[ 2 ] ; - - String names[] = Utils.decodeG5Knames( _gnodes.get( i ).getName() ) ; - - cluster = names[ 1 ] ; - site = names[ 2 ] ; + System.out.println( "** (Grid) Creation of cluster " + cluster + " on site " + site ) ; nClust.setName( cluster ) ; nClust.setSite( site ) ; _gnodes.get( i ).setInCluster( true ) ; _gnodes.get( i ).setMapped( false ) ; - _gnodes.get( i ).setSite( site ) ; - _gnodes.get( i ).setCluster( cluster ) ; + _gnodes.get( i ).setCluster( nClust ) ; nClust.addGNode( _gnodes.get( i ) ) ; @@ -255,50 +289,51 @@ public class Grid implements Serializable { /** Searching the cluster in which the node should be added **/ int j = 0 ; - for( j = 0; j < clusters.size(); j++ ) + boolean ok = false ; + + for( j = 0 ; j < clusters.size() ; j++ ) { - if( _g.getCluster().equalsIgnoreCase( clusters.get( j ).getName() ) ) + if( _g.getClusterName().equalsIgnoreCase( clusters.get( j ).getName() ) + && _g.getSiteName().equalsIgnoreCase( clusters.get( j ).getSite() ) ) { int pos = clusters.get( j ).isIn( _g ) ; if( pos == -1 ) { - _g.setSite( clusters.get( j ).getSite() ) ; _g.setInCluster( true ) ; _g.setMapped( false ) ; + _g.setCluster( clusters.get( j ) ) ; clusters.get( j ).addGNode( _g ) ; gnodesList.add( _g ) ; - + } else { - clusters.get( j ).removeGNode( _g ) ; - clusters.get( j ).addGNode( _g ) ; + _g.setCluster( clusters.get( j ) ) ; + clusters.get( j ).replaceGNode( _g ) ; } + ok = true ; break ; } } /** The cluster was not found, so it is a new one **/ - if( j == clusters.size() ) + if( ! ok ) { String site = "", cluster = "" ; Cluster nClust = new Cluster() ; - String names[] = Utils.decodeG5Knames( _g.getName() ) ; - - cluster = names[ 1 ] ; - site = names[ 2 ] ; + cluster = _g.getClusterName() ; // names[ 1 ] ; + site = _g.getSiteName() ; //names[ 2 ] ; - System.out.println("** (Grid) Creation of cluster: "+cluster); + System.out.println( "** (Grid) Creation of cluster " + cluster + " on site " + site ) ; nClust.setName( cluster ) ; nClust.setSite( site ) ; _g.setInCluster( true ) ; _g.setMapped( false ) ; - _g.setSite( site ) ; - _g.setCluster( cluster ) ; + _g.setCluster( nClust ) ; nClust.addGNode( _g ) ; @@ -362,9 +397,9 @@ public class Grid implements Serializable if( id != -1 ) { - clusters.get(id).setGNodeStatus( _g, _status ) ; + clusters.get( id ).setGNodeStatus( _g, _status ) ; } else { - System.err.println( "(Grid) Cluster "+_g.getCluster()+" not found!" ) ; + System.err.println( "(Grid) Cluster " + _g.getClusterName() + " not found!" ) ; } /** Change in local list **/ @@ -393,13 +428,11 @@ public class Grid implements Serializable { for( int i = 0 ; i < clusters.size() ; i++ ) { - if( _g.getCluster().equalsIgnoreCase( clusters.get( i ).getName() ) ) - { - if( _g.getSite().equalsIgnoreCase( clusters.get( i ).getSite() ) ) - { - ret = i ; - break ; - } + if( _g.getClusterName().equalsIgnoreCase( clusters.get( i ).getName() ) + && _g.getSiteName().equalsIgnoreCase( clusters.get( i ).getSite() ) ) + { + ret = i ; + break ; } } } @@ -432,7 +465,7 @@ public class Grid implements Serializable /** Computation of the average power of computing nodes **/ for( int i = 0 ; i < gnodesList.size() ; i++ ) { - if( ! gnodesList.get(i).getMapped() ) + if( ! gnodesList.get( i ).getMapped() ) { temp += gnodesList.get(i).getPower() ; nb_freenodes++ ; @@ -445,7 +478,7 @@ public class Grid implements Serializable temp = 0 ; for( int i = 0 ; i < gnodesList.size() ; i++ ) { - if( ! gnodesList.get(i).getMapped() ) + if( ! gnodesList.get( i ).getMapped() ) { temp += Math.pow( ( gnodesList.get(i).getPower() - average ), 2 ) ; } @@ -464,7 +497,6 @@ public class Grid implements Serializable hd = 1 ; } - return hd ; } @@ -490,6 +522,23 @@ public class Grid implements Serializable } + /** + * Return the average amount of nodes available in all clusters. + * @return The average available nodes of the architecture + */ + public double getAvgClusterNode() + { + int nb = 0 ; + + for( int i = 0 ; i < clusters.size() ; i++ ) + { + nb += clusters.get( i ).getNbFreeNodes() ; + } + + return ( nb / getNbFreenodes() ) ; + } + + /** * Initialization of computing nodes in the grid. Set all * of these nodes to be not mapped on, and do the same thing in each @@ -507,6 +556,7 @@ public class Grid implements Serializable for( int i = 0 ; i < clusters.size() ; i++ ) { clusters.get( i ).initGNodes() ; + clusters.get( i ).initMoreGNode() ; } } @@ -597,6 +647,17 @@ public class Grid implements Serializable return ret ; } + + /** + * Return the max distance it could exist between two computing nodes. + * @return The max distance + */ + public double getMaxDistance() + { + // TODO + return 30 ; + } + } diff --git a/src/and/Mapping/Linpack.java b/src/and/Mapping/Linpack.java index b92d7d3..b3a4997 100644 --- a/src/and/Mapping/Linpack.java +++ b/src/and/Mapping/Linpack.java @@ -81,11 +81,6 @@ public class Linpack int n,i,lda; int ipvt[] = new int[1000]; - //double mflops_result; - //double residn_result; - //double time_result; - //double eps_result; - lda = 1001; n = 500; @@ -114,15 +109,10 @@ public class Linpack eps_result = epslon((double)1.0); /* - - residn_result = resid/( n*norma*normx*eps_result ); - time_result = total; - mflops_result = ops/(1.0e6*total); - - return ("Mflops/s: " + mflops_result + - " Time: " + time_result + " secs" + - " Norm Res: " + residn_result + - " Precision: " + eps_result); + return ("Mflops/s: " + mflops_result + + " Time: " + time_result + " secs" + + " Norm Res: " + residn_result + + " Precision: " + eps_result); */ residn_result = resid/( n*norma*normx*eps_result ); residn_result += 0.005; // for rounding @@ -139,11 +129,6 @@ public class Linpack mflops_result = (int)(mflops_result*1000); mflops_result /= 1000; - // System.out.println("Mflops/s: " + mflops_result + - // " Time: " + time_result + " secs" + - // " Norm Res: " + residn_result + - // " Precision: " + eps_result); - return mflops_result ; } @@ -157,7 +142,7 @@ public class Linpack init = 1325; norma = 0.0; /* Next two for() statements switched. Solver wants -matrix in column order. --dmd 3/3/97 + matrix in column order. --dmd 3/3/97 */ for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { diff --git a/src/and/Mapping/Maheve.java b/src/and/Mapping/Maheve.java index f38b9fc..e0c1232 100644 --- a/src/and/Mapping/Maheve.java +++ b/src/and/Mapping/Maheve.java @@ -1,6 +1,7 @@ package and.Mapping; import java.util.ArrayList; +import java.util.Iterator; @@ -22,10 +23,9 @@ public class Maheve extends Algo public Maheve() { super() ; - name = "MAHEVE_2" ; + name = "MAHEVE_3" ; minNode = 5 ; nbSave = 2 ; - sortedCluster = new ArrayList() ; } @@ -44,7 +44,7 @@ public class Maheve extends Algo hd = 0 ; sortedCluster = new ArrayList() ; tasks = new ArrayList() ; - name = "MAHEVE_2" ; + name = "MAHEVE_3" ; } @@ -102,32 +102,26 @@ public class Maheve extends Algo @Override public void map() { /** If the mapping is possible ... **/ - if( ( gr != null ) && ( gr.getNbGTask() <= gl.getNbGNode() ) ) + if( ( gr != null ) && ( gr.getNbGTask() <= gl.getNbFreenodes() ) ) { 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) **/ + double hd_g = gl.getHeterogenityDegre() ; - /** Initialization of heterogeneity degree **/ - hd = gl.getHeterogenityDegre() ; + /* Correction of hd */ + // correction is function of the application and platform characteristics + hd = calcNewHd( hd_g ) ; + + System.out.println( "Corrected hd value: " + hd + " (" + hd_g + ")" ) ; /** 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() ; @@ -137,13 +131,9 @@ public class Maheve extends Algo return ; } + /** Mapping of tasks on nodes/clusters **/ + mapping() ; - /** 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 ; @@ -151,6 +141,60 @@ public class Maheve extends Algo } + private void mapping() + { + int ind = 0 ; + boolean ok, change ; + int div = 1 ; + int nbDep ; + + ArrayList cl = new ArrayList() ; + + for( int i = 0 ; i < sortedCluster.size() ; i++ ) + { + cl.add( sortedCluster.get( i ).clone() ) ; + } + + for( int i = 0 ; i < tasks.size() ; i++ ) + { + ok = false ; + + while( ! ok ) + { + nbDep = (int) ( tasks.get( i ).getNbDep() * (1.0 - hd) / div ) + 1 ; + + change = false ; + + if( (cl.get( ind ).getNbFreeNodes() - nbSave) >= nbDep ) + { + GNode gn = cl.get( ind ).getBetterFreeGNode() ; + if( gn != null ) + { + cl.get( ind ).setGNodeStatus( gn, true ) ; + mp.addMapping( (gl.getCluster( cl.get( ind ).getName()).exists( gn )) , tasks.get( i ) ) ; + ok = true ; + } else { + change = true ; + } + } else { + change = true ; + } + + if( change ) + { + ind++ ; + + if( ind == cl.size() ) + { + ind = 0 ; + div++ ; + } + } + } + } + } + + private void orderTasks() { ArrayList l1 = sortTasks() ; @@ -200,7 +244,7 @@ public class Maheve extends Algo tasks.add( _gt ) ; // ** Searching its dependencies ** // - int nbDep = (int) (_gt.getNbDep() * (1.0 - hd)) ; + int nbDep = (int) ( _gt.getNbDep() * (1.0 - hd) + 1 ) ; int cmpt = 0 ; int num = 0 ; @@ -218,21 +262,17 @@ public class Maheve extends Algo // ** Searching dependencies in sorted tasks list ** // - for( int i = 0 ; i < _ar.size() ; i++ ) + Iterator iter = _ar.iterator() ; + while( iter.hasNext() ) { - num = _ar.get( i ).getNum() ; + GTask gt = iter.next() ; + num = gt.getNum() ; - if( dep.contains( num ) ) + if( dep.contains( num ) ) { -// for( int j = 0 ; j < dep.size() ; j++ ) -// { -// if( num == dep.get( j ) ) -// { - ret.add( _ar.remove( i ) ) ; - cmpt++ ; -// dep.remove( j ) ; -// break ; -// } + ret.add( gt ) ; + iter.remove() ; + cmpt++ ; } if( cmpt == nbDep ) @@ -249,9 +289,20 @@ public class Maheve extends Algo private ArrayList sortTasks() { ArrayList ret = null ; + double maxW = 0, maxD = 0 ; ArrayList tmp = gr.getGraph() ; + maxD = gr.getMaxDep() ; + + for( int i = 0 ; i < gr.getNbGTask() ; i++ ) + { + if( gr.getGraph().get( i ).getWeight() > maxW ) + { + maxW = gr.getGraph().get( i ).getWeight() ; + } + } + if( tmp != null && tmp.size() > 0 ) { ret = new ArrayList() ; @@ -263,12 +314,12 @@ public class Maheve extends Algo for( int i = 0 ; i < tmp.size() ; i++ ) { - W = tmp.get( i ).getWeight() ; - D = tmp.get( i ).getNbDep() ; + W = tmp.get( i ).getWeight() / maxW ; + D = tmp.get( i ).getNbDep() / maxD ; ok = false ; - MT = Math.pow( W, hd ) * Math.pow( D, ( 1.0 - hd) ) ; + MT = Math.pow( W, hd ) + Math.pow( D, ( 1.0 - hd) ) ; if( ret.size() == 0 ) { @@ -300,66 +351,6 @@ public class Maheve extends Algo } - private ArrayList searchNodes( int _nbTask ) - { - ArrayList ret = null ; - - if( _nbTask > 0 ) - { - ret = new ArrayList() ; - int nbFound = 0 ; - int max = 0 ; - GNode g = null ; - boolean changeParameter = false ; - - while( nbFound < _nbTask ) - { - int i = 0 ; - - for( i = 0 ; i < sortedCluster.size() ; i++ ) - { - /** If there is enough nodes ... **/ - if( sortedCluster.get( i ).getNbFreeNodes() >= minNode ) - { - max = 0 ; - sortedCluster.get( i ).initMoreGNode() ; - - max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ; - - for( int j = 0 ; j < max ; j++ ) - { - g = sortedCluster.get( i ).moreGNode() ; - ret.add( g ) ; - - nbFound ++ ; - - if( nbFound >= _nbTask ) - break ; - } - } - - if( nbFound >= _nbTask ) - break ; - } - - if( i == sortedCluster.size() && nbFound < _nbTask ) - { - changeParameter = true ; - minNode-- ; - } - } - - if( changeParameter ) - { - System.err.println( "The parameter \"minNode\" has been reduced " + - "to allow the mapping process to be done." ) ; - } - } - - return ret ; - } - - /** * Sort clusters according to the heterogeneity degree of the platform and * the eventual application's threshold. @@ -372,18 +363,11 @@ public class Maheve extends Algo sortedCluster = null ; sortedCluster = new ArrayList() ; - ArrayList calcMark = new ArrayList() ; - - double hd_g = gl.getHeterogenityDegre() ; - - /* Correction of hd */ - hd = calcNewHd( hd_g ) ; - System.out.println("Corrected hd value: " + hd + " (" + hd_g + ")" ) ; - /** Sorting clusters **/ ArrayList tmp = gl.getClusters() ; + double[] marks = new double[ tmp.size() ] ; boolean ok ; double calcLoc = 0 ; @@ -392,35 +376,61 @@ public class Maheve extends Algo double Nm = 0, Pm = 0 ; - for( int i = 0 ; i < tmp.size() ; i++ ) + int i = 0 ; + + // Computing data + for( i = 0 ; i < tmp.size() ; i++ ) { Nm += tmp.get( i ).getNbFreeNodes() ; Pm += tmp.get( i ).getAvgAvailablePower() ; } - for( int i = 0 ; i < tmp.size() ; i++ ) + // Computing marks + for( i = 0 ; i < tmp.size() ; i++ ) { normN = tmp.get( i ).getNbFreeNodes() * 100 / Nm ; normP = tmp.get( i ).getAvgAvailablePower() * 100 / Pm ; /** The magic formula :P **/ - calcLoc = Math.pow( (normP * hd), 2) + - Math.pow( (normN * (1 - hd)), 2 ) ; + calcLoc = Math.pow( normP, hd) + + Math.pow( normN, (1 - hd) ) ; + marks[ i ] = calcLoc ; + } + + // Taking into account the network latency + ArrayList couples = new ArrayList() ; + if( tmp.size() > 1 ) + { + for( i = 0 ; i < tmp.size() - 1 ; i++ ) + { + for( int j = i+1 ; j < tmp.size() ; j++ ) + { + couples.add( new Couple( tmp.get( i ), marks[i], + tmp.get( j ), marks[j] ) ) ; + } + } + } else { + couples.add( new Couple( tmp.get(0), marks[0], null, -1 ) ) ; + } + + + // Sorting couples + ArrayList Scouples = new ArrayList() ; + for( i = 0 ; i < couples.size() ; i++ ) + { ok = false ; - if( sortedCluster.size() == 0 ) + if( Scouples.size() == 0 ) { - sortedCluster.add( tmp.get( i ) ) ; - calcMark.add( calcLoc ) ; + Scouples.add( couples.get( i ) ) ; } else { - for( int j = 0 ; j < sortedCluster.size() ; j++ ) + for( int j = 0 ; j < Scouples.size() ; j++ ) { - if( calcLoc > calcMark.get( j ) ) + if( couples.get( i ).getCoupleMark() > Scouples.get( j ).getCoupleMark() ) { - sortedCluster.add( j, tmp.get( i ) ) ; - calcMark.add( j, calcLoc ) ; + Scouples.add( j, couples.get( i ) ) ; ok = true ; break ; } @@ -428,11 +438,29 @@ public class Maheve extends Algo if( ! ok ) { - sortedCluster.add( tmp.get( i ) ) ; - calcMark.add( calcLoc ) ; + Scouples.add( couples.get( i ) ) ; } } } + + // Extracting clusters + for( i = 0 ; i < Scouples.size() ; i++ ) + { + if( ! sortedCluster.contains( Scouples.get(i).getBetterCluster() ) ) + { + sortedCluster.add( Scouples.get( i ).getBetterCluster() ) ; + } + + if( Scouples.get( i ).getOtherCluster() != null && + ! sortedCluster.contains( Scouples.get(i).getOtherCluster() )) + { + sortedCluster.add( Scouples.get( i ).getOtherCluster() ) ; + } + } + + tmp = null ; + couples = null ; + Scouples = null ; } } @@ -449,12 +477,20 @@ public class Maheve extends Algo double nhd = 0 ; double nbTask = gr.getNbGTask() ; - double nbDep = gr.getMaxDep() ; - double maxNodes = gl.getMaxClusterNode() ; + double avgNodesCluster = gl.getAvgClusterNode() ; + double nbAvgDep = gr.getAverageDep() ; /* Computation */ - nhd = hd_g / ( 10 * ( (nbDep / nbTask) + (nbDep / maxNodes) ) ) ; + double correc_appli = 1 - ((nbTask / nbAvgDep +1) / nbTask) ; + double correc_archi = 1 - (( avgNodesCluster / (nbAvgDep + 1) ) / avgNodesCluster) ; + System.out.println( correc_appli + " " +correc_archi ) ; + + nhd = hd_g + (correc_appli - 0.5) + (correc_archi - 0.5) ; + + if( nhd >= 1 ) nhd = 0.99 ; + if( nhd <= 0 ) nhd = 0.01 ; + return nhd ; } @@ -505,6 +541,11 @@ public class Maheve extends Algo } } + if( ! ok ) + { + System.err.println( "No repalacing node found! No left places on any cluster!" ) ; + } + nb_fault++ ; } @@ -540,6 +581,81 @@ public class Maheve extends Algo return true ; } + + private class Couple + { + Cluster c1, c2 ; + double m1, m2 ; + boolean single ; + + Couple( Cluster _c1, double _m1, Cluster _c2, double _m2 ) + { + c1 = _c1 ; m1 = _m1 ; + c2 = _c2 ; m2 = _m2 ; + + if( _c2 == null ) + { + single = true ; + } else { + single = false ; + } + } + + protected double getCoupleMark() + { + double d = -1 ; + int i = 0 ; + GNode g1, g2 ; + + while( d == -1 ) + { + g1 = c1.getGNodes().get( i ) ; + g2 = c2.getGNodes().get( i ) ; + + if( g1 == null || g2 == null ) + { + System.err.println( "There is no more node in at least one cluster" ) ; + return 100000.0 ; + } + + d = Math.pow(gl.getDistance( g1, g2 ), (1- hd)) ; + i++ ; + } + + return ( m1 + m2 ) / d ; + } + + protected Cluster getBetterCluster() + { + if( single ) + { + return c1 ; + } + + if( m1 > m2 ) + { + return c1 ; + } else { + return c2 ; + } + } + + protected Cluster getOtherCluster() + { + if( single ) + { + return null ; + } + + if( m1 > m2 ) + { + return c2 ; + } else { + return c1 ; + } + } + } + } /** 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 e8320c4..1803d63 100644 --- a/src/and/Mapping/Mapping.java +++ b/src/and/Mapping/Mapping.java @@ -18,6 +18,7 @@ public class Mapping implements Serializable private ArrayList mapping2 ; private ArrayList other ; private int type ; // 0 : mapping task/node ; 1 : mapping tasks/cluster + private Grid gd ; /** @@ -29,6 +30,7 @@ public class Mapping implements Serializable mapping2 = new ArrayList() ; other = new ArrayList() ; type = -1 ; + gd = null ; } @@ -41,6 +43,17 @@ public class Mapping implements Serializable mapping2 = new ArrayList() ; other = new ArrayList() ; type = -1 ; + gd = null ; + } + + + /** + * Set the grid in which the mapping is done. + * @param _gd The grid + */ + public void setGrid( Grid _gd ) + { + gd = _gd ; } @@ -63,12 +76,13 @@ public class Mapping implements Serializable /** For the usage of algorithms which map groups of tasks on cluster **/ GNode tmp = null ; + c.initMoreGNode() ; for( int i = 0 ; i < at.size() ; i++ ) { tmp = c.moreGNode() ; if( tmp != null ) { - insertMapping( new Association( tmp, at.get( i ) ) ) ; + insertMapping( new Association( tmp, at.get( i ) ), false ) ; } else { System.err.println( "Error during reception of the next GNode !" ) ; break ; @@ -78,10 +92,12 @@ public class Mapping implements Serializable /** - * Add a mapping association in the general mapping. - * @param _a Association between a task and a node + * Add a mapping association between a task and a node + * in the general mapping. + * @param _gn The node on which the task is mapped + * @param _gt The task mapped on the node */ - public void addMapping( Association _a ) + public void addMapping( GNode _gn, GTask _gt ) { if( type == 0 || type == -1 ) { @@ -91,7 +107,7 @@ public class Mapping implements Serializable System.exit( 1 ) ; } - insertMapping( _a ) ; + insertMapping( new Association( _gn, _gt ), true ) ; } @@ -99,15 +115,45 @@ public class Mapping implements Serializable * Insert the association at the right place. * @param _a The association to be inserted */ - public void insertMapping( Association _a ) + public void insertMapping( Association _a, boolean _other ) { if( _a != null && _a.getGNode() != null && _a.getGTask() != null ) { mapping.add( _a ) ; + + if( _other ) + { + updateMapping2( _a ) ; + } } } + private void updateMapping2( Association _a ) + { + boolean ok = false ; + + for( int i = 0 ; i < mapping2.size() ; i++ ) + { + if( mapping2.get( i ).getCluster().getName().equalsIgnoreCase( _a.getGNode().getClusterName() ) ) + { + mapping2.get( i ).getGtasks().add( _a.getGTask() ) ; + + ok = true ; + break ; + } + } + + if( !ok ) + { + Cluster cl = _a.getGNode().getCluster() ; + ArrayList gr = new ArrayList() ; + gr.add( _a.getGTask() ) ; + mapping2.add( new Association( cl, gr ) ) ; + } + } + + /** * Determine if a node is used as an other node in the mapping. * @param _g The node to search @@ -209,9 +255,11 @@ public class Mapping implements Serializable if( mapping.size() != 0 ) { - for( int i = 0 ; i < mapping.size() ; i++ ) + ArrayList mp = organizeMapping() ; + + for( int i = 0 ; i < mp.size() ; i++ ) { - ar.add( mapping.get( i ).getGNode() ) ; + ar.add( mp.get( i ).getGNode() ) ; } } @@ -219,6 +267,28 @@ public class Mapping implements Serializable } + private ArrayList organizeMapping() + { + ArrayList ret = null ; + + if( mapping.size() > 0 ) + { + ret = new ArrayList( mapping.size() ) ; + for( int i = 0 ; i < mapping.size() ; i++ ) + ret.add( null ) ; + + for( int i = 0 ; i < mapping.size() ; i++ ) + { + ret.set( mapping.get( i ).getGTask().getNum(), mapping.get( i ) ) ; + } + } else { + System.out.println( "No mapping..." ) ; + } + + return ret ; + } + + /** * Print the status of the mapping done, according to its type. */ @@ -246,11 +316,11 @@ public class Mapping implements Serializable for( int i = 0 ; i < mapping2.size() ; i++ ) { System.out.print( "\t\tCluster \"" + mapping2.get( i ).getCluster().getName() + "\" => { ") ; - for( int j = 0 ; j < mapping2.get( i ).getGtask().size() ; j++ ) + for( int j = 0 ; j < mapping2.get( i ).getGtasks().size() ; j++ ) { - System.out.print( mapping2.get( i ).getGtask().get( j ).getNum() ) ; + System.out.print( mapping2.get( i ).getGtasks().get( j ).getNum() ) ; - if( j != mapping2.get( i ).getGtask().size() - 1 ) + if( j != mapping2.get( i ).getGtasks().size() - 1 ) { System.out.print( ", " ) ; } @@ -355,23 +425,19 @@ public class Mapping implements Serializable public int calcDepExt() { int depExt = 0 ; - ArrayList ar ; - ArrayList deps ; + + ArrayList mp = organizeMapping() ; - for( int i = 0 ; i < mapping.size() ; i++ ) + for( int i = 0 ; i < mp.size() ; i++ ) { - ar = mapping.get(i).getGtask() ; - - for( int j = 0 ; j < ar.size() ; j++ ) + ArrayList dids = mp.get( i ).getGTask().getDependenciesIds() ; + + for( int j = 0 ; j < dids.size() ; j++ ) { - deps = ar.get(j).getDependencies() ; - - for( int k = 0 ; k < deps.size() ; k++ ) + if( ! mp.get( i ).getGNode().getSiteName().equalsIgnoreCase( + mp.get( dids.get(j) ).getGNode().getSiteName() ) ) { - if( ! ar.contains( deps.get(k) ) ) - { - depExt++ ; - } + depExt++ ; } } } @@ -379,6 +445,79 @@ public class Mapping implements Serializable return ( depExt / 2 ) ; } + + /** + * ** TO BE MODIFIED !!! + * @return + */ + public double calcAsyncMark() + { + double mark = 0 ; + + ArrayList comput = new ArrayList() ; + ArrayList comput2 = new ArrayList() ; + double max_time = 0 ; + + ArrayList mp = organizeMapping() ; + + /** Initialization **/ + for( int i = 0 ; i < mp.size() ; i++ ) + { + Double calc = new Double( mp.get( i ).getGTask().getWeight() / + mp.get( i ).getGNode().getPower() ) ; + + comput.add( calc ) ; + comput2.add( new Double ( -1 ) ) ; + + if( calc > max_time ) + { + max_time = calc ; + } + } + + /** Normalization **/ + for( int i = 0 ; i < mp.size() ; i++ ) + { + comput.set( i, comput.get( i ) / max_time ) ; + } + + + for( int k = 0 ; k < 2 ; k++ ) + for( int i = 0 ; i < mp.size() ; i++ ) + { + ArrayList tmp = mp.get(i).getGTask().getDependenciesIds() ; + + double calc = 0 ; + double valv ; + + for( int j = 0 ; j < tmp.size() ; j++ ) + { + if( comput2.get( j ) != -1 ) + { + valv = comput2.get( j ) ; + } else { + valv = comput.get( j ) ; + } + + calc += ( valv + ( gd.getDistance( mp.get( i ).getGNode(), mp.get( j ).getGNode() ) + / gd.getMaxDistance() ) ) ; + } + + comput2.set( i, comput.get( i ) * calc ) ; + } + + mark = -1 ; + for( int i = 0 ; i < comput2.size() ; i++ ) + { + if( mark < comput2.get( i ) ) + { + mark = comput2.get( i ) ; + } + } + + return mark ; + } + } /** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/Simple.java b/src/and/Mapping/Simple.java index b6c19a9..7db86a9 100644 --- a/src/and/Mapping/Simple.java +++ b/src/and/Mapping/Simple.java @@ -109,7 +109,7 @@ public class Simple extends Algo /** Save the Mapping **/ for( int i = 0 ; i < atraiter.size() ; i++ ) { - mp.addMapping( new Association( archi.get( i ), atraiter.get( i ) ) ) ; + mp.addMapping( archi.get( i ), atraiter.get( i ) ) ; } } else { diff --git a/src/and/Mapping/Utils.java b/src/and/Mapping/Utils.java index bef5dd4..1cd073b 100644 --- a/src/and/Mapping/Utils.java +++ b/src/and/Mapping/Utils.java @@ -89,8 +89,8 @@ public class Utils n.setMemory( memory ) ; n.setNb_cores( nbCore ) ; n.setName( name ) ; - n.setCluster( names[1] ) ; - n.setSite( names[2] ) ; + n.setClusterName( names[1] ) ; + n.setSiteName( names[2] ) ; n.setIP( ip ) ; n.setMapped( false ) ; @@ -116,32 +116,30 @@ public class Utils for( int i = 0 ; i < _an.size() ; i++ ) { - /* Variables edition */ + /* Variables edition */ - String names[] = decodeG5Knames( _an.get( i ).getName() ) ; - - cluster = names[ 1 ] ; - site = names[ 2 ] ; + cluster = _an.get( i ).getClusterName() ; //names[ 1 ] ; + site = _an.get( i ).getSiteName() ; //names[ 2 ] ; /* Insertion of the node in its cluster */ - boolean trouve = false ; + boolean found = false ; for( int j = 0 ; j < clusters.size() ; j++ ) { - if( clusters.get( j ).getName().equals( cluster ) && clusters.get( j ).getSite().equals( site )) + if( clusters.get( j ).getName().equalsIgnoreCase( cluster ) + && clusters.get( j ).getSite().equalsIgnoreCase( site )) { _an.get( i ).setInCluster( true ) ; _an.get( i ).setMapped( false ) ; - _an.get( i ).setSite( clusters.get( j ).getSite() ) ; - _an.get( i ).setCluster( clusters.get( j ).getName() ) ; + _an.get( i ).setCluster( clusters.get( j ) ) ; clusters.get( j ).addGNode( _an.get( i ) ) ; - trouve = true ; + found = true ; break ; } } - if( ! trouve ) + if( ! found ) { Cluster cl = new Cluster() ; @@ -150,8 +148,7 @@ public class Utils _an.get( i ).setInCluster( true ) ; _an.get( i ).setMapped( false ) ; - _an.get( i ).setSite( site ) ; - _an.get( i ).setCluster( cluster ) ; + _an.get( i ).setCluster( cl ) ; cl.addGNode( _an.get( i ) ) ; @@ -172,7 +169,7 @@ public class Utils * @param _name The full name of the G5K node * @return The three parts of the name */ - protected static String[] decodeG5Knames( String _name ) + public static String[] decodeG5Knames( String _name ) { String temp = "" ; String tab[] = new String[ 5 ] ; @@ -182,12 +179,12 @@ public class Utils tab = temp.split( "!" ) ; - ret[0] = tab[ 0 ] ; - ret[2] = tab[ 1 ] ; + ret[0] = tab[ 0 ] ; // node name + ret[2] = tab[ 1 ] ; // site name tab = ret[0].split( "-" ) ; - ret[ 1 ] = tab[ 0 ] ; + ret[ 1 ] = tab[ 0 ] ; // cluster name return ret ; }