Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
New stable version with the add of the Maheve algorithm.
authorSébastien Miquée <sebastien.miquee@univ-fcomte.fr>
Fri, 7 May 2010 08:51:55 +0000 (10:51 +0200)
committerSébastien Miquée <sebastien.miquee@univ-fcomte.fr>
Fri, 7 May 2010 08:51:55 +0000 (10:51 +0200)
 - Adding the new efficient MAHEVE mapping algorithm.

 - Correction of some bugs.

 - Adding minor functionalities.

 - Cleaning code.

14 files changed:
src/and/Mapping/Algo.java
src/and/Mapping/Architecture.java
src/and/Mapping/Association.java
src/and/Mapping/Cluster.java
src/and/Mapping/DefaultMapping.java
src/and/Mapping/FT_AIAC_QM.java [new file with mode: 0644]
src/and/Mapping/FT_FEC.java [new file with mode: 0644]
src/and/Mapping/GNode.java
src/and/Mapping/Graph.java
src/and/Mapping/Grid.java
src/and/Mapping/Maheve.java [new file with mode: 0644]
src/and/Mapping/Mapping.java
src/and/Mapping/Simple.java
src/and/Mapping/Utils.java

index 142b8a6..ab4a895 100644 (file)
@@ -17,6 +17,8 @@ public abstract class Algo implements Serializable
        protected Grid gl ;
        protected Mapping mp ;
        protected String ids ;
+       protected String name ;
+       protected int nb_fault ;
        
        
        /**
@@ -28,6 +30,8 @@ public abstract class Algo implements Serializable
                gl = new Grid() ;
                mp = new Mapping() ;
                ids = "" ;
+               name = "" ;
+               nb_fault = 0 ;
        }
        
        
@@ -42,6 +46,8 @@ public abstract class Algo implements Serializable
                gl = _gl ;
                mp = new Mapping() ;
                ids = "" ;
+               name = "" ;
+               nb_fault = 0 ;
        }
        
        
@@ -105,11 +111,34 @@ public abstract class Algo implements Serializable
         */
        public void setIdS( String _s )
        {
-               ids = _s ;
+               if( _s != null )
+               {
+                       ids = _s ;
+               }
        }
        
        
        /**
+        * Set the algorithms parameters when this one is instanciated 
+        * by a class load mechanism.
+        * @param _params
+        * @return
+        */
+       public boolean setParams( Object[] _params )
+       {
+               if( _params.length >= 2 )
+               {
+                       gr = (Graph) _params[0] ;
+                       gl = (Grid) _params[1];
+               } else {
+                       System.err.println( "Not enough parameters!" ) ;
+                       return false ;
+               }
+               
+               return true ;
+       }
+       
+       /**
         * Return the string identifier of the algorithm.
         * @return The algorithm's identifier
         */
@@ -120,21 +149,26 @@ public abstract class Algo implements Serializable
        
        
        /**
-        * Update the grid status after having done the mapping.
+        * Set the name of the mapping algorithm.
+        * @param _n The new name
         */
-       public void updateGrid()
+       public void setName( String _n )
        {
-               if( mp.getMappedGNodes().size() > 0 )
+               if( _n != null )
                {
-                       ArrayList<GNode> temp = mp.getMappedGNodes() ;
-                       for( int i = 0 ; i < temp.size() ; i++ )
-                       {
-                               gl.getClusterOfNode( temp.get( i ) ).setGNodeStatus( temp.get( i ), true ) ;
-                               
-                               gl.setMappedStatus( temp.get( i ), true ) ;
-                       }
+                       name = _n ;
                }
        }
+       
+       
+       /**
+        * Return the name of the mapping algorithm.
+        * @return The algorithm's name
+        */
+       public String getName()
+       {
+               return name ;
+       }
 }
 
 /** La programmation est un art, respectons ceux qui la pratiquent !! **/
index 91e45a9..530c9da 100644 (file)
@@ -1,5 +1,6 @@
 package and.Mapping ;
 
+import java.io.Serializable;
 import java.util.ArrayList;
 
 
@@ -8,8 +9,10 @@ import java.util.ArrayList;
  * @author S&eacute;bastien Miqu&eacute;e
  *
  */
