Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
c193bc8ee0e2c8b2ddf1a042b405048b10e594ab
[mapping.git] / src / and / Mapping / LSM.java
1 package and.Mapping ;
2
3
4 import java.util.ArrayList;
5
6
7
8
9 /**
10  * Mapping algorithm based on the Edge-Cut principles
11  * @author Sébastien Miquée
12  *
13  */
14 public class LSM extends Algo
15 {
16         private static final long serialVersionUID = 1L;
17         
18         
19         private ArrayList<GTask> atraiter ;
20         private ArrayList<GTask> encours ;
21         private ArrayList<GTask> fait ;
22 //      private Architecture archi ;
23         private ArrayList<Architecture> liste_archi ;
24         private double dep_min ;
25         ArrayList<GTask> mappees ;
26         
27         
28         /**
29          * Default constructor.
30          */
31         public LSM()
32         {
33                 super() ;
34                 
35                 atraiter = new ArrayList<GTask>() ;
36                 encours = new ArrayList<GTask>() ;
37                 fait = new ArrayList<GTask>() ;
38 //              archi = new Architecture() ;
39                 liste_archi = new ArrayList<Architecture>() ;
40                 dep_min = 0 ;
41                 mappees = null ;
42         }
43         
44         
45         /**
46          * Constructor.
47          * @param _gr Application graph to be mapped on
48          * @param _gl Grid graph
49          */
50         public LSM( Graph _gr, Grid _gl )
51         {
52                 super( _gr, _gl ) ;
53                 
54                 atraiter = new ArrayList<GTask>() ;
55                 encours = new ArrayList<GTask>() ;
56                 fait = new ArrayList<GTask>() ;
57 //              archi = new Architecture() ;
58                 liste_archi = new ArrayList<Architecture>() ;
59                 dep_min = 0 ;
60                 mappees = null ;
61         }
62         
63         
64         /**
65          * Constructor.
66          * @param _gr Application graph to be mapped on
67          * @param _gl Grid graph
68          * @param _dep_min Minimum amount of local dependencies
69          */
70         public LSM( Graph _gr, Grid _gl, double _dep_min )
71         {
72                 super( _gr, _gl ) ;
73                 
74                 atraiter = new ArrayList<GTask>() ;
75                 encours = new ArrayList<GTask>() ;
76                 fait = new ArrayList<GTask>() ;
77 //              archi = new Architecture() ;
78                 liste_archi = new ArrayList<Architecture>() ;
79                 dep_min = _dep_min ;
80                 mappees = null ;
81         }
82         
83         
84         @SuppressWarnings("unchecked")
85         @Override
86         public void map() 
87         {
88                 System.out.println( "***********************************" ) ;
89                 System.out.println( "* Launching the Edge-Cuts Mapping *" ) ;
90                 System.out.println( "***********************************\n\n" ) ;
91
92                 /* Si le mapping est possible ... */
93                 if( gr.getNbGTask() <= gl.getNbGNode() )
94                 {
95                         atraiter = (ArrayList<GTask>) gr.getGraph().clone() ;
96                         
97                         liste_archi = construireArchi( gl, gr.getNbGTask() ) ;
98                         
99                         tri_dep() ;
100                         
101                         int indice = -1 ;
102                         int nb_ok = 0 ;
103                         double places = 0 ;
104                         double dep = -1 ;
105                         
106 //                      double moy = gr.getAverageDep() ;
107                         GTask tmp = null ;
108                         Cluster cl = null ;
109
110                         boolean change_cluster = false ;
111                         
112 //                      System.out.println("nb cluster : "+liste_archi.get(0).getNbClusters() );
113                         
114
115                         while( nb_ok < gr.getNbGTask() )
116                         {                               
117                                 if( places == 0 || change_cluster )
118                                 {
119                                         if( change_cluster )
120                                         {
121                                                 // Ajout du mapping
122                                                 mp.addMapping( cl, mappees ) ;
123                                         }
124                                         
125                                         if( nb_ok < gr.getNbGTask() )
126                                         {
127                                                 // Changement de cluster
128                                                 indice ++ ;
129                                                 
130                                                 if( indice == liste_archi.get(0).getNbClusters() )
131                                                 {
132                                                         System.out.println( "No more cluster !! Impossible to respect constrains !! " ) ;
133                                                         //System.exit( 2 ) ;
134                                                         mp.initMapping() ;
135                                                         return ;
136                                                 }
137                                                 
138                                                 cl = null ;
139                                                 cl = liste_archi.get(0).getArchi().get( indice ) ;
140                                                 places = cl.getNbGNode() ;
141                                                 change_cluster = false ;
142                                                 mappees = null ;
143                                                 mappees = new ArrayList<GTask>() ;
144                                         }
145                                 }
146                                 
147                                 if( ( atraiter.size() + encours.size() ) <= places )
148                                 {
149                                         for( int i = 0 ; i < atraiter.size() ; i++ )
150                                         {
151                                                 mappees.add( atraiter.get( i ) ) ;
152                                                 nb_ok++ ;
153                                                 places-- ;
154                                         }
155                                         
156                                         for( int i = 0 ; i < encours.size() ; i++ )
157                                         {
158                                                 mappees.add( encours.get( i ) ) ;
159                                                 nb_ok++ ;
160                                                 places-- ;
161                                         }
162                                         
163                                         atraiter = null ;
164                                         encours = null ;
165                                         
166                                         atraiter = new ArrayList<GTask>() ;
167                                         encours = new ArrayList<GTask>() ;
168                                         
169                                         mp.addMapping( cl, mappees ) ;
170                                 }
171                                 
172                                 if( encours.size() == 0 && atraiter.size() > 0 )
173                                 {
174                                         encours.add( atraiter.get(0) ) ;
175                                 }
176                                 
177                                 if( encours.size() > 0 ) 
178                                 {
179                                         tmp = encours.get( 0 ) ;
180                                 }
181                                 
182                                 
183 //                              if( ( calc_dep( tmp )* dep_min * moy ) <= places && places > 0 )
184                                 dep = calc_dep( tmp ) ;
185                                 
186                                 if( dep != -1 && 1 + ( dep * dep_min ) <= places && places > 0 )
187                                 {
188                                         places -- ;
189                                         nb_ok ++ ;
190                                         
191                                         ajoutDep( tmp ) ;
192                                         
193                                         mappees.add( tmp ) ;
194                                         fait.add( tmp ) ;
195                                         
196                                         atraiter.remove( tmp ) ;
197                                         encours.remove( tmp ) ;
198                                 } else {
199                                         change_cluster = true ;
200                                 }
201                                 
202                                 if( places == 0 )
203                                 {
204                                         change_cluster = true ;
205                                 }
206                                 
207                                 tmp = null ;
208                                 
209 //                              try {
210 //                                      Thread.sleep( 1000 ) ;
211 //                              } catch( InterruptedException e ) {
212 //                                      e.printStackTrace() ;
213 //                              }
214 //                              
215 //                              mp.affiche() ;
216 //                              System.out.println( "reste : " + places + " sur " + cl.getNom() ) ;
217 //                              System.out.println( "nb_ok = " +nb_ok);
218 //                              System.out.println("etat : "+encours);
219 //                              System.out.println("etat2 : "+mappees);
220 //                              System.out.println( "etat3 : "+atraiter);
221                         }
222                         
223                 
224                 } else {
225                         System.out.println( "\n\n!!! Mapping impossible ! There are more tasks than nodes !!!\n" ) ;
226                 }
227                 
228                 /** Update in cluster the status of nodes **/
229                 updateGrid() ;
230         }
231         
232         /**
233          * 
234          * @param _t
235          */
236         private void ajoutDep( GTask _t ) 
237         {
238                 if( _t != null )
239                 {
240                         GTask tmp = null ;
241                         
242                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
243                         {
244                                 tmp = _t.getDependencies().get( i ) ;
245                                 
246                                 if( ! fait.contains( tmp ) && ! encours.contains( tmp ) 
247                                                 && tmp.getNbDep() < _t.getNbDep() )
248                                 {
249 //                                      System.out.println("haha => "+tmp.getNum() ) ;
250                                         int j = 0 ;
251                                         for( j = 0 ; j < encours.size() ; j++ )
252                                         {
253                                                 if( tmp.getNbDep() < encours.get( j ).getNbDep() )
254                                                 {
255                                                         encours.add( j, tmp ) ;
256                                                         j = encours.size() + 10 ;
257                                                 }
258                                         }
259                                         
260                                         if( j == encours.size() )
261                                         {
262                                                 encours.add( tmp ) ;
263                                         }
264                                         
265                                         atraiter.remove( tmp ) ;
266                                         
267                                         tmp = null ;
268                                 }
269                         }
270                 }
271         }
272
273         
274         /**
275          * 
276          * @param _t
277          * @return
278          */
279         private double calc_dep( GTask _t ) 
280         {
281                 int dep = 0 ;
282                 int ext = 0 ;
283                 
284                 double res = -1 ;
285                 
286                 if( _t != null )
287                 {
288                         for( int i = 0 ; i < _t.getNbDep() ; i++ )
289                         {
290                                 if( ! fait.contains( _t.getDependencies().get( i ) ) )
291                                 {
292                                         dep ++ ;
293                                 } else {
294                                         if( ! mappees.contains( _t.getDependencies().get( i ) ) )
295                                         {
296                                                 ext++ ;
297                                         }
298                                 }
299                                 
300                         }
301                         
302                         if( ( dep + ext ) < _t.getNbDep() * dep_min )
303                         {
304                                 res = 0 ;
305                         } else {
306                                 res = dep + ( ext * 0.5 ) ;
307                         }
308                         
309 //                      System.out.println("dep de "+t.getNum()+" => " + res);
310                         
311                 }
312                 
313                 
314                 return res ;
315         }
316                 
317
318         /**
319          * 
320          * @param _gl
321          * @param _nbGTask
322          * @return
323          */
324         @SuppressWarnings("unchecked")
325         private ArrayList<Architecture> construireArchi( Grid _gl, int _nbGTask ) 
326         {
327                 ArrayList<Architecture> ar = new ArrayList<Architecture>() ;
328                 
329                 ArrayList<Cluster> cl = (ArrayList<Cluster>) gl.getClusters().clone() ;
330                 
331                 
332                 // Méthode à faire !
333                 Architecture a = new Architecture() ;
334                 
335                 for( int i = 0 ; i < cl.size() ; i ++ )
336                 {
337                         a.addCluster( cl.get( i ) ) ;
338                 }
339
340                 ar.add( a ) ;
341                 
342                 return ar ;
343         }
344         
345         /**
346          * 
347          */
348         @SuppressWarnings("unchecked")
349         private void tri_dep()
350         {
351                 int nb_tache = gr.getNbGTask() ;
352                 int nb_tri = 0 ;
353                 int niveau = 0 ;
354                 int niveau_fait = -1 ;
355                 int temp = 0 ;
356                 
357                 ArrayList<GTask> tmp = new ArrayList<GTask>() ;
358                 ArrayList<Integer> tab = new ArrayList<Integer>() ;
359
360                 while( nb_tri < nb_tache )
361                 {               
362                         // Recherche du niveau en décroissant
363                         for( int i = 0 ; i < nb_tache ; i++ )
364                         {
365                                 temp = atraiter.get(i).getNbDep() ; 
366                                 
367                                 if( niveau < temp )
368                                 {
369                                         if( niveau_fait != -1 )
370                                         {
371                                                 if( temp < niveau_fait )
372                                                 {
373                                                         niveau = temp ;
374                                                 }
375                                         } else {
376                                                 niveau = temp ;
377                                         }
378                                 }
379                         }
380                         
381                         // Recherche des taches du niveau courrant
382                         for( int i = 0 ; i < nb_tache ; i++ )
383                         {
384                                 if( atraiter.get( i ).getNbDep() == niveau )
385                                 {
386                                         tmp.add( atraiter.get( i ) ) ;
387                                         tab.add( atraiter.get( i ).getNum() ) ;
388                                         
389                                         nb_tri ++ ;
390                                 }
391                         }
392                         
393                         niveau_fait = niveau ;
394                         niveau = 0 ;
395                         
396                 }
397                 
398                 atraiter = (ArrayList<GTask>) tmp.clone() ;
399                 
400 //              for( int i = 0 ; i < nb_tache ; i++ )
401 //              {
402 //                      System.out.print( atraiter.get(i).getNum() +" " ) ;
403 //              }
404 //              System.out.println();
405         }
406
407
408         @Override
409         public GNode replaceNode( GNode _dead, ArrayList<GNode> _ag ) 
410         {
411                 /** Update in cluster the status of nodes **/
412                 updateGrid() ;
413                 
414                 return null;
415         }
416
417
418         @Override
419         public GNode getOtherGNode( ArrayList<GNode> _ag ) {
420                 // TODO Auto-generated method stub
421                 return null;
422         }
423         
424 }
425
426 /** La programmation est un art, respectons ceux qui la pratiquent !! **/