+++ /dev/null
-package and.Mapping ;
-
-
-import java.util.ArrayList;
-
-
-
-
-/**
- * Mapping algorithm based on the Edge-Cut principles
- * @author Sébastien Miquée
- *
- */
-public class LSM extends Algo
-{
- private static final long serialVersionUID = 1L;
-
-
- private ArrayList<GTask> atraiter ;
- private ArrayList<GTask> encours ;
- private ArrayList<GTask> fait ;
-// private Architecture archi ;
- private ArrayList<Architecture> liste_archi ;
- private double dep_min ;
- ArrayList<GTask> mappees ;
-
-
- /**
- * Default constructor.
- */
- public LSM()
- {
- super() ;
-
- atraiter = new ArrayList<GTask>() ;
- encours = new ArrayList<GTask>() ;
- fait = new ArrayList<GTask>() ;
-// archi = new Architecture() ;
- liste_archi = new ArrayList<Architecture>() ;
- dep_min = 0 ;
- mappees = null ;
- }
-
-
- /**
- * Constructor.
- * @param _gr Application graph to be mapped on
- * @param _gl Grid graph
- */
- public LSM( Graph _gr, Grid _gl )
- {
- super( _gr, _gl ) ;
-
- atraiter = new ArrayList<GTask>() ;
- encours = new ArrayList<GTask>() ;
- fait = new ArrayList<GTask>() ;
-// archi = new Architecture() ;
- liste_archi = new ArrayList<Architecture>() ;
- dep_min = 0 ;
- mappees = null ;
- }
-
-
- /**
- * Constructor.
- * @param _gr Application graph to be mapped on
- * @param _gl Grid graph
- * @param _dep_min Minimum amount of local dependencies
- */
- public LSM( Graph _gr, Grid _gl, double _dep_min )
- {
- super( _gr, _gl ) ;
-
- atraiter = new ArrayList<GTask>() ;
- encours = new ArrayList<GTask>() ;
- fait = new ArrayList<GTask>() ;
-// archi = new Architecture() ;
- liste_archi = new ArrayList<Architecture>() ;
- dep_min = _dep_min ;
- mappees = null ;
- }
-
-
- @SuppressWarnings("unchecked")
- @Override
- public void map()
- {
- System.out.println( "***********************************" ) ;
- System.out.println( "* Launching the Edge-Cuts Mapping *" ) ;
- System.out.println( "***********************************\n\n" ) ;
-
- /* Si le mapping est possible ... */
- if( gr.getNbGTask() <= gl.getNbGNode() )
- {
- atraiter = (ArrayList<GTask>) gr.getGraph().clone() ;
-
- liste_archi = construireArchi( gl, gr.getNbGTask() ) ;
-
- tri_dep() ;
-
- int indice = -1 ;
- int nb_ok = 0 ;
- double places = 0 ;
- double dep = -1 ;
-
-// double moy = gr.getAverageDep() ;
- GTask tmp = null ;
- Cluster cl = null ;
-
- boolean change_cluster = false ;
-
-// System.out.println("nb cluster : "+liste_archi.get(0).getNbClusters() );
-
-
- while( nb_ok < gr.getNbGTask() )
- {
- if( places == 0 || change_cluster )
- {
- if( change_cluster )
- {
- // Ajout du mapping
- mp.addMapping( cl, mappees ) ;
- }
-
- if( nb_ok < gr.getNbGTask() )
- {
- // Changement de cluster
- indice ++ ;
-
- if( indice == liste_archi.get(0).getNbClusters() )
- {
- System.out.println( "No more cluster !! Impossible to respect constrains !! " ) ;
- //System.exit( 2 ) ;
- mp.initMapping() ;
- return ;
- }
-
- cl = null ;
- cl = liste_archi.get(0).getArchi().get( indice ) ;
- places = cl.getNbGNode() ;
- change_cluster = false ;
- mappees = null ;
- mappees = new ArrayList<GTask>() ;
- }
- }
-
- if( ( atraiter.size() + encours.size() ) <= places )
- {
- for( int i = 0 ; i < atraiter.size() ; i++ )
- {
- mappees.add( atraiter.get( i ) ) ;
- nb_ok++ ;
- places-- ;
- }
-
- for( int i = 0 ; i < encours.size() ; i++ )
- {
- mappees.add( encours.get( i ) ) ;
- nb_ok++ ;
- places-- ;
- }
-
- atraiter = null ;
- encours = null ;
-
- atraiter = new ArrayList<GTask>() ;
- encours = new ArrayList<GTask>() ;
-
- mp.addMapping( cl, mappees ) ;
- }
-
- if( encours.size() == 0 && atraiter.size() > 0 )
- {
- encours.add( atraiter.get(0) ) ;
- }
-
- if( encours.size() > 0 )
- {
- tmp = encours.get( 0 ) ;
- }
-
-
-// if( ( calc_dep( tmp )* dep_min * moy ) <= places && places > 0 )
- dep = calc_dep( tmp ) ;
-
- if( dep != -1 && 1 + ( dep * dep_min ) <= places && places > 0 )
- {
- places -- ;
- nb_ok ++ ;
-
- ajoutDep( tmp ) ;
-
- mappees.add( tmp ) ;
- fait.add( tmp ) ;
-
- atraiter.remove( tmp ) ;
- encours.remove( tmp ) ;
- } else {
- change_cluster = true ;
- }
-
- if( places == 0 )
- {
- change_cluster = true ;
- }
-
- tmp = null ;
-
-// try {
-// Thread.sleep( 1000 ) ;
-// } catch( InterruptedException e ) {
-// e.printStackTrace() ;
-// }
-//
-// mp.affiche() ;
-// System.out.println( "reste : " + places + " sur " + cl.getNom() ) ;
-// System.out.println( "nb_ok = " +nb_ok);
-// System.out.println("etat : "+encours);
-// System.out.println("etat2 : "+mappees);
-// System.out.println( "etat3 : "+atraiter);
- }
-
-
- } else {
- System.out.println( "\n\n!!! Mapping impossible ! There are more tasks than nodes !!!\n" ) ;
- }
-
- /** Update in cluster the status of nodes **/
- updateGrid() ;
- }
-
- /**
- *
- * @param _t
- */
- private void ajoutDep( GTask _t )
- {
- if( _t != null )
- {
- GTask tmp = null ;
-
- for( int i = 0 ; i < _t.getNbDep() ; i++ )
- {
- tmp = _t.getDependencies().get( i ) ;
-
- if( ! fait.contains( tmp ) && ! encours.contains( tmp )
- && tmp.getNbDep() < _t.getNbDep() )
- {
-// System.out.println("haha => "+tmp.getNum() ) ;
- int j = 0 ;
- for( j = 0 ; j < encours.size() ; j++ )
- {
- if( tmp.getNbDep() < encours.get( j ).getNbDep() )
- {
- encours.add( j, tmp ) ;
- j = encours.size() + 10 ;
- }
- }
-
- if( j == encours.size() )
- {
- encours.add( tmp ) ;
- }
-
- atraiter.remove( tmp ) ;
-
- tmp = null ;
- }
- }
- }
- }
-
-
- /**
- *
- * @param _t
- * @return
- */
- private double calc_dep( GTask _t )
- {
- int dep = 0 ;
- int ext = 0 ;
-
- double res = -1 ;
-
- if( _t != null )
- {
- for( int i = 0 ; i < _t.getNbDep() ; i++ )
- {
- if( ! fait.contains( _t.getDependencies().get( i ) ) )
- {
- dep ++ ;
- } else {
- if( ! mappees.contains( _t.getDependencies().get( i ) ) )
- {
- ext++ ;
- }
- }
-
- }
-
- if( ( dep + ext ) < _t.getNbDep() * dep_min )
- {
- res = 0 ;
- } else {
- res = dep + ( ext * 0.5 ) ;
- }
-
-// System.out.println("dep de "+t.getNum()+" => " + res);
-
- }
-
-
- return res ;
- }
-
-
- /**
- *
- * @param _gl
- * @param _nbGTask
- * @return
- */
- @SuppressWarnings("unchecked")
- private ArrayList<Architecture> construireArchi( Grid _gl, int _nbGTask )
- {
- ArrayList<Architecture> ar = new ArrayList<Architecture>() ;
-
- ArrayList<Cluster> cl = (ArrayList<Cluster>) gl.getClusters().clone() ;
-
-
- // Méthode à faire !
- Architecture a = new Architecture() ;
-
- for( int i = 0 ; i < cl.size() ; i ++ )
- {
- a.addCluster( cl.get( i ) ) ;
- }
-
- ar.add( a ) ;
-
- return ar ;
- }
-
- /**
- *
- */
- @SuppressWarnings("unchecked")
- private void tri_dep()
- {
- int nb_tache = gr.getNbGTask() ;
- int nb_tri = 0 ;
- int niveau = 0 ;
- int niveau_fait = -1 ;
- int temp = 0 ;
-
- ArrayList<GTask> tmp = new ArrayList<GTask>() ;
- ArrayList<Integer> tab = new ArrayList<Integer>() ;
-
- while( nb_tri < nb_tache )
- {
- // Recherche du niveau en décroissant
- for( int i = 0 ; i < nb_tache ; i++ )
- {
- temp = atraiter.get(i).getNbDep() ;
-
- if( niveau < temp )
- {
- if( niveau_fait != -1 )
- {
- if( temp < niveau_fait )
- {
- niveau = temp ;
- }
- } else {
- niveau = temp ;
- }
- }
- }
-
- // Recherche des taches du niveau courrant
- for( int i = 0 ; i < nb_tache ; i++ )
- {
- if( atraiter.get( i ).getNbDep() == niveau )
- {
- tmp.add( atraiter.get( i ) ) ;
- tab.add( atraiter.get( i ).getNum() ) ;
-
- nb_tri ++ ;
- }
- }
-
- niveau_fait = niveau ;
- niveau = 0 ;
-
- }
-
- atraiter = (ArrayList<GTask>) tmp.clone() ;
-
-// for( int i = 0 ; i < nb_tache ; i++ )
-// {
-// System.out.print( atraiter.get(i).getNum() +" " ) ;
-// }
-// System.out.println();
- }
-
-
- @Override
- public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag )
- {
- /** Update in cluster the status of nodes **/
- updateGrid() ;
-
- return null;
- }
-
-
- @Override
- public GNode getOtherGNode( ArrayList<GNode> _ag ) {
- // TODO Auto-generated method stub
- return null;
- }
-
-}
-
-/** La programmation est un art, respectons ceux qui la pratiquent !! **/
