Improvement of the Maheve algorithm.

[mapping.git] / src / and / Mapping / Maheve.java

diff --git a/src/and/Mapping/Maheve.java b/src/and/Mapping/Maheve.java
index 4a24142..c22bfc9 100644 (file)
--- a/src/and/Mapping/Maheve.java
+++ b/src/and/Mapping/Maheve.java
@@ -8,14 +8,14 @@ public class Maheve extends Algo
 {
        private static final long serialVersionUID = 1L;
 
-       private static final int minNode = 5 ;
-       private static final int nbSave = 2 ;
+       private static int minNode ;
+       private static int nbSave ;
        
        private double hd ;
        private ArrayList<Cluster> sortedCluster = null ;
        private ArrayList<GTask> tasks = null ;
        
-       
+               
        /**
         * Empty default constructor.
         */
@@ -23,6 +23,8 @@ public class Maheve extends Algo
        {
                super() ;
                name = "MAHEVE_2" ;
+               minNode = 5 ;
+               nbSave = 2 ;
                sortedCluster = new ArrayList<Cluster>() ;
        }
        
@@ -46,6 +48,57 @@ public class Maheve extends Algo
        }
        
        
+       /**
+        * Setter for the amount of nodes to preserve on each cluster
+        * for the fault tolerance (should be 0 in an environment without fault).
+        * @param _nbSave The amount of nodes to preserve
+        */
+       public void setNbSave( int _nbSave )
+       {
+               if( _nbSave >= 0 )
+               {
+                       nbSave = _nbSave ;
+               }
+       }
+       
+       
+       /**
+        * Getter to retrieving the amount of nodes preserved for fault tolerance.
+        * @return The amount of preserved nodes
+        */
+       public int getNbSave()
+       {
+               return nbSave ;
+       }
+       
+       
+       /**
+        * Setter for the minimum amount of nodes which should be present in
+        * a cluster to consider this latter in the mapping process.
+        * @param _minNode The minimum amount of nodes a cluster should have to be
+        * considered
+        */
+       public void setMinNode( int _minNode )
+       {
+               if( _minNode >= 0 )
+               {
+                       minNode = _minNode ;
+               }
+       }
+       
+       
+       /**
+        * Getter to retrieve the minimum amount of nodes a cluster should have
+        * to be considered in the mapping process.
+        * @return The minimum amount of nodes a cluster should have to be 
+        * considered
+        */
+       public int getMinNode()
+       {
+               return minNode ;
+       }
+       
+       
        @Override
        public void map() {
                /** If the mapping is possible ... **/
@@ -102,6 +155,8 @@ public class Maheve extends Algo
        {               
                ArrayList<GTask> l1 = sortTasks() ;
                
+               ArrayList<Integer> st = new ArrayList<Integer>() ;
+               
                if( l1 != null && l1.size() > 0 )
                {                       
                        ArrayList<GTask> l2 = new ArrayList<GTask>() ;
@@ -112,16 +167,18 @@ public class Maheve extends Algo
                                if( l2.size() == 0 )
                                {
                                        l2.add( l1.get( 0 ) ) ;
+                                       st.add( l1.get( 0 ).getNum() ) ;
                                }
                                
                                while( l2.size() > 0 )
                                {
                                        l1.remove( l2.get( 0 ) ) ;
-                                       tmp = addTask( l2.remove( 0 ), l1 ) ;
+                                       tmp = addTask( l2.remove( 0 ), l1, st ) ;
                                        
                                        for( int i = 0 ; i < tmp.size() ; i++ )
                                        {
                                                l2.add( tmp.get( i ) ) ;
+                                               st.add( tmp.get( i ).getNum() ) ;
                                        }
                                }
                        }
@@ -129,7 +186,8 @@ public class Maheve extends Algo
        }
        
        
-       private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar) 
+       private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar, 
+                                                                        ArrayList<Integer> _st )
        {
        
                ArrayList<GTask> ret = null ;
@@ -148,24 +206,33 @@ public class Maheve extends Algo
                        
                        ArrayList<Integer> dep = new ArrayList<Integer>() ;
                        
+                       // ** Retrieving dependencies and eliminating tasks already treated 
+                       // ** or in instance to be treated. **//
                        for( int i = 0 ; i < _gt.getDependencies().size() ; i++ )
                        {
-                               dep.add( _gt.getDependencies().get( i ).getNum() ) ;
+                               if( ! _st.contains( _gt.getDependencies().get( i ).getNum() ) )
+                               {
+                                       dep.add( _gt.getDependencies().get( i ).getNum() ) ;
+                               }
                        }
                        
+
+                       // ** Searching dependencies in sorted tasks list ** //
                        for( int i = 0 ; i < _ar.size() ; i++ )
                        {
                                num = _ar.get( i ).getNum() ;
                                
-                               for( int j = 0 ; j < dep.size() ; j++ )
+                               if( dep.contains( num ) ) 
                                {
-                                       if( num == dep.get( j ) )
-                                       {
+//                             for( int j = 0 ; j < dep.size() ; j++ )
+//                             {
+//                                     if( num == dep.get( j ) )
+//                                     {
                                                ret.add( _ar.remove( i ) ) ;
                                                cmpt++ ;
-                                               dep.remove( j ) ;
-                                               break ;
-                                       }
+//                                             dep.remove( j ) ;
+//                                             break ;
+//                                     }
                                }
                                
                                if( cmpt == nbDep )
@@ -243,31 +310,49 @@ public class Maheve extends Algo
                        int nbFound = 0 ;
                        int max = 0 ;
                        GNode g = null ;
+                       boolean changeParameter = false ;
                        
-                       for( int i = 0 ; i < sortedCluster.size() ; i++ )
+                       while( nbFound < _nbTask )
                        {
-                               /** If there is enough nodes ... **/
-                               if( sortedCluster.get( i ).getNbFreeNodes() >= minNode )
+                               int i = 0 ;
+                               
+                               for( i = 0 ; i < sortedCluster.size() ; i++ )
                                {
-                                       max = 0 ;
+                                       /** If there is enough nodes ... **/
+                                       if( sortedCluster.get( i ).getNbFreeNodes() >= minNode )
+                                       {
+                                               max = 0 ;
+                                               sortedCluster.get( i ).initMoreGNode() ;
                                        
-                                       max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ;
+                                               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 ) ;
+                                               for( int j = 0 ; j < max ; j++ )
+                                               {
+                                                       g = sortedCluster.get( i ).moreGNode() ;
+                                                       ret.add( g ) ;
                                                
-                                               nbFound ++ ;
+                                                       nbFound ++ ;
                                                
-                                               if( nbFound >= _nbTask )
-                                                       break ;
+                                                       if( nbFound >= _nbTask )
+                                                               break ;
+                                               }
                                        }
+                               
+                                       if( nbFound >= _nbTask )
+                                               break ;
                                }
                                
-                               if( nbFound >= _nbTask )
-                                       break ;
+                               if( i == sortedCluster.size() && nbFound < _nbTask )
+                               {
+                                       changeParameter = true ;
+                                       minNode-- ;
+                               }
+                       }
+                       
+                       if( changeParameter )
+                       {
+                               System.err.println( "The parameter \"minNode\" has been reduced " +
+                                               "to allow the mapping process to be done." ) ;
                        }
                }
                