-public class Architecture
+public class Architecture implements Serializable
 {
+       private static final long serialVersionUID = 1L;
+       
        private ArrayList<Cluster> archi ;
        private int nbNodes ;
        private int nbClusters ;
index 7d24134..ab8ebdc 100644 (file)
@@ -94,10 +94,18 @@ public class Association implements Serializable
        /**
         * Replace the GNode of the association.
         * @param _g The replacing GNode
+        * @return The state of the replacement
         */
-       public void setGNode( GNode _g )
+       public boolean setGNode( GNode _g )
        {
-               g = _g ;
+               if( _g != null )
+               {
+                       g = _g ;
+                       return true ;
+               } else {
+                       System.err.println( "(Association) The new GNode is null!" ) ;
+                       return false ;
+               }
        }
        
        
index 4d59d3d..712f17c 100644 (file)
@@ -14,12 +14,11 @@ public class Cluster implements Serializable
 {
        private static final long serialVersionUID = 1L;
        
-//     private int nb_node ;
        private String name ;
        private ArrayList<GNode> nodes ;
        private ArrayList<GNode> freenodes ;
        private String site ;
-//     private int indice ;
+       private int moreNode ;
        
        
        /**
@@ -27,56 +26,14 @@ public class Cluster implements Serializable
         */
        public Cluster()
        {
-//             nb_node = 0 ;
                name = "" ;
                nodes = new ArrayList<GNode>() ;
                freenodes = new ArrayList<GNode>() ;
                site = "" ;
-//             indice = 0 ;
+               moreNode = 0 ;
        }
        
        
-//     /**
-//      * Constructor.
-//      * @param _nb The amount of computing nodes in the cluster
-//      */
-//     public Cluster( int _nb )
-//     {
-//             nb_node = _nb ;
-//             name = "" ;
-//             nodes = new ArrayList<GNode>() ;
-//             freenodes = new ArrayList<GNode>() ;
-//             site = "" ;
-////           indice = 0 ;
-//             
-//             
-//             for( int i = 0 ; i < nb_node ; i++ )
-//             {
-//                     nodes.add( new GNode() ) ;
-//             }
-//     }
-       
-       
-//     /**
-//      * Constructor.
-//      * @param _nb The amount of computing nodes in the cluster
-//      * @param _name Cluster's name
-//      */
-//     public Cluster( int _nb, String _name )
-//     {
-////           nb_node = _nb ;
-//             name = _name ;
-//             nodes = new ArrayList<GNode>() ;
-//             site = "" ;
-////           indice = 0 ;
-//             
-//             for( int i = 0 ; i < nb_node ; i++ )
-//             {
-//                     nodes.add( new GNode() ) ;
-//             }
-//     }
-       
-       
        /**
         * Set the name of the cluster.
         * @param _name Cluster's name
@@ -98,8 +55,6 @@ public class Cluster implements Serializable
                        _n.setInCluster( true ) ;
                        nodes.add( _n ) ;
 
-//                     nb_node++ ;
-               
                        if( ! _n.getMapped() )
                        {
                                freenodes.add( _n ) ;
@@ -134,7 +89,6 @@ public class Cluster implements Serializable
         */
        public int getNbGNode()
        {
-//             return nb_node ;
                return nodes.size() ;
        }
        
@@ -184,29 +138,14 @@ public class Cluster implements Serializable
                return pos ;
        }
        
-//     /**
-//      * Initialization of indice variable.
-//      */
-//     public void initIndice()
-//     {
-//             indice = 0 ;
-//     }
-
-
        /**
-        * Return the next computing node in the cluster,
-        * according to the indice variable.
+        * Return the next available computing node in the cluster.
         * @return The next node in the cluster
         */
        public GNode nextGNode() 
        {
                GNode ret = null ;
                
-//             if( indice < nb_node )
-//             {
-//                     ret = nodes.get( indice ) ;
-//                     indice++ ;
-//             }
                if( freenodes.size() > 0 )
                {
                        ret = freenodes.get( 0 ) ;
@@ -214,6 +153,30 @@ public class Cluster implements Serializable
                
                return ret ;
        }
+       
+       
+       /**
+        * Return the next available computing node in the cluster,
+        * according to the moreNode iterator.
+        * @return The next node in the cluster
+        */
+       public GNode moreGNode()
+       {
+               GNode ret = null ;
+               
+               if( freenodes.size() > 0 )
+               {
+                       if( moreNode >= freenodes.size() )
+                       {
+                               moreNode = 0 ;
+                       }
+                       
+                       ret = freenodes.get( moreNode ) ;
+                       moreNode++ ;
+               }
+               
+               return ret ;
+       }
 
 
        /**
@@ -222,18 +185,40 @@ public class Cluster implements Serializable
         */
        public void removeGNode( GNode _dead ) 
        {
-               if( _dead != null && _dead.getCluster().equals( name ) && _dead.getSite().equals( site )  )
+               if( _dead != null )
                {
-                       for( int i = 0 ; i < nodes.size() ; i++ )
+                       if( _dead.getCluster().equals( name ) && _dead.getSite().equals( site )  )
                        {
-                               if( _dead.getId() == nodes.get( i ).getId() )
+                               int i = 0 ;
+                               for( i = 0 ; i < nodes.size() ; i++ )
                                {
-                                       freenodes.remove( nodes.remove( i ) ) ;
-//                                     nb_node-- ;
-                                       
-                                       break ;
+                                       if( _dead.getId() == nodes.get( i ).getId() )
+                                       {
+                                               nodes.remove( i ) ;
+
+                                               int j = 0 ;
+                                               for( j = 0 ; j < freenodes.size() ; j++ )
+                                               {
+                                                       if( freenodes.get(j).getId() == _dead.getId() )
+                                                       {
+                                                               freenodes.remove( j ) ;
+                                                               break ;
+                                                       }
+                                               }
+
+                                               break ;
+                                       }
                                }
+                               
+                               if( i > nodes.size() )
+                               {
+                                       System.err.println( "(Cluster) The GNode was not found in the list!" );
+                               }
+                       } else {
+                               System.err.println( "(Cluster) The GNode to be deleted is not mine!" ) ;
                        }
+               } else {
+                       System.err.println( "(Cluster) The GNode to be deleted is null!" ) ;
                }
        }
        
@@ -255,7 +240,15 @@ public class Cluster implements Serializable
                                        
                                        if( _status ) 
                                        {
-                                               freenodes.remove( nodes.get(i) ) ;
+                                               for( int j = 0 ; j < freenodes.size() ; j++ )
+                                               {
+                                                       if( freenodes.get(j).getId() == nodes.get(i).getId() )
+                                                       {
+                                                               freenodes.remove( j ) ;
+                                                               break ;
+                                                       }
+                                               }
+
                                        } else {
                                                if( ! freenodes.contains( nodes.get( i ) ) )
                                                        freenodes.add( nodes.get( i ) ) ;
@@ -279,29 +272,19 @@ public class Cluster implements Serializable
        /**
         * Compute and return the real available computing power of the cluster,
         * including the heterogeneity degree of the platform. 
-        * @param _het The heterogeneity degree of the platform
         * @return The real available computing power
         */
-       public double getAvailablePower( double _het )
+       public double getAvailablePower()
        {
                double ret = 0 ;
                
                /** If there is some available nodes **/
                if( freenodes.size() > 0 )
-               {
-                       double het = _het ;
-                       double totalPower = 0 ;
-                       
-                       if( het == 0 )
-                               het = 0.00001 ;
-                       
+               {                                               
                        for( int i = 0 ; i < freenodes.size() ; i++ )
                        {
-                               totalPower += freenodes.get( i ).getPower() ;
+                               ret += freenodes.get( i ).getPower() ;
                        }
-                       
-                       ret = Math.pow( ( totalPower / freenodes.size() ), ( 2 * het) ) *
-                             ( freenodes.size() / ( het * het) ) ;
                }
                
                return ret ;
index 2f096b8..3de90b1 100644 (file)
@@ -2,6 +2,7 @@ package and.Mapping ;
 
 
 import java.util.ArrayList;
+import java.util.Random;
 
 
 /**
@@ -23,6 +24,7 @@ public class DefaultMapping extends Algo
        public DefaultMapping()
        {
                super() ;
+               name = "DefaultMapping" ;
        }
        
 
@@ -35,6 +37,7 @@ public class DefaultMapping extends Algo
        {
                super( _gr, _gd ) ;
                archi = _gnodes ;
+               name = "DefaultMapping" ;
        }
        
 
@@ -60,9 +63,6 @@ public class DefaultMapping extends Algo
                } else {
                        System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
                }
-               
-               /** Update in cluster the status of nodes **/
-               updateGrid() ;
        }
 
 
@@ -71,7 +71,7 @@ public class DefaultMapping extends Algo
        {
                GNode ret = null ;
                
-               if( _dead != null )
+               if( _dead != null && _ag != null )
                {
                        int pos = 0 ;
                        pos = mp.getIdOfAssociation( _dead ) ;
@@ -84,18 +84,17 @@ public class DefaultMapping extends Algo
                        
                        if( _ag.size() > 0 )
                        {
-                               ret = _ag.get( 0 ) ;
-                               
+                               Random r = new Random() ;
+                               ret = _ag.get( r.nextInt( _ag.size() ) ) ;
                                
                        } else {
                                System.err.println( "Not enought available nodes in gnodes to replace one !" ) ;
                                return null ;
-                       }               
+                       }       
+                       
+                       nb_fault++ ;
                }
                
-               /** Update in cluster the status of nodes **/
-               updateGrid() ;
-               
                return ret ;
        }
 
@@ -106,7 +105,7 @@ public class DefaultMapping extends Algo
                /** Returning the first node in the list **/
                if( _ag.size() > 0 )
                {
-                       return _ag.get( 1 ) ;
+                       return _ag.get( 0 ) ;
                } 
                
                return null ;
diff --git a/src/and/Mapping/FT_AIAC_QM.java b/src/and/Mapping/FT_AIAC_QM.java
new file mode 100644 (file)
index 0000000..a7e87c6
--- /dev/null
@@ -0,0 +1,619 @@
+package and.Mapping ;
+
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Random;
+
+
+/**
+ * Implementation of the Fault Tolerant AIAC Quick Quality Map (FT-AIAC-QM) algorithm
+ * @author S&eacute;bastien Miqu&eacute;e
+ * @version 1.0
+ */
+public class FT_AIAC_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 FT_AIAC_QM()
+       {
+               super() ;
+               name = "AIAC-QM" ;
+       }
+       
+
+       /**
+        * Constructor
+        * @param _gr Application graph to be mapped on
+        * @param _gd Grid graph
+        * @param _f Search factor
+        */
+       public FT_AIAC_QM( Graph _gr, Grid _gd, double _f )
+       {
+               super( _gr, _gd ) ;
+               
+               f = _f ;
+               name = "AIAC-QM" ;
+       }
+       
+       /**
+        * 
+        * @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 FT-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" ) ;
+               }
+       }
+       
+       /**
+        * 
+        * @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 implements Serializable
+       {
+               private static final long serialVersionUID = 1L;
+               
+               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 ;
+               
+               /** 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 ) ;
+                               }
+                       }               
+                       
+                       nb_fault++ ;
+               }
+               
+               return ret ;
+       }
+
+
+       @Override
+       public GNode getOtherGNode( ArrayList<GNode> _ag ) 
+       {
+               GNode ret = null ;
+               
+               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/FT_FEC.java b/src/and/Mapping/FT_FEC.java
new file mode 100644 (file)
index 0000000..28f78f8
--- /dev/null
@@ -0,0 +1,521 @@
+package and.Mapping ;
+
+
+import java.util.ArrayList;
+
+
+
+
+/**
+ * Mapping algorithm based on the Edge-Cut principles
+ * @author S&eacute;bastien Miqu&eacute;e
+ *
+ */
+public class FT_FEC extends Algo
+{
+       private static final long serialVersionUID = 1L;
+       
+       
+       private ArrayList<GTask> atraiter ;
+       private ArrayList<GTask> encours ;
+       private ArrayList<GTask> fait ;
+       private ArrayList<Cluster> clList ;
+       private double dep_min ;
+       ArrayList<GTask> mappees ;
+       
+       
+       /**
+        * Default constructor.
+        */
+       public FT_FEC()
+       {
+               super() ;
+               
+               atraiter = new ArrayList<GTask>() ;
+               encours = new ArrayList<GTask>() ;
+               fait = new ArrayList<GTask>() ;
+               clList = new ArrayList<Cluster>() ;
+               dep_min = 0 ;
+               mappees = null ;
+       }
+       
+       
+       /**
+        * Constructor.
+        * @param _gr Application graph to be mapped on
+        * @param _gl Grid graph
+        */
+       public FT_FEC( Graph _gr, Grid _gl )
+       {
+               super( _gr, _gl ) ;
+               
+               atraiter = new ArrayList<GTask>() ;
+               encours = new ArrayList<GTask>() ;
+               fait = new ArrayList<GTask>() ;
+               clList = new ArrayList<Cluster>() ;
+               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 FT_FEC( Graph _gr, Grid _gl, double _dep_min )
+       {
+               super( _gr, _gl ) ;
+               
+               atraiter = new ArrayList<GTask>() ;
+               encours = new ArrayList<GTask>() ;
+               fait = new ArrayList<GTask>() ;
+               clList = new ArrayList<Cluster>() ;
+               dep_min = _dep_min ;
+               mappees = null ;
+       }
+       
+       
+       @SuppressWarnings("unchecked")
+       @Override
+       public void map() 
+       {
+               System.out.println( "*********************************" ) ;
+               System.out.println( "* Launching the FT-F-EC Mapping *" ) ;
+               System.out.println( "*********************************\n\n" ) ;
+
+               /* If the mapping is possible ... */
+               if( gr.getNbGTask() <= gl.getNbGNode() )
+               {
+                       boolean mapping_done =false ;
+                       boolean reduce = false ;
+                       
+                       if( dep_min > 1.0 )
+                       {
+                               dep_min = 1.0 ;
+                       }
+                       
+                       if( dep_min < 0 )
+                       {
+                               dep_min = 0 ;
+                       }
+
+                       while( ! mapping_done )
+                       {
+                               reduce = false ;
+                               atraiter = (ArrayList<GTask>) gr.getGraph().clone() ;
+
+                               clList = sortClusters() ;
+                               
+                               tri_dep() ;
+
+                               int indice = -1 ;
+                               int nb_ok = 0 ;
+                               double places = 0 ;
+                               double dep = -1 ;
+
+                               GTask tmp = null ;
+                               Cluster cl = null ;
+
+                               boolean change_cluster = false ;
+
+
+                               while( nb_ok < gr.getNbGTask() )
+                               {                               
+                                       if( places == 0 || change_cluster )
+                                       {
+                                               if( change_cluster )
+                                               {
+                                                       // Adding mapping
+                                                       mp.addMapping( cl, mappees ) ;
+                                               }
+
+                                               if( nb_ok < gr.getNbGTask() )
+                                               {
+                                                       // Switching cluster
+                                                       indice ++ ;
+
+                                                       if( indice == clList.size()  )
+                                                       {
+                                                               System.out.println( "No more cluster !! Impossible to respect constrains !! " ) ;
+                                                               mp.initMapping() ;
+                                                               reduce = true ;
+                                                       }
+
+                                                       cl = null ;
+                                                       cl = clList.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 ) ;
+                                               
+                                               mapping_done = true ;
+                                               reduce = false ;
+                                               break ;
+                                       }
+
+                                       if( encours.size() == 0 && atraiter.size() > 0 )
+                                       {
+                                               encours.add( atraiter.remove(0) ) ;
+                                       }
+
+                                       tmp = null ;
+                                       
+                                       if( encours.size() > 0 ) 
+                                       {
+                                               tmp = encours.get( 0 ) ;
+                                       }
+
+                                       if( tmp != null )
+                                       {
+                                               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 ;
+                                       }
+                               }
+
+                               if( reduce )
+                               {
+                                       mapping_done = false ;
+
+                                       System.out.println( "Reducing the minimum dependancies parameter..." ) ;
+                                       dep_min = dep_min - 0.1 ;
+                                       nb_ok = 0 ;
+                               }
+
+                       }
+
+
+               } else {
+                       System.err.println( "\n\n!!! Mapping impossible ! There are more tasks than nodes !!!\n" ) ;
+               }
+       }
+       
+       private ArrayList<Cluster> sortClusters() 
+       {
+               ArrayList<Cluster> ret = new ArrayList<Cluster>() ;
+               
+               boolean ok ;
+               
+               for( int i = 0 ; i < gl.getNbCluster() ; i++ )
+               {
+                       ok = false ;
+                       
+                       if( ret.size() == 0 )
+                       {
+                               ret.add( gl.getClusters().get( i ) ) ;
+                       } else {
+                               for( int j = 0 ; j < ret.size() ; j++ )
+                               {
+                                       if( gl.getClusters().get( i ).getNbFreeNodes() > ret.get( j ).getNbFreeNodes() )
+                                       {
+                                               ret.add( j, gl.getClusters().get( i ) ) ;
+                                               ok = true ;
+                                               break ;
+                                       }
+                               }
+                               
+                               if( ! ok ) 
+                               {
+                                       ret.add( gl.getClusters().get( i ) ) ;          
+                               }
+                       }
+               }
+               
+               return ret ;
+       }
+
+
+       /**
+        * 
+        * @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() )
+                               {
+                                       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 ) ;
+                       }
+               }
+
+               return res ;
+       }
+               
+
+       
+       /**
+        * 
+        */
+       @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 ;
+                                       }
+                               }
+                       }
+                       
+                       // Searching task of the current level
+                       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() ;
+       }
+
+
+       @Override
+       public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag ) 
+       {
+               GNode ret = null ;
+               
+               /** 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 = null ;
+                                       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 ) ;
+                                       
+                                       ret.setMapped( true ) ;
+                               }
+                       }                       
+               }
+               
+               return ret ;
+       }
+
+
+       @Override
+       public GNode getOtherGNode( ArrayList<GNode> _ag ) 
+       {
+               GNode ret = null ;
+               
+               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 !! **/
index b76d0c1..e7d5f94 100644 (file)
@@ -23,6 +23,7 @@ public class GNode implements Serializable
        private boolean inCluster ;
        private String cluster ;
        private String site ;
+       private String ip ;
        
        
        /**
@@ -293,6 +294,26 @@ public class GNode implements Serializable
                return name ;
        }
        
+       
+       /**
+        * Return the IP address of the GNode.
+        * @return The IP address
+        */
+       public String getIP()
+       {
+               return ip ;
+       }
+       
+       
+       /**
+        * Set the IP address of the GNode.
+        * @param _ip The IP address
+        */
+       public void setIP( String _ip )
+       {
+               ip = _ip ;
+       }
+       
 }
 
 /** La programmation est un art, respectons ceux qui la pratiquent !! **/
