Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
a8f04723b102b5be56e8b3319123b5875d1fa440
[mapping.git] / src / and / Mapping / Maheve.java
1 package and.Mapping;
2
3 import java.util.ArrayList;
4
5
6
7 public class Maheve extends Algo
8 {
9         private static final long serialVersionUID = 1L;
10
11         private static final int minNode = 5 ;
12         private static final int nbSave = 2 ;
13         
14         private double hd ;
15         private ArrayList<Cluster> sortedCluster = null ;
16         private ArrayList<GTask> tasks = null ;
17         
18                 
19         /**
20          * Empty default constructor.
21          */
22         public Maheve()
23         {
24                 super() ;
25                 name = "MAHEVE_2" ;
26                 sortedCluster = new ArrayList<Cluster>() ;
27         }
28         
29         
30         /**
31          * Constructor of this algorithm, which takes into parameter
32          * the application graph, the grid architecture, and the correction
33          * parameter which indicates the threshold of the heterogeneity degree.
34          * @param _gr The application graph
35          * @param _gl The grid architecture
36          * @param _threshold The heterogeneity threshold
37          */
38         public Maheve( Graph _gr, Grid _gl )
39         {
40                 super( _gr, _gl ) ;
41                 
42                 hd = 0 ;
43                 sortedCluster = new ArrayList<Cluster>() ;
44                 tasks = new ArrayList<GTask>() ;
45                 name = "MAHEVE_2" ;
46         }
47         
48         
49         @Override
50         public void map() {
51                 /** If the mapping is possible ... **/
52                 if( ( gr != null ) && ( gr.getNbGTask() <= gl.getNbGNode() ) )
53                 {
54                         System.out.println( "******************************************" ) ;
55                         System.out.println( "* Launching the MAHEVE Mapping algorithm *" ) ;
56                         System.out.println( "******************************************\n\n" ) ;
57                         
58                         /** Local variables **/
59                         ArrayList<GNode> used = null ;
60                         
61                         /** Initialization of heterogeneity degree **/
62                         hd = gl.getHeterogenityDegre() ;
63                         
64                         
65                         /** Ordering clusters according to their real power **/
66                         updateSortedClusters() ;
67                 
68                         /** Searching the corresponding nodes **/
69                         used = searchNodes( gr.getNbGTask() ) ;
70                         
71                         if( used == null || used.size() == 0 )
72                         {
73                                 System.err.println( "No node returned!" ) ;
74                                 return ;
75                         }
76                 
77                         
78                         /** Ordering tasks **/
79                         orderTasks() ;
80                         
81                         if( tasks == null || tasks.size() == 0 )
82                         {
83                                 System.err.println( "Unable to retrieve tasks to be mapped on!" ) ;
84                                 return ;
85                         }
86                         
87                         
88                         /** Save the Mapping **/
89                         for( int i = 0 ; i < tasks.size() ; i++ )
90                         {
91                                 mp.addMapping( new Association( used.get( i ), tasks.get( i ) ) ) ;
92                         }
93                 
94                 } else {
95                         System.err.println( "\n\n!!! Unable to map application!\n\n" ) ;
96                         return ;
97                 }
98         }
99
100         
101         private void orderTasks()
102         {               
103                 ArrayList<GTask> l1 = sortTasks() ;
104                 
105                 ArrayList<Integer> st = new ArrayList<Integer>() ;
106                 
107                 if( l1 != null && l1.size() > 0 )
108                 {                       
109                         ArrayList<GTask> l2 = new ArrayList<GTask>() ;
110                         ArrayList<GTask> tmp = new ArrayList<GTask>() ;
111                         
112                         while( l1.size() > 0 )
113                         {
114                                 if( l2.size() == 0 )
115                                 {
116                                         l2.add( l1.get( 0 ) ) ;
117                                         st.add( l1.get( 0 ).getNum() ) ;
118                                 }
119                                 
120                                 while( l2.size() > 0 )
121                                 {
122                                         l1.remove( l2.get( 0 ) ) ;
123                                         tmp = addTask( l2.remove( 0 ), l1, st ) ;
124                                         
125                                         for( int i = 0 ; i < tmp.size() ; i++ )
126                                         {
127                                                 l2.add( tmp.get( i ) ) ;
128                                                 st.add( tmp.get( i ).getNum() ) ;
129                                         }
130                                 }
131                         }
132                 }
133         }
134         
135         
136         private ArrayList<GTask> addTask(GTask _gt, ArrayList<GTask> _ar, 
137                                                                          ArrayList<Integer> _st )
138         {
139         
140                 ArrayList<GTask> ret = null ;
141                 
142                 if( _gt != null && _ar != null )
143                 {
144                         ret = new ArrayList<GTask>() ;
145                         
146                         // ** Adding the task in the main list ** //
147                         tasks.add( _gt ) ;
148                         
149                         // ** Searching its dependencies ** //
150                         int nbDep = (int) (_gt.getNbDep() * (1.0 - hd)) ;
151                         int cmpt = 0 ;
152                         int num = 0 ;
153                         
154                         ArrayList<Integer> dep = new ArrayList<Integer>() ;
155                         
156                         // ** Retrieving dependencies and eliminating tasks already treated 
157                         // ** or in instance to be treated. **//
158                         for( int i = 0 ; i < _gt.getDependencies().size() ; i++ )
159                         {
160                                 if( ! _st.contains( _gt.getDependencies().get( i ).getNum() ) )
161                                 {
162                                         dep.add( _gt.getDependencies().get( i ).getNum() ) ;
163                                 }
164                         }
165                         
166
167                         // ** Searching dependencies in sorted tasks list ** //
168                         for( int i = 0 ; i < _ar.size() ; i++ )
169                         {
170                                 num = _ar.get( i ).getNum() ;
171                                 
172                                 if( dep.contains( num ) ) 
173                                 {
174 //                              for( int j = 0 ; j < dep.size() ; j++ )
175 //                              {
176 //                                      if( num == dep.get( j ) )
177 //                                      {
178                                                 ret.add( _ar.remove( i ) ) ;
179                                                 cmpt++ ;
180 //                                              dep.remove( j ) ;
181 //                                              break ;
182 //                                      }
183                                 }
184                                 
185                                 if( cmpt == nbDep )
186                                 {
187                                         break ;
188                                 }
189                         }
190                 }
191                 
192                 return ret;
193         }
194
195
196         private ArrayList<GTask> sortTasks()
197         {
198                 ArrayList<GTask> ret = null ;
199                 
200                 ArrayList<GTask> tmp = gr.getGraph() ;
201                 
202                 if( tmp != null && tmp.size() > 0 )
203                 {
204                         ret = new ArrayList<GTask>() ;
205                         
206                         ArrayList<Double> mt = new ArrayList<Double>() ;
207                         
208                         double W, D, MT ;
209                         boolean ok = false ;
210                         
211                         for( int i = 0 ; i < tmp.size() ; i++ )
212                         {
213                                 W = tmp.get( i ).getWeight() ;
214                                 D = tmp.get( i ).getNbDep() ;
215                                 
216                                 ok = false ;
217                                 
218                                 MT = Math.pow( W, hd ) * Math.pow( D, ( 1.0 - hd) ) ;
219                                 
220                                 if( ret.size() == 0 )
221                                 {
222                                         ret.add( tmp.get( i ) ) ;
223                                         mt.add( MT ) ;
224                                 } else {
225                                         for( int j = 0 ; j < ret.size() ; j++ )
226                                         {
227                                                 if( MT > mt.get( j ) )
228                                                 {
229                                                         ret.add( j, tmp.get( i ) ) ;
230                                                         mt.add( j, MT ) ;
231                                                         
232                                                         ok = true ;
233                                                         break ;
234                                                 }
235                                         }
236                                         
237                                         if( ! ok )
238                                         {
239                                                 ret.add( tmp.get( i ) ) ;
240                                                 mt.add( MT ) ;
241                                         }
242                                 }
243                         }
244                 }
245                         
246                 return ret ;
247         }
248
249
250         private ArrayList<GNode> searchNodes( int _nbTask ) 
251         {
252                 ArrayList<GNode> ret = null ;
253                 
254                 if( _nbTask > 0 )
255                 {
256                         ret = new ArrayList<GNode>() ;
257                         int nbFound = 0 ;
258                         int max = 0 ;
259                         GNode g = null ;
260                         
261                         for( int i = 0 ; i < sortedCluster.size() ; i++ )
262                         {
263                                 /** If there is enough nodes ... **/
264                                 if( sortedCluster.get( i ).getNbFreeNodes() >= minNode )
265                                 {
266                                         max = 0 ;
267                                         sortedCluster.get( i ).initMoreGNode() ;
268                                         
269                                         max = sortedCluster.get( i ).getNbFreeNodes() - nbSave ;
270                                         
271                                         for( int j = 0 ; j < max ; j++ )
272                                         {
273                                                 g = sortedCluster.get( i ).moreGNode() ;
274                                                 ret.add( g ) ;
275                                                 
276                                                 nbFound ++ ;
277                                                 
278                                                 if( nbFound >= _nbTask )
279                                                         break ;
280                                         }
281                                 }
282                                 
283                                 if( nbFound >= _nbTask )
284                                         break ;
285                         }
286                 }
287                 
288                 return ret ;
289         }
290
291
292         /**
293          * Sort clusters according to the heterogeneity degree of the platform and
294          * the eventual application's threshold. 
295          */
296         private void updateSortedClusters() 
297         {
298                 if( gl != null )
299                 {
300                         /** Purging the local list **/
301                         sortedCluster = null ;
302                         sortedCluster = new ArrayList<Cluster>() ;
303                         
304                         ArrayList<Double> calcMark = new ArrayList<Double>() ;
305                         
306                         hd = gl.getHeterogenityDegre() ;
307
308                         /** Sorting clusters **/
309                         ArrayList<Cluster> tmp = gl.getClusters() ;
310                         
311                         boolean ok ;
312                         
313                         double calcLoc = 0 ;
314                         double normN ;
315                         double normP ;
316                         
317                         double Nm = 0, Pm = 0 ;
318                         
319                         for( int i = 0 ; i < tmp.size() ; i++ )
320                         {
321                                 Nm += tmp.get( i ).getNbFreeNodes() ;
322                                 Pm += tmp.get( i ).getAvgAvailablePower() ;
323                         }
324                         
325                         for( int i = 0 ; i < tmp.size() ; i++ )
326                         {
327                                 normN = tmp.get( i ).getNbFreeNodes() * 100 / Nm ;
328                                 normP = tmp.get( i ).getAvgAvailablePower() * 100 / Pm ;
329                                 
330                                 /** The magic formula :P **/
331                                 calcLoc = Math.sqrt( Math.pow( (normP * hd), 2) +
332                                                   Math.pow( (normN *(1 - hd)), 2 ) ) ;
333                                 
334                                 ok = false ;
335                                 
336                                 if( sortedCluster.size() == 0 )
337                                 {
338                                         sortedCluster.add( tmp.get( i ) ) ;
339                                         calcMark.add( calcLoc ) ;
340                                 } else {
341                                         
342                                         for( int j = 0 ; j < sortedCluster.size() ; j++ )
343                                         {
344                                                 if( calcLoc > calcMark.get( j ) )
345                                                 {
346                                                         sortedCluster.add( j, tmp.get( i ) ) ;
347                                                         calcMark.add( j, calcLoc ) ;
348                                                         ok = true ;
349                                                         break ;
350                                                 }
351                                         }
352                                         
353                                         if( ! ok )
354                                         {
355                                                 sortedCluster.add( tmp.get( i ) ) ;
356                                                 calcMark.add( calcLoc ) ;
357                                         }
358                                 }
359                         }
360                 }
361         }
362
363
364         @Override
365         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag ) 
366         {
367                 GNode ret = null ;      
368                 
369                 /** If something has to be done **/
370                 if( _dead != null )
371                 {
372                         boolean ok = false ;
373                         /** Any place on the same cluster ? **/
374                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
375                         {
376                                 Cluster cl = null ;
377                                 
378                                 int id = gl.getClusterOfNode( _dead ) ;
379                                 
380                                 if( id != -1 )
381                                 {
382                                         cl = gl.getClusters().get(id) ;
383                                         
384                                         if( cl.getNbFreeNodes() > 0 )
385                                         {
386                                                 ret = cl.nextGNode() ;
387                                                 ok = true ;
388                                         }
389                                 } else {
390                                         System.err.println( "Cluster not found!" ) ;
391                                 }
392                         }
393                         
394                         /** If there is no more place, try other clusters **/
395                         if( ! ok )
396                         {
397                                 updateSortedClusters() ;
398                                 
399                                 for( int i = 0 ; i < sortedCluster.size() ; i++ )
400                                 {
401                                         if( sortedCluster.get( i ).getNbFreeNodes() > 0 )
402                                         {
403                                                 ret = sortedCluster.get( i ).nextGNode() ;
404                                                 ok = true ;
405                                                 break ;
406                                         }
407                                 }
408                         }
409                         
410                         nb_fault++ ;
411                 }
412                 
413                 return ret ;
414         }
415         
416         
417         @Override
418         public GNode getOtherGNode( ArrayList<GNode> _ag ) 
419         {
420                 GNode ret = null ;      
421                 
422                 /** Searching the cluster which has the more free nodes **/
423                 int pos = -1, max = 0, cur = 0 ;
424                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
425                 {
426                         cur = gl.getClusters().get( i ).getNbFreeNodes() ;
427                         if( cur > max)
428                         {
429                                 pos = i ;
430                                 max = cur ;
431                         }
432                 }
433
434                 ret = gl.getClusters().get( pos ).nextGNode() ;
435                 
436                 return ret ;
437         }
438         
439 }
440
441 /** La programmation est un art, respectons ceux qui la pratiquent !! **/