@@ -297,19 +382,25 @@ public class Maheve extends Algo
                        boolean ok ;
                        
                        double calcLoc = 0 ;
-                       double locP ;
-                       int N ;
-                       double P ;
+                       double normN ;
+                       double normP ;
+                       
+                       double Nm = 0, Pm = 0 ;
+                       
+                       for( int i = 0 ; i < tmp.size() ; i++ )
+                       {
+                               Nm += tmp.get( i ).getNbFreeNodes() ;
+                               Pm += tmp.get( i ).getAvgAvailablePower() ;
+                       }
                        
                        for( int i = 0 ; i < tmp.size() ; i++ )
                        {
-                               N = tmp.get( i ).getNbFreeNodes() ;
-                               P = tmp.get( i ).getAvailablePower() ;
-                               locP = P / N ;
+                               normN = tmp.get( i ).getNbFreeNodes() * 100 / Nm ;
+                               normP = tmp.get( i ).getAvgAvailablePower() * 100 / Pm ;
                                
                                /** The magic formula :P **/
-                               calcLoc = Math.sqrt( locP * Math.pow((1.5 * hd + 0.3), 2) +
-                                                N * Math.pow((1.1 - hd), 2 ) ) ;
+                               calcLoc = Math.sqrt( Math.pow( (normP * hd), 2) +
+                                                 Math.pow( (normN *(1 - hd)), 2 ) ) ;
                                
                                ok = false ;