index 79efb2f..8f255cd 100644 (file)
@@ -17,7 +17,6 @@ public class Graph implements Serializable
 
        
        private ArrayList<GTask> graph ;
-//     private int nb_task ;
        private int nb_dep_total ;
        
        
@@ -27,7 +26,6 @@ public class Graph implements Serializable
        public Graph()
        {
                graph = new ArrayList<GTask>() ;
-//             nb_task = 0 ;
                nb_dep_total = 0 ;
        }
        
@@ -39,7 +37,6 @@ public class Graph implements Serializable
        public int getNbGTask()
        {
                return graph.size() ;
-//             return nb_task ;
        }
        
        
@@ -70,7 +67,6 @@ public class Graph implements Serializable
                        {
                                graph.add( _lt.get( i ).getNum(), _lt.get( i ) ) ;
                                nb_dep_total += _lt.get( i ).getNbDep() ;
-//                             nb_task ++ ;
                        }
                }
        }
index 3501a2d..57345cd 100644 (file)
@@ -14,9 +14,6 @@ public class Grid implements Serializable
 {
        private static final long serialVersionUID = 1L;
 
-       
-//     private int nb_cluster ;
-//     private int nb_node ;
        private ArrayList<Cluster> clusters ;
        private ArrayList<GNode> gnodesList;
        private boolean gnodesList_done;
@@ -27,8 +24,6 @@ public class Grid implements Serializable
         */
        public Grid()
        {
-//             nb_cluster = 0 ;
-//             nb_node = 0 ;
                clusters = new ArrayList<Cluster>() ;
                gnodesList = new ArrayList<GNode>() ;
                gnodesList_done = false ;
@@ -49,8 +44,6 @@ public class Grid implements Serializable
                        {
                                gnodesList.add( c.getGNodes().get( i ) ) ;
                        }
-//                     nb_cluster++ ;
-//                     nb_node += c.getNbGNode() ;
                }
        }
        
