Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
6483cd8f7e016ccf6800fcf51d2ec74407d08ef6
[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                 /** Update in cluster the status of nodes **/
213                 updateGrid() ;
214         }
215         
216         /**
217          * 
218          * @param _nb
219          * @return
220          */
221         private GTask2 taskOn( GNode _nb ) 
222         {
223                 for( int i = 0 ; i < atraiter.size() ; i++ )
224                 {
225                         if( atraiter.get( i ).getMapedOn().equals( _nb ) )
226                         {
227                                 return atraiter.get( i ) ;
228                         }
229                 }
230                 
231                 return null;
232         }
233
234         /**
235          * 
236          * @param _g
237          * @param _deep
238          * @return
239          */
240         private ArrayList<GNode> researchNeighbours( GTask2 _g, double _deep) 
241         {
242                 ArrayList<GNode> nb = new ArrayList<GNode>() ;
243                 ArrayList<GTask2> neighbours = new ArrayList<GTask2>() ;
244                 
245                 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
246                 {
247                         neighbours.add( atraiter.get( _g.getGTask().getDependencies().get( i ).getNum() ) ) ;
248                 }
249                 
250                 for( int i = 0 ; i < archi.size() ; i++ )
251                 {
252                         for( int j = 0 ; j < neighbours.size() ; j++ )
253                         {
254                                 GNode tmp = neighbours.get( j ).getMapedOn() ;
255                         
256                                 if( gl.getDistance( tmp, archi.get( i ) ) <= _deep && ! nb.contains( tmp ) )
257                                 {
258                                         nb.add( tmp ) ;
259                                 }
260                         }
261                 }
262                 
263                 return nb ;
264         }
265
266
267         /**
268          * Initialization of the mapping. Each task is mapped on computing
269          * nodes in order of their rank.
270          */
271         private void initMapping() 
272         {
273                 for( int i = 0 ; i < atraiter.size() ; i++ )
274                 {
275                         atraiter.get( i ).setGNode( archi.get( i ) ) ;
276                 }
277         }
278
279
280         /**
281          * 
282          * @param _g
283          * @param _n
284          * @return
285          */
286         private double execTimeOn( GTask2 _g, GNode _n ) 
287         {               
288                 _g.setGNode( _n ) ;
289                         
290                 return calcExecTime( _g ) ;
291         }
292
293         /**
294          * 
295          * @param _n
296          * @param _r
297          * @return
298          */
299         private GNode selectRandomGNode( int _n, int _r ) 
300         {
301                 GNode g = null ;
302                 
303                 Random rand = new Random() ;
304                 
305                 g = archi.get( rand.nextInt( _n / _r ) ) ;
306                 
307                 while( isTaskNotMoveableOn( g ) )
308                 {
309                         g = archi.get( rand.nextInt( _n / _r ) ) ;
310                 }
311                 
312                 return g ;
313         }
314
315
316         /**
317          * 
318          * @param _g
319          * @return
320          */
321         private boolean isTaskNotMoveableOn( GNode _g ) 
322         {
323                 for( int i = 0 ; i < atraiter.size() ; i++ )
324                 {
325                         if( atraiter.get( i ).getMapedOn().equals( _g ) && ! atraiter.get( i ).isMoveable() )
326                         {
327                                 return true ;
328                         }
329                 }
330         
331                 return false ;
332         }
333
334
335         /**
336          * 
337          * @return
338          */
339         private boolean isOneMoveable() 
340         {
341                 if( atraiter != null && atraiter.size() > 0 )
342                 {
343                         for( int i = 0 ; i < atraiter.size() ; i++ )
344                         {
345                                 if( atraiter.get( i ).isMoveable() )
346                                 {
347                                         return true ;
348                                 }
349                         }
350                 }
351                 
352                 return false ;
353         }
354         
355         
356         /**
357          * 
358          * @param _g
359          * @return
360          */
361         private double calcExecTime( GTask2 _g )
362         {
363                 double w = -1 ;
364                 
365                 if( _g != null )
366                 {       
367                         // Weight of computation
368                         w = ( _g.getGTask().getWeight() / _g.mappedOn.getPower() ) ;
369                         
370                         // Weight of communications
371                         int tab[] = new int[ _g.getGTask().getNbDep() ] ;
372                         for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
373                         {
374                                 tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
375                         }
376                         
377                         for( int i = 0 ; i < tab.length ; i++ )
378                         {
379                                 double tmp = gl.getDistance( _g.getMapedOn(), atraiter.get( tab[i] ).getMapedOn() ) ;
380                                 
381                                 if( tmp >= 0 )
382                                 {
383                                         w += tmp ;
384                                 }               
385                         }
386                 }
387                 
388                 return w ;
389         }
390
391
392         /**
393          * 
394          * @param _g
395          */
396         private void updateExecTime( GTask2 _g )
397         {
398                 double w = calcExecTime( _g ) ;
399                 
400                 if( w >= 0 )
401                 {
402                         if( w > _g.getExecTime() )
403                         {
404                                 _g.setMoveable( true ) ;
405                         }
406                         
407                         _g.setExecTime( w ) ;
408                 }
409         }
410         
411         
412         /**
413          * 
414          * @param _g
415          */
416         private void updateExecTimeNeighbours( GTask2 _g )
417         {
418                 int tab[] = new int[ _g.getGTask().getNbDep() ] ;
419                 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
420                 {
421                         tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
422                 }
423                 
424                 for( int i = 0 ; i < tab.length ; i++ )
425                 {
426                         updateExecTime( atraiter.get( tab[i] ) ) ;                      
427                 }
428         }
429         
430         
431         
432         /** Intern class **/
433         /**
434          * Temporary class.
435          */
436         private class GTask2
437         {
438                 private GTask g ;
439                 private boolean moveable ;
440                 private double execTime ;
441                 private GNode mappedOn ;
442                 
443                 public GTask2()
444                 {
445                         g = null ;
446                         moveable = false ;
447                         execTime = -1 ;
448                         mappedOn = null ;
449                 }
450                 
451                 public GTask2( GTask _g )
452                 {
453                         g = _g ;
454                         moveable = false ;
455                         execTime = -1 ;
456                         mappedOn = null ;
457                 }
458                 
459                 public boolean isMoveable()
460                 {
461                         return moveable ;
462                 }
463                 
464                 public void setMoveable( boolean b )
465                 {
466                         moveable = b ;
467                 }
468                 
469                 public void setGNode( GNode _g )
470                 {
471                         mappedOn = _g ;
472                 }
473                 
474                 
475                 public GTask getGTask()
476                 {
477                         return g ;
478                 }
479                 
480                 
481                 public double getExecTime()
482                 {
483                         return execTime ;
484                 }
485                 
486                 
487                 public void setExecTime( double _d )
488                 {
489                         execTime = _d ;
490                 }
491                 
492                 public GNode getMapedOn()
493                 {
494                         return mappedOn ;
495                 }
496                 
497                 
498                 public GTask2 clone()
499                 {
500                         GTask2 g_new = new GTask2() ;
501                         g_new.execTime = this.execTime ;
502                         g_new.g = this.g ;
503                         g_new.mappedOn = this.mappedOn ;
504                         g_new.moveable = this.moveable ;
505                         
506                         return g_new ;
507                 }
508         }
509
510
511
512         @Override
513         public GNode replaceNode(GNode _dead, ArrayList<GNode> _ag ) 
514         {
515                 GNode ret = null ;
516                 
517                 /** Updating the grid if there is any modification **/
518                 if( _ag != null && _ag.size() != 0 )
519                 {
520                         gl.updateGrid( _ag ) ;
521                 }
522                 
523                 /** If something has to be done **/
524                 if( _dead != null )
525                 {
526                         ArrayList<GNode> ac = new ArrayList<GNode>() ;
527                         GNode tmp = null ;
528                 
529                         /** Searching if clusters have some free nodes **/
530                         for( int i = 0 ; i < gl.getNbCluster() ; i++ )
531                         {
532                                 if( gl.getClusters().get( i ).getNbFreeNodes() > 0 )
533                                 {
534                                         tmp = gl.getClusters().get( i ).nextGNode() ;
535                                         
536                                         if( tmp != null )
537                                         {
538                                                 ac.add( tmp ) ;
539                                         }
540                                 }
541                         }
542                         
543                         /** If there some nodes in clusters **/
544                         if( ac.size() > 0 )
545                         {
546                                 double power = -1, best = -1 ;
547                                 int bestNode = -1 ;
548                                 
549                                 /** Searching the replacing node with the higher 
550                                  * computing power
551                                  */
552                                 for( int i = 0 ; i < ac.size() ; i++ )
553                                 {
554                                         power = ac.get( i ).getPower() ;
555                                         
556                                         if( best == -1 )
557                                         {
558                                                 best = power ;
559                                                 bestNode = i ;
560                                         } else {
561                                                 if( power < best )
562                                                 {
563                                                         best = power ;
564                                                         bestNode = i ;
565                                                 }
566                                         }
567                                 }
568                                 
569                                 /** Is there any node candidate ? **/
570                                 if( bestNode != -1 )
571                                 {
572                                         ret = ac.get( bestNode ) ;
573                                 }
574                         }                       
575                 }
576                 
577                 /** Update in cluster the status of nodes **/
578                 updateGrid() ;
579                 
580                 return ret ;
581         }
582
583
584         @Override
585         public GNode getOtherGNode( ArrayList<GNode> _ag ) 
586         {
587                 GNode ret = null ;
588                 
589                 /** Updating the grid if there is any modification **/
590                 if( _ag != null && _ag.size() != 0 )
591                 {
592                         gl.updateGrid( _ag ) ;
593                 }
594                 
595                 int free[] = new int[ gl.getNbCluster() ] ;
596                 
597                 /** Searching if clusters have some free nodes **/
598                 for( int i = 0 ; i < gl.getNbCluster() ; i++ )
599                 {
600                         free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ;
601                 }
602                 
603                 /** Returning a node from the cluster which has the most
604                  * available nodes
605                  */
606                 int most = -1, max = 0 ;
607                 
608                 for( int i = 0 ; i < free.length ; i++ )
609                 {
610                         if( free[ i ] > max )
611                         {
612                                 max = free[ i ] ;
613                                 most = i ;
614                         }
615                 }
616                 
617                 /** Is there any cluster candidate ? **/
618                 if( most != -1 )
619                 {
620                         ret = gl.getClusters().get( most ).nextGNode() ;
621                 }
622                 
623                 
624                 return ret ;
625         }
626 }
627
628
629
630 /** La programmation est un art, respectons ceux qui la pratiquent !! **/