From 6917abb37fd33708a5b71554d6cf9e866ba8fe4e Mon Sep 17 00:00:00 2001 From: thiery Date: Wed, 5 Jul 2006 13:48:42 +0000 Subject: [PATCH] Add a SimDag example (mixtesim) created from an old SG 2.18 example git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@2484 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- examples/simdag/mixtesim/Makedefs | 21 + examples/simdag/mixtesim/Makefile | 17 + examples/simdag/mixtesim/bin/dagfile | 34 ++ examples/simdag/mixtesim/bin/gridfile.xml | 167 ++++++ .../simdag/mixtesim/include/list_scheduling.h | 55 ++ .../include/mixtesim_datastructures.h | 131 +++++ .../mixtesim/include/mixtesim_prototypes.h | 23 + .../simdag/mixtesim/include/mixtesim_types.h | 14 + examples/simdag/mixtesim/src/Makefile | 19 + examples/simdag/mixtesim/src/dag.c | 460 ++++++++++++++++ examples/simdag/mixtesim/src/grid.c | 518 ++++++++++++++++++ examples/simdag/mixtesim/src/heft.c | 445 +++++++++++++++ .../mixtesim/src/list_scheduling_util.c | 172 ++++++ examples/simdag/mixtesim/src/main.c | 330 +++++++++++ 14 files changed, 2406 insertions(+) create mode 100644 examples/simdag/mixtesim/Makedefs create mode 100644 examples/simdag/mixtesim/Makefile create mode 100644 examples/simdag/mixtesim/bin/dagfile create mode 100644 examples/simdag/mixtesim/bin/gridfile.xml create mode 100644 examples/simdag/mixtesim/include/list_scheduling.h create mode 100644 examples/simdag/mixtesim/include/mixtesim_datastructures.h create mode 100644 examples/simdag/mixtesim/include/mixtesim_prototypes.h create mode 100644 examples/simdag/mixtesim/include/mixtesim_types.h create mode 100644 examples/simdag/mixtesim/src/Makefile create mode 100644 examples/simdag/mixtesim/src/dag.c create mode 100644 examples/simdag/mixtesim/src/grid.c create mode 100644 examples/simdag/mixtesim/src/heft.c create mode 100644 examples/simdag/mixtesim/src/list_scheduling_util.c create mode 100644 examples/simdag/mixtesim/src/main.c diff --git a/examples/simdag/mixtesim/Makedefs b/examples/simdag/mixtesim/Makedefs new file mode 100644 index 0000000000..208af199fe --- /dev/null +++ b/examples/simdag/mixtesim/Makedefs @@ -0,0 +1,21 @@ +# System-dependent values determined by the configuration script. + +# +# Should not print info about cd-ing to directories +# +.SILENT: + +# +# Variables +# +SIMGRID_PATH = $(HOME) +MY_MIXTESIM_ROOT = $(HOME)/simgrid/simgrid/examples/simdag/mixtesim +CFLAGS = -I$(MY_MIXTESIM_ROOT)/include \ + -I$(SIMGRID_PATH)/include \ + -finline-functions -g -Wall -Werror +CC = gcc +LD = gcc + +LIBS = -lm + +SIMGRIDLIB = $(HOME)/lib/libsimgrid.so diff --git a/examples/simdag/mixtesim/Makefile b/examples/simdag/mixtesim/Makefile new file mode 100644 index 0000000000..0e103ea6ea --- /dev/null +++ b/examples/simdag/mixtesim/Makefile @@ -0,0 +1,17 @@ +include ./Makedefs + +default: pre executable + +pre: + @rm -f ./make.log + @echo "Make log for Mixtesim" > ./make.log + +executable: + cd src; make all + +wc: + @ wc -l `find . -name "*.[ch]"` | grep total + +clean: + @ cd src; $(MAKE) clean + @ /bin/rm -f ./bin/mixtesim diff --git a/examples/simdag/mixtesim/bin/dagfile b/examples/simdag/mixtesim/bin/dagfile new file mode 100644 index 0000000000..f7fb6980e3 --- /dev/null +++ b/examples/simdag/mixtesim/bin/dagfile @@ -0,0 +1,34 @@ +NODE_COUNT 32 +NODE 0 1 ROOT 0.0 +NODE 1 2,3,4,5,6,7 COMPUTATION 13512840 +NODE 2 8 TRANSFER 2250000 +NODE 3 9 TRANSFER 2250000 +NODE 4 10 TRANSFER 2250000 +NODE 5 11 TRANSFER 2250000 +NODE 6 12 TRANSFER 2250000 +NODE 7 13 TRANSFER 2250000 +NODE 8 14,15 COMPUTATION 17210020 +NODE 14 26 TRANSFER 1000000 +NODE 15 27 TRANSFER 1000000 +NODE 9 16,17 COMPUTATION 16452590 +NODE 16 26 TRANSFER 1562500 +NODE 17 27 TRANSFER 1562500 +NODE 10 18,19 COMPUTATION 45283690 +NODE 18 26 TRANSFER 2250000 +NODE 19 27 TRANSFER 2250000 +NODE 11 20,21 COMPUTATION 11806970 +NODE 20 26 TRANSFER 0562500 +NODE 21 27 TRANSFER 0562500 +NODE 12 22,23 COMPUTATION 14832260 +NODE 22 26 TRANSFER 2250000 +NODE 23 27 TRANSFER 2250000 +NODE 13 24,25 COMPUTATION 18832050 +NODE 24 26 TRANSFER 1062500 +NODE 25 27 TRANSFER 1062500 +NODE 26 28 COMPUTATION 33674670 +NODE 28 30 TRANSFER 0300000 +NODE 27 29 COMPUTATION 11186360 +NODE 29 30 TRANSFER 0250000 +NODE 30 31 COMPUTATION 10941360 +NODE 31 - END 0.0 +# DAG END diff --git a/examples/simdag/mixtesim/bin/gridfile.xml b/examples/simdag/mixtesim/bin/gridfile.xml new file mode 100644 index 0000000000..ee2ad5ed31 --- /dev/null +++ b/examples/simdag/mixtesim/bin/gridfile.xml @@ -0,0 +1,167 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/examples/simdag/mixtesim/include/list_scheduling.h b/examples/simdag/mixtesim/include/list_scheduling.h new file mode 100644 index 0000000000..13bbf67d53 --- /dev/null +++ b/examples/simdag/mixtesim/include/list_scheduling.h @@ -0,0 +1,55 @@ +#ifndef LIST_SCHEDULING_H +#define LIST_SCHEDULING_H + +#include +#include +#include + +void allocateNodeAttributes(DAG dag); +void freeNodeAttributes(DAG dag); +void allocateHostAttributes(); +void freeHostAttributes(); +void implementSimgridSchedule(DAG dag, Node *list); + +/* Link local_link; */ + +#define LIST_SCHEDULING_NOT_SCHEDULED 0 +#define LIST_SCHEDULING_READY 1 +#define LIST_SCHEDULING_SCHEDULED 2 +#define LIST_SCHEDULING_RUNNING 3 + + + +/**************/ +/* Attributes */ +/**************/ + +typedef struct _NodeAttribute *NodeAttribute; +typedef struct _HostAttribute *HostAttribute; + +struct _NodeAttribute { + SD_workstation_t host; /* The host on which the node has been scheduled */ + SD_link_t link; /* The link on which the transfer is running */ + double start; /* time the task is supposed to start */ + double finish; /* time the task is supposed to finish */ + int state; /* scheduled, not scheduled, ready */ + double SL; + int tag; + + double mean_cost; /* used by heft */ + double rank_u; /* used by heft */ + + double data_available; +}; + +struct _HostAttribute { + double first_available; + int nb_nodes; + int *nodes; + int state; +}; + +#define NODE_ATTR(x) ((NodeAttribute)(x->metadata)) +#define HOST_ATTR(x) ((HostAttribute)(SD_workstation_get_data(x))) + +#endif diff --git a/examples/simdag/mixtesim/include/mixtesim_datastructures.h b/examples/simdag/mixtesim/include/mixtesim_datastructures.h new file mode 100644 index 0000000000..9dbf2fcd8a --- /dev/null +++ b/examples/simdag/mixtesim/include/mixtesim_datastructures.h @@ -0,0 +1,131 @@ +#ifndef MIXTESIM_DATASTRUCTURES_H +#define MIXTESIM_DATASTRUCTURES_H + +#include "simdag/simdag.h" +#include "mixtesim_types.h" + +/* NODE structure */ +struct _Node { + /* nodes that must complete before this node can start */ + int nb_parents; + Node *parents; /* array of size nb_parents */ + + /* nodes that cannot start until this node has completed */ + int nb_children; + Node *children; /* array of size nb_children */ + + /* index of this node in the DAG->nodes array */ + int global_index; + + node_t type; /* node type: TRANSFER or COMMUNICATION */ + + double cost; /* cost of the computation */ + /* or file transfer on a resource */ + + /* Pointer to the SIMGRID Task that will + * be used for the simulation. The abstract task should + * be created upon creation of this node, and will be + * de-allocated when SG_shutdown() is called + */ + SD_task_t sd_task; + + void *metadata; /* For use by the scheduling algorithms */ +}; + +Node newNode(); /* Allocates memory for a node */ +void freeNode(); /* Free memory for a node */ +void printNode(DAG dag, Node node); /* print node info */ + +/* DAG structure */ +struct _DAG { + Node root; /* first node */ + Node end; /* last node */ + + /* Array of nodes, for direct access */ + int nb_nodes; + Node *nodes; /* array of size nb_nodes */ +}; + +DAG parseDAGFile(char *filename); /* Construct a DAG from a */ + /* DAG description file */ +DAG newDAG(); /* allocate memory for a DAG, called by parseDAGFile() */ +void freeDAG(DAG dag); /* free memory for a DAG */ +void printDAG(DAG dag); /* prints DAG info */ + +/* /\* HOST structure *\/ */ +/* struct _Host { */ +/* /\* index in the Grid->hosts array *\/ */ +/* int global_index; */ + +/* /\* in which cluster this host is *\/ */ +/* int cluster; */ + +/* /\* relative speed of the host *\/ */ +/* double rel_speed; */ +/* /\* Pointer to the SIMGRID Resource that will be used */ +/* * for the simulation. The resource should be created upon */ +/* * creation of this host, and will be de-allocated when */ +/* * SG_shutdown() is called */ +/* *\/ */ +/* /\* char *cpu_trace;*\/ */ + +/* void *metadata; */ + +/* /\* SG_resourcesharing_t mode;*\/ */ + +/* SD_workstation_t sd_host; */ +/* }; */ + +/* Host newHost(); /\* Allocate memory for a host *\/ */ +/* void freeHost(Host h); /\* free memory for a host *\/ */ + + +/* /\* LINK structure *\/ */ +/* struct _Link { */ +/* /\* index of this link in the Grid->links array *\/ */ +/* int global_index; */ +/* /\* Pointer to the SIMGRID Resource that will be used */ +/* * for the simulation. The resource shouild be created upon */ +/* * creation of this host, and will be de-allocated when */ +/* * SG_shutdown() is called */ +/* *\/ */ +/* /\* char *latency_trace; */ +/* char *bandwidth_trace;*\/ */ + +/* /\* SG_resourcesharing_t mode;*\/ */ + +/* SD_link_t sd_link; */ +/* }; */ + +/* Link newLink(); /\* Allocate memory for a link *\/ */ +/* void freeLink(Link l); /\* free memory for a link *\/ */ + +/* GRID structure */ +/* struct _Grid { */ +/* int nb_hosts; /\* Number of hosts in the Grid *\/ */ +/* Host *hosts; /\* array of size nb_hosts *\/ */ +/* int nb_links; /\* Number of links in the Grid *\/ */ +/* Link *links; /\* array of size nb_links *\/ */ + +/* /\* connection matrix. connections[i][j] is a pointer */ +/* * to the network link that connects hosts of */ +/* * global_index i and j, that is grid->hosts[i] */ +/* * and grid->hosts[j]. This matrix is likely to */ +/* * be symetric since we probably assume that links */ +/* * behave the same way in both directions. Note that */ +/* * simulating non-bi-directional performance characteristics */ +/* * would not be trivial as two separate links would not */ +/* * model any contention between traffic going both ways */ +/* *\/ */ +/* /\* SG_Resource **routes;*\/ */ +/* /\* SD_link_t **connections;*\/ */ +/* }; */ + +/* Grid parseGridFile(char *filename); /\* Creates a Grid from a *\/ */ +/* /\* Grid description file *\/ */ +/* Grid newGrid(); /\* Allocates memory for a Grid *\/ */ +/* void freeGrid(); /\* frees memory of a Grid. free Hosts and Links *\/ */ +/* void printGrid(Grid grid); /\* print Grid info *\/ */ + + +#endif /* MIXTESIM_DATA_STRUCTURES */ diff --git a/examples/simdag/mixtesim/include/mixtesim_prototypes.h b/examples/simdag/mixtesim/include/mixtesim_prototypes.h new file mode 100644 index 0000000000..2b22a379c8 --- /dev/null +++ b/examples/simdag/mixtesim/include/mixtesim_prototypes.h @@ -0,0 +1,23 @@ +#ifndef MIXTESIM_PROTOTYPES_H +#define MIXTESIM_PROTOTYPES_H + +#include "mixtesim_types.h" +#include "mixtesim_datastructures.h" + +#ifndef MAX +# define MAX(x,y) ((x) > (y) ? (x) : (y)) +#endif +#ifndef MIN +# define MIN(x,y) ((x) > (y) ? (x) : (y)) +#endif + + +int HEFT(DAG dag); + +/* parsing */ +/*Grid parseGridFile(char*filename);*/ +DAG parseDAGFile(char*filename); + +int createSimgridObjects(); + +#endif /* MIXTESIM_PROTOTYPES_H */ diff --git a/examples/simdag/mixtesim/include/mixtesim_types.h b/examples/simdag/mixtesim/include/mixtesim_types.h new file mode 100644 index 0000000000..10ea62f0ec --- /dev/null +++ b/examples/simdag/mixtesim/include/mixtesim_types.h @@ -0,0 +1,14 @@ +#ifndef MIXTESIM_TYPES_H +#define MIXTESIM_TYPES_H + +typedef struct _DAG *DAG; +typedef struct _Node *Node; + +typedef enum { + NODE_COMPUTATION=0, + NODE_TRANSFER, + NODE_ROOT, + NODE_END +} node_t; + +#endif /* MIXTESIM_TYPES_H */ diff --git a/examples/simdag/mixtesim/src/Makefile b/examples/simdag/mixtesim/src/Makefile new file mode 100644 index 0000000000..6bcc351966 --- /dev/null +++ b/examples/simdag/mixtesim/src/Makefile @@ -0,0 +1,19 @@ +include ../Makedefs + +default: all + +MIXTESIM = ../bin/mixtesim + +MIXTESIM_OBJECTS = ./heft.o\ + ./main.o \ + ./dag.o \ + ./list_scheduling_util.o + +all: $(MIXTESIM) + +$(MIXTESIM): $(MIXTESIM_OBJECTS) + $(LD) $(MIXTESIM_OBJECTS) -o $(MIXTESIM) $(SIMGRIDLIB) \ + $(APPLESEEDSLIB) -lm + +clean: + /bin/rm -f *.o *~ diff --git a/examples/simdag/mixtesim/src/dag.c b/examples/simdag/mixtesim/src/dag.c new file mode 100644 index 0000000000..983604cf43 --- /dev/null +++ b/examples/simdag/mixtesim/src/dag.c @@ -0,0 +1,460 @@ +#include +#include +#include + +#include "mixtesim_prototypes.h" + +/** ** + ** STRUCTURE ** + ** **/ + +/* + * newDAG() + */ +DAG newDAG() +{ + return (DAG)calloc(1,sizeof(struct _DAG)); +} + +/* + * freeDAG() + */ +void freeDAG(DAG dag) +{ + int i; + + for (i=0;inb_nodes;i++) { + freeNode(dag->nodes[i]); + } + if (dag->nodes) + free(dag->nodes); + free(dag); + return; +} + +/* + * newNode() + */ +Node newNode() +{ + return (Node)calloc(1,sizeof(struct _Node)); +} + +/* + * freeNode() + */ +void freeNode(Node n) +{ + if (n->parents) + free(n->parents); + if (n->children) + free(n->children); + free(n); + return; +} + +/* + * printDAG() + */ +void printDAG(DAG dag) +{ + fprintf(stderr,"%d nodes: # (children) [parents]\n",dag->nb_nodes); + printNode(dag,dag->root); +} + +/* + * printNode() + */ +void printNode(DAG dag, Node node) +{ + int i; + fprintf(stderr,"%d (",node->global_index); + + /* print children info */ + for (i=0;inb_children-1;i++) { + fprintf(stderr,"%d,",node->children[i]->global_index); + } + if (node->nb_children> 0) + fprintf(stderr,"%d",node->children[node->nb_children-1]->global_index); + fprintf(stderr,") "); + + /* print parent info */ + fprintf(stderr,"["); + for (i=0;inb_parents-1;i++) { + fprintf(stderr,"%d,",node->parents[i]->global_index); + } + if (node->nb_parents > 0) + fprintf(stderr,"%d",node->parents[node->nb_parents-1]->global_index); + fprintf(stderr,"] "); + + /* print special inf */ + if (dag->root == node) { + fprintf(stderr,"ROOT\n"); + } else if (dag->end == node) { + fprintf(stderr,"END\n"); + } else { + fprintf(stderr,"\n"); + } + + for (i=0;inb_children;i++) { + printNode(dag, node->children[i]); + } + return; +} + +/** ** + ** PARSING ** + ** **/ + +static int parseLine(DAG,char*); +static int parseNodeLine(DAG,char*); +static int parseNodeCountLine(DAG,char*); +static node_t string2NodeType(const char*); +static int string2NodeList(const char*,int**,int*); +static int finalizeDAG(DAG); + +/* temporary array in which children lists are stored. Once all nodes + * have been parsed, one can go through these lists and assign actual + * Node pointers to real children lists + */ +char **tmp_childrens; + +/* + * parseDAGFile() + */ +DAG parseDAGFile(char *filename) +{ + FILE *f; + char line[4024]; + int i,count=0; + char *tmp; + DAG new; + + /* initialize the global children list array */ + tmp_childrens=NULL; + + /* opening the DAG description file */ + if (!(f=fopen(filename,"r"))) { + fprintf(stderr,"Impossible to open file '%s'\n",filename); + return NULL; + } + + /* allocate memory for the DAG */ + new = newDAG(); + + /* Go through the lines of the file */ + while(fgets(line,4024,f)) { + count++; + if (line[0]=='#') /* comment lines */ + continue; + if (line[0]=='\n') /* empty lines */ + continue; + tmp=strdup(line); /* somehow, strduping makes it work ? */ + if (parseLine(new,tmp) == -1) { + fprintf(stderr,"Error in DAG description file at line %d\n",count); + fclose(f); + return NULL; + } + free(tmp); + } + fclose(f); + + /* fill in child lists, parent lists, and perform a few + * reality checks + */ + if (finalizeDAG(new) == -1) { + freeDAG(new); + return NULL; + } + + /* free the temporary global child list array */ + for (i=0;inb_nodes;i++) { + if (tmp_childrens[i]) + free(tmp_childrens[i]); + } + free(tmp_childrens); + + return new; +} + +/* + * finalizeDAG(): fills in the child lists with actual pointers, + * creates the parent lists, checks some things about the Root + * and the End node. + */ +static int finalizeDAG(DAG dag) +{ + int i,j; + int *childrenlist,nb_children; + + /* Set the children pointers */ + for (i=0;inb_nodes;i++) { + Node node=dag->nodes[i]; + + /* convert the textual list to an integer list */ + if (string2NodeList(tmp_childrens[i],&childrenlist,&nb_children) == -1) { + fprintf(stderr,"Error: invalid child list '%s'\n", + tmp_childrens[i]); + return -1; + } + /* set the number of children */ + node->nb_children=nb_children; + + /* create the child list with pointers to nodes */ + if (nb_children) { + node->children=(Node*)calloc(nb_children,sizeof(Node)); + for (j=0;jchildren[j]=dag->nodes[childrenlist[j]]; + } + free(childrenlist); + } + } + + /* Set the parent pointers */ + for (i=0;inb_nodes;i++) { + for (j=0;jnodes[i]->nb_children;j++) { + Node node=dag->nodes[i]->children[j]; + node->parents=(Node*)realloc(node->parents, + (node->nb_parents+1)*sizeof(Node)); + node->parents[node->nb_parents]=dag->nodes[i]; + (node->nb_parents)++; + } + } + + /* A few sanity checks */ + if (!(dag->root) || !(dag->end)) { + fprintf(stderr,"Error: Graph has missing end points\n"); + return -1; + } + + if (dag->root->nb_parents != 0) { + fprintf(stderr,"Error: The Root should have no parents\n"); + return -1; + } + if (dag->end->nb_children != 0) { + fprintf(stderr,"Error: The End should have no children\n"); + return -1; + } + return 0; +} + +/* + * parseLine() + */ +static int parseLine(DAG dag, char *line) +{ + char *ptr; + + /* If the line does not start with a keyword, then bail */ + ptr=strchr(line,' '); + if (ptr==NULL) { + fprintf(stderr,"Syntax error\n"); + return -1; + } else{ + *ptr='\0'; + } + + /* deal with the two possible keywords */ + if (!strncmp(line,"NODE_COUNT",strlen("NODE_COUNT"))) + return parseNodeCountLine(dag,ptr+1); + if (!strncmp(line,"NODE",strlen("NODE"))) + return parseNodeLine(dag,ptr+1); + + fprintf(stderr,"Unknown keyword %s\n",line); + return -1; +} + +/* + * parseNodeCountLine() + * + * NODE_COUNT + */ +int parseNodeCountLine(DAG dag, char *line) +{ + int count; + + /* more than one NODE_COUNT statements ? */ + if (dag->nb_nodes != 0) { + fprintf(stderr,"Error: Only one Node Count specification allowed\n"); + return -1; + } + + /* get the count and checks that it's >0 */ + count=atoi(line); + if (count == 0) { + fprintf(stderr,"Error: invalid Node count\n"); + return -1; + } + + /* allocate the node array within the dag */ + dag->nb_nodes=count; + dag->nodes=(Node *)calloc(dag->nb_nodes,sizeof(Node)); + /* allocate space in the temporary gobal childlist array */ + tmp_childrens=(char **)calloc(dag->nb_nodes,sizeof(char*)); + return 0; +} + +/* + * parseNodeLine() + * + * NODE + */ +int parseNodeLine(DAG dag, char *line) +{ + char *ptr; + Node node; + + char *s_index,*s_childlist,*s_type,*s_cost; + int index; + node_t type; + double cost; + + /* NODE_COUNT should be called before NODE */ + if (dag->nb_nodes == 0) { + fprintf(stderr,"Error: Node Count must be specified before Nodes\n"); + return -1; + } + + /* Get index */ + ptr=strchr(line,' '); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_index=line; + *ptr='\0'; + line=ptr+1; + + + /* Get childlist */ + ptr=strchr(line,' '); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_childlist=line; + *ptr='\0'; + line=ptr+1; + + /* get node type */ + ptr=strchr(line,' '); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_type=line; + *ptr='\0'; + line=ptr+1; + + /* get cost */ + ptr=strchr(line,'\n'); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_cost=line; + *ptr='\0'; + + /* Process strings, but store childlist for later */ + index=atoi(s_index); + if ((type=string2NodeType(s_type)) ==-1) + return -1; + cost=atof(s_cost); + tmp_childrens[index]=strdup(s_childlist); + + /* Creating the node */ + node = newNode(); + node->global_index = index; + node->cost=cost; + node->type=type; + + /* Is this the root ? */ + if (node->type == NODE_ROOT) { + if (dag->root) { + fprintf(stderr,"Error: only one Root node allowed\n"); + return -1; + } else { + dag->root = node; + + } + } + /* Is this the end ? */ + if (node->type == NODE_END) { + if (dag->end) { + fprintf(stderr,"Error: only one End node allowed\n"); + return -1; + } else { + dag->end = node; + } + } + + /* Is the node beyond the total number of nodes ? */ + if (node->global_index >= dag->nb_nodes) { + fprintf(stderr,"Error: More nodes than the node count\n"); + return -1; + } + + /* Have we seen that node before ? */ + if (dag->nodes[node->global_index] != NULL) { + fprintf(stderr,"Error: Two nodes share index %d\n", + node->global_index); + return -1; + } + /* add the node to the global array */ + dag->nodes[node->global_index]=node; + return 1; +} + +/* + * string2NodeList() + * parser x,y,z and returns {x,y,z} and 3 + * Does not really do good error checking + */ +static int string2NodeList(const char *string, int **list, int *nb_nodes) +{ + char *start,*ptr; + int count=0; + + *list=NULL; + + /* no children "-" */ + if (!strcmp(string,"-")) { + *nb_nodes=0; + *list=NULL; + return 0; + } + + /* Get all indexes in the list */ + start = (char*)string; + while((ptr = strchr(start,','))) { + *ptr='\0'; + *list=(int*)realloc(*list,(count+1)*sizeof(int)); + (*list)[count]=atoi(start); + count++; + start = ptr+1; + } + *list=(int*)realloc(*list,(count+1)*sizeof(int)); + (*list)[count]=atoi(start); + count++; + + *nb_nodes=count; + return 0; +} + +/* + * string2NodeType() + */ +static node_t string2NodeType(const char *string) { + if (!strcmp(string,"ROOT")) { + return NODE_ROOT; + } else if (!strcmp(string,"END")) { + return NODE_END; + } else if (!strcmp(string,"COMPUTATION")) { + return NODE_COMPUTATION; + } else if (!strcmp(string,"TRANSFER")) { + return NODE_TRANSFER; + } + fprintf(stderr,"Error: Unknown Node Type '%s'\n",string); + return -1; +} + diff --git a/examples/simdag/mixtesim/src/grid.c b/examples/simdag/mixtesim/src/grid.c new file mode 100644 index 0000000000..34f6a34f47 --- /dev/null +++ b/examples/simdag/mixtesim/src/grid.c @@ -0,0 +1,518 @@ +#include +#include +#include + +#include "simgrid.h" + +#include "mixtesim_prototypes.h" + +/** ** + ** STRUCTURE ** + ** **/ + +/* + * newHost() + */ +Host newHost() +{ + return (Host)calloc(1,sizeof(struct _Host)); +} + +/* + * freeHost() + */ +void freeHost(Host h) +{ + if (h->cpu_trace) + free(h->cpu_trace); + free(h); + return; +} + +/* + * newLink() + */ +Link newLink() +{ + return (Link)calloc(1,sizeof(struct _Link)); +} + +/* + * freeLink() + */ +void freeLink(Link l) +{ + if (l->latency_trace) + free(l->latency_trace); + if (l->bandwidth_trace) + free(l->bandwidth_trace); + free(l); + return; +} + +/* + * newGrid() + */ +Grid newGrid() +{ + return (Grid)calloc(1,sizeof(struct _Grid)); +} + +/* + * freeGrid() + */ +void freeGrid(Grid g) +{ + int i; + for (i=0;inb_hosts;i++) + freeHost(g->hosts[i]); + if (g->hosts) + free(g->hosts); + for (i=0;inb_links;i++) + freeLink(g->links[i]); + if (g->links) + free(g->links); + if (g->connections) { + for (i=0;inb_hosts;i++) { + if (g->connections[i]) { + free(g->connections[i]); + } + } + free(g->connections); + } + free(g); + return; +} + + +/** ** + ** PARSING ** + ** **/ + +static int createConnectionMatrix(Grid grid); +static int parseLine(Grid,char*); +static int parseLinkCountLine(Grid,char*); +static int parseHostCountLine(Grid,char*); +static int parseLinkLine(Grid,char*); +static int parseHostLine(Grid,char*); + +/* + * parseGridFile() + */ +Grid parseGridFile(char *filename) +{ + Grid new; + int i; + + new = newGrid(); + + new->nb_host = SD_workstation_get_number(); + + + new->nb_link = SD_link_get_number(); + + FILE *f; + char line[4084]; + int count=0; + char *tmp; + + Grid new; + + /* open Grid description file */ + if (!(f=fopen(filename,"r"))) { + fprintf(stderr,"Impossible to open file '%s'\n",filename); + return NULL; + } + + /* Allocate memory for the Grid */ + new=newGrid(); + + /* go through the lines in the files */ + while(fgets(line,4084,f)) { + count++; + if (line[0]=='#') /* comment line */ + continue; + if (line[0]=='\n') /* empty line */ + continue; + tmp=strdup(line); /* strdupoing seesm to make it work */ + if (parseLine(new,tmp) == -1) { + fprintf(stderr,"Error in Grid description file at line %d\n",count); + fclose(f); + return NULL; + } + free(tmp); + } + fclose(f); + + /* Create the connection matrix */ + createConnectionMatrix(new); + + return new; +} + +/* + * parseLine() + */ +static int parseLine(Grid grid, char *line) +{ + char *ptr; + /* does the line start with a keyword ? */ + ptr=strchr(line,' '); + if (ptr==NULL) { + fprintf(stderr,"Syntax error\n"); + return -1; + } else{ + *ptr='\0'; + } + /* process the different key words */ + if (!strncmp(line,"LINK_COUNT",strlen("LINK_COUNT"))) + return parseLinkCountLine(grid,ptr+1); + if (!strncmp(line,"LINK",strlen("LINK"))) + return parseLinkLine(grid,ptr+1); + if (!strncmp(line,"HOST_COUNT",strlen("HOST_COUNT"))) + return parseHostCountLine(grid,ptr+1); + if (!strncmp(line,"HOST",strlen("HOST"))) + return parseHostLine(grid,ptr+1); + + fprintf(stderr,"Unknown keyword %s\n",line); + return -1; +} + +/* + * parseHostCountLine() + * + * HOST_COUNT + */ +int parseHostCountLine(Grid grid, char *line) +{ + int i,count; + + /* HOST_COUNT should be called only once */ + if (grid->nb_hosts != 0) { + fprintf(stderr,"Error: Only one Host Count specification allowed\n"); + return -1; + } + + /* get the count */ + count=atoi(line); + /* check that count >0 */ + if (count == 0) { + fprintf(stderr,"Error: invalid Host count\n"); + return -1; + } + /* allocate the grid->hosts array */ + grid->nb_hosts=count; + grid->hosts=(Host *)calloc(grid->nb_hosts,sizeof(Host)); + + /* allocate the connection matrix */ + grid->connections=(Link ***)calloc(grid->nb_hosts,sizeof(Link**)); + for (i=0;inb_hosts;i++) { + grid->connections[i]=(Link **)calloc(grid->nb_hosts,sizeof(Link*)); + } + return 0; +} + +/* + * parseLinkCountLine() + * + * LINK_COUNT + */ +int parseLinkCountLine(Grid grid, char *line) +{ + int count; + + /* LINK_COUNT should be called only once */ + if (grid->nb_links != 0) { + fprintf(stderr,"Error: Only one Link Count specification allowed\n"); + return -1; + } + + /* get the count */ + count=atoi(line); + if (count == 0) { + fprintf(stderr,"Error: invalid Link count\n"); + return -1; + } + /* allocate the grid->links array */ + grid->nb_links=count; + grid->links=(Link *)calloc(grid->nb_links,sizeof(Link)); + + return 0; +} + +/* + * parseHostLine() + * + * HOST + */ +int parseHostLine(Grid grid, char *line) +{ + char *ptr; + Host host; + char *s_indexlist,*s_cpu_file,*s_rel_speed,*s_mode; + int *hostIndexList=NULL; + int nb_hostOnLine, i, min,max; + double rel_speed; + + /* HOST_COUNT must be called before HOST */ + if (grid->nb_hosts == 0) { + fprintf(stderr,"Error: Host Count must be specified before Hosts\n"); + return -1; + } + + /* Get index List*/ + ptr=strchr(line,' '); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_indexlist=line; + *ptr='\0'; + line=ptr+1; + + /* Get rel_speed */ + ptr=strchr(line,' '); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_rel_speed=line; + *ptr='\0'; + line=ptr+1; + + /* Get cpu_file */ + ptr=strchr(line,' '); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_cpu_file=line; + *ptr='\0'; + line=ptr+1; + + /* get mode */ + ptr=strchr(line,'\n'); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_mode=line; + *ptr='\0'; + + /* Process strings */ + ptr = strchr(s_indexlist,'-'); + min = atoi(s_indexlist); + max = atoi(ptr+1); + nb_hostOnLine = max-min+1; + hostIndexList=(int*)calloc(max-min+1,sizeof(int)); + for (i=0;iglobal_index = min+i; + host->rel_speed = rel_speed; + if (!host->global_index) { + host->cluster=0; + } else if (host->rel_speed != + grid->hosts[host->global_index-1]->rel_speed) { + host->cluster = grid->hosts[host->global_index-1]->cluster +1; + } else { + host->cluster = grid->hosts[host->global_index-1]->cluster; + } + + host->cpu_trace = strdup(s_cpu_file); + if (!strcmp(s_mode,"IN_ORDER")) { + host->mode = SG_SEQUENTIAL_IN_ORDER; + } else if (!strcmp(s_mode,"OUT_OF_ORDER")) { + host->mode = SG_SEQUENTIAL_OUT_OF_ORDER; + } else if (!strcmp(s_mode,"TIME_SLICED")) { + host->mode = SG_TIME_SLICED; + } else { + fprintf(stderr,"Error: invalid mode specification '%s'\n",s_mode); + return -1; + } + /* Is the host beyond the index */ + if (host->global_index >= grid->nb_hosts) { + fprintf(stderr,"Error: More hosts than the host count\n"); + return -1; + } + + /* Have we seen that host before ? */ + if (grid->hosts[host->global_index] != NULL) { + fprintf(stderr,"Error: Two hosts share index %d\n", + host->global_index); + return -1; + } + /* Add the host to the grid->hosts array */ + grid->hosts[host->global_index]=host; + } + return 1; +} + +/* + * parseLinkLine() + * + * LINK + */ +int parseLinkLine(Grid grid, char *line) +{ + char *ptr; + Link link; + char buffer[16]; + + char *s_indexlist,*s_lat_file,*s_band_file,*s_mode; + int *linkIndexList=NULL; + int nb_linkOnLine, i, min,max; + + /* LINK_COUNT must be called before LINK */ + if (grid->nb_links == 0) { + fprintf(stderr,"Error: Link Count must be specified before Links\n"); + return -1; + } + + /* Get index */ + ptr=strchr(line,' '); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_indexlist=line; + *ptr='\0'; + line=ptr+1; + + + /* Get lat_file */ + ptr=strchr(line,' '); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_lat_file=line; + *ptr='\0'; + line=ptr+1; + + /* Get band_file */ + ptr=strchr(line,' '); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_band_file=line; + *ptr='\0'; + line=ptr+1; + + /* get mode */ + ptr=strchr(line,'\n'); + if (!ptr) { + fprintf(stderr,"Syntax error\n"); + return -1; + } + s_mode=line; + *ptr='\0'; + + /* Process strings */ + ptr = strchr(s_indexlist,'-'); + min = atoi(s_indexlist); + if (ptr) { + max = atoi(ptr+1); + } else { + max=min; + } + nb_linkOnLine = max-min+1; + linkIndexList=(int*)calloc(max-min+1,sizeof(int)); + for (i=0;iglobal_index = min+i; + link->latency_trace=strdup(s_lat_file); + link->bandwidth_trace=strdup(s_band_file); + if (!strcmp(s_mode,"IN_ORDER")) { + link->mode = SG_SEQUENTIAL_IN_ORDER; + } else if (!strcmp(s_mode,"OUT_OF_ORDER")) { + link->mode = SG_SEQUENTIAL_OUT_OF_ORDER; + } else if (!strcmp(s_mode,"TIME_SLICED")) { + link->mode = SG_TIME_SLICED; + } else if (!strcmp(s_mode,"FAT_PIPE")){ + link->mode = SG_FAT_PIPE; + } else { + fprintf(stderr,"Error: invalid mode specification '%s'\n",s_mode); + return -1; + } + sprintf(buffer,"link%d",min+i); + + /* Is the node beyond the index */ + if (link->global_index >= grid->nb_links) { + fprintf(stderr,"Error: More links than the link count\n"); + return -1; + } + + + /* Have we seen that link before ? */ + if (grid->links[link->global_index] != NULL) { + fprintf(stderr,"Error: Two links share index %d\n", + link->global_index); + return -1; + } + /* Add the link to the grid->links array */ + grid->links[link->global_index]=link; + } + return 1; +} + +static int createConnectionMatrix(Grid grid){ + int i,j,nb_clusters; + for (i=0;inb_hosts;i++){ + for(j=0;jnb_hosts;j++){ + if (i==j) { + grid->connections[i][j]=(Link*)calloc(1, sizeof(Link)); + grid->connections[i][j][0]=newLink(); + (grid->connections[i][j][0])->global_index=-1; + }else{ + /* Intra cluster connection */ + if (grid->hosts[i]->cluster == grid->hosts[j]->cluster) { + grid->connections[i][j]=(Link*)calloc(3, sizeof(Link)); + grid->connections[i][j][0]= grid->links[i]; + grid->connections[i][j][1]= + grid->links[grid->nb_hosts+grid->hosts[i]->cluster]; + grid->connections[i][j][2]= grid->links[j]; + } else { /* Inter cluster connection */ + grid->connections[i][j]=(Link*)calloc(7, sizeof(Link)); + + nb_clusters = grid->hosts[grid->nb_hosts-1]->cluster+1; + + /* Src host */ + grid->connections[i][j][0]= grid->links[i]; + /* Src switch */ + grid->connections[i][j][1]= + grid->links[grid->nb_hosts+grid->hosts[i]->cluster]; + /* Src gateway */ + grid->connections[i][j][2]= + grid->links[grid->nb_hosts+grid->hosts[i]->cluster+nb_clusters]; + /* Backbone */ + grid->connections[i][j][3]= + grid->links[grid->nb_links-1]; + /* Dest gateway */ + grid->connections[i][j][4]= + grid->links[grid->nb_hosts+grid->hosts[j]->cluster+nb_clusters]; + /* Dest switch */ + grid->connections[i][j][5]= + grid->links[grid->nb_hosts+grid->hosts[j]->cluster]; + /* Dest host */ + grid->connections[i][j][6]= grid->links[j]; + + } + } + } + } + return 1; +} + diff --git a/examples/simdag/mixtesim/src/heft.c b/examples/simdag/mixtesim/src/heft.c new file mode 100644 index 0000000000..2a57f5017a --- /dev/null +++ b/examples/simdag/mixtesim/src/heft.c @@ -0,0 +1,445 @@ +#include +#include +#include + +#include "mixtesim_prototypes.h" +#include "list_scheduling.h" + +#include "simdag/simdag.h" +#include "xbt/log.h" + +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mixtesim_heft, mixtesim, + "Logging specific to Mixtesim (heft)"); + +/* static function prototypes */ + +static Node *computeNodeList(DAG dag); +static int rankUCompareNode(const void *n1, const void *n2); +static int scheduleList(DAG dag, Node *L); +static void scheduleNode(Node node); + +static double computeAverageLinkSpeed(); +static double computeAverageLinkLatency(); +static double computeAverageExecutionTime(Node node); + +static void assignMeanCost(Node node); +static double computeAndAssignRankU(Node node); + + +static double computeEarliestStartTime(Node node, SD_workstation_t host); +static double computeEarliestFinishTime(Node node, SD_workstation_t host); +static void scheduleNodeOnHost(Node node, SD_workstation_t host); + + +/* + * HEFT(): Implementation of HEFT + */ +int HEFT(DAG dag) +{ + Node *L=NULL; + + /* Compute mean cost for each node */ + assignMeanCost(dag->root); + + /* Compute Rank_u for each node */ + computeAndAssignRankU(dag->root); + + /* Compute the list for the schedule */ + if ((L = computeNodeList(dag)) == NULL) + return -1; + + /* Schedule */ + if (scheduleList(dag,L) == -1) + return -1; + + /* Analyze */ +/* if (analyzeSchedule (grid,dag,L) == -1) */ +/* return -1; */ + + /* Implement the Simgrid schedule */ + implementSimgridSchedule(dag,L); + + if (L) + free (L); + + return 0; +} + +static Node *computeNodeList(DAG dag) +{ + int i; + int nb_comp_nodes=0; + Node *L=NULL; + + for (i=0;inb_nodes;i++) { + if (dag->nodes[i]->type != NODE_COMPUTATION) + continue; + L = (Node *)realloc(L,(nb_comp_nodes+1)*sizeof(Node)); + L[nb_comp_nodes] = dag->nodes[i]; + nb_comp_nodes++; + } + + /* sort L by rank_u */ + qsort(L,nb_comp_nodes,sizeof(Node),rankUCompareNode); + + /* NULL-terminate the list */ + L = (Node *)realloc(L,(nb_comp_nodes+1)*sizeof(Node)); + L[nb_comp_nodes]=NULL; + + return L; +} + +/* + * rankUCompareNode() + */ +static int rankUCompareNode(const void *n1, const void *n2) +{ + double rank_u1, rank_u2; + + rank_u1 = NODE_ATTR((*((Node *)n1)))->rank_u; + rank_u2 = NODE_ATTR((*((Node *)n2)))->rank_u; + + if (rank_u1 > rank_u2) + return -1; + else if (rank_u1 == rank_u2) + return 0; + else + return 1; +} + +/* + * scheduleList() + */ +static int scheduleList(DAG dag, Node *L) +{ + int i=0; + Node node; + + /* Schedules the nodes in the order of list L */ + while ((node=L[i++])) { + scheduleNode(node); + } + return 0; +} + +/* + * scheduleNode() + * pick a host + */ +static void scheduleNode(Node node) +{ + int i; + SD_workstation_t host; + SD_workstation_t best_host; + double EFT; + double min_EFT=-1.0; + int nb_hosts = SD_workstation_get_number(); + const SD_workstation_t *hosts = SD_workstation_get_list(); + + /* pick the best host */ + for (i=0;isg_task->name, */ +/* host->sg_host->name, EFT); */ + + /* is it the best one ? */ + if ((min_EFT == -1.0)|| + (EFT < min_EFT)) { + min_EFT = EFT; + best_host = host; + } + } + + scheduleNodeOnHost(node, best_host); + + return; +} + +/* + * computeAverageLinkSpeed() + */ +static double computeAverageLinkSpeed() +{ + int i; + double bandwidth, ave; + int nb_links = SD_link_get_number(); + const SD_link_t *links = SD_link_get_list(); + + ave=0.0; + for (i=0;isd_task, 1, &hosts[i], + &node->cost, &communication_amount, -1.0); + + ave += exec_time; + } + + return (ave / nb_hosts); +} + +/* + * computeAverageCommunicationTime() + */ +static double computeAverageCommunicationTime(Node node) +{ + return (computeAverageLinkLatency() + + (node->cost / computeAverageLinkSpeed())); +} + +/* + * computeEarliestFinishTime() + */ +static double computeEarliestFinishTime(Node node, SD_workstation_t host) +{ + double executionTime, EST; + double communication_amount = 0.0; + + EST = computeEarliestStartTime(node, host); + executionTime = + SD_task_get_execution_time(node->sd_task, 1, &host, &node->cost, + &communication_amount, -1.0); + + return executionTime + EST; +} + +/* + * computeEarliestStartTime() + */ +static double computeEarliestStartTime(Node node, SD_workstation_t host) +{ + double earliest_start_time=0.0; + int i; + double host_available = HOST_ATTR(host)->first_available; + double data_available; + double transfer_time; + double last_data_available; + Node parent,grand_parent; + SD_workstation_t grand_parent_host; +/* SD_link_t link; */ + + if (node->nb_parents != 0) { + /* compute last_data_available */ + last_data_available=-1.0; + for (i=0;inb_parents;i++) { + parent = node->parents[i]; + + /* No transfers to schedule */ + if (parent->type == NODE_ROOT) { + data_available=0.0; + break; + } + /* normal case */ + if (parent->type == NODE_TRANSFER) { + if (parent->nb_parents > 1) { + fprintf(stderr,"Warning: transfer has 2 parents\n"); + } + grand_parent = parent->parents[0]; + grand_parent_host = NODE_ATTR(grand_parent)->host; + transfer_time = + SD_route_get_communication_time(grand_parent_host, host, parent->cost); + +/* link = SD_workstation_route_get_list(grand_parent_host, host)[0]; */ + +/* if (link->global_index == -1) { */ +/* /\* it is the local link so transfer_time = 0 *\/ */ +/* transfer_time = 0.0; */ +/* } else { */ +/* transfer_time = SG_getLinkLatency(link->sg_link, */ +/* NODE_ATTR(grand_parent)->finish) + */ +/* parent->cost/SG_getLinkBandwidth(link->sg_link, */ +/* NODE_ATTR(grand_parent)->finish); */ +/* } */ + data_available = NODE_ATTR(grand_parent)->finish + transfer_time; + } + + /* no transfer */ + if (parent->type == NODE_COMPUTATION) { + data_available = NODE_ATTR(parent)->finish; + } + + if (last_data_available < data_available) + last_data_available = data_available; + } + + /* return the MAX "*/ + earliest_start_time = MAX(host_available,last_data_available); + + } + return earliest_start_time; +} + + +/* + * computeAndAssignRankU() + */ +static double computeAndAssignRankU(Node node) +{ + int i; + double my_rank_u = 0.0, max_rank_u, current_child_rank_u; + Node child,grand_child; + + my_rank_u = NODE_ATTR(node)->mean_cost; + max_rank_u = -1.0; + + for (i=0;inb_children;i++) { + child = node->children[i]; + + if (node->type == NODE_ROOT) + { + my_rank_u = computeAndAssignRankU(child); + } + + if (child->type == NODE_TRANSFER) { /* normal case */ + if (child->nb_children > 1) { + fprintf(stderr,"Warning: transfer has 2 children\n"); + } + grand_child = child->children[0]; + current_child_rank_u = NODE_ATTR(child)->mean_cost + + computeAndAssignRankU(grand_child); + if (max_rank_u < current_child_rank_u) + max_rank_u = current_child_rank_u; + } + else /* child is the end node */ + max_rank_u = 0.0; + + } + + my_rank_u += max_rank_u; + + NODE_ATTR(node)->rank_u = my_rank_u; + return my_rank_u ; +} + +/* + * assignMeanCost() + */ +static void assignMeanCost(Node node) +{ + int i; + + for (i=0;inb_children;i++) { + if (node->children[i]->type == NODE_COMPUTATION) + NODE_ATTR(node->children[i])->mean_cost = + computeAverageExecutionTime(node->children[i]); + else + NODE_ATTR(node->children[i])->mean_cost = + computeAverageCommunicationTime(node->children[i]); + assignMeanCost(node->children[i]); + } + return; +} + + +/* + * scheduleNodeOnHost() + */ +static void scheduleNodeOnHost(Node node, SD_workstation_t host) +{ + int i; + double data_available, transfer_time, last_data_available; +/* SD_link_t link; */ + Node parent, grand_parent; + SD_workstation_t grand_parent_host; + double communication_amount = 0.0; + + INFO2("Affecting node '%s' to host '%s'", SD_task_get_name(node->sd_task), + SD_workstation_get_name(host)); + + last_data_available=-1.0; + for (i=0;inb_parents;i++) { + parent = node->parents[i]; + + if (parent->type == NODE_ROOT) {/* No transfers to schedule */ + data_available=0.0; + break; + } + + if (parent->type == NODE_TRANSFER) { /* normal case */ + if (parent->nb_parents > 1) { + fprintf(stderr,"Warning: transfer has 2 parents\n"); + } + grand_parent = parent->parents[0]; + grand_parent_host = NODE_ATTR(grand_parent)->host; + transfer_time = + SD_route_get_communication_time(grand_parent_host, host, parent->cost); + +/* link = SD_workstation_route_get_list(grand_parent_host, host)[0]; */ + +/* if (link->global_index == -1) { */ +/* /\* it is the local link so transfer_time = 0 *\/ */ +/* transfer_time = 0.0; */ +/* } else { */ +/* transfer_time = SG_getLinkLatency(link->sg_link, */ +/* NODE_ATTR(grand_parent)->finish) + */ +/* parent->cost/SG_getLinkBandwidth(link->sg_link, */ +/* NODE_ATTR(grand_parent)->finish); */ +/* } */ + + data_available = NODE_ATTR(grand_parent)->finish + transfer_time; + } + + /* no transfer */ + if (parent->type == NODE_COMPUTATION) { + data_available = NODE_ATTR(parent)->finish; + } + + if (last_data_available < data_available) + last_data_available = data_available; + } + + /* node attributes */ + NODE_ATTR(node)->start=MAX(last_data_available, + HOST_ATTR(host)->first_available); + NODE_ATTR(node)->finish=NODE_ATTR(node)->start + + SD_task_get_execution_time(node->sd_task, 1, &host, &node->cost, + &communication_amount, -1.0); +/* SG_getPrediction(SG_PERFECT, 0.0, NULL,host->sg_host, */ +/* NODE_ATTR(node)->start,node->cost); */ + + NODE_ATTR(node)->host = host; + NODE_ATTR(node)->state = LIST_SCHEDULING_SCHEDULED; + + /* host attributes */ + HOST_ATTR(host)->first_available = NODE_ATTR(node)->finish; + + return; +} diff --git a/examples/simdag/mixtesim/src/list_scheduling_util.c b/examples/simdag/mixtesim/src/list_scheduling_util.c new file mode 100644 index 0000000000..d1ab22cdd2 --- /dev/null +++ b/examples/simdag/mixtesim/src/list_scheduling_util.c @@ -0,0 +1,172 @@ +#include +#include +#include + +#include "mixtesim_prototypes.h" +#include "list_scheduling.h" + +#include "simdag/simdag.h" +#include "xbt/log.h" + +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mixtesim_list_scheduling, mixtesim, + "Logging specific to Mixtesim (list scheduling)"); + +/* + * freeHostAttributes() + */ +void freeHostAttributes() +{ + int i; + int nb_hosts = SD_workstation_get_number(); + const SD_workstation_t *hosts = SD_workstation_get_list(); + + for (i=0;inb_nodes;i++) { + if (dag->nodes[i]->metadata) { + free(dag->nodes[i]->metadata); + } + } + return; +} + +/* + * allocateNodeAttributes() + */ +void allocateNodeAttributes(DAG dag) +{ + int i; + + for (i=0;inb_nodes;i++) { + dag->nodes[i]->metadata = + (NodeAttribute)calloc(1,sizeof(struct _NodeAttribute)); + if (dag->nodes[i]->type == NODE_COMPUTATION) + NODE_ATTR(dag->nodes[i])->state = LIST_SCHEDULING_NOT_SCHEDULED; + } + return; +} + +/* + * implementSimgridSchedule() + */ +void implementSimgridSchedule(DAG dag, Node *list) +{ + int j,k; + Node node; + Node grand_parent; + SD_workstation_t grand_parent_host; + SD_workstation_t host; +/* Link link; */ +/* SD_link_t *route;*/ + + const double no_cost[] = {0.0, 0.0}; + const double small_cost = 1.0; /* doesn't work with 0.0 */ + e_SD_task_state_t state; + SD_workstation_t host_list[] = {NULL, NULL}; + double communication_amount[] = {0.0, 0.0, + 0.0, 0.0}; + + /* Schedule Root */ + if (SD_task_get_state(dag->root->sd_task) == SD_NOT_SCHEDULED) { + DEBUG1("Dag root cost = %f", dag->root->cost); + DEBUG1("Scheduling root task '%s'", SD_task_get_name(dag->root->sd_task)); + SD_task_schedule(dag->root->sd_task, 1, SD_workstation_get_list(), + &small_cost, no_cost, -1.0); + DEBUG2("Task '%s' state: %d", SD_task_get_name(dag->root->sd_task), SD_task_get_state(dag->root->sd_task)); + } + + /* Schedule the computation */ + for (j=0;list[j];j++) { + node=list[j]; + + /* schedule the task */ + DEBUG1("Scheduling computation task '%s'", SD_task_get_name(node->sd_task)); + SD_task_schedule(node->sd_task, 1, &NODE_ATTR(node)->host, + &node->cost, no_cost, -1.0); + DEBUG2("Task '%s' state: %d", SD_task_get_name(node->sd_task), SD_task_get_state(node->sd_task)); + + /* schedule the parent transfer */ + for (k=0;knb_parents;k++) { + if (node->parents[k]->type == NODE_ROOT) + break; + /* no transfer */ + if (node->parents[k]->type == NODE_COMPUTATION) + continue; + /* normal case */ + if (node->parents[k]->type == NODE_TRANSFER) { + state = SD_task_get_state(node->parents[k]->sd_task); + if (state != SD_RUNNING && state != SD_DONE) { + grand_parent=node->parents[k]->parents[0]; + grand_parent_host=NODE_ATTR(grand_parent)->host; + host=NODE_ATTR(node)->host; + + host_list[0] = grand_parent_host; + host_list[1] = host; + communication_amount[1] = node->parents[k]->cost; + DEBUG1("Scheduling transfer task '%s'", SD_task_get_name(node->parents[k]->sd_task)); + SD_task_schedule(node->parents[k]->sd_task, 2, host_list, + no_cost, communication_amount, -1.0); + DEBUG2("Task '%s' state: %d", SD_task_get_name(node->parents[k]->sd_task), + SD_task_get_state(node->parents[k]->sd_task)); + +/* if (!route) { */ +/* if (SG_scheduleTaskOnResource(node->parents[k]->sg_task, */ +/* local_link->sg_link) */ +/* == -1) { */ +/* fprintf(stderr,"Task '%s' already in state %d\n", */ +/* node->parents[k]->sg_task->name, */ +/* node->parents[k]->sg_task->state); */ +/* } */ +/* } else { */ +/* if (SG_scheduleTaskOnResource(node->parents[k]->sg_task, */ +/* route) */ +/* == -1) { */ +/* fprintf(stderr,"Task '%s' already in state %d\n", */ +/* node->parents[k]->sg_task->name, */ +/* node->parents[k]->sg_task->state); */ +/* } */ +/* } */ + } + } + } + } + + /* Schedule End */ +/* SG_scheduleTaskOnResource(dag->end->sg_task,local_link->sg_link); */ + SD_task_schedule(dag->end->sd_task, 1, SD_workstation_get_list(), + &small_cost, no_cost, -1.0); + + + return; +} + + diff --git a/examples/simdag/mixtesim/src/main.c b/examples/simdag/mixtesim/src/main.c new file mode 100644 index 0000000000..5839fbbd9d --- /dev/null +++ b/examples/simdag/mixtesim/src/main.c @@ -0,0 +1,330 @@ +#include +#include +#include +#include +#include + +#include "mixtesim_prototypes.h" +#include "list_scheduling.h" + +#include "simdag/simdag.h" +#include "xbt/log.h" + +XBT_LOG_NEW_DEFAULT_CATEGORY(mixtesim, + "Logging specific to this SimDag example"); + +/* static int createSimgridResources(); */ +static int createSimgridTasks(); + +DAG dag; +/*extern Link local_link;*/ + +int main(int argc, char **argv) { + + char *platform_file; + SD_task_t *changed_tasks; + int i; + +/* xbt_log_control_set("sd.thres=debug"); */ +/* xbt_log_control_set("sd_kernel.thres=debug"); */ +/* xbt_log_control_set("surf_kernel.thres=debug"); */ +/* xbt_log_control_set("mixtesim.thres=debug"); */ + + + if (argc < 1) { + printf("Usage: %s xml_platform_file dagfile ", argv[0]); + printf("example: %s gridfile.xml dagfile", argv[0]); + exit(1); + } + + /* initialisation of SD */ + SD_init(&argc, argv); + + /* creation of the environment */ + platform_file = argv[1]; + SD_create_environment(platform_file); + + /*Parse DAG file */ + dag = parseDAGFile(argv[2]); + + + allocateNodeAttributes(dag); + allocateHostAttributes(); + + /* create Simgrid objects */ + createSimgridObjects(); + + HEFT(dag); + + printDAG(dag); + + changed_tasks = SD_simulate(-1.0); + + INFO0("Tasks whose state has changed:"); + i = 0; + while(changed_tasks[i] != NULL) { + switch (SD_task_get_state(changed_tasks[i])) { + case SD_SCHEDULED: + INFO1("%s is scheduled.", SD_task_get_name(changed_tasks[i])); + break; + case SD_READY: + INFO1("%s is ready.", SD_task_get_name(changed_tasks[i])); + break; + case SD_RUNNING: + INFO1("%s is running.", SD_task_get_name(changed_tasks[i])); + break; + case SD_DONE: + INFO1("%s is done.", SD_task_get_name(changed_tasks[i])); + break; + case SD_FAILED: + INFO1("%s is failed.", SD_task_get_name(changed_tasks[i])); + break; + default: + INFO1("Unknown status for %s", SD_task_get_name(changed_tasks[i])); + break; + } + i++; + } + free(changed_tasks); + + /* clear some memory */ + freeNodeAttributes(dag); + freeHostAttributes(); + + /* reset SimDag */ + SD_exit(); + + return 0; +} + +/* + * createSimgridObjects() + */ +int createSimgridObjects() +{ + /* Create resources */ +/* if (createSimgridResources() == -1) */ +/* return -1; */ + + /* Create tasks */ + if (createSimgridTasks() == -1) + return -1; + + return 0; +} + +/* + * createSimgridResources() + */ +/* static int createSimgridResources() */ +/* { */ +/* int i,j; */ +/* char buffer[32]; */ +/* SG_Resource *sg_TCPlinks; */ +/* SG_Resource fast_link; */ + +/* /\* The almost infinetely fast TCP link *\/ */ +/* fast_link = SG_newTCPLink("infinetly_fast_TCPlink", */ +/* NULL, */ +/* 0.0, EPSILON, NULL, */ +/* 0.0, 1000.0, */ +/* SG_TCP_SHARED,NULL); */ + +/* sg_TCPlinks = (SG_Resource*) calloc (2, sizeof(SG_Resource)); */ +/* sg_TCPlinks[0] = fast_link; */ +/* sg_TCPlinks[1] = NULL; */ + +/* /\* And the almost infinetely fast TCP route *\/ */ +/* local_link = newLink(); */ +/* local_link->sg_link = */ +/* SG_newTCPRoute ("infinitely_fast_route", sg_TCPlinks, NULL); */ +/* free(sg_TCPlinks); */ + +/* /\* Create hosts *\/ */ +/* for (i=0;inb_hosts;i++) { */ +/* if (createSimgridHost(grid->hosts[i]) == -1) */ +/* return -1; */ +/* } */ + +/* /\* Create TCP links *\/ */ +/* for (i=0;inb_links;i++) { */ +/* if (createSimgridLink(grid->links[i]) == -1) */ +/* return -1; */ +/* } */ + +/* /\* Create TCP routes *\/ */ +/* grid->routes=(SG_Resource**)calloc(grid->nb_hosts,sizeof(SG_Resource*)); */ + +/* for (i=0;inb_hosts;i++) { */ +/* grid->routes[i]=(SG_Resource *)calloc(grid->nb_hosts,sizeof(SG_Resource)); */ +/* for (j=0;jnb_hosts;j++) { */ +/* sprintf(buffer,"route#%d-%d",i,j); */ +/* if (i!=j) { */ +/* if (grid->hosts[i]->cluster == grid->hosts[j]->cluster) { */ +/* /\* Intra cluster route *\/ */ +/* /\* src - switch - dest*\/ */ +/* sg_TCPlinks = (SG_Resource*) calloc (4, sizeof(SG_Resource)); */ +/* sg_TCPlinks[0] = grid->connections[i][j][0]->sg_link; */ +/* sg_TCPlinks[1] = grid->connections[i][j][1]->sg_link; */ +/* sg_TCPlinks[2] = grid->connections[i][j][2]->sg_link; */ +/* sg_TCPlinks[3] = NULL; */ +/* } else { */ +/* /\* Inter cluster route *\/ */ +/* /\* src - switch - gateway - backbone - gateway - switch - dest*\/ */ +/* sg_TCPlinks = (SG_Resource*) calloc (8, sizeof(SG_Resource)); */ +/* sg_TCPlinks[0] = grid->connections[i][j][0]->sg_link; */ +/* sg_TCPlinks[1] = grid->connections[i][j][1]->sg_link; */ +/* sg_TCPlinks[2] = grid->connections[i][j][2]->sg_link; */ +/* sg_TCPlinks[3] = grid->connections[i][j][3]->sg_link; */ +/* sg_TCPlinks[4] = grid->connections[i][j][4]->sg_link; */ +/* sg_TCPlinks[5] = grid->connections[i][j][5]->sg_link; */ +/* sg_TCPlinks[6] = grid->connections[i][j][6]->sg_link; */ +/* sg_TCPlinks[7] = NULL; */ +/* } */ +/* grid->routes[i][j] = SG_newTCPRoute (buffer, sg_TCPlinks, NULL); */ +/* free(sg_TCPlinks); */ +/* } else { */ +/* /\*Self communication => no route *\/ */ +/* grid->routes[i][j] = NULL; */ +/* } */ +/* } */ +/* } */ +/* return 0; */ +/* } */ + +/* static int createSimgridHost(Host h) */ +/* { */ +/* char buffer[32]; */ +/* char *filename; */ +/* double offset; */ +/* double value; */ + +/* sprintf(buffer,"host#%d",h->global_index); */ + +/* if (parseTraceSpec(h->cpu_trace,&filename,&offset,&value) == -1) { */ +/* fprintf(stderr,"Syntax error: host#%d\n",h->global_index); */ +/* return -1; */ +/* } */ + +/* h->sg_host = SG_newHost(buffer,h->rel_speed, */ +/* h->mode, filename,offset,value, */ +/* NULL, NULL, 0, h); */ +/* free(filename); */ + +/* return 0; */ +/* } */ + +/* /\* */ +/* * createSimgridLink() */ +/* * */ +/* *\/ */ +/* static int createSimgridLink(Link l) */ +/* { */ +/* char buffer[32]; */ +/* char *filename1,*filename2; */ +/* double offset1,offset2; */ +/* double value1,value2; */ + +/* sprintf(buffer,"link#%d",l->global_index); */ + +/* if ((parseTraceSpec(l->latency_trace,&filename1,&offset1,&value1) == -1) || */ +/* (parseTraceSpec(l->bandwidth_trace,&filename2,&offset2,&value2) == -1)) { */ +/* fprintf(stderr,"Syntax error: link#%d\n",l->global_index); */ +/* return -1; */ +/* } */ + + +/* if (l->mode == SG_TIME_SLICED) { */ +/* l->sg_link=SG_newTCPLink (buffer, */ +/* filename1, offset1, value1, */ +/* filename2, offset2, value2, */ +/* SG_TCP_SHARED,NULL); */ +/* } */ + +/* if (l->mode == SG_FAT_PIPE) { */ +/* l->sg_link=SG_newTCPLink (buffer, */ +/* filename1, offset1, value1, */ +/* filename2, offset2, value2, */ +/* SG_TCP_BACKBONE,NULL); */ +/* } */ + +/* free(filename1); */ +/* free(filename2); */ + +/* return 0; */ +/* } */ + +/* + * createSimgridTasks() + * + */ +static int createSimgridTasks() +{ + Node node; + char buffer[32]; + int i,j; + + /* Creating the tasks */ + for (i=0;inb_nodes;i++) { + node = dag->nodes[i]; + sprintf(buffer,"node#%d",node->global_index); + node->sd_task = SD_task_create(buffer, node, 1.0); + } + + /* Set the dependencies */ + for (i=0;inb_nodes;i++) { + node = dag->nodes[i]; + for (j=0;jnb_parents;j++) { + SD_task_dependency_add(NULL, NULL, node->parents[j]->sd_task, node->sd_task); + } + } + return 0; +} + + +/* + * parseTraceSpec() + */ +/* static int parseTraceSpec(char* spec,char**filename, */ +/* double *offset, double *value) */ +/* { */ +/* char *tmp; */ + +/* tmp = strchr(spec,':'); */ +/* if (!tmp) { */ +/* fprintf(stderr,"Parse error: missing ':' in trace specification\n"); */ +/* return -1; */ +/* } */ + +/* *filename=NULL; */ +/* *offset=0.0; */ +/* *value=0.0; */ + +/* if (tmp == spec) { /\* FIXED *\/ */ +/* if (!*(tmp+1)) { */ +/* fprintf(stderr,"Parse error: invalid value specification\n"); */ +/* return -1; */ +/* } */ +/* *value = atof(tmp+1); */ +/* if (*value < 0.0) { */ +/* fprintf(stderr,"Error: invalid value\n"); */ +/* return -1; */ +/* } */ +/* return 0; */ +/* } */ + +/* /\* TRACE *\/ */ +/* *tmp='\0'; */ +/* *filename=strdup(spec); */ +/* if (!*(tmp+1)) { */ +/* fprintf(stderr,"Parse error: invalid offset specification\n"); */ +/* return -1; */ +/* } */ +/* *offset = atof(tmp+1); */ +/* if (*offset < 0.0) { */ +/* fprintf(stderr,"Error: invalid offset\n"); */ +/* return -1; */ +/* } */ + +/* return 0; */ +/* } */ -- 2.20.1