@@ -68,9 +61,7 @@ public class Grid implements Serializable
                        for( int i = 0 ; i < al.size() ; i++ )
                        {
                                clusters.add( al.get( i ) ) ;
-//                             nb_cluster++ ;
                                nbCLusterNodes = al.get( i ).getNbGNode() ;
-//                             nb_node += nbCLusterNodes ;
                                
                                for( int j = 0 ; j < nbCLusterNodes ; j++ )
                                {
@@ -88,7 +79,6 @@ public class Grid implements Serializable
        public int getNbCluster()
        {
                return clusters.size() ;
-//             return nb_cluster ;
        }
        
        
@@ -99,7 +89,6 @@ public class Grid implements Serializable
        public int getNbGNode()
        {
                return gnodesList.size() ;
-//             return nb_node ;
        }
        
        
@@ -113,18 +102,6 @@ public class Grid implements Serializable
        }
        
        
-//     /**
-//      * Initialization of clusters.
-//      */
-//     public void initClusters()
-//     {
-//             for( int i = 0 ; i < nb_cluster ; i++ )
-//             {
-//                     clusters.get( i ).initIndice() ;
-//             }
-//     }
-       
-       
        /**
         * Compute and return the distance between two clusters.
         * @param _g1 First cluster
@@ -157,8 +134,6 @@ public class Grid implements Serializable
                        }
                }
                
-               //
-               
                if( cluster1.compareTo( cluster2 ) == 0 )
                {
                        d = 1 ;
@@ -227,8 +202,7 @@ public class Grid implements Serializable
                                                        _gnodes.get( i ).setInCluster( true ) ;
                                                        _gnodes.get( i ).setMapped( false ) ;
                                                
-                                                       clusters.get( i ).addGNode( _gnodes.get( j ) ) ;
-//                                                     nb_node++ ;
+                                                       clusters.get( j ).addGNode( _gnodes.get( i ) ) ;
                                                        gnodesList.add( _gnodes.get( i ) ) ;
                                                        
                                                } else {
@@ -260,10 +234,8 @@ public class Grid implements Serializable
                                        _gnodes.get( i ).setCluster( cluster ) ;
                                        
                                        nClust.addGNode( _gnodes.get( i ) ) ;
-//                                     nb_cluster++ ;
                                        
                                        clusters.add( nClust ) ;
-//                                     nb_node++ ;
                                        gnodesList.add( _gnodes.get( i ) ) ;
                                }
                        }
@@ -274,34 +246,92 @@ public class Grid implements Serializable
        
        
        /**
-        * Remove a computing node from the grid.
-        * @param _dead The node to be removed
+        * Upgrade the grid with a new node.
+        * @param _g The new node
         */
-       public void removeGNode( GNode _dead ) 
+       public void addGNode( GNode _g )
        {
-               if( _dead != null )
+               if( _g != null )
                {
-                       if( _dead.getMapped() )
+                       /** Searching the cluster in which the node should be added **/
+                       int j = 0 ;
+                       for( j = 0; j < clusters.size(); j++ )
                        {
-                               String site = "", cluster = "" ;
-                       
-                               site = _dead.getSite() ;
-                               cluster = _dead.getCluster() ;
-                       
-                               /** Removing GNode from its cluster **/                 
-                               for( int j = 0 ; j < clusters.size() ; j++ )
+                               if( _g.getCluster().equalsIgnoreCase( clusters.get( j ).getName() ) )
                                {
-                                       if( clusters.get( j ).getName().equals( cluster ) && clusters.get( j ).getSite().equals( site ))
+                                       int pos = clusters.get( j ).isIn( _g ) ;
+                                               
+                                       if( pos == -1 )
                                        {
-                                               clusters.get( j ).removeGNode( _dead ) ;
-                                       
-                                               break ;
+                                               _g.setSite( clusters.get( j ).getSite() ) ;
+                                               _g.setInCluster( true ) ;
+                                               _g.setMapped( false ) ;
+                                               
+                                               clusters.get( j ).addGNode( _g ) ;
+                                               gnodesList.add( _g ) ;
+                                                       
+                                       } else {
+                                               clusters.get( j ).removeGNode( _g ) ;
+                                               clusters.get( j ).addGNode( _g ) ;
                                        }
+                                               
+                                       break ;
                                }
                        }
+                               
+                       /** The cluster was not found, so it is a new one **/
+                       if( j == clusters.size() )
+                       {
+                               String site = "", cluster = "" ;
+                               Cluster nClust = new Cluster() ;
+                                               
+                               String names[] = Utils.decodeG5Knames( _g.getName() ) ;
+                                       
+                               cluster = names[ 1 ] ;
+                               site = names[ 2 ] ;
+                               
+                               System.out.println("** (Grid) Creation of cluster: "+cluster);
+                               
+                               nClust.setName( cluster ) ;
+                               nClust.setSite( site ) ;
+                                       
+                               _g.setInCluster( true ) ;
+                               _g.setMapped( false ) ;
+                               _g.setSite( site ) ;
+                               _g.setCluster( cluster ) ;
+                                       
+                               nClust.addGNode( _g ) ;
+                                       
+                               clusters.add( nClust ) ;
+                               gnodesList.add( _g ) ;
+                       }
+               }
                        
+               gnodesList_done = false ;
+       }
+       
+       
+       /**
+        * Remove a computing node from the grid.
+        * @param _dead The node to be removed
+        */
+       public void removeGNode( GNode _dead ) 
+       {
+               if( _dead != null )
+               {
+                       /** Removing GNode from its cluster **/ 
+                       int id = getClusterOfNode( _dead ) ; 
+                       
+                       if( id != -1 )
+                       {
+                               clusters.get( id ).removeGNode( _dead ) ;
+                       } else {
+                               System.err.println( "(Grid) Cluster of dead node not found!" ) ;
+                       }
+
                        /** Removing the dead node from the global list **/
-                       for( int i = 0 ; i < gnodesList.size() ; i++ )
+                       int i = 0 ;
+                       for( i = 0 ; i < gnodesList.size() ; i++ )
                        {
                                if( _dead.getId() == gnodesList.get( i ).getId() )
                                {
@@ -309,9 +339,11 @@ public class Grid implements Serializable
                                        break ;
                                }
                        }
+
+               } else {
+                       System.err.println( "(Grid) The GNode to be deleted is null!" ) ;
                }
-               
-//             nb_node-- ;
+
                gnodesList_done = false ;
        }
        
@@ -326,7 +358,14 @@ public class Grid implements Serializable
                if( _g != null )
                {
                        /** Change in the cluster **/
-                       getClusterOfNode( _g ).setGNodeStatus( _g, _status ) ;
+                       int id = getClusterOfNode( _g ) ;
+                       
+                       if( id != -1 )
+                       {
+                               clusters.get(id).setGNodeStatus( _g, _status ) ;
+                       } else {
+                               System.err.println( "(Grid) Cluster "+_g.getCluster()+" not found!" ) ;
+                       }
                        
                        /** Change in local list **/
                        for( int i = 0 ; i < gnodesList.size() ; i++ )
@@ -346,20 +385,26 @@ public class Grid implements Serializable
         * @param _g A node
         * @return The cluster containing the node
         */
-       public Cluster getClusterOfNode( GNode _g )
+       public int getClusterOfNode( GNode _g )
        {
+               int ret = -1 ;
+               
                if( _g != null )
                {
                        for( int i = 0 ; i < clusters.size() ; i++ )
                        {
                                if( _g.getCluster().equalsIgnoreCase( clusters.get( i ).getName() ) ) 
                                {
-                                       return clusters.get( i ) ;
+                                       if( _g.getSite().equalsIgnoreCase( clusters.get( i ).getSite() ) ) 
+                                       {
+                                               ret = i ;
+                                               break ;
+                                       }
                                }
                        }
                }
                
-               return null ;
+               return ret ;
        }
        
        /**
@@ -402,7 +447,13 @@ public class Grid implements Serializable
                std = Math.sqrt( temp ) ;
                
                /** Computation of the relative standard deviation **/
-               hd = 100 * std / average ;
+               hd = std / average ;
+               
+               /** Correction of the maximum value **/
+               if( hd > 1 )
+               {
+                       hd = 1 ;
+               }
                
                
                return hd ;
@@ -445,7 +496,14 @@ public class Grid implements Serializable
                        {
                                setMappedStatus( _ag.get( i ), false ) ;
                                
-                               getClusterOfNode( _ag.get( i ) ).setGNodeStatus( _ag.get( i ), false ) ;
+                               int id = getClusterOfNode( _ag.get( i ) ) ;
+                               
+                               if( id != -1 )
+                               {
+                                       clusters.get(id).setGNodeStatus( _ag.get( i ), false ) ;
+                               } else {
+                                       System.err.println( "Cluster not found" ) ;
+                               }
                        }
                }
        }
