- New version of MAHEVE: performance enhancement.
- Adding some functionalities in the library for the new version
of MAHEVE and to enhance library performance.
@echo
@echo "## Generating Javadoc ..."
@echo
- javadoc -d ./$(JAVADOC) ./$(SRC)/$(PACKAGE)/*.java
+ javadoc -windowtitle "Mapping Library" -d ./$(JAVADOC) ./$(SRC)/$(PACKAGE)/*.java
clean:
ids = "" ;
name = "" ;
nb_fault = 0 ;
+ mp.setGrid( _gl ) ;
}
* Return the associated tasks list.
* @return The associated tasks list
*/
- public ArrayList<GTask> getGtask()
+ public ArrayList<GTask> getGtasks()
{
return at ;
}
*/
public void addGNode( GNode _n )
{
- if( _n != null )
+ if( _n != null && _n.getClusterName().equalsIgnoreCase( name ) )
{
_n.setInCluster( true ) ;
nodes.add( _n ) ;
}
+ /**
+ * Return the list of free computing nodes which are in the cluster.
+ * @return The list of free nodes
+ */
+ public ArrayList<GNode> getFreeGNodes()
+ {
+ return freenodes ;
+ }
+
+
/**
* Return cluster's name.
* @return Cluster's name
/**
- * 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
*/
{
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
{
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++ )
}
}
+
+ /**
+ * 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 !! **/
* @param _gr Tasks graph to be mapped
* @param _gd Grid graph
*/
- public DefaultMapping( Graph _gr, Grid _gd, ArrayList<GNode> _gnodes )
+ public DefaultMapping( Graph _gr, Grid _gd )
{
super( _gr, _gd ) ;
- archi = _gnodes ;
name = "DefaultMapping" ;
}
if( gr.getNbGTask() <= gl.getNbGNode() )
{
atraiter = gr.getGraph() ;
+ archi = gl.getFreeGNodes() ;
+
System.out.println( "*******************************************" ) ;
System.out.println( "* Launching the Default Mapping algorithm *" ) ;
/** 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 {
/** Initial mapping **/
initMapping() ;
+
/** Main loop **/
while( isOneMoveable() )
{
/** 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 {
{
dep_min = 0 ;
}
+
+ for( int i = 0 ; i < gl.getNbCluster() ; i++ )
+ {
+ gl.getClusters().get( i ).initMoreGNode() ;
+ }
+
while( ! mapping_done )
{
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 ;
/**
public GNode()
{
name = "" ;
- cluster = "" ;
- site = "" ;
+ clusterName = "" ;
+ siteName = "" ;
nb_cores = 0 ;
frequency = 0 ;
mflops = 0 ;
id = -1 ;
mapped = false ;
inCluster = false ;
+ cluster = null ;
+ }
+
+
+ public void setCluster( Cluster _cl )
+ {
+ cluster = _cl ;
+ }
+
+ public Cluster getCluster()
+ {
+ return cluster ;
}
* 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 ;
}
* 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 ;
}
* 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 ;
}
* 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 ;
}
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 !! **/
/**
- * Return the task's dependencies list.
+ * Return the task dependencies list.
* @return The dependencies list
*/
public ArrayList<GTask> getDependencies()
}
+ /**
+ * Return the ids of the dependences of the task in a list.
+ * @return The ids list
+ */
+ public ArrayList<Integer> getDependenciesIds()
+ {
+ ArrayList<Integer> ret = new ArrayList<Integer>() ;
+
+ 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
}
+ /**
+ * 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
*/
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 ;
}
}
+ /**
+ * Return the list of free computing nodes in the grid.
+ * @return The list of free computing nodes
+ */
+ public ArrayList<GNode> getFreeGNodes()
+ {
+ ArrayList<GNode> ret = new ArrayList<GNode>() ;
+
+ for( int i = 0 ; i < clusters.size() ; i++ )
+ {
+ ArrayList<GNode> 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
{
/** 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 ) ;
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 ) ) ;
{
/** 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 ) ;
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 **/
{
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 ;
}
}
}
/** 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++ ;
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 ) ;
}
hd = 1 ;
}
-
return hd ;
}
}
+ /**
+ * 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
for( int i = 0 ; i < clusters.size() ; i++ )
{
clusters.get( i ).initGNodes() ;
+ clusters.get( i ).initMoreGNode() ;
}
}
return ret ;
}
+
+ /**
+ * Return the max distance it could exist between two computing nodes.
+ * @return The max distance
+ */
+ public double getMaxDistance()
+ {
+ // TODO
+ return 30 ;
+ }
+
}
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;
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
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 ;
}
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++) {
package and.Mapping;
import java.util.ArrayList;
+import java.util.Iterator;
public Maheve()
{
super() ;
- name = "MAHEVE_2" ;
+ name = "MAHEVE_3" ;
minNode = 5 ;
nbSave = 2 ;
- sortedCluster = new ArrayList<Cluster>() ;
}
hd = 0 ;
sortedCluster = new ArrayList<Cluster>() ;
tasks = new ArrayList<GTask>() ;
- name = "MAHEVE_2" ;
+ name = "MAHEVE_3" ;
}
@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<GNode> 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() ;
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 ;
}
+ private void mapping()
+ {
+ int ind = 0 ;
+ boolean ok, change ;
+ int div = 1 ;
+ int nbDep ;
+
+ ArrayList<Cluster> cl = new ArrayList<Cluster>() ;
+
+ 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<GTask> l1 = sortTasks() ;
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 ;
// ** Searching dependencies in sorted tasks list ** //
- for( int i = 0 ; i < _ar.size() ; i++ )
+ Iterator<GTask> 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 )
private ArrayList<GTask> sortTasks()
{
ArrayList<GTask> ret = null ;
+ double maxW = 0, maxD = 0 ;
ArrayList<GTask> 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<GTask>() ;
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 )
{
}
- private ArrayList<GNode> searchNodes( int _nbTask )
- {
- ArrayList<GNode> ret = null ;
-
- if( _nbTask > 0 )
- {
- ret = new ArrayList<GNode>() ;
- int nbFound = 0 ;
- int max = 0 ;
- GNode g = null ;
- 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.
sortedCluster = null ;
sortedCluster = new ArrayList<Cluster>() ;
- ArrayList<Double> calcMark = new ArrayList<Double>() ;
-
- double hd_g = gl.getHeterogenityDegre() ;
-
- /* Correction of hd */
- hd = calcNewHd( hd_g ) ;
- System.out.println("Corrected hd value: " + hd + " (" + hd_g + ")" ) ;
-
/** Sorting clusters **/
ArrayList<Cluster> tmp = gl.getClusters() ;
+ double[] marks = new double[ tmp.size() ] ;
boolean ok ;
double calcLoc = 0 ;
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<Couple> couples = new ArrayList<Couple>() ;
+ 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<Couple> Scouples = new ArrayList<Couple>() ;
+ 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 ;
}
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 ;
}
}
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 ;
}
}
}
+ if( ! ok )
+ {
+ System.err.println( "No repalacing node found! No left places on any cluster!" ) ;
+ }
+
nb_fault++ ;
}
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 !! **/
private ArrayList<Association> mapping2 ;
private ArrayList<GNode> other ;
private int type ; // 0 : mapping task/node ; 1 : mapping tasks/cluster
+ private Grid gd ;
/**
mapping2 = new ArrayList<Association>() ;
other = new ArrayList<GNode>() ;
type = -1 ;
+ gd = null ;
}
mapping2 = new ArrayList<Association>() ;
other = new ArrayList<GNode>() ;
type = -1 ;
+ gd = null ;
+ }
+
+
+ /**
+ * Set the grid in which the mapping is done.
+ * @param _gd The grid
+ */
+ public void setGrid( Grid _gd )
+ {
+ gd = _gd ;
}
/** 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 ;
/**
- * 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 )
{
System.exit( 1 ) ;
}
- insertMapping( _a ) ;
+ insertMapping( new Association( _gn, _gt ), true ) ;
}
* 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<GTask> gr = new ArrayList<GTask>() ;
+ 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
if( mapping.size() != 0 )
{
- for( int i = 0 ; i < mapping.size() ; i++ )
+ ArrayList<Association> mp = organizeMapping() ;
+
+ for( int i = 0 ; i < mp.size() ; i++ )
{
- ar.add( mapping.get( i ).getGNode() ) ;
+ ar.add( mp.get( i ).getGNode() ) ;
}
}
}
+ private ArrayList<Association> organizeMapping()
+ {
+ ArrayList<Association> ret = null ;
+
+ if( mapping.size() > 0 )
+ {
+ ret = new ArrayList<Association>( 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.
*/
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( ", " ) ;
}
public int calcDepExt()
{
int depExt = 0 ;
- ArrayList<GTask> ar ;
- ArrayList<GTask> deps ;
+
+ ArrayList<Association> 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<Integer> 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++ ;
}
}
}
return ( depExt / 2 ) ;
}
+
+ /**
+ * ** TO BE MODIFIED !!!
+ * @return
+ */
+ public double calcAsyncMark()
+ {
+ double mark = 0 ;
+
+ ArrayList<Double> comput = new ArrayList<Double>() ;
+ ArrayList<Double> comput2 = new ArrayList<Double>() ;
+ double max_time = 0 ;
+
+ ArrayList<Association> 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<Integer> 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 !! **/
/** 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 {
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 ) ;
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() ;
_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 ) ) ;
* @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 ] ;
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 ;
}
