Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
04f6a43f092ba747f28b76259b0901f0144cf89e
[mapping.git] / src / and / Mapping / QM.java
1 package and.Mapping ;
2
3
4 import java.util.ArrayList;
5 import java.util.Random;
6
7
8 /**
9  * Implementation of the AIAC Quick Quality Map (AIAC-QM) algorithm
10  * @author Sébastien Miquée
11  * @version 1.0
12  */
13 public class QM extends Algo
14 {
15         private static final long serialVersionUID = 1L;
16         
17         
18         private ArrayList<GTask2> atraiter ;
19         private ArrayList<GNode> archi ;
20         private double f ; // search factor
21         
22         
23         /**
24          * Default constructor.
25          */
26         public QM()
27         {
28                 super() ;
29         }
30         
31
32         /**
33          * Constructor
34          * @param _gr Application graph to be mapped on
35          * @param _gd Grid graph
36          * @param _f Search factor
37          */
38         public QM( Graph _gr, Grid _gd, double _f )
39         {
40                 super( _gr, _gd ) ;
41                 
42                 f = _f ;
43         }
44         
45         /**
46          * 
47          * @return
48          */
49         private ArrayList<GNode> sortInitGNode() 
50         {
51                 ArrayList<GNode> grn = null ;
52                 
53                 if( gl != null )
54                 {
55                         grn = new ArrayList<GNode>() ;
56                         
57                         ArrayList<GNode> tmp = gl.getGNodes() ;
58         
59                         grn.add( tmp.get( 0 ) ) ;
60                         
61                         boolean ok ;
62                 
63                         for( int i = 1 ; i < tmp.size() ; i++ )
64                         {
65                                 ok = false ;
66                                 
67                                 for( int j = 0 ; j < grn.size() ; j++ )
68                                 {
69                                         if( tmp.get( i ).getPower() > grn.get( j ).getPower() )
70                                         {
71                                                 grn.add( j, tmp.get( i ) ) ;
72                                                 ok = true ;
73                                                 break ;
74                                         }
75                                 }
76                                 
77                                 if( ok == false )
78                                 {
79                                         grn.add( tmp.get( i ) ) ;
80                                 }
81                         }
82                 }
83
84                 return grn ;
85         }
86
87
88         private ArrayList<GTask2> listToGTask2( Graph _gr ) 
89         {
90                 ArrayList<GTask2> gr2 = null ;
91                 
92                 if( _gr != null )
93                 {
94                         gr2 = new ArrayList<GTask2>() ;
95                 
96                         for( int i = 0 ; i < _gr.getNbGTask() ; i++ )
97                         {
98                                 gr2.add( new GTask2( _gr.getGraph().get( i ) ) ) ;
99                         }
100                 }
101                 
102                 return gr2 ;
103         }
104
105
106         @Override
107         public void map() 
108         {
109                 /* If the mapping is possible ... */
110                 if( gr.getNbGTask() <= gl.getNbGNode() )
111                 {
112                         atraiter = listToGTask2( gr ) ;
113                         archi = sortInitGNode() ;
114                         
115                         /** Local Variables **/
116                         GNode nc = null ;
117                         double yc = -1 ;
118                         GNode nb = null ;
119                         double yb = -1 ;
120                         GNode nr = null ;
121                         double yr = -1 ;
122                         double ynb = -1 ;
123
124                         
125                         System.out.println( "*******************************************" ) ;
126                         System.out.println( "* Launching the AIAC-QM Mapping algorithm *" ) ;
127                         System.out.println( "*******************************************\n\n" ) ;
128                         
129                         /** Initial values **/
130                         int r = 1 ; // Number of rounds
131                         int n = gr.getNbGTask() ; // Number of tasks
132                         
133                         /** Initial mapping **/
134                         initMapping() ;
135                         
136                         /** Main loop **/
137                         while( isOneMoveable() )
138                         {
139                                 for( int ti = 0 ; ti < atraiter.size() ; ti++ )
140                                 {
141                                         if( atraiter.get( ti ).isMoveable() )
142                                         {
143                                                 nc = atraiter.get( ti ).getMapedOn() ;
144                                                 yc = atraiter.get( ti ).getExecTime() ;
145                                                 nb = nc ;
146                                                 yb = yc ;
147                                                 
148                                                 /** Search a node to map on **/
149                                                 for( int k = 0 ; k < ( f * n / r ) ; k++ )
150                                                 {
151                                                         nr = selectRandomGNode( n, r ) ;
152                                                         yr = execTimeOn( atraiter.get( ti ).clone(), nr ) ;
153                                                         
154                                                         if( yr < yb )
155                                                         {
156                                                                 nb = nr ;
157                                                                 yb = yr ;
158                                                         }
159                                                 }
160                                                 
161                                                 /** Research of the neighbours' nodes **/
162                                                 ArrayList<GNode> neighbours = researchNeighbours( atraiter.get( ti ), 1 ) ;
163                                                 
164                                                 for( int ni = 0 ; ni < neighbours.size() ; ni++ )
165                                                 {
166                                                         ynb = execTimeOn( atraiter.get( ti ).clone(), neighbours.get( ni ) ) ;
167                                                 
168                                                         if( ynb < yb )
169                                                         {
170                                                                 nb = neighbours.get( ni ) ;
171                                                                 yb = ynb ;
172                                                         }
173                                                 }
174                                                 
175                                                 
176                                                 /** Mapping of the task **/
177                                                 if( ! nb.equals( nc ) )
178                                                 {
179                                                         GTask2 t_ = taskOn( nb ) ;
180                                                         if( t_ != null && t_.isMoveable() )
181                                                         {
182                                                                 t_.setGNode( null ) ;
183                                                         } 
184                                                         
185                                                         atraiter.get( ti ).setGNode( nb ) ;
186                                                         
187                                                         updateExecTimeNeighbours( atraiter.get( ti ) ) ;
188                                                 }
189                                         }
190                                         
191                                         /** The task is fixed on this node **/
192                                         atraiter.get( ti ).setMoveable( false ) ;
193                                         
194                                         /** If all tasks have been considered **/
195                                         if( ti == atraiter.size() - 1 )
196                                         {
197                                                 r++ ;
198                                         }
199                                 }
200                         }
201                         
202                         /** Save the Mapping **/
203                         for( int i = 0 ; i < atraiter.size() ; i++ )
204                         {
205                                 mp.addMapping( new Association( atraiter.get( i ).getMapedOn(), atraiter.get( i ).getGTask() ) ) ;
206                         }
207                 
208                 } else {
209                         System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
210                 }
211         }
212         
213         /**
214          * 
215          * @param _nb
216          * @return
217          */
218         private GTask2 taskOn( GNode _nb ) 
219         {
220                 for( int i = 0 ; i < atraiter.size() ; i++ )
221                 {
222                         if( atraiter.get( i ).getMapedOn().equals( _nb ) )
223                         {
224                                 return atraiter.get( i ) ;
225                         }
226                 }
227                 
228                 return null;
229         }
230
231         /**
232          * 
233          * @param _g
234          * @param _deep
235          * @return
236          */
237         private ArrayList<GNode> researchNeighbours( GTask2 _g, double _deep) 
238         {
239                 ArrayList<GNode> nb = new ArrayList<GNode>() ;
240                 ArrayList<GTask2> neighbours = new ArrayList<GTask2>() ;
241                 
242                 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
243                 {
244                         neighbours.add( atraiter.get( _g.getGTask().getDependencies().get( i ).getNum() ) ) ;
245                 }
246                 
247                 for( int i = 0 ; i < archi.size() ; i++ )
248                 {
249                         for( int j = 0 ; j < neighbours.size() ; j++ )
250                         {
251                                 GNode tmp = neighbours.get( j ).getMapedOn() ;
252                         
253                                 if( gl.getDistance( tmp, archi.get( i ) ) <= _deep && ! nb.contains( tmp ) )
254                                 {
255                                         nb.add( tmp ) ;
256                                 }
257                         }
258                 }
259                 
260                 return nb ;
261         }
262
263
264         /**
265          * Initialization of the mapping. Each task is mapped on computing
266          * nodes in order of their rank.
267          */
268         private void initMapping() 
269         {
270                 for( int i = 0 ; i < atraiter.size() ; i++ )
271                 {
272                         atraiter.get( i ).setGNode( archi.get( i ) ) ;
273                 }
274         }
275
276
277         /**
278          * 
279          * @param _g
280          * @param _n
281          * @return
282          */
283         private double execTimeOn( GTask2 _g, GNode _n ) 
284         {               
285                 _g.setGNode( _n ) ;
286                         
287                 return calcExecTime( _g ) ;
288         }
289
290         /**
291          * 
292          * @param _n
293          * @param _r
294          * @return
295          */
296         private GNode selectRandomGNode( int _n, int _r ) 
297         {
298                 GNode g = null ;
299                 
300                 Random rand = new Random() ;
301                 
302                 g = archi.get( rand.nextInt( _n / _r ) ) ;
303                 
304                 while( isTaskNotMoveableOn( g ) )
305                 {
306                         g = archi.get( rand.nextInt( _n / _r ) ) ;
307                 }
308                 
309                 return g ;
310         }
311
312
313         /**
314          * 
315          * @param _g
316          * @return
317          */
318         private boolean isTaskNotMoveableOn( GNode _g ) 
319         {
320                 for( int i = 0 ; i < atraiter.size() ; i++ )
321                 {
322                         if( atraiter.get( i ).getMapedOn().equals( _g ) && ! atraiter.get( i ).isMoveable() )
323                         {
324                                 return true ;
325                         }
326                 }
327         
328                 return false ;
329         }
330
331
332         /**
333          * 
334          * @return
335          */
336         private boolean isOneMoveable() 
337         {
338                 if( atraiter != null && atraiter.size() > 0 )
339                 {
340                         for( int i = 0 ; i < atraiter.size() ; i++ )
341                         {
342                                 if( atraiter.get( i ).isMoveable() )
343                                 {
344                                         return true ;
345                                 }
346                         }
347                 }
348                 
349                 return false ;
350         }
351         
352         
353         /**
354          * 
355          * @param _g
356          * @return
357          */
358         private double calcExecTime( GTask2 _g )
359         {
360                 double w = -1 ;
361                 
362                 if( _g != null )
363                 {       
364                         // Weight of computation
365                         w = ( _g.getGTask().getWeight() / _g.mappedOn.getPower() ) ;
366                         
367                         // Weight of communications
368                         int tab[] = new int[ _g.getGTask().getNbDep() ] ;
369                         for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
370                         {
371                                 tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
372                         }
373                         
374                         for( int i = 0 ; i < tab.length ; i++ )
375                         {
376                                 double tmp = gl.getDistance( _g.getMapedOn(), atraiter.get( tab[i] ).getMapedOn() ) ;
377                                 
378                                 if( tmp >= 0 )
379                                 {
380                                         w += tmp ;
381                                 }               
382                         }
383                 }
384                 
385                 return w ;
386         }
387
388
389         /**
390          * 
391          * @param _g
392          */
393         private void updateExecTime( GTask2 _g )
394         {
395                 double w = calcExecTime( _g ) ;
396                 
397                 if( w >= 0 )
398                 {
399                         if( w > _g.getExecTime() )
400                         {
401                                 _g.setMoveable( true ) ;
402                         }
403                         
404                         _g.setExecTime( w ) ;
405                 }
406         }
407         
408         
409         /**
410          * 
411          * @param _g
412          */
413         private void updateExecTimeNeighbours( GTask2 _g )
414         {
415                 int tab[] = new int[ _g.getGTask().getNbDep() ] ;
416                 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
417                 {
418                         tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
419                 }
420                 
421                 for( int i = 0 ; i < tab.length ; i++ )
422                 {
423                         updateExecTime( atraiter.get( tab[i] ) ) ;                      
424                 }
425         }
426         
427         
428         
429         /** Intern class **/
430         /**
431          * Temporary class.
432          */
433         private class GTask2
434         {
435                 private GTask g ;
436                 private boolean moveable ;
437                 private double execTime ;
438                 private GNode mappedOn ;
439                 
440                 public GTask2()
441                 {
442                         g = null ;
443                         moveable = false ;
444                         execTime = -1 ;
445                         mappedOn = null ;
446                 }
447                 
448                 public GTask2( GTask _g )
449                 {
450                         g = _g ;
451                         moveable = false ;
452                         execTime = -1 ;
453                         mappedOn = null ;
454                 }
455                 
456                 public boolean isMoveable()
457                 {
458                         return moveable ;
459                 }
460                 
461                 public void setMoveable( boolean b )
462                 {
463                         moveable = b ;
464                 }
465                 
466                 public void setGNode( GNode _g )
467                 {
468                         mappedOn = _g ;
469                 }
470                 
471                 
472                 public GTask getGTask()
473                 {
474                         return g ;
475                 }
476                 
477                 
478                 public double getExecTime()
479                 {
480                         return execTime ;
481                 }
482                 
483                 
484                 public void setExecTime( double _d )
485                 {
486                         execTime = _d ;
487                 }
488                 
489                 public GNode getMapedOn()
490                 {
491                         return mappedOn ;
492                 }
493                 
494                 
495                 public GTask2 clone()
496                 {
497                         GTask2 g_new = new GTask2() ;
498                         g_new.execTime = this.execTime ;
499                         g_new.g = this.g ;
500                         g_new.mappedOn = this.mappedOn ;
501                         g_new.moveable = this.moveable ;
502                         
503                         return g_new ;
504                 }
505         }
506
507
508
509         @Override
510         public GNode replaceNode(GNode _dead, ArrayList<GNode> _ag ) 
511         {
512                 return null;
513         }
514
515
516         @Override
517         public GNode getOtherGNode( ArrayList<GNode> _ag ) {
518                 // TODO Auto-generated method stub
519                 return null;
520         }
521 }
522
523
524
525 /** La programmation est un art, respectons ceux qui la pratiquent !! **/