@@ -466,6 +524,47 @@ public class Grid implements Serializable
                
                System.out.println();
        }
+
+
+       /**
+        * Return the average power of the grid, by computing the average for 
+        * eac cluster.
+        * @return The average power of the grid
+        */
+       public double getAvgFreePower() 
+       {
+               double ret = 0 ;
+               int nb = 0 ;
+               
+               if( clusters != null && clusters.size() > 0 )
+               {
+                       for( int i = 0 ; i < clusters.size() ; i++ )
+                       {
+                               nb++ ;
+                       
+                               ret += clusters.get( i ).getAvailablePower() / clusters.get( i ).getNbFreeNodes() ;
+                       }
+               
+                       ret = ret / nb ;
+                       
+               }
+               
+               return ret ;
+       }
+       
+
+       /**
+        * Return the amount of freenodes available in the whole grid.
+        * @return The amount of available nodes
+        */
+       public int getNbFreenodes()
+       {
+               int ret = 0 ;
+               
+               for( int i = 0 ; i < clusters.size() ; i++ )
+                       ret += clusters.get(i).getNbFreeNodes() ;
+               return ret ;
+       }
        
 }
 
diff --git a/src/and/Mapping/Maheve.java b/src/and/Mapping/Maheve.java
new file mode 100644 (file)
index 0000000..4a24142
--- /dev/null
@@ -0,0 +1,421 @@
+package and.Mapping;
+
+import java.util.ArrayList;
+
+
+
+public class Maheve extends Algo
+{
+       private static final long serialVersionUID = 1L;
+
+       private static final int minNode = 5 ;
+       private static final int nbSave = 2 ;
+       
+       private double hd ;
+       private ArrayList<Cluster> sortedCluster = null ;
+       private ArrayList<GTask> tasks = null ;
+       
+       
+       /**
+        * Empty default constructor.
+        */
+       public Maheve()
+       {
+               super() ;
+               name = "MAHEVE_2" ;
+               sortedCluster = new ArrayList<Cluster>() ;
+       }
+       
+       
+       /**
+        * Constructor of this algorithm, which takes into parameter
+        * the application graph, the grid architecture, and the correction
+        * parameter which indicates the threshold of the heterogeneity degree.
+        * @param _gr The application graph
+        * @param _gl The grid architecture
+        * @param _threshold The heterogeneity threshold
+        */
+       public Maheve( Graph _gr, Grid _gl )
+       {
+               super( _gr, _gl ) ;
+               
+               hd = 0 ;
+               sortedCluster = new ArrayList<Cluster>() ;
+               tasks = new ArrayList<GTask>() ;
+               name = "MAHEVE_2" ;
+       }
+       
+       
+       @Override
+       public void map() {
+               /** If the mapping is possible ... **/
+               if( ( gr != null ) && ( gr.getNbGTask() <= gl.getNbGNode() ) )
+               {
+                       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 = gl.getHeterogenityDegre() ;
+                       
+                       
+                       /** 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() ;
+                       
+                       if( tasks == null || tasks.size() == 0 )
+                       {
+                               System.err.println( "Unable to retrieve tasks to be mapped on!" ) ;
+                               return ;
+                       }
+                       
+                       
+                       /** 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 orderTasks()
+       {               
+               ArrayList<GTask> l1 = sortTasks() ;
+               
+               if( l1 != null && l1.size() > 0 )
+               {                       
+                       ArrayList<GTask> l2 = new ArrayList<GTask>() ;
+                       ArrayList<GTask> tmp = new ArrayList<GTask>() ;
+                       
+                       while( l1.size() > 0 )
+                       {
+                               if( l2.size() == 0 )
+                               {
+                                       l2.add( l1.get( 0 ) ) ;
+                               }
+                               
+                               while( l2.size() > 0 )
+                               {
+                                       l1.remove( l2.get( 0 ) ) ;
+                                       tmp = addTask( l2.remove( 0 ), l1 ) ;
+                                       
+                                       for( int i = 0 ; i < tmp.size() ; i++ )
+                                       {
+                                               l2.add( tmp.get( i ) ) ;
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       
+       private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar) 
+       {
+       
+               ArrayList<GTask> ret = null ;
+               
+               if( _gt != null && _ar != null )
+               {
+                       ret = new ArrayList<GTask>() ;
+                       
+                       // ** Adding the task in the main list ** //
+                       tasks.add( _gt ) ;
+                       
+                       // ** Searching its dependencies ** //
+                       int nbDep = (int) (_gt.getNbDep() * (1.0 - hd)) ;
+                       int cmpt = 0 ;
+                       int num = 0 ;
+                       
+                       ArrayList<Integer> dep = new ArrayList<Integer>() ;
+                       
+                       for( int i = 0 ; i < _gt.getDependencies().size() ; i++ )
+                       {
+                               dep.add( _gt.getDependencies().get( i ).getNum() ) ;
+                       }
+                       
+                       for( int i = 0 ; i < _ar.size() ; i++ )
+                       {
+                               num = _ar.get( i ).getNum() ;
+                               
+                               for( int j = 0 ; j < dep.size() ; j++ )
+                               {
+                                       if( num == dep.get( j ) )
+                                       {
+                                               ret.add( _ar.remove( i ) ) ;
+                                               cmpt++ ;
+                                               dep.remove( j ) ;
+                                               break ;
+                                       }
+                               }
+                               
+                               if( cmpt == nbDep )
+                               {
+                                       break ;
+                               }
+                       }
+               }
+               
+               return ret;
+       }
+
+
+       private ArrayList<GTask> sortTasks()
+       {
+               ArrayList<GTask> ret = null ;
+               
+               ArrayList<GTask> tmp = gr.getGraph() ;
+               
+               if( tmp != null && tmp.size() > 0 )
+               {
+                       ret = new ArrayList<GTask>() ;
+                       
+                       ArrayList<Double> mt = new ArrayList<Double>() ;
+                       
+                       double W, D, MT ;
+                       boolean ok = false ;
+                       
+                       for( int i = 0 ; i < tmp.size() ; i++ )
+                       {
+                               W = tmp.get( i ).getWeight() ;
+                               D = tmp.get( i ).getNbDep() ;
+                               
+                               ok = false ;
+                               
+                               MT = Math.pow( W, hd ) * Math.pow( D, ( 1.0 - hd) ) ;
+                               
+                               if( ret.size() == 0 )
+                               {
+                                       ret.add( tmp.get( i ) ) ;
+                                       mt.add( MT ) ;
+                               } else {
+                                       for( int j = 0 ; j < ret.size() ; j++ )
+                                       {
+                                               if( MT > mt.get( j ) )
+                                               {
+                                                       ret.add( j, tmp.get( i ) ) ;
+                                                       mt.add( j, MT ) ;
+                                                       
+                                                       ok = true ;
+                                                       break ;
+                                               }
+                                       }
+                                       
+                                       if( ! ok )
+                                       {
+                                               ret.add( tmp.get( i ) ) ;
+                                               mt.add( MT ) ;
+                                       }
+                               }
+                       }
+               }
+                       
+               return ret ;
+       }
+
+
+       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 ;
+                       
+                       for( int i = 0 ; i < sortedCluster.size() ; i++ )
+                       {
+                               /** If there is enough nodes ... **/
+                               if( sortedCluster.get( i ).getNbFreeNodes() >= minNode )
+                               {
+                                       max = 0 ;
+                                       
+                                       max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ;
+                                       
+                                       for( int j = 0 ; j < max ; j++ )
+                                       {
+                                               g = sortedCluster.get( i ).nextGNode() ;
+                                               ret.add( g ) ;
+                                               sortedCluster.get( i ).setGNodeStatus( g, true ) ;
+                                               
+                                               nbFound ++ ;
+                                               
+                                               if( nbFound >= _nbTask )
+                                                       break ;
+                                       }
+                               }
+                               
+                               if( nbFound >= _nbTask )
+                                       break ;
+                       }
+               }
+               
+               return ret ;
+       }
+
+
+       /**
+        * Sort clusters according to the heterogeneity degree of the platform and
+        * the eventual application's threshold. 
+        */
+       private void updateSortedClusters() 
+       {
+               if( gl != null )
+               {
+                       /** Purging the local list **/
+                       sortedCluster = null ;
+                       sortedCluster = new ArrayList<Cluster>() ;
+                       
+                       ArrayList<Double> calcMark = new ArrayList<Double>() ;
+                       
+                       hd = gl.getHeterogenityDegre() ;
+
+                       /** Sorting clusters **/
+                       ArrayList<Cluster> tmp = gl.getClusters() ;
+                       
+                       boolean ok ;
+                       
+                       double calcLoc = 0 ;
+                       double locP ;
+                       int N ;
+                       double P ;
+                       
+                       for( int i = 0 ; i < tmp.size() ; i++ )
+                       {
+                               N = tmp.get( i ).getNbFreeNodes() ;
+                               P = tmp.get( i ).getAvailablePower() ;
+                               locP = P / N ;
+                               
+                               /** The magic formula :P **/
+                               calcLoc = Math.sqrt( locP * Math.pow((1.5 * hd + 0.3), 2) +
+                                                N * Math.pow((1.1 - hd), 2 ) ) ;
+                               
+                               ok = false ;
+                               
+                               if( sortedCluster.size() == 0 )
+                               {
+                                       sortedCluster.add( tmp.get( i ) ) ;
+                                       calcMark.add( calcLoc ) ;
+                               } else {
+                                       
+                                       for( int j = 0 ; j < sortedCluster.size() ; j++ )
+                                       {
+                                               if( calcLoc > calcMark.get( j ) )
+                                               {
+                                                       sortedCluster.add( j, tmp.get( i ) ) ;
+                                                       calcMark.add( j, calcLoc ) ;
+                                                       ok = true ;
+                                                       break ;
+                                               }
+                                       }
+                                       
+                                       if( ! ok )
+                                       {
+                                               sortedCluster.add( tmp.get( i ) ) ;
+                                               calcMark.add( calcLoc ) ;
+                                       }
+                               }
+                       }
+               }
+       }
+
+
+       @Override
+       public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag ) 
+       {
+               GNode ret = null ;      
+               
+               /** If something has to be done **/
+               if( _dead != null )
+               {
+                       boolean ok = false ;
+                       /** Any place on the same cluster ? **/
+                       for( int i = 0 ; i < gl.getNbCluster() ; i++ )
+                       {
+                               Cluster cl = null ;
+                               
+                               int id = gl.getClusterOfNode( _dead ) ;
+                               
+                               if( id != -1 )
+                               {
+                                       cl = gl.getClusters().get(id) ;
+                                       
+                                       if( cl.getNbFreeNodes() > 0 )
+                                       {
+                                               ret = cl.nextGNode() ;
+                                               ok = true ;
+                                       }
+                               } else {
+                                       System.err.println( "Cluster not found!" ) ;
+                               }
+                       }
+                       
+                       /** If there is no more place, try other clusters **/
+                       if( ! ok )
+                       {
+                               updateSortedClusters() ;
+                               
+                               for( int i = 0 ; i < sortedCluster.size() ; i++ )
+                               {
+                                       if( sortedCluster.get( i ).getNbFreeNodes() > 0 )
+                                       {
+                                               ret = sortedCluster.get( i ).nextGNode() ;
+                                               ok = true ;
+                                               break ;
+                                       }
+                               }
+                       }
+                       
+                       nb_fault++ ;
+               }
+               
+               return ret ;
+       }
+       
+       
+       @Override
+       public GNode getOtherGNode( ArrayList<GNode> _ag ) 
+       {
+               GNode ret = null ;      
+               
+               /** Searching the cluster which has the more free nodes **/
+               int pos = -1, max = 0, cur = 0 ;
+               for( int i = 0 ; i < gl.getNbCluster() ; i++ )
+               {
+                       cur = gl.getClusters().get( i ).getNbFreeNodes() ;
+                       if( cur > max)
+                       {
+                               pos = i ;
+                               max = cur ;
+                       }
+               }
+
+               ret = gl.getClusters().get( pos ).nextGNode() ;
+               
+               return ret ;
+       }
+       
+}
+
+/** La programmation est un art, respectons ceux qui la pratiquent !! **/
index 9429df4..e8320c4 100644 (file)
@@ -16,6 +16,7 @@ public class Mapping implements Serializable
        /* Two kinds of Mapping, according to algorithms' goal */
        private ArrayList<Association> mapping ;
        private ArrayList<Association> mapping2 ;
