From: Sébastien Miquée Date: Tue, 2 Feb 2010 13:37:08 +0000 (+0100) Subject: Creation of Mapping repository. X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/mapping.git/commitdiff_plain/919cd5f7e473b8b22b46a6b6c221341ca8cd738b Creation of Mapping repository. --- 919cd5f7e473b8b22b46a6b6c221341ca8cd738b diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..80e8513 --- /dev/null +++ b/Makefile @@ -0,0 +1,38 @@ +# +# Makefile for Mapping library +# Author : Sébastien Miquée +# + +JAVAC=javac +BIN=bin +LIB=lib +SRC=src +PACK=and +PACKAGE=$(PACK)/Mapping +JAR=Mapping.jar + + +compile:clean + @echo + @echo "Compilation of Mapping library ..." + @echo + mkdir $(BIN) + $(JAVAC) -cp .:./$(LIB)/* -d ./$(BIN) ./$(SRC)/$(PACKAGE)/*.java + + +jar:compile + @echo + @echo "Creation of Mapping jar ..." + @echo + jar -cvfm $(JAR) Manifest -C $(BIN) $(PACK)/ $(LIB) + +clean: + @echo + @echo "Cleaning project ..." + @echo + rm -rf bin $(JAR) + + +# +## +# diff --git a/Manifest b/Manifest new file mode 100644 index 0000000..5cccaf4 --- /dev/null +++ b/Manifest @@ -0,0 +1,2 @@ +Manifest-Version: 1.0 +Class-path: .\lib\:. diff --git a/lib/libsigar-amd64-freebsd-6.so b/lib/libsigar-amd64-freebsd-6.so new file mode 100644 index 0000000..9ec33a9 Binary files /dev/null and b/lib/libsigar-amd64-freebsd-6.so differ diff --git a/lib/libsigar-amd64-linux.so b/lib/libsigar-amd64-linux.so new file mode 100644 index 0000000..49b2f05 Binary files /dev/null and b/lib/libsigar-amd64-linux.so differ diff --git a/lib/libsigar-amd64-solaris.so b/lib/libsigar-amd64-solaris.so new file mode 100644 index 0000000..ae9a4f1 Binary files /dev/null and b/lib/libsigar-amd64-solaris.so differ diff --git a/lib/libsigar-ia64-hpux-11.sl b/lib/libsigar-ia64-hpux-11.sl new file mode 100755 index 0000000..1dc74db Binary files /dev/null and b/lib/libsigar-ia64-hpux-11.sl differ diff --git a/lib/libsigar-ia64-linux.so b/lib/libsigar-ia64-linux.so new file mode 100644 index 0000000..2bd2fc8 Binary files /dev/null and b/lib/libsigar-ia64-linux.so differ diff --git a/lib/libsigar-pa-hpux-11.sl b/lib/libsigar-pa-hpux-11.sl new file mode 100755 index 0000000..c63eb22 Binary files /dev/null and b/lib/libsigar-pa-hpux-11.sl differ diff --git a/lib/libsigar-ppc-aix-5.so b/lib/libsigar-ppc-aix-5.so new file mode 100644 index 0000000..480c440 Binary files /dev/null and b/lib/libsigar-ppc-aix-5.so differ diff --git a/lib/libsigar-ppc-linux.so b/lib/libsigar-ppc-linux.so new file mode 100644 index 0000000..d5637a7 Binary files /dev/null and b/lib/libsigar-ppc-linux.so differ diff --git a/lib/libsigar-ppc64-aix-5.so b/lib/libsigar-ppc64-aix-5.so new file mode 100644 index 0000000..9a3a737 Binary files /dev/null and b/lib/libsigar-ppc64-aix-5.so differ diff --git a/lib/libsigar-ppc64-linux.so b/lib/libsigar-ppc64-linux.so new file mode 100644 index 0000000..4875241 Binary files /dev/null and b/lib/libsigar-ppc64-linux.so differ diff --git a/lib/libsigar-s390x-linux.so b/lib/libsigar-s390x-linux.so new file mode 100644 index 0000000..ae8ac4b Binary files /dev/null and b/lib/libsigar-s390x-linux.so differ diff --git a/lib/libsigar-sparc-solaris.so b/lib/libsigar-sparc-solaris.so new file mode 100644 index 0000000..507effe Binary files /dev/null and b/lib/libsigar-sparc-solaris.so differ diff --git a/lib/libsigar-sparc64-solaris.so b/lib/libsigar-sparc64-solaris.so new file mode 100644 index 0000000..1a4bc18 Binary files /dev/null and b/lib/libsigar-sparc64-solaris.so differ diff --git a/lib/libsigar-universal-macosx.dylib b/lib/libsigar-universal-macosx.dylib new file mode 100644 index 0000000..4a35824 Binary files /dev/null and b/lib/libsigar-universal-macosx.dylib differ diff --git a/lib/libsigar-universal64-macosx.dylib b/lib/libsigar-universal64-macosx.dylib new file mode 100644 index 0000000..dc27122 Binary files /dev/null and b/lib/libsigar-universal64-macosx.dylib differ diff --git a/lib/libsigar-x86-freebsd-5.so b/lib/libsigar-x86-freebsd-5.so new file mode 100644 index 0000000..67de5df Binary files /dev/null and b/lib/libsigar-x86-freebsd-5.so differ diff --git a/lib/libsigar-x86-freebsd-6.so b/lib/libsigar-x86-freebsd-6.so new file mode 100644 index 0000000..7b3a264 Binary files /dev/null and b/lib/libsigar-x86-freebsd-6.so differ diff --git a/lib/libsigar-x86-linux.so b/lib/libsigar-x86-linux.so new file mode 100644 index 0000000..5d2630e Binary files /dev/null and b/lib/libsigar-x86-linux.so differ diff --git a/lib/libsigar-x86-solaris.so b/lib/libsigar-x86-solaris.so new file mode 100644 index 0000000..ea33591 Binary files /dev/null and b/lib/libsigar-x86-solaris.so differ diff --git a/lib/sigar.jar b/lib/sigar.jar new file mode 100644 index 0000000..8fe8400 Binary files /dev/null and b/lib/sigar.jar differ diff --git a/lib/xstream-1.3.1.jar b/lib/xstream-1.3.1.jar new file mode 100644 index 0000000..4ef4219 Binary files /dev/null and b/lib/xstream-1.3.1.jar differ diff --git a/src/and/Mapping/Algo.java b/src/and/Mapping/Algo.java new file mode 100644 index 0000000..79a210f --- /dev/null +++ b/src/and/Mapping/Algo.java @@ -0,0 +1,79 @@ +package and.Mapping ; + +import java.io.Serializable; +import java.util.ArrayList; + + +/** + * Abstract class defining the structure for mapping algorithms + * @author Sébastien Miquée + */ +public abstract class Algo implements Serializable +{ + private static final long serialVersionUID = 1L; + + /* Variables */ + protected Graph gr ; + protected Grid gl ; + protected Mapping mp ; + + + /** + * Default constructor. + */ + public Algo() + { + gr = new Graph() ; + gl = new Grid() ; + mp = new Mapping() ; + } + + + /** + * Constructor. + * @param _gr Tasks graph to be mapped + * @param _gl Grid graph + */ + public Algo( Graph _gr, Grid _gl ) + { + gr = _gr ; + gl = _gl ; + mp = new Mapping() ; + } + + + /** + * Mapping function. + */ + public abstract void map() ; + + + /** + * Replace a fallen node by a new one, according to the mapping policy. + * @param _dead The fallen node to be replaced + * @param _ag The list of all available computing nodes + * @return The new node + */ + public abstract GNode replaceNode( GNode _dead, ArrayList _ag ) ; + + + /** + * Find a new node, which may not takes part into the computation process. + * Typically such kind of node is used to create a new spawner or a new super-node, + * in order to bring fault tolerance. + * @return Another node which will not compute + */ + public abstract GNode getOtherGNode() ; + + + /** + * Return mapping done. + * @return The mapping done + */ + public Mapping getMapping() + { + return mp ; + } +} + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/Architecture.java b/src/and/Mapping/Architecture.java new file mode 100644 index 0000000..91e45a9 --- /dev/null +++ b/src/and/Mapping/Architecture.java @@ -0,0 +1,72 @@ +package and.Mapping ; + +import java.util.ArrayList; + + +/** + * Class representing a set of clusters forming a network architecture + * @author Sébastien Miquée + * + */ +public class Architecture +{ + private ArrayList archi ; + private int nbNodes ; + private int nbClusters ; + + + /** + * Default constructor. + */ + public Architecture() + { + archi = new ArrayList() ; + nbNodes = 0 ; + nbClusters = 0 ; + } + + + /** + * Add a cluster in the architecture. + * @param c Cluster to be add. + */ + public void addCluster( Cluster c ) + { + archi.add( c ) ; + nbNodes += c.getNbGNode() ; + nbClusters ++ ; + } + + + /** + * Return the amount of computing nodes in the architecture. + * @return The amount of nodes + */ + public int getNbNodes() + { + return nbNodes ; + } + + + /** + * Return the amount of clusters in the architecture. + * @return The amoutn of clusters + */ + public int getNbClusters() + { + return nbClusters ; + } + + + /** + * Return the architecture in a clusters list form. + * @return A clusters list + */ + public ArrayList getArchi() + { + return archi ; + } + +} + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/Association.java b/src/and/Mapping/Association.java new file mode 100644 index 0000000..543c849 --- /dev/null +++ b/src/and/Mapping/Association.java @@ -0,0 +1,95 @@ +package and.Mapping ; + + +import java.io.Serializable; +import java.util.ArrayList; + + + +/** + * Class representing an association between a tasks list and a cluster + * on which they are mapped, or between a task and a computing node + * @author Sébastien Miquée + * + */ +public class Association implements Serializable +{ + private static final long serialVersionUID = 1L; + + + private Cluster c = null ; + private ArrayList at = null ; + private GNode g = null ; + private GTask t = null ; + + /** + * Default constructor. + */ + public Association(){} + + + /** + * Constructor. + * @param _c Associated cluster + * @param _at Tasks list + */ + public Association( Cluster _c, ArrayList _at ) + { + c = _c ; + at = _at ; + } + + + /** + * Constructor. + * @param _g Associated computing node + * @param _t Associated task + */ + public Association( GNode _g, GTask _t ) + { + g = _g ; + t = _t ; + } + + + /** + * Return the associated cluster. + * @return The associated cluster + */ + public Cluster getCluster() + { + return c ; + } + + + /** + * Return the associated tasks list. + * @return The associated tasks list + */ + public ArrayList getGtask() + { + return at ; + } + + /** + * Return the associated computing node. + * @return The associated node + */ + public GNode getGNode() + { + return g ; + } + + + /** + * Return the associated task. + * @return The associated task + */ + public GTask getGTask() + { + return t ; + } + +} + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/Cluster.java b/src/and/Mapping/Cluster.java new file mode 100644 index 0000000..8d798f5 --- /dev/null +++ b/src/and/Mapping/Cluster.java @@ -0,0 +1,220 @@ +package and.Mapping ; + + +import java.io.Serializable; +import java.util.ArrayList; + + +/** + * Class representing a computing nodes cluster + * @author Sébastien Miquée + * + */ +public class Cluster implements Serializable +{ + private static final long serialVersionUID = 1L; + + private int nb_node ; + private String name ; + private ArrayList nodes ; + private String site ; + private int indice ; + + + /** + * Default constructor. + */ + public Cluster() + { + nb_node = 0 ; + name = "" ; + nodes = new ArrayList() ; + site = "" ; + indice = 0 ; + } + + + /** + * Constructor. + * @param _nb The amount of computing nodes in the cluster + */ + public Cluster( int _nb ) + { + nb_node = _nb ; + name = "" ; + nodes = new ArrayList() ; + site = "" ; + indice = 0 ; + + + for( int i = 0 ; i < nb_node ; i++ ) + { + nodes.add( new GNode() ) ; + } + } + + + /** + * Constructor. + * @param _nb The amount of computing nodes in the cluster + * @param _name Cluster's name + */ + public Cluster( int _nb, String _name ) + { + nb_node = _nb ; + name = _name ; + nodes = new ArrayList() ; + site = "" ; + indice = 0 ; + + for( int i = 0 ; i < nb_node ; i++ ) + { + nodes.add( new GNode() ) ; + } + } + + + /** + * Set the name of the cluster. + * @param _name Cluster's name + */ + public void setName( String _name ) + { + name = _name ; + } + + + /** + * Adding a computing node to the cluster. + * @param _n Node to be add + */ + public void addGNode( GNode _n ) + { + _n.setInCluster( true ) ; + nodes.add( _n ) ; + + nb_node++ ; + } + + + /** + * Return the list of computing nodes which are in the cluster. + * @return The list of nodes + */ + public ArrayList getGNodes() + { + return nodes ; + } + + + /** + * Return cluster's name. + * @return Cluster's name + */ + public String getName() + { + return name ; + } + + + /** + * Return the amount of computing nodes in the cluster. + * @return The amount of nodes + */ + public int getNbGNode() + { + return nb_node ; + } + + + /** + * Set the site in which the cluster is. + * @param _site Site's name + */ + public void setSite( String _site ) + { + site = _site ; + } + + + /** + * Return the site's name in which the cluster is. + * @return The site's name + */ + public String getSite() + { + return site ; + } + + + /** + * Test if a computing node is in the cluster. + * @param _g The node to be tested + * @return True is _g is in, False else + */ + public boolean isIn( GNode _g ) + { + if( _g != null ) + { + if( nodes.contains( _g ) ) + { + return true ; + } + } + + return false ; + } + + /** + * Initialization of indice variable. + */ + public void initIndice() + { + indice = 0 ; + } + + + /** + * Return the next computing node in the cluster, + * according to the indice variable. + * @return The next node in the cluster + */ + public GNode nextGNode() + { + GNode ret = null ; + + if( indice < nb_node ) + { + ret = nodes.get( indice ) ; + indice++ ; + } + + return ret ; + } + + + /** + * Remove a failed node from the cluster. + * @param _dead The failed node + */ + public void removeGNode( GNode _dead ) + { + if( _dead != null && _dead.getCluster().equals( name ) && _dead.getSite().equals( site ) ) + { + for( int i = 0 ; i < nodes.size() ; i++ ) + { + if( _dead.getId() == nodes.get( i ).getId() ) + { + nodes.remove( i ) ; + nb_node-- ; + + break ; + } + } + } + + } + +} + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/DefaultMapping.java b/src/and/Mapping/DefaultMapping.java new file mode 100644 index 0000000..5cdb0a2 --- /dev/null +++ b/src/and/Mapping/DefaultMapping.java @@ -0,0 +1,89 @@ +package and.Mapping ; + + +import java.util.ArrayList; + + +/** + * Implementation of JaceP2P default mapping + * @author Sébastien Miquée + * @version 1.0 + */ +public class DefaultMapping extends Algo +{ + private static final long serialVersionUID = 1L; + + + private ArrayList atraiter ; + private ArrayList archi ; + + /** + * Default constructor. + */ + public DefaultMapping() + { + super() ; + } + + + /** + * Constructor. + * @param _gr Tasks graph to be mapped + * @param _gd Grid graph + */ + public DefaultMapping( Graph _gr, Grid _gd, ArrayList _gnodes ) + { + super( _gr, _gd ) ; + archi = _gnodes ; + } + + + + @Override + public void map() + { + /* If the mapping is possible ... */ + if( gr.getNbGTask() <= gl.getNbGNode() ) + { + atraiter = gr.getGraph() ; + + System.out.println( "*******************************************" ) ; + System.out.println( "* Launching the Default Mapping algorithm *" ) ; + System.out.println( "*******************************************\n\n" ) ; + + /** Save the Mapping **/ + for( int i = 0 ; i < atraiter.size() ; i++ ) + { + mp.addMapping( new Association( archi.get( i ), atraiter.get( i ) ) ) ; + } + + } else { + System.err.println( "\n\n!!! Unable to map application !\n\n" ) ; + } + } + + + @Override + public GNode replaceNode( GNode _dead, ArrayList _ag ) + { + GNode ret = null ; + + if( _dead != null ) + { + return _ag.get( 0 ) ; + } + + return ret ; + } + + + @Override + public GNode getOtherGNode() { + // TODO Auto-generated method stub + return null; + } +} + + + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/GNode.java b/src/and/Mapping/GNode.java new file mode 100644 index 0000000..5e6dcaf --- /dev/null +++ b/src/and/Mapping/GNode.java @@ -0,0 +1,262 @@ +package and.Mapping ; + +import java.io.Serializable; + + +/** + * Class representing a computing node + * @author Sébastien Miquée + * + */ +public class GNode implements Serializable +{ + private static final long serialVersionUID = 1L; + + private String name ; + private int nb_cores ; + private int frequency ; + private int memory ; + private Object node ; + private long id ; + private boolean mapped ; + private boolean inCluster ; + private String cluster ; + private String site ; + + + /** + * Default constructor. + */ + public GNode() + { + name = "" ; + cluster = "" ; + site = "" ; + nb_cores = 0 ; + frequency = 0 ; + memory = 0 ; + node = null ; + id = -1 ; + mapped = false ; + inCluster = false ; + } + + + /** + * Set the cluster's name in which the computing node is. + * @param _c The name of the cluster containing the node + */ + public void setCluster( String _c ) + { + cluster = _c ; + } + + + /** + * Return the cluster's name in which the node is. + * @return The cluster's name + */ + public String getCluster() + { + return cluster ; + } + + + /** + * Set the site's name in which the computing node is. + * @param _s The site's name + */ + public void setSite( String _s ) + { + site = _s ; + } + + + /** + * Return the name of the site in which the computing node is. + * @return The site's name + */ + public String getSite() + { + return site ; + } + + + /** + * Change the status of the node concerning its participation in the computation. + * @param _b The status of its participation + */ + public void setMapped( boolean _b ) + { + mapped = _b ; + } + + + /** + * Return the status of the participation of the computing node. + * @return The status of the node + */ + public boolean getMapped() + { + return mapped ; + } + + + /** + * Set the status of the computing node in order to know if + * it is in cluster or not. + * @param _b The status of the node + */ + public void setInCluster( boolean _b ) + { + inCluster = _b ; + } + + + /** + * Return the status of the computing node concerning its + * presence, or not, in a cluster. + * @return The status of the node + */ + public boolean getInCluster() + { + return inCluster ; + } + + + /** + * Set the name of the computing node. + * @param _name The node's name + */ + public void setName( String _name ) + { + name = _name ; + } + + + /** + * Return the name of the computing node + * @return The node's name + */ + public String getName() + { + return name ; + } + + + /** + * Set the external representation of the node. This object + * represents the node in application using this library. + * @param n The external representation of the node + */ + public void setNode( Object n ) + { + node = n ; + } + + + /** + * Return the external representation of the node. + * @return The external representation of the node + */ + public Object getNode() + { + return node ; + } + + + + /** + * Set the amount of computing cores of the computing node. + * @param _nb_cores The amount of cores + */ + public void setNb_cores( int _nb_cores ) + { + nb_cores = _nb_cores; + } + + + /** + * Return the amount of computing cores of the computing node. + * @return The amount of cores + */ + public int getNb_cores() + { + return nb_cores; + } + + + /** + * Set the frequency of computing cores of the computing node. + * @param _freq The frequency of cores + */ + public void setFrequency( int _freq ) + { + frequency = _freq ; + } + + + /** + * Return the frequency of computing cores of the computing node. + * @return The frequency of cores + */ + public int getFrequency() + { + return frequency ; + } + + + /** + * Set the amount of available memory of the computing node. + * @param _mem Amount of memory + */ + public void setMemory( int _mem ) + { + memory = _mem ; + } + + + /** + * Return the amount of the available memory of the computing node. + * @return The amount of memory + */ + public int getMemory() + { + return memory ; + } + + + /** + * Return the computational power of the computing node. It includes + * the multiplication of cores by frequency plus a coefficient for the + * memory. + * @return The computational power of the computing node + */ + public int getPower() + { + return ( nb_cores * frequency ) ; + } + + + /** + * Set the uniq identifier of the computing node. + * @param _id The identifier of the node + */ + public void setId( long _id ) + { + id = _id ; + } + + + /** + * Return the uniq identifier of the computing node. + * @return The identifier of the node + */ + public long getId() + { + return id ; + } + +} + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/GTask.java b/src/and/Mapping/GTask.java new file mode 100644 index 0000000..8dd430b --- /dev/null +++ b/src/and/Mapping/GTask.java @@ -0,0 +1,166 @@ +package and.Mapping ; + + +import java.io.Serializable; +import java.util.ArrayList; + + +/** + * Class representing an application task + * @author Sébastien Miquée + * + */ +public class GTask implements Serializable +{ + private static final long serialVersionUID = 1L; + + + private int num ; + private int weight ; + private ArrayList dependencies ; + private int nb_dep ; + + + /** + * Default constructor. + */ + public GTask() + { + num = -1 ; + weight = 10000 ; + dependencies = new ArrayList() ; + nb_dep = 0 ; + } + + + /** + * Constructor. + * @param _n Task number + */ + public GTask( int _n ) + { + num = _n ; + weight = 10000 ; + dependencies = new ArrayList() ; + nb_dep = 0 ; + } + + + /** + * Add a dependency to the task. + * @param _t Dependency task + */ + public void addDependance( GTask _t ) + { + if( _t != null ) + { + if( ! _t.equals( this ) && ! dependencies.contains( _t ) ) + { + dependencies.add( _t ) ; + nb_dep ++ ; + } + } + } + + + + /** + * Return the task's number in a string. + * @return A String containing the task's number + */ + public String toString() + { + return "" + num ; + } + + + /** + * Add a dependencies list to the task. + * @param at The dependencies list + */ + public void addDependance( ArrayList at ) + { + if( at != null ) + { + for( int i = 0 ; i < at.size() ; i++ ) + { + this.addDependance( at.get( i ) ) ; + } + } + } + + + /** + * Define the task's computing weight. + * @param _p The computing weight + */ + public void setWeight( int _p ) + { + weight = _p ; + } + + + /** + * Return the task's weight. + * @return The task's weight + */ + public int getWeight() + { + return weight ; + } + + + /** + * Return the task's dependencies list. + * @return The dependencies list + */ + public ArrayList getDependencies() + { + return dependencies ; + } + + + /** + * Return the task's number. + * @return The task's number + */ + public int getNum() + { + return num ; + } + + + /** + * Return the amount of dependencies of the task. + * @return The amount of dependencies + */ + public int getNbDep() + { + return nb_dep ; + } + + + /** + * Return the task's dependencies list in a text form. + * @return The String containing the dependencies list + */ + public String printDep() + { + String s = "{ " ; + + for( int i = 0 ; i < nb_dep ; i++ ) + { + s = s + dependencies.get( i ).getNum() ; + if( i != nb_dep - 1 ) + { + s = s + ", " ; + } + } + + s = s + " }" ; + + return s ; + } +} + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/Graph.java b/src/and/Mapping/Graph.java new file mode 100644 index 0000000..58a719d --- /dev/null +++ b/src/and/Mapping/Graph.java @@ -0,0 +1,96 @@ +package and.Mapping ; + + +import java.io.Serializable; +import java.util.ArrayList; + + + + +/** + * Class representing the interaction graph of an application + * @author Sébastien Miquée + */ +public class Graph implements Serializable +{ + private static final long serialVersionUID = 1L; + + + private ArrayList graph ; + private int nb_task ; + private int nb_dep_total ; + + + /** + * Default constructor. + */ + public Graph() + { + graph = new ArrayList() ; + nb_task = 0 ; + nb_dep_total = 0 ; + } + + + /** + * Return the amount of tasks in the graph. + * @return The amount of tasks + */ + public int getNbGTask() + { + return nb_task ; + } + + + /** + * Add a task in the interaction graph. + * @param t Task to be add + */ + public void addGTask( GTask t ) + { + if( t != null ) + { + graph.add( t.getNum(), t ) ; + nb_dep_total += t.getNbDep() ; + nb_task ++ ; + } + } + + + /** + * Return the graph in a tasks list form. + * @return The tasks list + */ + public ArrayList getGraph() + { + return graph ; + } + + + /** + * Return the average of dependencies of tasks in the graph. + * @return The average of dependencies + */ + public double getAverageDep() + { + return nb_dep_total / nb_task ; + } + + + /** + * Print the graph in a text version. + */ + public void print() + { + System.out.println(); + System.out.println( "\t=> Composition of interaction graph:\n" ) ; + for( int i = 0 ; i < nb_task ; i++ ) + { + System.out.println( "\t\tTask \""+ graph.get(i).getNum() +"\" => " + graph.get(i).printDep() ) ; + } + + System.out.println(); + } +} + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/Grid.java b/src/and/Mapping/Grid.java new file mode 100644 index 0000000..b9a6efa --- /dev/null +++ b/src/and/Mapping/Grid.java @@ -0,0 +1,284 @@ +package and.Mapping ; + + +import java.io.Serializable; +import java.util.ArrayList; + + + +/** + * Class representing a computing grid, composed of multiple clusters + * @author Sébastien Miquée + */ +public class Grid implements Serializable +{ + private static final long serialVersionUID = 1L; + + + private int nb_cluster ; + private int nb_node ; + private ArrayList clusters ; + private ArrayList gnodesList; + private boolean gnodesList_done; + + + /** + * Default constructor + */ + public Grid() + { + nb_cluster = 0 ; + nb_node = 0 ; + clusters = new ArrayList() ; + gnodesList = null ; + gnodesList_done = false ; + } + + + /** + * Add a cluster in the grid. + * @param c Cluster to be add + */ + public void addCluster( Cluster c ) + { + if( c != null ) + { + clusters.add( c ) ; + nb_cluster ++ ; + nb_node += c.getNbGNode() ; + } + } + + + /** + * Add a clusters list in the grid. + * @param al List of clusters to be add + */ + public void addClusters( ArrayList al ) + { + if( al != null ) + { + for( int i = 0 ; i < al.size() ; i++ ) + { + clusters.add( al.get( i ) ) ; + nb_cluster ++ ; + nb_node += al.get( i ).getNbGNode() ; + } + } + } + + + /** + * Return the amount of clusters in the grid. + * @return The amount of clusters + */ + public int getNbCluster() + { + return nb_cluster ; + } + + + /** + * Return the amount of computing nodes in the grid. + * @return The amount of computing nodes + */ + public int getNbGNode() + { + return nb_node ; + } + + + /** + * Return the grid in a clusters list view. + * @return Clusters list + */ + public ArrayList getClusters() + { + return clusters ; + } + + + /** + * Initialization of clusters. + */ + public void initClusters() + { + for( int i = 0 ; i < nb_cluster ; i++ ) + { + clusters.get( i ).initIndice() ; + } + } + + + /** + * Compute and return the distance between two clusters. + * @param _g1 First cluster + * @param _g2 Second cluster + * @return The distance between the two clusters + */ + public double getDistance( GNode _g1, GNode _g2 ) + { + double d = 0 ; + + if( _g1.equals( _g2 ) ) + { + return d ; + } + + String cluster1 = "c1", cluster2 = "c2", site1 = "s1", site2 = "s2" ; + + for( int i = 0 ; i < clusters.size() ; i++ ) + { + if( clusters.get( i ).isIn( _g1) ) + { + cluster1 = clusters.get( i ).getName() ; + site1 = clusters.get( i ).getSite() ; + } + + if( clusters.get( i ).isIn( _g2) ) + { + cluster2 = clusters.get( i ).getName() ; + site2 = clusters.get( i ).getSite() ; + } + } + + // + + if( cluster1.compareTo( cluster2 ) == 0 ) + { + d = 1 ; + } else { + if( site1.compareTo( site2 ) == 0 ) + { + d = 2 ; + } else { + d = 3 ; + } + } + + return d ; + } + + + /** + * Return the list of computing nodes in the grid. + * @return The list of computing nodes + */ + public ArrayList getGNodes() + { + if( ! gnodesList_done ) + { + gnodesList = new ArrayList() ; + + for( int i = 0 ; i < clusters.size() ; i++ ) + { + ArrayList ar = clusters.get( i ).getGNodes() ; + + for( int j = 0 ; j < ar.size() ; j++ ) + { + gnodesList.add( ar.get( j ) ) ; + } + } + + gnodesList_done = true ; + } + + return gnodesList ; + } + + + /** + * Plop !! + * @param _gnodes + */ + public void updateGrid( ArrayList _gnodes ) + { + if( _gnodes != null && _gnodes.size() != 0 ) + { + for( int i = 0 ; i < _gnodes.size() ; i++ ) + { + + } + + gnodesList_done = false ; + } + } + + + /** + * Remove a computing node from the grid. + * @param _dead The node to be removed + */ + public void removeGNode( GNode _dead ) + { + if( _dead != null ) + { + if( _dead.getMapped() ) + { + String site = "", cluster = "" ; + + site = _dead.getSite() ; + cluster = _dead.getCluster() ; + + /* Removing GNode from its cluster */ + for( int j = 0 ; j < clusters.size() ; j++ ) + { + if( clusters.get( j ).getName().equals( cluster ) && clusters.get( j ).getSite().equals( site )) + { + clusters.get( j ).removeGNode( _dead ) ; + + break ; + } + } + } + + /* Removing the dead node from the global list */ + for( int i = 0 ; i < nb_node ; i++ ) + { + if( _dead.getId() == gnodesList.get( i ).getId() ) + { + gnodesList.remove( i ) ; + break ; + } + } + } + + nb_node-- ; + gnodesList_done = false ; + } + + + /** + * Compute the heterogeneity degree of the grid. + * This is based on a ratio between the average and the + * standard deviation of computing nodes' power. + * @return The heterogeneity degree of the grid + */ + public double getHeterogenityDegre() + { + double hd = -1 ; + + + return hd ; + } + + + /** + * Print a comprehensible text version of the grid. + */ + public void print() + { + System.out.println(); + System.out.println( "\t=> Grid composition :\n" ) ; + for( int i = 0 ; i < nb_cluster ; i++ ) + { + System.out.println( "\t\tCluster \""+ clusters.get(i).getName() +"\" : " + clusters.get(i).getNbGNode() ) ; + } + + System.out.println(); + } + +} + + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/LSM.java b/src/and/Mapping/LSM.java new file mode 100644 index 0000000..6dc6cd7 --- /dev/null +++ b/src/and/Mapping/LSM.java @@ -0,0 +1,420 @@ +package and.Mapping ; + + +import java.util.ArrayList; + + + + +/** + * Mapping algorithm based on the Edge-Cut principles + * @author Sébastien Miquée + * + */ +public class LSM extends Algo +{ + private static final long serialVersionUID = 1L; + + + private ArrayList atraiter ; + private ArrayList encours ; + private ArrayList fait ; +// private Architecture archi ; + private ArrayList liste_archi ; + private double dep_min ; + ArrayList mappees ; + + + /** + * Default constructor. + */ + public LSM() + { + super() ; + + atraiter = new ArrayList() ; + encours = new ArrayList() ; + fait = new ArrayList() ; +// archi = new Architecture() ; + liste_archi = new ArrayList() ; + dep_min = 0 ; + mappees = null ; + } + + + /** + * Constructor. + * @param _gr Application graph to be mapped on + * @param _gl Grid graph + */ + public LSM( Graph _gr, Grid _gl ) + { + super( _gr, _gl ) ; + + atraiter = new ArrayList() ; + encours = new ArrayList() ; + fait = new ArrayList() ; +// archi = new Architecture() ; + liste_archi = new ArrayList() ; + dep_min = 0 ; + mappees = null ; + } + + + /** + * Constructor. + * @param _gr Application graph to be mapped on + * @param _gl Grid graph + * @param _dep_min Minimum amount of local dependencies + */ + public LSM( Graph _gr, Grid _gl, double _dep_min ) + { + super( _gr, _gl ) ; + + atraiter = new ArrayList() ; + encours = new ArrayList() ; + fait = new ArrayList() ; +// archi = new Architecture() ; + liste_archi = new ArrayList() ; + dep_min = _dep_min ; + mappees = null ; + } + + + @SuppressWarnings("unchecked") + @Override + public void map() + { + System.out.println( "***********************************" ) ; + System.out.println( "* Launching the Edge-Cuts Mapping *" ) ; + System.out.println( "***********************************\n\n" ) ; + + /* Si le mapping est possible ... */ + if( gr.getNbGTask() <= gl.getNbGNode() ) + { + atraiter = (ArrayList) gr.getGraph().clone() ; + + liste_archi = construireArchi( gl, gr.getNbGTask() ) ; + + tri_dep() ; + + int indice = -1 ; + int nb_ok = 0 ; + double places = 0 ; + double dep = -1 ; + +// double moy = gr.getAverageDep() ; + GTask tmp = null ; + Cluster cl = null ; + + boolean change_cluster = false ; + +// System.out.println("nb cluster : "+liste_archi.get(0).getNbClusters() ); + + + while( nb_ok < gr.getNbGTask() ) + { + if( places == 0 || change_cluster ) + { + if( change_cluster ) + { + // Ajout du mapping + mp.addMapping( cl, mappees ) ; + } + + if( nb_ok < gr.getNbGTask() ) + { + // Changement de cluster + indice ++ ; + + if( indice == liste_archi.get(0).getNbClusters() ) + { + System.out.println( "No more cluster !! Impossible to respect constrains !! " ) ; + //System.exit( 2 ) ; + mp.initMapping() ; + return ; + } + + cl = null ; + cl = liste_archi.get(0).getArchi().get( indice ) ; + places = cl.getNbGNode() ; + change_cluster = false ; + mappees = null ; + mappees = new ArrayList() ; + } + } + + if( ( atraiter.size() + encours.size() ) <= places ) + { + for( int i = 0 ; i < atraiter.size() ; i++ ) + { + mappees.add( atraiter.get( i ) ) ; + nb_ok++ ; + places-- ; + } + + for( int i = 0 ; i < encours.size() ; i++ ) + { + mappees.add( encours.get( i ) ) ; + nb_ok++ ; + places-- ; + } + + atraiter = null ; + encours = null ; + + atraiter = new ArrayList() ; + encours = new ArrayList() ; + + mp.addMapping( cl, mappees ) ; + } + + if( encours.size() == 0 && atraiter.size() > 0 ) + { + encours.add( atraiter.get(0) ) ; + } + + if( encours.size() > 0 ) + { + tmp = encours.get( 0 ) ; + } + + +// if( ( calc_dep( tmp )* dep_min * moy ) <= places && places > 0 ) + dep = calc_dep( tmp ) ; + + if( dep != -1 && 1 + ( dep * dep_min ) <= places && places > 0 ) + { + places -- ; + nb_ok ++ ; + + ajoutDep( tmp ) ; + + mappees.add( tmp ) ; + fait.add( tmp ) ; + + atraiter.remove( tmp ) ; + encours.remove( tmp ) ; + } else { + change_cluster = true ; + } + + if( places == 0 ) + { + change_cluster = true ; + } + + tmp = null ; + +// try { +// Thread.sleep( 1000 ) ; +// } catch( InterruptedException e ) { +// e.printStackTrace() ; +// } +// +// mp.affiche() ; +// System.out.println( "reste : " + places + " sur " + cl.getNom() ) ; +// System.out.println( "nb_ok = " +nb_ok); +// System.out.println("etat : "+encours); +// System.out.println("etat2 : "+mappees); +// System.out.println( "etat3 : "+atraiter); + } + + + } else { + System.out.println( "\n\n!!! Mapping impossible ! There are more tasks than nodes !!!\n" ) ; + } + } + + /** + * + * @param _t + */ + private void ajoutDep( GTask _t ) + { + if( _t != null ) + { + GTask tmp = null ; + + for( int i = 0 ; i < _t.getNbDep() ; i++ ) + { + tmp = _t.getDependencies().get( i ) ; + + if( ! fait.contains( tmp ) && ! encours.contains( tmp ) + && tmp.getNbDep() < _t.getNbDep() ) + { +// System.out.println("haha => "+tmp.getNum() ) ; + int j = 0 ; + for( j = 0 ; j < encours.size() ; j++ ) + { + if( tmp.getNbDep() < encours.get( j ).getNbDep() ) + { + encours.add( j, tmp ) ; + j = encours.size() + 10 ; + } + } + + if( j == encours.size() ) + { + encours.add( tmp ) ; + } + + atraiter.remove( tmp ) ; + + tmp = null ; + } + } + } + } + + + /** + * + * @param _t + * @return + */ + private double calc_dep( GTask _t ) + { + int dep = 0 ; + int ext = 0 ; + + double res = -1 ; + + if( _t != null ) + { + for( int i = 0 ; i < _t.getNbDep() ; i++ ) + { + if( ! fait.contains( _t.getDependencies().get( i ) ) ) + { + dep ++ ; + } else { + if( ! mappees.contains( _t.getDependencies().get( i ) ) ) + { + ext++ ; + } + } + + } + + if( ( dep + ext ) < _t.getNbDep() * dep_min ) + { + res = 0 ; + } else { + res = dep + ( ext * 0.5 ) ; + } + +// System.out.println("dep de "+t.getNum()+" => " + res); + + } + + + return res ; + } + + + /** + * + * @param _gl + * @param _nbGTask + * @return + */ + @SuppressWarnings("unchecked") + private ArrayList construireArchi( Grid _gl, int _nbGTask ) + { + ArrayList ar = new ArrayList() ; + + ArrayList cl = (ArrayList) gl.getClusters().clone() ; + + + // Méthode à faire ! + Architecture a = new Architecture() ; + + for( int i = 0 ; i < cl.size() ; i ++ ) + { + a.addCluster( cl.get( i ) ) ; + } + + ar.add( a ) ; + + return ar ; + } + + /** + * + */ + @SuppressWarnings("unchecked") + private void tri_dep() + { + int nb_tache = gr.getNbGTask() ; + int nb_tri = 0 ; + int niveau = 0 ; + int niveau_fait = -1 ; + int temp = 0 ; + + ArrayList tmp = new ArrayList() ; + ArrayList tab = new ArrayList() ; + + while( nb_tri < nb_tache ) + { + // Recherche du niveau en décroissant + for( int i = 0 ; i < nb_tache ; i++ ) + { + temp = atraiter.get(i).getNbDep() ; + + if( niveau < temp ) + { + if( niveau_fait != -1 ) + { + if( temp < niveau_fait ) + { + niveau = temp ; + } + } else { + niveau = temp ; + } + } + } + + // Recherche des taches du niveau courrant + for( int i = 0 ; i < nb_tache ; i++ ) + { + if( atraiter.get( i ).getNbDep() == niveau ) + { + tmp.add( atraiter.get( i ) ) ; + tab.add( atraiter.get( i ).getNum() ) ; + + nb_tri ++ ; + } + } + + niveau_fait = niveau ; + niveau = 0 ; + + } + + atraiter = (ArrayList) tmp.clone() ; + +// for( int i = 0 ; i < nb_tache ; i++ ) +// { +// System.out.print( atraiter.get(i).getNum() +" " ) ; +// } +// System.out.println(); + } + + + @Override + public GNode replaceNode( GNode _dead, ArrayList _ag ) + { + return null; + } + + + @Override + public GNode getOtherGNode() { + // TODO Auto-generated method stub + return null; + } + +} + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/Mapping.java b/src/and/Mapping/Mapping.java new file mode 100644 index 0000000..c6c4060 --- /dev/null +++ b/src/and/Mapping/Mapping.java @@ -0,0 +1,261 @@ +package and.Mapping ; + +import java.io.Serializable; +import java.util.ArrayList; + + +/** + * Class representing the tasks mapping on clusters and/or nodes + * @author Sébastien Miquée + * + */ +public class Mapping implements Serializable +{ + private static final long serialVersionUID = 1L; + + /* Two kinds of Mapping, according to algorithms' goal */ + private ArrayList mapping ; + private ArrayList mapping2 ; + private int type ; // 0 : mapping task/node ; 1 : mapping tasks/cluster + + + /** + * Default constructor + */ + public Mapping() + { + mapping = new ArrayList() ; + mapping2 = new ArrayList() ; + type = -1 ; + } + + + /** + * Initialization of the Mapping variables + */ + public void initMapping() + { + mapping = new ArrayList() ; + mapping2 = new ArrayList() ; + type = -1 ; + } + + + /** + * Add in the mapping an association between a cluster and tasks set. + * @param c Cluster of the association + * @param at Tasks set to be associated + */ + public void addMapping( Cluster c, ArrayList at ) + { + mapping2.add( new Association( c, at ) ) ; + + if( type == 1 || type == -1 ) + { + type = 1 ; + } else { + System.err.println( "Mapping type mismatch !" ) ; + System.exit( 1 ) ; + } + + /** For the usage of algorithms which map groups of tasks on cluster **/ + for( int i = 0 ; i < at.size() ; i++ ) + { + insertMapping( new Association( c.nextGNode(), at.get( i ) ) ) ; + } + } + + + /** + * Add a mapping association in the general mapping. + * @param _a Association between a task and a node + */ + public void addMapping( Association _a ) + { + if( type == 0 || type == -1 ) + { + type = 0 ; + } else { + System.err.println( "Mapping type mismatch !" ) ; + System.exit( 1 ) ; + } + + insertMapping( _a ) ; + } + + + /** + * Insert the association at the right place. + * @param _a The association to be inserted + */ + public void insertMapping( Association _a ) + { + if( _a != null && _a.getGNode() != null && _a.getGTask() != null ) + { + int ind = _a.getGTask().getNum() ; + + mapping.add( ind - 1, _a ) ; + } + } + + + /** + * Remove a failed node from the mapping. + * @param _deadNode The failed node + * @return The task associated with the failed node + */ + public GTask removeGNode( GNode _deadNode ) + { + GTask gt = null ; + + for( int i = 0 ; i < mapping.size() ; i++ ) + { + if( mapping.get( i ).getGNode().getId() == _deadNode.getId() ) + { + gt = mapping.get( i ).getGTask() ; + mapping.remove( i ) ; + break ; + } + } + + return gt ; + } + + + /** + * Return the list of GNodes on which tasks are mapped, in order + * of the task number. + * @return The ordered list, according to the GTasks id, of GNodes involved in the mapping + */ + public ArrayList getMappedGNodes() + { + ArrayList ar = new ArrayList() ; + + if( mapping.size() != 0 ) + { +// if( type == 0 ) +// { +// ArrayList tmp = (ArrayList) mapping.clone() ; + + for( int i = 0 ; i < mapping.size() ; i++ ) + { +// for( int j = 0 ; j < tmp.size() ; j++ ) +// { +// if( tmp.get( j ).getGTask().getNum() == i ) +// { + ar.add( mapping.get( i ).getGNode() ) ; +// tmp.remove( j ) ; +// j = tmp.size() + 2 ; +// } +// } + } +// } +// +// if( type == 1 ) +// { +// ArrayList tmp = (ArrayList) mapping2.clone() ; +// +// for( int i = 0 ; i < mapping2.size() ; i++ ) +// { +// for( int j = 0 ; j < tmp.size() ; j++ ) +// { +// if( tmp.get( j ).getGTask().getNum() == i ) +// { +// ar.add( tmp.get( j ).getGNode() ) ; +// tmp.remove( j ) ; +// j = tmp.size() + 2 ; +// } +// } +// } +// } + } + + return ar ; + } + + + /** + * Print the status of the mapping done, according to its type. + */ + public void print() + { + System.out.println(); + System.out.println( "\t=> Mapping done :\n" ) ; + + if( type == 0 ) + { + ArrayList ar = getMappedGNodes() ; + + for( int i = 0 ; i < ar.size() ; i++ ) + { + System.out.println( "Task " + i + " on " + ar.get( i ).getName() ) ; + } + + System.out.println() ; + } + + if( type == 1 ) + { + for( int i = 0 ; i < mapping2.size() ; i++ ) + { + System.out.print( "\t\tCluster \"" + mapping2.get( i ).getCluster().getName() + "\" => { ") ; + for( int j = 0 ; j < mapping2.get( i ).getGtask().size() ; j++ ) + { + System.out.print( mapping2.get( i ).getGtask().get( j ).getNum() ) ; + + if( j != mapping2.get( i ).getGtask().size() - 1 ) + { + System.out.print( ", " ) ; + } + } + System.out.println( " } " ) ; + System.out.println() ; + } + } + } + + + /** + * Return the mapping done. + * @return The mapping + */ + public ArrayList getMapping() + { + return mapping ; + } + + + /** + * Return the amount of external tasks dependencies, in cluster point of view. + * @return The amount of external dependencies + */ + public int calcDepExt() + { + int depExt = 0 ; + ArrayList ar ; + ArrayList deps ; + + for( int i = 0 ; i < mapping.size() ; i++ ) + { + ar = mapping.get(i).getGtask() ; + + for( int j = 0 ; j < ar.size() ; j++ ) + { + deps = ar.get(j).getDependencies() ; + + for( int k = 0 ; k < deps.size() ; k++ ) + { + if( ! ar.contains( deps.get(k) ) ) + { + depExt++ ; + } + } + } + } + + return ( depExt / 2 ) ; + } + +} + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/QM.java b/src/and/Mapping/QM.java new file mode 100644 index 0000000..f437ec7 --- /dev/null +++ b/src/and/Mapping/QM.java @@ -0,0 +1,525 @@ +package and.Mapping ; + + +import java.util.ArrayList; +import java.util.Random; + + +/** + * Implementation of the AIAC Quick Quality Map (AIAC-QM) algorithm + * @author Sébastien Miquée + * @version 1.0 + */ +public class QM extends Algo +{ + private static final long serialVersionUID = 1L; + + + private ArrayList atraiter ; + private ArrayList archi ; + private double f ; // search factor + + + /** + * Default constructor. + */ + public QM() + { + super() ; + } + + + /** + * Constructor + * @param _gr Application graph to be mapped on + * @param _gd Grid graph + * @param _f Search factor + */ + public QM( Graph _gr, Grid _gd, double _f ) + { + super( _gr, _gd ) ; + + f = _f ; + } + + /** + * + * @return + */ + private ArrayList sortInitGNode() + { + ArrayList grn = null ; + + if( gl != null ) + { + grn = new ArrayList() ; + + ArrayList tmp = gl.getGNodes() ; + + grn.add( tmp.get( 0 ) ) ; + + boolean ok ; + + for( int i = 1 ; i < tmp.size() ; i++ ) + { + ok = false ; + + for( int j = 0 ; j < grn.size() ; j++ ) + { + if( tmp.get( i ).getPower() > grn.get( j ).getPower() ) + { + grn.add( j, tmp.get( i ) ) ; + ok = true ; + break ; + } + } + + if( ok == false ) + { + grn.add( tmp.get( i ) ) ; + } + } + } + + return grn ; + } + + + private ArrayList listToGTask2( Graph _gr ) + { + ArrayList gr2 = null ; + + if( _gr != null ) + { + gr2 = new ArrayList() ; + + for( int i = 0 ; i < _gr.getNbGTask() ; i++ ) + { + gr2.add( new GTask2( _gr.getGraph().get( i ) ) ) ; + } + } + + return gr2 ; + } + + + @Override + public void map() + { + /* If the mapping is possible ... */ + if( gr.getNbGTask() <= gl.getNbGNode() ) + { + atraiter = listToGTask2( gr ) ; + archi = sortInitGNode() ; + + /** Local Variables **/ + GNode nc = null ; + double yc = -1 ; + GNode nb = null ; + double yb = -1 ; + GNode nr = null ; + double yr = -1 ; + double ynb = -1 ; + + + System.out.println( "*******************************************" ) ; + System.out.println( "* Launching the AIAC-QM Mapping algorithm *" ) ; + System.out.println( "*******************************************\n\n" ) ; + + /** Initial values **/ + int r = 1 ; // Number of rounds + int n = gr.getNbGTask() ; // Number of tasks + + /** Initial mapping **/ + initMapping() ; + + /** Main loop **/ + while( isOneMoveable() ) + { + for( int ti = 0 ; ti < atraiter.size() ; ti++ ) + { + if( atraiter.get( ti ).isMoveable() ) + { + nc = atraiter.get( ti ).getMapedOn() ; + yc = atraiter.get( ti ).getExecTime() ; + nb = nc ; + yb = yc ; + + /** Search a node to map on **/ + for( int k = 0 ; k < ( f * n / r ) ; k++ ) + { + nr = selectRandomGNode( n, r ) ; + yr = execTimeOn( atraiter.get( ti ).clone(), nr ) ; + + if( yr < yb ) + { + nb = nr ; + yb = yr ; + } + } + + /** Research of the neighbours' nodes **/ + ArrayList neighbours = researchNeighbours( atraiter.get( ti ), 1 ) ; + + for( int ni = 0 ; ni < neighbours.size() ; ni++ ) + { + ynb = execTimeOn( atraiter.get( ti ).clone(), neighbours.get( ni ) ) ; + + if( ynb < yb ) + { + nb = neighbours.get( ni ) ; + yb = ynb ; + } + } + + + /** Mapping of the task **/ + if( ! nb.equals( nc ) ) + { + GTask2 t_ = taskOn( nb ) ; + if( t_ != null && t_.isMoveable() ) + { + t_.setGNode( null ) ; + } + + atraiter.get( ti ).setGNode( nb ) ; + + updateExecTimeNeighbours( atraiter.get( ti ) ) ; + } + } + + /** The task is fixed on this node **/ + atraiter.get( ti ).setMoveable( false ) ; + + /** If all tasks have been considered **/ + if( ti == atraiter.size() - 1 ) + { + r++ ; + } + } + } + + /** Save the Mapping **/ + for( int i = 0 ; i < atraiter.size() ; i++ ) + { + mp.addMapping( new Association( atraiter.get( i ).getMapedOn(), atraiter.get( i ).getGTask() ) ) ; + } + + } else { + System.err.println( "\n\n!!! Unable to map application !\n\n" ) ; + } + } + + /** + * + * @param _nb + * @return + */ + private GTask2 taskOn( GNode _nb ) + { + for( int i = 0 ; i < atraiter.size() ; i++ ) + { + if( atraiter.get( i ).getMapedOn().equals( _nb ) ) + { + return atraiter.get( i ) ; + } + } + + return null; + } + + /** + * + * @param _g + * @param _deep + * @return + */ + private ArrayList researchNeighbours( GTask2 _g, double _deep) + { + ArrayList nb = new ArrayList() ; + ArrayList neighbours = new ArrayList() ; + + for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ ) + { + neighbours.add( atraiter.get( _g.getGTask().getDependencies().get( i ).getNum() ) ) ; + } + + for( int i = 0 ; i < archi.size() ; i++ ) + { + for( int j = 0 ; j < neighbours.size() ; j++ ) + { + GNode tmp = neighbours.get( j ).getMapedOn() ; + + if( gl.getDistance( tmp, archi.get( i ) ) <= _deep && ! nb.contains( tmp ) ) + { + nb.add( tmp ) ; + } + } + } + + return nb ; + } + + + /** + * Initialization of the mapping. Each task is mapped on computing + * nodes in order of their rank. + */ + private void initMapping() + { + for( int i = 0 ; i < atraiter.size() ; i++ ) + { + atraiter.get( i ).setGNode( archi.get( i ) ) ; + } + } + + + /** + * + * @param _g + * @param _n + * @return + */ + private double execTimeOn( GTask2 _g, GNode _n ) + { + _g.setGNode( _n ) ; + + return calcExecTime( _g ) ; + } + + /** + * + * @param _n + * @param _r + * @return + */ + private GNode selectRandomGNode( int _n, int _r ) + { + GNode g = null ; + + Random rand = new Random() ; + + g = archi.get( rand.nextInt( _n / _r ) ) ; + + while( isTaskNotMoveableOn( g ) ) + { + g = archi.get( rand.nextInt( _n / _r ) ) ; + } + + return g ; + } + + + /** + * + * @param _g + * @return + */ + private boolean isTaskNotMoveableOn( GNode _g ) + { + for( int i = 0 ; i < atraiter.size() ; i++ ) + { + if( atraiter.get( i ).getMapedOn().equals( _g ) && ! atraiter.get( i ).isMoveable() ) + { + return true ; + } + } + + return false ; + } + + + /** + * + * @return + */ + private boolean isOneMoveable() + { + if( atraiter != null && atraiter.size() > 0 ) + { + for( int i = 0 ; i < atraiter.size() ; i++ ) + { + if( atraiter.get( i ).isMoveable() ) + { + return true ; + } + } + } + + return false ; + } + + + /** + * + * @param _g + * @return + */ + private double calcExecTime( GTask2 _g ) + { + double w = -1 ; + + if( _g != null ) + { + // Weight of computation + w = ( _g.getGTask().getWeight() / _g.mappedOn.getPower() ) ; + + // Weight of communications + int tab[] = new int[ _g.getGTask().getNbDep() ] ; + for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ ) + { + tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ; + } + + for( int i = 0 ; i < tab.length ; i++ ) + { + double tmp = gl.getDistance( _g.getMapedOn(), atraiter.get( tab[i] ).getMapedOn() ) ; + + if( tmp >= 0 ) + { + w += tmp ; + } + } + } + + return w ; + } + + + /** + * + * @param _g + */ + private void updateExecTime( GTask2 _g ) + { + double w = calcExecTime( _g ) ; + + if( w >= 0 ) + { + if( w > _g.getExecTime() ) + { + _g.setMoveable( true ) ; + } + + _g.setExecTime( w ) ; + } + } + + + /** + * + * @param _g + */ + private void updateExecTimeNeighbours( GTask2 _g ) + { + int tab[] = new int[ _g.getGTask().getNbDep() ] ; + for( int i = 0 ; i < _g.getGTask().getNbDep() ; i++ ) + { + tab[ i ] = _g.getGTask().getDependencies().get( i ).getNum() ; + } + + for( int i = 0 ; i < tab.length ; i++ ) + { + updateExecTime( atraiter.get( tab[i] ) ) ; + } + } + + + + /** Intern class **/ + /** + * Temporary class. + */ + private class GTask2 + { + private GTask g ; + private boolean moveable ; + private double execTime ; + private GNode mappedOn ; + + public GTask2() + { + g = null ; + moveable = false ; + execTime = -1 ; + mappedOn = null ; + } + + public GTask2( GTask _g ) + { + g = _g ; + moveable = false ; + execTime = -1 ; + mappedOn = null ; + } + + public boolean isMoveable() + { + return moveable ; + } + + public void setMoveable( boolean b ) + { + moveable = b ; + } + + public void setGNode( GNode _g ) + { + mappedOn = _g ; + } + + + public GTask getGTask() + { + return g ; + } + + + public double getExecTime() + { + return execTime ; + } + + + public void setExecTime( double _d ) + { + execTime = _d ; + } + + public GNode getMapedOn() + { + return mappedOn ; + } + + + public GTask2 clone() + { + GTask2 g_new = new GTask2() ; + g_new.execTime = this.execTime ; + g_new.g = this.g ; + g_new.mappedOn = this.mappedOn ; + g_new.moveable = this.moveable ; + + return g_new ; + } + } + + + + @Override + public GNode replaceNode(GNode _dead, ArrayList _ag ) + { + return null; + } + + + @Override + public GNode getOtherGNode() { + // TODO Auto-generated method stub + return null; + } +} + + + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/Simple.java b/src/and/Mapping/Simple.java new file mode 100644 index 0000000..e320082 --- /dev/null +++ b/src/and/Mapping/Simple.java @@ -0,0 +1,135 @@ +package and.Mapping ; + + +import java.util.ArrayList; + + +/** + * Implementation of Simple Mapping algorithm + * @author Sébastien Miquée + * @version 1.0 + */ +public class Simple extends Algo +{ + private static final long serialVersionUID = 1L; + + + private ArrayList atraiter ; + private ArrayList archi ; + + /** + * Default constructor. + */ + public Simple() + { + super() ; + } + + + /** + * Constructor. + * @param _gr Application graph to be mapped on + * @param _gd Grid graph + */ + public Simple( Graph _gr, Grid _gd ) + { + super( _gr, _gd ) ; + } + + /** + * + * @return + */ + private ArrayList sortInitGNode() + { + ArrayList grn = null ; + + if( gl != null ) + { + grn = new ArrayList() ; + + // Tri des clusters suivant leur taille + ArrayList cl = gl.getClusters() ; + ArrayList cl2 = new ArrayList() ; + + int max = 0 ; + Cluster c = null ; + Cluster c2 = null ; + + while( cl2.size() != gl.getNbCluster() ) + { + + max = 0 ; + + for( int i = 0 ; i < cl.size() ; i++ ) + { + c = cl.get( i ) ; + if( c.getNbGNode() > max ) + { + c2 = c ; + max = c.getNbGNode() ; + } + } + + cl2.add( c2 ) ; + cl.remove( c2 ) ; + } + + for( int i = 0 ; i < cl2.size() ; i++ ) + { + Cluster tmp = cl2.get( i ) ; + + for( int j = 0 ; j < tmp.getNbGNode() ; j++ ) + { + grn.add( tmp.getGNodes().get( j ) ) ; + } + } + } + + return grn ; + } + + + @Override + public void map() + { + /* If the mapping is possible ... */ + if( gr.getNbGTask() <= gl.getNbGNode() ) + { + archi = sortInitGNode() ; + atraiter = gr.getGraph() ; + + System.out.println( "******************************************" ) ; + System.out.println( "* Launching the Simple Mapping algorithm *" ) ; + System.out.println( "******************************************\n\n" ) ; + + /** Save the Mapping **/ + for( int i = 0 ; i < atraiter.size() ; i++ ) + { + mp.addMapping( new Association( archi.get( i ), atraiter.get( i ) ) ) ; + } + + } else { + System.err.println( "\n\n!!! Unable to map application !\n\n" ) ; + } + } + + + @Override + public GNode replaceNode(GNode replaced, ArrayList _ag ) + { + // TODO + return null ; + } + + + @Override + public GNode getOtherGNode() { + // TODO Auto-generated method stub + return null; + } +} + + + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/ diff --git a/src/and/Mapping/Utils.java b/src/and/Mapping/Utils.java new file mode 100644 index 0000000..2127186 --- /dev/null +++ b/src/and/Mapping/Utils.java @@ -0,0 +1,425 @@ +package and.Mapping ; + + +import java.io.FileInputStream; +import java.io.FileNotFoundException; +import java.io.FileOutputStream; +import java.io.OutputStreamWriter; +import java.io.PrintWriter; +import java.net.InetAddress; +import java.util.ArrayList; + +import org.hyperic.sigar.CpuInfo; +import org.hyperic.sigar.Mem; +import org.hyperic.sigar.Sigar; +import org.hyperic.sigar.SigarException; + +import com.thoughtworks.xstream.XStream; +import com.thoughtworks.xstream.io.xml.DomDriver; + + + +/** + * Class providing some tools to the library + * @author Séastien Miquée + */ +public class Utils +{ +// public static String getOS() +// { +// return System.getProperty( "os.name" ) ; +// } + + + /** + * Creation of the representation of the node in the Mapping point of view. It needs + * some information about the computing node, which will be exploited by mapping + * algorithms. + * @return A node from the Mapping library + */ + public static GNode createGNode() + { + GNode n = new GNode() ; + int nbCore = 0 ; + int frequency = 0 ; + int memory = 0 ; + String name = "" ; + +// InputStream ips ; +// InputStreamReader ipsr ; +// BufferedReader br ; +// String ligne ; +// +// +// String fichier_cpu = "" ; +// String fichier_mem = "" ; +// +// +// if( getOS().equals( "Linux" ) ) +// { +// fichier_cpu = "/proc/cpuinfo" ; +// fichier_mem = "/proc/meminfo" ; +// +// /* Lecture des informations processeur */ +// try{ +// ips = new FileInputStream( fichier_cpu ) ; +// ipsr = new InputStreamReader( ips ) ; +// br = new BufferedReader( ipsr ) ; +// +// +// while( ( ligne = br.readLine() ) != null ) +// { +// if( ligne.contains( "processor" ) ) +// { +// nb_coeurs ++ ; +// } +// +// if( ligne.contains("cpu MHz") ) +// { +// String tab[] = new String[2] ; +// +// tab = ligne.split( ":" ) ; +// +// frequence = ( int ) Double.parseDouble( tab[1] ) ; +// } +// +// } +// +// br.close() ; +// ipsr.close() ; +// ips.close() ; +// +// } catch( Exception e ) { +// System.out.println( e.toString() ) ; +// } +// +// +// /* Lecture des informations mémoire */ +// try { +// ips = new FileInputStream( fichier_mem ) ; +// ipsr = new InputStreamReader( ips ) ; +// br = new BufferedReader( ipsr ) ; +// +// while( ( ligne = br.readLine() ) != null ) +// { +// if( ligne.contains("MemTotal") ) +// { +// String tab[] = new String[2] ; +// +// tab = ligne.split( ":" ) ; +// ligne = tab[1].trim() ; +// tab = ligne.split( " " ) ; +// memoire = ( int ) Double.parseDouble( tab[0] ) ; +// } +// +// } +// +// br.close() ; +// ipsr.close() ; +// ips.close() ; +// +// } catch( Exception e ) { +// System.out.println( e.toString() ) ; +// } +// +// } + + /* Creating the hardware information retriever */ + Sigar sigar = new Sigar() ; + + /* CPU information */ + CpuInfo cpuinfo[] = null ; + try { + cpuinfo = sigar.getCpuInfoList(); + } catch (SigarException e) { + System.err.println( "Unable to retrieve CPU information !" ) ; + e.printStackTrace(); + System.exit( 1 ) ; + } + + int tmp = 0 ; + for( int i = 0 ; i < cpuinfo.length ; i++ ) + { + nbCore++ ; + tmp+= cpuinfo[i].getMhz() ; + } + + /* The frequency is the average of cores frequencies */ + frequency = tmp / nbCore ; + + + /* Memory information */ + Mem mem = null ; + try { + mem = sigar.getMem() ; + } catch (SigarException e) { + System.err.println( "Unable to retrieve memory information !" ) ; + e.printStackTrace(); + System.exit( 1 ) ; + } + + memory = (int)mem.getFree()/1000 ; + + + /* Host name */ + try { + InetAddress addr = InetAddress.getLocalHost() ; + name = new String( addr.getCanonicalHostName() ) ; + } catch( final Exception e ) { + System.err.println( "Unalbe to retrieve host name !" ) ; + e.printStackTrace(); + System.exit( 1 ) ; + } + + + /* Updating node information */ + n.setFrequency( frequency ) ; + n.setMemory( memory ) ; + n.setNb_cores( nbCore ) ; + n.setName( name ) ; + + return n ; + } + + /** + * Creation of the representation of the grid, according to clusters into sites. + * This representation may only fit on Grid'5000 like architectures (with computing + * nodes name based on the following pattern |cluster_name|id_of_node_into_cluster|.|site_of_cluster|.|organisation|.*|). + * @param _an the list of computing nodes connected + * @return the grid's architecture + */ + public static Grid createGridG5k( ArrayList _an ) + { + Grid gr = new Grid() ; + + if( _an != null ) + { + String temp ; + String nom, cluster, site ; + + + ArrayList clusters = new ArrayList() ; + + for( int i = 0 ; i < _an.size() ; i++ ) + { + /* Variables edition */ + String tab[] = new String[ 5 ] ; + + temp = _an.get( i ).getName().trim().replace('.', '!' ) ; + + tab = temp.split( "!" ) ; + + nom = tab[ 0 ] ; + site = tab[ 1 ] ; + + tab = nom.split( "-" ) ; + + // IUT + //cluster = "iut" ; + + // G5K + cluster = tab[ 0 ] ; + + //System.out.println( nom + " dans " + cluster + " du site " + site ) ; + + + /* Insertion du noeud dans son cluster */ + boolean trouve = false ; + + for( int j = 0 ; j < clusters.size() ; j++ ) + { + if( clusters.get( j ).getName().equals( cluster ) && clusters.get( j ).getSite().equals( site )) + { + _an.get( i ).setInCluster( true ) ; + _an.get( i ).setSite( clusters.get( j ).getSite() ) ; + _an.get( i ).setCluster( clusters.get( j ).getName() ) ; + clusters.get( j ).addGNode( _an.get( i ) ) ; + trouve = true ; + + break ; + } + } + + if( ! trouve ) + { + Cluster cl = new Cluster() ; + + cl.setName( cluster ) ; + cl.setSite( site ) ; + + _an.get( i ).setInCluster( true ) ; + _an.get( i ).setSite( site ) ; + _an.get( i ).setCluster( cluster ) ; + + cl.addGNode( _an.get( i ) ) ; + + clusters.add( cl ) ; + } + } + + gr.addClusters( clusters ) ; + + } + + return gr ; + } + + + /** + * Write the Grid object in an XML file. + * @param _gl Grid graph to be write + * @param _file File's name + * @param _path File's path + */ + public static void writeGrid( Grid _gl, String _file, String _path ) + { + if ( ! _file.equals( "" ) && ! _file.endsWith( ".xml" ) ) + { + _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier + } + + if( ! _file.equals( "" ) ) + { + String path = "" ; + + if( _path.length() != 0 ) + { + path = _path+"/"+_file ; + } else { + path = new String( "./" + _file ) ; + } + + XStream xstream = new XStream( new DomDriver() ) ; + + String xml = xstream.toXML( _gl ) ; + + PrintWriter ecrivain = null ; + + try { + ecrivain = new PrintWriter( new OutputStreamWriter( new FileOutputStream( path ), "UTF8" ) ) ; + + ecrivain.println( "" ) ; + ecrivain.println( xml ) ; + + ecrivain.close() ; + } catch( Exception e ) { + System.err.println( "\nError during the write opération !\n" ) ; + e.printStackTrace() ; + } + } + } + + /** + * Write an application Graph in a file. + * @param _gr Application Graph to be write + * @param _file File's name + * @param _path File's path + */ + public static void writeGraph( Graph _gr, String _file, String _path ) + { + if ( ! _file.equals( "" ) && ! _file.endsWith( ".xml" ) ) + { + _file = _file + ".xml"; // On ajoute l'extension xml au nom du fichier + } + + if( ! _file.equals( "" ) ) + { + String path = "" ; + + if( _path.length() != 0 ) + { + path = _path+"/"+_file ; + } else { + path = new String( "./" + _file ) ; + } + + XStream xstream = new XStream( new DomDriver() ) ; + + String xml = xstream.toXML( _gr ) ; + + PrintWriter ecrivain = null ; + + try { + ecrivain = new PrintWriter( new OutputStreamWriter( new FileOutputStream( path ), "UTF8" ) ) ; + + ecrivain.println( "" ) ; + ecrivain.println( xml ) ; + + ecrivain.close() ; + } catch( Exception e ) { + System.err.println( "\nError during the write opération !\n" ) ; + e.printStackTrace() ; + } + } + } + + + /** + * Read an application Graph from a file. + * @param _file File's name + * @return The application Graph read + */ + public static Graph readGraph( String _file ) + { + if ( _file.equals( "" ) || ! _file.endsWith( ".xml" ) ) + { + System.err.println( "Bad file !\n" ) ; + return null ; + } + + Graph gr = null ; + + XStream xstream = new XStream( new DomDriver() ) ; + + try { + gr = (Graph) xstream.fromXML( new FileInputStream( _file ) ) ; + } catch( FileNotFoundException e ) { + System.err.println( "File not found !\n" ) ; + e.printStackTrace(); + return null ; + } catch( ClassCastException e ) { + System.err.println( "The file does not contain a Graph" ) ; + e.printStackTrace() ; + return null ; + } + + return gr ; + } + + + /** + * Read a Grid graph from a file. + * @param _file File's name + * @return The Grid graph read + */ + public static Grid readGrid( String _file ) + { + if ( _file.equals( "" ) || ! _file.endsWith( ".xml" ) ) + { + System.err.println( "Bad file !\n" ) ; + return null ; + } + + Grid gr = null ; + + XStream xstream = new XStream( new DomDriver() ) ; + + try { + gr = (Grid) xstream.fromXML( new FileInputStream( _file ) ) ; + } catch( FileNotFoundException e ) { + System.err.println( "File not found !\n" ) ; + e.printStackTrace(); + return null ; + } catch( ClassCastException e ) { + System.err.println( "The file does not contain a Grid" ) ; + e.printStackTrace() ; + return null ; + } + + return gr ; + } + +} + + +/** La programmation est un art, respectons ceux qui la pratiquent !! **/