Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Cleaning project.
authorSébastien Miquée <sebastien.miquee@univ-fcomte.fr>
Fri, 7 May 2010 08:54:45 +0000 (10:54 +0200)
committerSébastien Miquée <sebastien.miquee@univ-fcomte.fr>
Fri, 7 May 2010 08:54:45 +0000 (10:54 +0200)
Makefile
src/and/Mapping/LSM.java [deleted file]
src/and/Mapping/QM.java [deleted file]

index 5e7081a..ba63f69 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -12,12 +12,6 @@ JAR=Mapping.jar
 EXT=com/
 JAVADOC=javadoc
 
 EXT=com/
 JAVADOC=javadoc
 
-compile:
-       @echo
-       @echo "## Compilation of Mapping library ..."
-       @echo
-       $(JAVAC) -d ./$(BIN) ./$(SRC)/$(PACKAGE)/*.java
-
 
 jar:clean compile
        @echo
 
 jar:clean compile
        @echo
@@ -26,6 +20,13 @@ jar:clean compile
        jar -cvfm ./$(JAR) Manifest ./$(EXT) -C ./$(BIN) ./$(PACK)/
 
 
        jar -cvfm ./$(JAR) Manifest ./$(EXT) -C ./$(BIN) ./$(PACK)/
 
 
+compile:
+       @echo
+       @echo "## Compilation of Mapping library ..."
+       @echo
+       $(JAVAC) -d ./$(BIN) ./$(SRC)/$(PACKAGE)/*.java
+
+
 javadoc:cleanDoc
        @echo
        @echo "## Generating Javadoc ..."
 javadoc:cleanDoc
        @echo
        @echo "## Generating Javadoc ..."
diff --git a/src/and/Mapping/LSM.java b/src/and/Mapping/LSM.java
deleted file mode 100644 (file)
index 0ac63a5..0000000
+++ /dev/null
@@ -1,525 +0,0 @@
-package and.Mapping ;
-
-
-import java.util.ArrayList;
-
-
-
-
-/**
- * Mapping algorithm based on the Edge-Cut principles
- * @author S&eacute;bastien Miqu&eacute;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 ) 
-       {
-               GNode ret = null ;
-               
-               /** Updating the grid if there is any modification **/
-               if( _ag != null && _ag.size() != 0 )
-               {
-                       gl.updateGrid( _ag ) ;
-               }
-               
-               /** If something has to be done **/
-               if( _dead != null )
-               {
-                       ArrayList<GNode> ac = new ArrayList<GNode>() ;
-                       GNode tmp = null ;
-               
-                       /** Searching if clusters have some free nodes **/
-                       for( int i = 0 ; i < gl.getNbCluster() ; i++ )
-                       {
-                               if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
-                               {
-                                       tmp = gl.getClusters().get( i ).nextGNode() ;
-                                       
-                                       if( tmp != null )
-                                       {
-                                               ac.add( tmp ) ;
-                                       }
-                               }
-                       }
-                       
-                       /** If there some nodes in clusters **/
-                       if( ac.size() > 0 )
-                       {
-                               double dist = -1, best = -1 ;
-                               int bestNode = -1 ;
-                               
-                               /** Searching the replacing node with the lower distance
-                                * between it and the failed node
-                                */
-                               for( int i = 0 ; i < ac.size() ; i++ )
-                               {
-                                       dist = gl.getDistance( _dead, ac.get( i ) ) ;
-                                       
-                                       if( best == -1 )
-                                       {
-                                               best = dist ;
-                                               bestNode = i ;
-                                       } else {
-                                               if( dist < best )
-                                               {
-                                                       best = dist ;
-                                                       bestNode = i ;
-                                               }
-                                       }
-                               }
-                               
-                               /** Is there any node candidate ? **/
-                               if( bestNode != -1 )
-                               {
-                                       ret = ac.get( bestNode ) ;
-                               }
-                       }                       
-               }
-               
-               /** Update in cluster the status of nodes **/
-               updateGrid() ;
-               
-               return ret ;
-       }
-
-
-       @Override
-       public GNode getOtherGNode( ArrayList<GNode> _ag ) 
-       {
-               GNode ret = null ;
-               
-               /** Updating the grid if there is any modification **/
-               if( _ag != null && _ag.size() != 0 )
-               {
-                       gl.updateGrid( _ag ) ;
-               }
-               
-               int free[] = new int[ gl.getNbCluster() ] ;
-               
-               /** Searching if clusters have some free nodes **/
-               for( int i = 0 ; i < gl.getNbCluster() ; i++ )
-               {
-                       free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ;
-               }
-               
-               /** Returning a node from the cluster which has the most
-                * available nodes
-                */
-               int most = -1, max = 0 ;
-               
-               for( int i = 0 ; i < free.length ; i++ )
-               {
-                       if( free[ i ] > max )
-                       {
-                               max = free[ i ] ;
-                               most = i ;
-                       }
-               }
-               
-               /** Is there any cluster candidate ? **/
-               if( most != -1 )
-               {
-                       ret = gl.getClusters().get( most ).nextGNode() ;
-               }
-               
-               
-               return ret ;
-       }
-       
-}
-
-/** La programmation est un art, respectons ceux qui la pratiquent !! **/
diff --git a/src/and/Mapping/QM.java b/src/and/Mapping/QM.java
deleted file mode 100644 (file)
index 6483cd8..0000000
+++ /dev/null
@@ -1,630 +0,0 @@
-package and.Mapping ;
-
-
-import java.util.ArrayList;
-import java.util.Random;
-
-
-/**
- * Implementation of the AIAC Quick Quality Map (AIAC-QM) algorithm
- * @author S&eacute;bastien Miqu&eacute;e
- * @version 1.0
- */
-public class QM extends Algo
-{
-       private static final long serialVersionUID = 1L;
-       
-       
-       private ArrayList<GTask2> atraiter ;
-       private ArrayList<GNode> archi ;
-       private double f ; // search factor
-       
-       
-       /**
-        * Default constructor.
-        */
-       public QM()
-       {
-               super() ;
-       }
-       
-
-       /**
-        * Constructor
-        * @param _gr Application graph to be mapped on
-        * @param _gd Grid graph
-        * @param _f Search factor
-        */
-       public QM( Graph _gr, Grid _gd, double _f )
-       {
-               super( _gr, _gd ) ;
-               
-               f = _f ;
-       }
-       
-       /**
-        * 
-        * @return
-        */
-       private ArrayList<GNode> sortInitGNode() 
-       {
-               ArrayList<GNode> grn = null ;
-               
-               if( gl != null )
-               {
-                       grn = new ArrayList<GNode>() ;
-                       
-                       ArrayList<GNode> tmp = gl.getGNodes() ;
-       
-                       grn.add( tmp.get( 0 ) ) ;
-                       
-                       boolean ok ;
-               
-                       for( int i = 1 ; i < tmp.size() ; i++ )
-                       {
-                               ok = false ;
-                               
-                               for( int j = 0 ; j < grn.size() ; j++ )
-                               {
-                                       if( tmp.get( i ).getPower() > grn.get( j ).getPower() )
-                                       {
-                                               grn.add( j, tmp.get( i ) ) ;
-                                               ok = true ;
-                                               break ;
-                                       }
-                               }
-                               
-                               if( ok == false )
-                               {
-                                       grn.add( tmp.get( i ) ) ;
-                               }
-                       }
-               }
-
-               return grn ;
-       }
-
-
-       private ArrayList<GTask2> listToGTask2( Graph _gr ) 
-       {
-               ArrayList<GTask2> gr2 = null ;
-               
-               if( _gr != null )
-               {
-                       gr2 = new ArrayList<GTask2>() ;
-               
-                       for( int i = 0 ; i < _gr.getNbGTask() ; i++ )
-                       {
-                               gr2.add( new GTask2( _gr.getGraph().get( i ) ) ) ;
-                       }
-               }
-               
-               return gr2 ;
-       }
-
-
-       @Override
-       public void map() 
-       {
-               /* If the mapping is possible ... */
-               if( gr.getNbGTask() <= gl.getNbGNode() )
-               {
-                       atraiter = listToGTask2( gr ) ;
-                       archi = sortInitGNode() ;
-                       
-                       /** Local Variables **/
-                       GNode nc = null ;
-                       double yc = -1 ;
-                       GNode nb = null ;
-                       double yb = -1 ;
-                       GNode nr = null ;
-                       double yr = -1 ;
-                       double ynb = -1 ;
-
-                       
-                       System.out.println( "*******************************************" ) ;
-                       System.out.println( "* Launching the AIAC-QM Mapping algorithm *" ) ;
-                       System.out.println( "*******************************************\n\n" ) ;
-                       
-                       /** Initial values **/
-                       int r = 1 ; // Number of rounds
-                       int n = gr.getNbGTask() ; // Number of tasks
-                       
-                       /** Initial mapping **/
-                       initMapping() ;
-                       
-                       /** Main loop **/
-                       while( isOneMoveable() )
-                       {
-                               for( int ti = 0 ; ti < atraiter.size() ; ti++ )
-                               {
-                                       if( atraiter.get( ti ).isMoveable() )
-                                       {
-                                               nc = atraiter.get( ti ).getMapedOn() ;
-                                               yc = atraiter.get( ti ).getExecTime() ;
-                                               nb = nc ;
-                                               yb = yc ;
-                                               
-                                               /** Search a node to map on **/
-                                               for( int k = 0 ; k < ( f * n / r ) ; k++ )
-                                               {
-                                                       nr = selectRandomGNode( n, r ) ;
-                                                       yr = execTimeOn( atraiter.get( ti ).clone(), nr ) ;
-                                                       
-                                                       if( yr < yb )
-                                                       {
-                                                               nb = nr ;
-                                                               yb = yr ;
-                                                       }
-                                               }
-                                               
-                                               /** Research of the neighbours' nodes **/
-                                               ArrayList<GNode> neighbours = researchNeighbours( atraiter.get( ti ), 1 ) ;
-                                               
-                                               for( int ni = 0 ; ni < neighbours.size() ; ni++ )
-                                               {
-                                                       ynb = execTimeOn( atraiter.get( ti ).clone(), neighbours.get( ni ) ) ;
-                                               
-                                                       if( ynb < yb )
-                                                       {
-                                                               nb = neighbours.get( ni ) ;
-                                                               yb = ynb ;
-                                                       }
-                                               }
-                                               
-                                               
-                                               /** Mapping of the task **/
-                                               if( ! nb.equals( nc ) )
-                                               {
-                                                       GTask2 t_ = taskOn( nb ) ;
-                                                       if( t_ != null && t_.isMoveable() )
-                                                       {
-                                                               t_.setGNode( null ) ;
-                                                       } 
-                                                       
-                                                       atraiter.get( ti ).setGNode( nb ) ;
-                                                       
-                                                       updateExecTimeNeighbours( atraiter.get( ti ) ) ;
-                                               }
-                                       }
-                                       
-                                       /** The task is fixed on this node **/
-                                       atraiter.get( ti ).setMoveable( false ) ;
-                                       
-                                       /** If all tasks have been considered **/
-                                       if( ti == atraiter.size() - 1 )
-                                       {
-                                               r++ ;
-                                       }
-                               }
-                       }
-                       
-                       /** Save the Mapping **/
-                       for( int i = 0 ; i < atraiter.size() ; i++ )
-                       {
-                               mp.addMapping( new Association( atraiter.get( i ).getMapedOn(), atraiter.get( i ).getGTask() ) ) ;
-                       }
-               
-               } else {
-                       System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
-               }
-               
-               /** Update in cluster the status of nodes **/
-               updateGrid() ;
-       }
-       
-       /**
-        * 
-        * @param _nb
-        * @return
-        */
-       private GTask2 taskOn( GNode _nb ) 
-       {
-               for( int i = 0 ; i < atraiter.size() ; i++ )
-               {
-                       if( atraiter.get( i ).getMapedOn().equals( _nb ) )
-                       {
-                               return atraiter.get( i ) ;
-                       }
-               }
-               
-               return null;
-       }
-
-       /**
-        * 
-        * @param _g
-        * @param _deep
-        * @return
-        */
-       private ArrayList<GNode> researchNeighbours( GTask2 _g, double _deep) 
-       {
-               ArrayList<GNode> nb = new ArrayList<GNode>() ;
-               ArrayList<GTask2> neighbours = new ArrayList<GTask2>() ;
-               
-               for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
-               {
-                       neighbours.add( atraiter.get( _g.getGTask().getDependencies().get( i ).getNum() ) ) ;
-               }
-               
-               for( int i = 0 ; i < archi.size() ; i++ )
-               {
-                       for( int j = 0 ; j < neighbours.size() ; j++ )
-                       {
-                               GNode tmp = neighbours.get( j ).getMapedOn() ;
-                       
-                               if( gl.getDistance( tmp, archi.get( i ) ) <= _deep && ! nb.contains( tmp ) )
-                               {
-                                       nb.add( tmp ) ;
-                               }
-                       }
-               }
-               
-               return nb ;
-       }
-
-
-       /**
-        * Initialization of the mapping. Each task is mapped on computing
-        * nodes in order of their rank.
-        */
-       private void initMapping() 
-       {
-               for( int i = 0 ; i < atraiter.size() ; i++ )
-               {
-                       atraiter.get( i ).setGNode( archi.get( i ) ) ;
-               }
-       }
-
-
-       /**
-        * 
-        * @param _g
-        * @param _n
-        * @return
-        */
-       private double execTimeOn( GTask2 _g, GNode _n ) 
-       {               
-               _g.setGNode( _n ) ;
-                       
-               return calcExecTime( _g ) ;
-       }
-
-       /**
-        * 
-        * @param _n
-        * @param _r
-        * @return
-        */
-       private GNode selectRandomGNode( int _n, int _r ) 
-       {
-               GNode g = null ;
-               
-               Random rand = new Random() ;
-               
-               g = archi.get( rand.nextInt( _n / _r ) ) ;
-               
-               while( isTaskNotMoveableOn( g ) )
-               {
-                       g = archi.get( rand.nextInt( _n / _r ) ) ;
-               }
-               
-               return g ;
-       }
-
-
-       /**
-        * 
-        * @param _g
-        * @return
-        */
-       private boolean isTaskNotMoveableOn( GNode _g ) 
-       {
-               for( int i = 0 ; i < atraiter.size() ; i++ )
-               {
-                       if( atraiter.get( i ).getMapedOn().equals( _g ) && ! atraiter.get( i ).isMoveable() )
-                       {
-                               return true ;
-                       }
-               }
-       
-               return false ;
-       }
-
-
-       /**
-        * 
-        * @return
-        */
-       private boolean isOneMoveable() 
-       {
-               if( atraiter != null && atraiter.size() > 0 )
-               {
-                       for( int i = 0 ; i < atraiter.size() ; i++ )
-                       {
-                               if( atraiter.get( i ).isMoveable() )
-                               {
-                                       return true ;
-                               }
-                       }
-               }
-               
-               return false ;
-       }
-       
-       
-       /**
-        * 
-        * @param _g
-        * @return
-        */
-       private double calcExecTime( GTask2 _g )
-       {
-               double w = -1 ;
-               
-               if( _g != null )
-               {       
-                       // Weight of computation
-                       w = ( _g.getGTask().getWeight() / _g.mappedOn.getPower() ) ;
-                       
-                       // Weight of communications
-                       int tab[] = new int[ _g.getGTask().getNbDep() ] ;
-                       for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
-                       {
-                               tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
-                       }
-                       
-                       for( int i = 0 ; i < tab.length ; i++ )
-                       {
-                               double tmp = gl.getDistance( _g.getMapedOn(), atraiter.get( tab[i] ).getMapedOn() ) ;
-                               
-                               if( tmp >= 0 )
-                               {
-                                       w += tmp ;
-                               }               
-                       }
-               }
-               
-               return w ;
-       }
-
-
-       /**
-        * 
-        * @param _g
-        */
-       private void updateExecTime( GTask2 _g )
-       {
-               double w = calcExecTime( _g ) ;
-               
-               if( w >= 0 )
-               {
-                       if( w > _g.getExecTime() )
-                       {
-                               _g.setMoveable( true ) ;
-                       }
-                       
-                       _g.setExecTime( w ) ;
-               }
-       }
-       
-       
-       /**
-        * 
-        * @param _g
-        */
-       private void updateExecTimeNeighbours( GTask2 _g )
-       {
-               int tab[] = new int[ _g.getGTask().getNbDep() ] ;
-               for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
-               {
-                       tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
-               }
-               
-               for( int i = 0 ; i < tab.length ; i++ )
-               {
-                       updateExecTime( atraiter.get( tab[i] ) ) ;                      
-               }
-       }
-       
-       
-       
-       /** Intern class **/
-       /**
-        * Temporary class.
-        */
-       private class GTask2
-       {
-               private GTask g ;
-               private boolean moveable ;
-               private double execTime ;
-               private GNode mappedOn ;
-               
-               public GTask2()
-               {
-                       g = null ;
-                       moveable = false ;
-                       execTime = -1 ;
-                       mappedOn = null ;
-               }
-               
-               public GTask2( GTask _g )
-               {
-                       g = _g ;
-                       moveable = false ;
-                       execTime = -1 ;
-                       mappedOn = null ;
-               }
-               
-               public boolean isMoveable()
-               {
-                       return moveable ;
-               }
-               
-               public void setMoveable( boolean b )
-               {
-                       moveable = b ;
-               }
-               
-               public void setGNode( GNode _g )
-               {
-                       mappedOn = _g ;
-               }
-               
-               
-               public GTask getGTask()
-               {
-                       return g ;
-               }
-               
-               
-               public double getExecTime()
-               {
-                       return execTime ;
-               }
-               
-               
-               public void setExecTime( double _d )
-               {
-                       execTime = _d ;
-               }
-               
-               public GNode getMapedOn()
-               {
-                       return mappedOn ;
-               }
-               
-               
-               public GTask2 clone()
-               {
-                       GTask2 g_new = new GTask2() ;
-                       g_new.execTime = this.execTime ;
-                       g_new.g = this.g ;
-                       g_new.mappedOn = this.mappedOn ;
-                       g_new.moveable = this.moveable ;
-                       
-                       return g_new ;
-               }
-       }
-
-
-
-       @Override
-       public GNode replaceNode(GNode _dead, ArrayList<GNode> _ag ) 
-       {
-               GNode ret = null ;
-               
-               /** Updating the grid if there is any modification **/
-               if( _ag != null && _ag.size() != 0 )
-               {
-                       gl.updateGrid( _ag ) ;
-               }
-               
-               /** If something has to be done **/
-               if( _dead != null )
-               {
-                       ArrayList<GNode> ac = new ArrayList<GNode>() ;
-                       GNode tmp = null ;
-               
-                       /** Searching if clusters have some free nodes **/
-                       for( int i = 0 ; i < gl.getNbCluster() ; i++ )
-                       {
-                               if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
-                               {
-                                       tmp = gl.getClusters().get( i ).nextGNode() ;
-                                       
-                                       if( tmp != null )
-                                       {
-                                               ac.add( tmp ) ;
-                                       }
-                               }
-                       }
-                       
-                       /** If there some nodes in clusters **/
-                       if( ac.size() > 0 )
-                       {
-                               double power = -1, best = -1 ;
-                               int bestNode = -1 ;
-                               
-                               /** Searching the replacing node with the higher 
-                                * computing power
-                                */
-                               for( int i = 0 ; i < ac.size() ; i++ )
-                               {
-                                       power = ac.get( i ).getPower() ;
-                                       
-                                       if( best == -1 )
-                                       {
-                                               best = power ;
-                                               bestNode = i ;
-                                       } else {
-                                               if( power < best )
-                                               {
-                                                       best = power ;
-                                                       bestNode = i ;
-                                               }
-                                       }
-                               }
-                               
-                               /** Is there any node candidate ? **/
-                               if( bestNode != -1 )
-                               {
-                                       ret = ac.get( bestNode ) ;
-                               }
-                       }                       
-               }
-               
-               /** Update in cluster the status of nodes **/
-               updateGrid() ;
-               
-               return ret ;
-       }
-
-
-       @Override
-       public GNode getOtherGNode( ArrayList<GNode> _ag ) 
-       {
-               GNode ret = null ;
-               
-               /** Updating the grid if there is any modification **/
-               if( _ag != null && _ag.size() != 0 )
-               {
-                       gl.updateGrid( _ag ) ;
-               }
-               
-               int free[] = new int[ gl.getNbCluster() ] ;
-               
-               /** Searching if clusters have some free nodes **/
-               for( int i = 0 ; i < gl.getNbCluster() ; i++ )
-               {
-                       free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ;
-               }
-               
-               /** Returning a node from the cluster which has the most
-                * available nodes
-                */
-               int most = -1, max = 0 ;
-               
-               for( int i = 0 ; i < free.length ; i++ )
-               {
-                       if( free[ i ] > max )
-                       {
-                               max = free[ i ] ;
-                               most = i ;
-                       }
-               }
-               
-               /** Is there any cluster candidate ? **/
-               if( most != -1 )
-               {
-                       ret = gl.getClusters().get( most ).nextGNode() ;
-               }
-               
-               
-               return ret ;
-       }
-}
-
-
-
-/** La programmation est un art, respectons ceux qui la pratiquent !! **/