+       private ArrayList<GNode> other ;
        private int type ; // 0 : mapping task/node ; 1 : mapping tasks/cluster
        
        
@@ -26,6 +27,7 @@ public class Mapping implements Serializable
        {
                mapping = new ArrayList<Association>() ;
                mapping2 = new ArrayList<Association>() ;
+               other = new ArrayList<GNode>() ;
                type = -1 ;
        }
        
@@ -37,6 +39,7 @@ public class Mapping implements Serializable
        {
                mapping = new ArrayList<Association>() ;
                mapping2 = new ArrayList<Association>() ;
+               other = new ArrayList<GNode>() ;
                type = -1 ;
        }
        
@@ -62,7 +65,7 @@ public class Mapping implements Serializable
                GNode tmp = null ;
                for( int i = 0 ; i < at.size() ; i++ )
                {
-                       tmp = c.nextGNode() ;
+                       tmp = c.moreGNode() ;
                        if( tmp != null )
                        {
                                insertMapping( new Association( tmp, at.get( i ) ) ) ;
@@ -100,15 +103,79 @@ public class Mapping implements Serializable
        {
                if( _a != null && _a.getGNode() != null && _a.getGTask() != null )
                {
-//                     int ind = _a.getGTask().getNum() ;
-//                     
-//                     mapping.add( ind - 1, _a ) ;
                        mapping.add( _a ) ;
                }
        }
        
        
        /**
+        * Determine if a node is used as an other node in the mapping.
+        * @param _g The node to search
+        * @return The position of the node
+        */
+       private int searchOther( GNode _g )
+       {
+               int pos = -1 ;
+               
+               if( _g != null )
+               {
+                       for( int i = 0 ; i < other.size() ; i++ )
+                       {
+                               if( _g.getId() == other.get( i ).getId() ) 
+                               {
+                                       pos = i ;
+                                       break ;
+                               }
+                       }
+               }
+               
+               return pos ;
+       }
+       
+       
+       /**
+        * Add a new node in the other nodes list.
+        * @param _g The other node
+        */
+       public void addOtherNode( GNode _g )
+       {
+               if( _g != null )
+               {
+                       int pos = searchOther( _g ) ;
+                       
+                       if( pos != -1 )
+                       {
+                               other.add( _g ) ;
+                       } else {
+                               System.out.println( "This node already exist in OtherNodes! " +
+                                               "I replace it" ) ;
+                               other.set( pos, _g ) ;
+                       }
+               }
+       }
+       
+       
+       /**
+        * Remove a node in the other nodes list.
+        * @param _g The node to be removed
+        */
+       public void removeOtherNode( GNode _g )
+       {
+               if( _g != null )
+               {
+                       int pos = searchOther( _g ) ;
+                       
+                       if( pos != -1 )
+                       {
+                               other.remove( pos ) ;
+                       } else {
+                               System.err.println( "This node does not exist in OtherNodes!" ) ;
+                       }
+               }
+       }
+       
+       
+       /**
         * Remove a failed node from the mapping.
         * @param _deadNode The failed node
         * @return The task associated with the failed node
@@ -139,59 +206,30 @@ public class Mapping implements Serializable
        public ArrayList<GNode> getMappedGNodes()
        {
                ArrayList<GNode> ar = new ArrayList<GNode>() ;
-               
+
                if( mapping.size() != 0 )
                {
-//                     if( type == 0 )
-//                     {
-//                             ArrayList<Association> tmp = (ArrayList<Association>) mapping.clone() ;
-                       
-                               for( int i = 0 ; i < mapping.size() ; i++ )
-                               {
-//                                     for( int j = 0 ; j < tmp.size() ; j++ )
-//                                     {
-//                                             if( tmp.get( j ).getGTask().getNum() == i )
-//                                             {
-                                                       ar.add( mapping.get( i ).getGNode() ) ;
-//                                                     tmp.remove( j ) ;
-//                                                     j = tmp.size() + 2 ;
-//                                             }
-//                                     }
-                               }
-//                     }
-//                     
-//                     if( type == 1 )
-//                     {
-//                             ArrayList<Association> tmp = (ArrayList<Association>) mapping2.clone() ;
-//                             
-//                             for( int i = 0 ; i < mapping2.size() ; i++ )
-//                             {
-//                                     for( int j = 0 ; j < tmp.size() ; j++ )
-//                                     {
-//                                             if( tmp.get( j ).getGTask().getNum() == i )
-//                                             {
-//                                                     ar.add( tmp.get( j ).getGNode() ) ;
-//                                                     tmp.remove( j ) ;
-//                                                     j = tmp.size() + 2 ;
-//                                             }
-//                                     }
-//                             }
-//                     }
+                       for( int i = 0 ; i < mapping.size() ; i++ )
+                       {
+                               ar.add( mapping.get( i ).getGNode() ) ;
+                       }
                }
-               
+
                return ar ;
        }
-       
+
        
        /**
         * Print the status of the mapping done, according to its type.
         */
-       public void print()
+       public void print( int _type )
        {
+               int type_print = _type ;
+               
                System.out.println();
                System.out.println( "\t=> Mapping done:\n" ) ;
                
-               if( type == 0 )
+               if( type_print == 0 )
                {
                        ArrayList<GNode> ar = getMappedGNodes() ;
                        
@@ -203,7 +241,7 @@ public class Mapping implements Serializable
                        System.out.println() ;
                }
                
-               if( type == 1 )
+               if( type_print == 1 )
                {
                        for( int i = 0 ; i < mapping2.size() ; i++ )
                        {
@@ -258,6 +296,59 @@ public class Mapping implements Serializable
        
        
        /**
+        * Return the association of the given position.
+        * @param _id The position of the Association
+        * @return The Association requested
+        */
+       public Association getAssociation( int _id ) 
+       {
+               if( _id >= 0 && _id < mapping.size() )
+               {
+                       return mapping.get( _id ) ;
+               } else { 
+                       return null ;
+               }
+       }
+       
+       
+       /**
+        * Remove the association of the given position.
+        * @param _id The position of the Association
+        * @return The Association removed
+        */
+       public Association removeAssociation( int _id )
+       {
+               if( _id >= 0 && _id < mapping.size() )
+               {
+                       return mapping.remove( _id ) ;
+               } else {
+                       return null ;
+               }
+       }
+       
+       /**
+        * Return the position of the association containing 
+        * the GTask of a specified rank.
+        * @param _taskRank The rank of the task
+        * @return The position of the association
+        */
+       public int getIdOfAssociation( int _taskRank )
+       {
+               int ret = -1 ;
+               
+               for( int i = 0 ; i < mapping.size() ; i++ )
+               {
+                       if( mapping.get( i ).getGTask().getNum() == _taskRank )
+                       {
+                               ret = i ;
+                               break ;
+                       }
+               }
+               
+               return ret ;
+       }
+       
+       /**
         * Return the amount of external tasks dependencies, in cluster point of view.
         * @return The amount of external dependencies
         */
index 3092a99..403b008 100644 (file)
@@ -5,7 +5,7 @@ import java.util.ArrayList;
 
 
 /**
- * Implementation of Simple Mapping algorithm
+ * Implementation of the Simple Mapping algorithm (no fault tolerance mechanism)
  * @author S&eacute;bastien Miqu&eacute;e
  * @version 1.0
  */
@@ -23,6 +23,7 @@ public class Simple extends Algo
        public Simple()
        {
                super() ;
+               name = "Simple" ;
        }
        
 
@@ -34,6 +35,8 @@ public class Simple extends Algo
        public Simple( Graph _gr, Grid _gd )
        {
                super( _gr, _gd ) ;
+               
+               name = "Simple" ;
        }
        
        /**
@@ -48,7 +51,7 @@ public class Simple extends Algo
                {
                        grn = new ArrayList<GNode>() ;
                        
-                       // Tri des clusters suivant leur taille
+                       // Sorting clusters according to their "size"
                    ArrayList<Cluster> cl = gl.getClusters() ;
                    ArrayList<Cluster> cl2 = new ArrayList<Cluster>() ;
                    
@@ -113,8 +116,6 @@ public class Simple extends Algo
                        System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
                }
                
-               /** Update in cluster the status of nodes **/
-               updateGrid() ;
        }
 
 
@@ -142,12 +143,11 @@ public class Simple extends Algo
                        } else {
                                System.err.println( "Not enought available nodes in gnodes to replace one !" ) ;
                                return null ;
-                       }               
+                       }       
+                       
+                       nb_fault++ ;
                }
                
-               /** Update in cluster the status of nodes **/
-               updateGrid() ;
-               
                return ret ;
        }
 
