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