4 import java.util.ArrayList;
5 import java.util.Random;
9 * Implementation of the AIAC Quick Quality Map (AIAC-QM) algorithm
10 * @author Sébastien Miquée
13 public class QM extends Algo
15 private static final long serialVersionUID = 1L;
18 private ArrayList<GTask2> atraiter ;
19 private ArrayList<GNode> archi ;
20 private double f ; // search factor
24 * Default constructor.
34 * @param _gr Application graph to be mapped on
35 * @param _gd Grid graph
36 * @param _f Search factor
38 public QM( Graph _gr, Grid _gd, double _f )
49 private ArrayList<GNode> sortInitGNode()
51 ArrayList<GNode> grn = null ;
55 grn = new ArrayList<GNode>() ;
57 ArrayList<GNode> tmp = gl.getGNodes() ;
59 grn.add( tmp.get( 0 ) ) ;
63 for( int i = 1 ; i < tmp.size() ; i++ )
67 for( int j = 0 ; j < grn.size() ; j++ )
69 if( tmp.get( i ).getPower() > grn.get( j ).getPower() )
71 grn.add( j, tmp.get( i ) ) ;
79 grn.add( tmp.get( i ) ) ;
88 private ArrayList<GTask2> listToGTask2( Graph _gr )
90 ArrayList<GTask2> gr2 = null ;
94 gr2 = new ArrayList<GTask2>() ;
96 for( int i = 0 ; i < _gr.getNbGTask() ; i++ )
98 gr2.add( new GTask2( _gr.getGraph().get( i ) ) ) ;
109 /* If the mapping is possible ... */
110 if( gr.getNbGTask() <= gl.getNbGNode() )
112 atraiter = listToGTask2( gr ) ;
113 archi = sortInitGNode() ;
115 /** Local Variables **/
125 System.out.println( "*******************************************" ) ;
126 System.out.println( "* Launching the AIAC-QM Mapping algorithm *" ) ;
127 System.out.println( "*******************************************\n\n" ) ;
129 /** Initial values **/
130 int r = 1 ; // Number of rounds
131 int n = gr.getNbGTask() ; // Number of tasks
133 /** Initial mapping **/
137 while( isOneMoveable() )
139 for( int ti = 0 ; ti < atraiter.size() ; ti++ )
141 if( atraiter.get( ti ).isMoveable() )
143 nc = atraiter.get( ti ).getMapedOn() ;
144 yc = atraiter.get( ti ).getExecTime() ;
148 /** Search a node to map on **/
149 for( int k = 0 ; k < ( f * n / r ) ; k++ )
151 nr = selectRandomGNode( n, r ) ;
152 yr = execTimeOn( atraiter.get( ti ).clone(), nr ) ;
161 /** Research of the neighbours' nodes **/
162 ArrayList<GNode> neighbours = researchNeighbours( atraiter.get( ti ), 1 ) ;
164 for( int ni = 0 ; ni < neighbours.size() ; ni++ )
166 ynb = execTimeOn( atraiter.get( ti ).clone(), neighbours.get( ni ) ) ;
170 nb = neighbours.get( ni ) ;
176 /** Mapping of the task **/
177 if( ! nb.equals( nc ) )
179 GTask2 t_ = taskOn( nb ) ;
180 if( t_ != null && t_.isMoveable() )
182 t_.setGNode( null ) ;
185 atraiter.get( ti ).setGNode( nb ) ;
187 updateExecTimeNeighbours( atraiter.get( ti ) ) ;
191 /** The task is fixed on this node **/
192 atraiter.get( ti ).setMoveable( false ) ;
194 /** If all tasks have been considered **/
195 if( ti == atraiter.size() - 1 )
202 /** Save the Mapping **/
203 for( int i = 0 ; i < atraiter.size() ; i++ )
205 mp.addMapping( new Association( atraiter.get( i ).getMapedOn(), atraiter.get( i ).getGTask() ) ) ;
209 System.err.println( "\n\n!!! Unable to map application !\n\n" ) ;
212 /** Update in cluster the status of nodes **/
221 private GTask2 taskOn( GNode _nb )
223 for( int i = 0 ; i < atraiter.size() ; i++ )
225 if( atraiter.get( i ).getMapedOn().equals( _nb ) )
227 return atraiter.get( i ) ;
240 private ArrayList<GNode> researchNeighbours( GTask2 _g, double _deep)
242 ArrayList<GNode> nb = new ArrayList<GNode>() ;
243 ArrayList<GTask2> neighbours = new ArrayList<GTask2>() ;
245 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
247 neighbours.add( atraiter.get( _g.getGTask().getDependencies().get( i ).getNum() ) ) ;
250 for( int i = 0 ; i < archi.size() ; i++ )
252 for( int j = 0 ; j < neighbours.size() ; j++ )
254 GNode tmp = neighbours.get( j ).getMapedOn() ;
256 if( gl.getDistance( tmp, archi.get( i ) ) <= _deep && ! nb.contains( tmp ) )
268 * Initialization of the mapping. Each task is mapped on computing
269 * nodes in order of their rank.
271 private void initMapping()
273 for( int i = 0 ; i < atraiter.size() ; i++ )
275 atraiter.get( i ).setGNode( archi.get( i ) ) ;
286 private double execTimeOn( GTask2 _g, GNode _n )
290 return calcExecTime( _g ) ;
299 private GNode selectRandomGNode( int _n, int _r )
303 Random rand = new Random() ;
305 g = archi.get( rand.nextInt( _n / _r ) ) ;
307 while( isTaskNotMoveableOn( g ) )
309 g = archi.get( rand.nextInt( _n / _r ) ) ;
321 private boolean isTaskNotMoveableOn( GNode _g )
323 for( int i = 0 ; i < atraiter.size() ; i++ )
325 if( atraiter.get( i ).getMapedOn().equals( _g ) && ! atraiter.get( i ).isMoveable() )
339 private boolean isOneMoveable()
341 if( atraiter != null && atraiter.size() > 0 )
343 for( int i = 0 ; i < atraiter.size() ; i++ )
345 if( atraiter.get( i ).isMoveable() )
361 private double calcExecTime( GTask2 _g )
367 // Weight of computation
368 w = ( _g.getGTask().getWeight() / _g.mappedOn.getPower() ) ;
370 // Weight of communications
371 int tab[] = new int[ _g.getGTask().getNbDep() ] ;
372 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
374 tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
377 for( int i = 0 ; i < tab.length ; i++ )
379 double tmp = gl.getDistance( _g.getMapedOn(), atraiter.get( tab[i] ).getMapedOn() ) ;
396 private void updateExecTime( GTask2 _g )
398 double w = calcExecTime( _g ) ;
402 if( w > _g.getExecTime() )
404 _g.setMoveable( true ) ;
407 _g.setExecTime( w ) ;
416 private void updateExecTimeNeighbours( GTask2 _g )
418 int tab[] = new int[ _g.getGTask().getNbDep() ] ;
419 for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ )
421 tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ;
424 for( int i = 0 ; i < tab.length ; i++ )
426 updateExecTime( atraiter.get( tab[i] ) ) ;
439 private boolean moveable ;
440 private double execTime ;
441 private GNode mappedOn ;
451 public GTask2( GTask _g )
459 public boolean isMoveable()
464 public void setMoveable( boolean b )
469 public void setGNode( GNode _g )
475 public GTask getGTask()
481 public double getExecTime()
487 public void setExecTime( double _d )
492 public GNode getMapedOn()
498 public GTask2 clone()
500 GTask2 g_new = new GTask2() ;
501 g_new.execTime = this.execTime ;
503 g_new.mappedOn = this.mappedOn ;
504 g_new.moveable = this.moveable ;
513 public GNode replaceNode(GNode _dead, ArrayList<GNode> _ag )
515 /** Update in cluster the status of nodes **/
522 public GNode getOtherGNode( ArrayList<GNode> _ag ) {
523 // TODO Auto-generated method stub
530 /** La programmation est un art, respectons ceux qui la pratiquent !! **/