index a5ec4d2..068789d 100644 (file)
@@ -69,7 +69,19 @@ public class Utils
                        e.printStackTrace();
                        System.exit( 1 ) ;
                } 
+               
+               /* Host IP */
+               String ip = null ;
+               try {
+                       InetAddress addr = InetAddress.getLocalHost() ;
+                       ip = addr.getHostAddress() ;
+               } catch( final Exception e ) {
+                       System.err.println( "Unalbe to retrieve host's name !" ) ;
+                       e.printStackTrace();
+                       System.exit( 1 ) ;
+               } 
 
+               String names[] = decodeG5Knames( name ) ;
                
                /* Updating node information */
                n.setFrequency( frequency ) ;
@@ -77,6 +89,9 @@ public class Utils
                n.setMemory( memory ) ;
                n.setNb_cores( nbCore ) ;
                n.setName( name ) ;
+               n.setCluster( names[1] ) ;
+               n.setSite( names[2] ) ;
+               n.setIP( ip ) ;
                n.setMapped( false ) ;
                
                return n ;
@@ -194,7 +209,7 @@ public class Utils
                
                if ( ! _file.endsWith( ".xml" ) )
                {
-                       _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+                       _file = _file + ".xml"; // Adding xml extension to file
                }
                
                if( ! _file.equals( "" ) )
@@ -244,7 +259,7 @@ public class Utils
                
                if ( ! _file.endsWith( ".xml" ) )
                {
-                       _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+                       _file = _file + ".xml"; // Adding xml extension to file
                }
                
                if( ! _file.equals( "" ) )
@@ -295,7 +310,7 @@ public class Utils
                
                if ( ! _file.endsWith( ".xml" ) )
                {
-                       _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+                       _file = _file + ".xml"; // Adding xml extension to file
                }
                
                if( ! _file.equals( "" ) )
@@ -346,7 +361,7 @@ public class Utils
                
                if ( ! _file.endsWith( ".xml" ) )
                {
-                       _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+                       _file = _file + ".xml"; // Adding xml extension to file
                }
                
                String path = "" ;
@@ -394,7 +409,7 @@ public class Utils
                
                if ( ! _file.endsWith( ".xml" ) )
                {
-                       _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+                       _file = _file + ".xml"; // Adding xml extension to file
                }
 
                String path = "" ;
@@ -442,7 +457,7 @@ public class Utils
                
                if ( ! _file.endsWith( ".xml" ) )
                {
-                       _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier
+                       _file = _file + ".xml"; // Adding xml extension to file
                }
 
                String path = "" ;