3 import java.util.ArrayList;
7 public class Maheve extends Algo
9 private static final long serialVersionUID = 1L;
11 private static int minNode ;
12 private static int nbSave ;
15 private ArrayList<Cluster> sortedCluster = null ;
16 private ArrayList<GTask> tasks = null ;
20 * Empty default constructor.
28 sortedCluster = new ArrayList<Cluster>() ;
33 * Constructor of this algorithm, which takes into parameter
34 * the application graph, the grid architecture, and the correction
35 * parameter which indicates the threshold of the heterogeneity degree.
36 * @param _gr The application graph
37 * @param _gl The grid architecture
38 * @param _threshold The heterogeneity threshold
40 public Maheve( Graph _gr, Grid _gl )
45 sortedCluster = new ArrayList<Cluster>() ;
46 tasks = new ArrayList<GTask>() ;
52 * Setter for the amount of nodes to preserve on each cluster
53 * for the fault tolerance (should be 0 in an environment without fault).
54 * @param _nbSave The amount of nodes to preserve
56 public void setNbSave( int _nbSave )
66 * Getter to retrieving the amount of nodes preserved for fault tolerance.
67 * @return The amount of preserved nodes
69 public int getNbSave()
76 * Setter for the minimum amount of nodes which should be present in
77 * a cluster to consider this latter in the mapping process.
78 * @param _minNode The minimum amount of nodes a cluster should have to be
81 public void setMinNode( int _minNode )
91 * Getter to retrieve the minimum amount of nodes a cluster should have
92 * to be considered in the mapping process.
93 * @return The minimum amount of nodes a cluster should have to be
96 public int getMinNode()
104 /** If the mapping is possible ... **/
105 if( ( gr != null ) && ( gr.getNbGTask() <= gl.getNbGNode() ) )
107 System.out.println( "******************************************" ) ;
108 System.out.println( "* Launching the MAHEVE Mapping algorithm *" ) ;
109 System.out.println( "******************************************\n\n" ) ;
111 /** Local variables **/
112 ArrayList<GNode> used = null ;
114 /** Initialization of heterogeneity degree **/
115 hd = gl.getHeterogenityDegre() ;
118 /** Ordering clusters according to their real power **/
119 updateSortedClusters() ;
121 /** Searching the corresponding nodes **/
122 used = searchNodes( gr.getNbGTask() ) ;
124 if( used == null || used.size() == 0 )
126 System.err.println( "No node returned!" ) ;
131 /** Ordering tasks **/
134 if( tasks == null || tasks.size() == 0 )
136 System.err.println( "Unable to retrieve tasks to be mapped on!" ) ;
141 /** Save the Mapping **/
142 for( int i = 0 ; i < tasks.size() ; i++ )
144 mp.addMapping( new Association( used.get( i ), tasks.get( i ) ) ) ;
148 System.err.println( "\n\n!!! Unable to map application!\n\n" ) ;
154 private void orderTasks()
156 ArrayList<GTask> l1 = sortTasks() ;
158 ArrayList<Integer> st = new ArrayList<Integer>() ;
160 if( l1 != null && l1.size() > 0 )
162 ArrayList<GTask> l2 = new ArrayList<GTask>() ;
163 ArrayList<GTask> tmp = new ArrayList<GTask>() ;
165 while( l1.size() > 0 )
169 l2.add( l1.get( 0 ) ) ;
170 st.add( l1.get( 0 ).getNum() ) ;
173 while( l2.size() > 0 )
175 l1.remove( l2.get( 0 ) ) ;
176 tmp = addTask( l2.remove( 0 ), l1, st ) ;
178 for( int i = 0 ; i < tmp.size() ; i++ )
180 l2.add( tmp.get( i ) ) ;
181 st.add( tmp.get( i ).getNum() ) ;
189 private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar,
190 ArrayList<Integer> _st )
193 ArrayList<GTask> ret = null ;
195 if( _gt != null && _ar != null )
197 ret = new ArrayList<GTask>() ;
199 // ** Adding the task in the main list ** //
202 // ** Searching its dependencies ** //
203 int nbDep = (int) (_gt.getNbDep() * (1.0 - hd)) ;
207 ArrayList<Integer> dep = new ArrayList<Integer>() ;
209 // ** Retrieving dependencies and eliminating tasks already treated
210 // ** or in instance to be treated. **//
211 for( int i = 0 ; i < _gt.getDependencies().size() ; i++ )
213 if( ! _st.contains( _gt.getDependencies().get( i ).getNum() ) )
215 dep.add( _gt.getDependencies().get( i ).getNum() ) ;
220 // ** Searching dependencies in sorted tasks list ** //
221 for( int i = 0 ; i < _ar.size() ; i++ )
223 num = _ar.get( i ).getNum() ;
225 if( dep.contains( num ) )
227 // for( int j = 0 ; j < dep.size() ; j++ )
229 // if( num == dep.get( j ) )
231 ret.add( _ar.remove( i ) ) ;
249 private ArrayList<GTask> sortTasks()
251 ArrayList<GTask> ret = null ;
253 ArrayList<GTask> tmp = gr.getGraph() ;
255 if( tmp != null && tmp.size() > 0 )
257 ret = new ArrayList<GTask>() ;
259 ArrayList<Double> mt = new ArrayList<Double>() ;
264 for( int i = 0 ; i < tmp.size() ; i++ )
266 W = tmp.get( i ).getWeight() ;
267 D = tmp.get( i ).getNbDep() ;
271 MT = Math.pow( W, hd ) * Math.pow( D, ( 1.0 - hd) ) ;
273 if( ret.size() == 0 )
275 ret.add( tmp.get( i ) ) ;
278 for( int j = 0 ; j < ret.size() ; j++ )
280 if( MT > mt.get( j ) )
282 ret.add( j, tmp.get( i ) ) ;
292 ret.add( tmp.get( i ) ) ;
303 private ArrayList<GNode> searchNodes( int _nbTask )
305 ArrayList<GNode> ret = null ;
309 ret = new ArrayList<GNode>() ;
313 boolean changeParameter = false ;
315 while( nbFound < _nbTask )
319 for( i = 0 ; i < sortedCluster.size() ; i++ )
321 /** If there is enough nodes ... **/
322 if( sortedCluster.get( i ).getNbFreeNodes() >= minNode )
325 sortedCluster.get( i ).initMoreGNode() ;
327 max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ;
329 for( int j = 0 ; j < max ; j++ )
331 g = sortedCluster.get( i ).moreGNode() ;
336 if( nbFound >= _nbTask )
341 if( nbFound >= _nbTask )
345 if( i == sortedCluster.size() && nbFound < _nbTask )
347 changeParameter = true ;
352 if( changeParameter )
354 System.err.println( "The parameter \"minNode\" has been reduced " +
355 "to allow the mapping process to be done." ) ;
364 * Sort clusters according to the heterogeneity degree of the platform and
365 * the eventual application's threshold.
367 private void updateSortedClusters()
371 /** Purging the local list **/
372 sortedCluster = null ;
373 sortedCluster = new ArrayList<Cluster>() ;
375 ArrayList<Double> calcMark = new ArrayList<Double>() ;
377 hd = gl.getHeterogenityDegre() ;
379 /** Sorting clusters **/
380 ArrayList<Cluster> tmp = gl.getClusters() ;
388 double Nm = 0, Pm = 0 ;
390 for( int i = 0 ; i < tmp.size() ; i++ )
392 Nm += tmp.get( i ).getNbFreeNodes() ;
393 Pm += tmp.get( i ).getAvgAvailablePower() ;
396 for( int i = 0 ; i < tmp.size() ; i++ )
398 normN = tmp.get( i ).getNbFreeNodes() * 100 / Nm ;
399 normP = tmp.get( i ).getAvgAvailablePower() * 100 / Pm ;
401 /** The magic formula :P **/
402 calcLoc = Math.sqrt( Math.pow( (normP * hd), 2) +
403 Math.pow( (normN *(1 - hd)), 2 ) ) ;
407 if( sortedCluster.size() == 0 )
409 sortedCluster.add( tmp.get( i ) ) ;
410 calcMark.add( calcLoc ) ;
413 for( int j = 0 ; j < sortedCluster.size() ; j++ )
415 if( calcLoc > calcMark.get( j ) )
417 sortedCluster.add( j, tmp.get( i ) ) ;
418 calcMark.add( j, calcLoc ) ;
426 sortedCluster.add( tmp.get( i ) ) ;
427 calcMark.add( calcLoc ) ;
436 public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
440 /** If something has to be done **/
444 /** Any place on the same cluster ? **/
445 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
449 int id = gl.getClusterOfNode( _dead ) ;
453 cl = gl.getClusters().get(id) ;
455 if( cl.getNbFreeNodes() > 0 )
457 ret = cl.nextGNode() ;
461 System.err.println( "Cluster not found!" ) ;
465 /** If there is no more place, try other clusters **/
468 updateSortedClusters() ;
470 for( int i = 0 ; i < sortedCluster.size() ; i++ )
472 if( sortedCluster.get( i ).getNbFreeNodes() > 0 )
474 ret = sortedCluster.get( i ).nextGNode() ;
489 public GNode getOtherGNode( ArrayList<GNode> _ag )
493 /** Searching the cluster which has the more free nodes **/
494 int pos = -1, max = 0, cur = 0 ;
495 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
497 cur = gl.getClusters().get( i ).getNbFreeNodes() ;
505 ret = gl.getClusters().get( pos ).nextGNode() ;
512 /** La programmation est un art, respectons ceux qui la pratiquent !! **/