4 import java.util.ArrayList;
10 * Mapping algorithm based on the Edge-Cut principles
11 * @author Sébastien Miquée
14 public class FT_FEC extends Algo
16 private static final long serialVersionUID = 1L;
19 private ArrayList<GTask> atraiter ;
20 private ArrayList<GTask> encours ;
21 private ArrayList<GTask> fait ;
22 private ArrayList<Cluster> clList ;
23 private double dep_min ;
24 ArrayList<GTask> mappees ;
28 * Default constructor.
34 atraiter = new ArrayList<GTask>() ;
35 encours = new ArrayList<GTask>() ;
36 fait = new ArrayList<GTask>() ;
37 clList = new ArrayList<Cluster>() ;
45 * @param _gr Application graph to be mapped on
46 * @param _gl Grid graph
48 public FT_FEC( Graph _gr, Grid _gl )
52 atraiter = new ArrayList<GTask>() ;
53 encours = new ArrayList<GTask>() ;
54 fait = new ArrayList<GTask>() ;
55 clList = new ArrayList<Cluster>() ;
63 * @param _gr Application graph to be mapped on
64 * @param _gl Grid graph
65 * @param _dep_min Minimum amount of local dependencies
67 public FT_FEC( Graph _gr, Grid _gl, double _dep_min )
71 atraiter = new ArrayList<GTask>() ;
72 encours = new ArrayList<GTask>() ;
73 fait = new ArrayList<GTask>() ;
74 clList = new ArrayList<Cluster>() ;
80 @SuppressWarnings("unchecked")
84 System.out.println( "*********************************" ) ;
85 System.out.println( "* Launching the FT-F-EC Mapping *" ) ;
86 System.out.println( "*********************************\n\n" ) ;
88 /* If the mapping is possible ... */
89 if( gr.getNbGTask() <= gl.getNbGNode() )
91 boolean mapping_done =false ;
92 boolean reduce = false ;
104 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
106 gl.getClusters().get( i ).initMoreGNode() ;
110 while( ! mapping_done )
113 atraiter = (ArrayList<GTask>) gr.getGraph().clone() ;
115 clList = sortClusters() ;
127 boolean change_cluster = false ;
130 while( nb_ok < gr.getNbGTask() )
132 if( places == 0 || change_cluster )
137 mp.addMapping( cl, mappees ) ;
140 if( nb_ok < gr.getNbGTask() )
145 if( indice == clList.size() )
147 System.out.println( "No more cluster !! Impossible to respect constrains !! " ) ;
153 cl = clList.get( indice ) ;
154 places = cl.getNbGNode() ;
155 change_cluster = false ;
157 mappees = new ArrayList<GTask>() ;
161 if( ( atraiter.size() + encours.size() ) <= places )
164 for( int i = 0 ; i < atraiter.size() ; i++ )
166 mappees.add( atraiter.get( i ) ) ;
171 for( int i = 0 ; i < encours.size() ; i++ )
173 mappees.add( encours.get( i ) ) ;
181 atraiter = new ArrayList<GTask>() ;
182 encours = new ArrayList<GTask>() ;
184 mp.addMapping( cl, mappees ) ;
186 mapping_done = true ;
191 if( encours.size() == 0 && atraiter.size() > 0 )
193 encours.add( atraiter.remove(0) ) ;
198 if( encours.size() > 0 )
200 tmp = encours.get( 0 ) ;
205 dep = calc_dep( tmp ) ;
207 if( dep != -1 && 1 + ( dep * dep_min ) <= places && places > 0 )
217 atraiter.remove( tmp ) ;
218 encours.remove( tmp ) ;
220 change_cluster = true ;
225 change_cluster = true ;
234 mapping_done = false ;
236 System.out.println( "Reducing the minimum dependancies parameter..." ) ;
237 dep_min = dep_min - 0.1 ;
245 System.err.println( "\n\n!!! Mapping impossible ! There are more tasks than nodes !!!\n" ) ;
249 private ArrayList<Cluster> sortClusters()
251 ArrayList<Cluster> ret = new ArrayList<Cluster>() ;
255 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
259 if( ret.size() == 0 )
261 ret.add( gl.getClusters().get( i ) ) ;
263 for( int j = 0 ; j < ret.size() ; j++ )
265 if( gl.getClusters().get( i ).getNbFreeNodes() > ret.get( j ).getNbFreeNodes() )
267 ret.add( j, gl.getClusters().get( i ) ) ;
275 ret.add( gl.getClusters().get( i ) ) ;
288 private void ajoutDep( GTask _t )
294 for( int i = 0 ; i < _t.getNbDep() ; i++ )
296 tmp = _t.getDependencies().get( i ) ;
298 if( ! fait.contains( tmp ) && ! encours.contains( tmp )
299 && tmp.getNbDep() < _t.getNbDep() )
302 for( j = 0 ; j < encours.size() ; j++ )
304 if( tmp.getNbDep() < encours.get( j ).getNbDep() )
306 encours.add( j, tmp ) ;
307 j = encours.size() + 10 ;
311 if( j == encours.size() )
316 atraiter.remove( tmp ) ;
330 private double calc_dep( GTask _t )
339 for( int i = 0 ; i < _t.getNbDep() ; i++ )
341 if( ! fait.contains( _t.getDependencies().get( i ) ) )
345 if( ! mappees.contains( _t.getDependencies().get( i ) ) )
353 if( ( dep + ext ) < _t.getNbDep() * dep_min )
357 res = dep + ( ext * 0.5 ) ;
369 @SuppressWarnings("unchecked")
370 private void tri_dep()
372 int nb_tache = gr.getNbGTask() ;
375 int niveau_fait = -1 ;
378 ArrayList<GTask> tmp = new ArrayList<GTask>() ;
379 ArrayList<Integer> tab = new ArrayList<Integer>() ;
381 while( nb_tri < nb_tache )
383 // Recherche du niveau en décroissant
384 for( int i = 0 ; i < nb_tache ; i++ )
386 temp = atraiter.get(i).getNbDep() ;
390 if( niveau_fait != -1 )
392 if( temp < niveau_fait )
402 // Searching task of the current level
403 for( int i = 0 ; i < nb_tache ; i++ )
405 if( atraiter.get( i ).getNbDep() == niveau )
407 tmp.add( atraiter.get( i ) ) ;
408 tab.add( atraiter.get( i ).getNum() ) ;
414 niveau_fait = niveau ;
419 atraiter = (ArrayList<GTask>) tmp.clone() ;
424 public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
428 /** If something has to be done **/
431 ArrayList<GNode> ac = new ArrayList<GNode>() ;
434 /** Searching if clusters have some free nodes **/
435 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
437 if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
440 tmp = gl.getClusters().get( i ).nextGNode() ;
449 /** If there some nodes in clusters **/
452 double dist = -1, best = -1 ;
455 /** Searching the replacing node with the lower distance
456 * between it and the failed node
458 for( int i = 0 ; i < ac.size() ; i++ )
460 dist = gl.getDistance( _dead, ac.get( i ) ) ;
475 /** Is there any node candidate ? **/
478 ret = ac.get( bestNode ) ;
480 ret.setMapped( true ) ;
490 public GNode getOtherGNode( ArrayList<GNode> _ag )
494 int free[] = new int[ gl.getNbCluster() ] ;
496 /** Searching if clusters have some free nodes **/
497 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
499 free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ;
502 /** Returning a node from the cluster which has the most
505 int most = -1, max = 0 ;
507 for( int i = 0 ; i < free.length ; i++ )
509 if( free[ i ] > max )
516 /** Is there any cluster candidate ? **/
519 ret = gl.getClusters().get( most ).nextGNode() ;
527 public boolean setParams(Object[] _params) {
533 /** La programmation est un art, respectons ceux qui la pratiquent !! **/