From 1519c5f2b2fd984d6a96f5901f8cc7effe784188 Mon Sep 17 00:00:00 2001 From: quintin Date: Thu, 2 Dec 2010 08:17:02 +0000 Subject: [PATCH] [src/simdag,examples/simdag] add the simulator inside the dot loader if the user provides one and a test to detect the cycle on the task graph git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@8861 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- examples/simdag/dot/CMakeLists.txt | 2 + examples/simdag/dot/dag_with_bad_schedule.dot | 24 ++ examples/simdag/dot/dag_with_cycle.dot | 25 ++ .../simdag/dot/dag_with_good_schedule.dot | 25 ++ examples/simdag/dot/simulate_dot.c | 112 +++++++++ include/xbt/dynar.h | 2 +- src/simdag/private.h | 3 + src/simdag/sd_daxloader.c | 1 + src/simdag/sd_dotloader.c | 230 +++++++++++++++--- 9 files changed, 394 insertions(+), 30 deletions(-) create mode 100644 examples/simdag/dot/dag_with_bad_schedule.dot create mode 100644 examples/simdag/dot/dag_with_cycle.dot create mode 100644 examples/simdag/dot/dag_with_good_schedule.dot create mode 100644 examples/simdag/dot/simulate_dot.c diff --git a/examples/simdag/dot/CMakeLists.txt b/examples/simdag/dot/CMakeLists.txt index 12bc21689f..224a873458 100644 --- a/examples/simdag/dot/CMakeLists.txt +++ b/examples/simdag/dot/CMakeLists.txt @@ -3,6 +3,8 @@ cmake_minimum_required(VERSION 2.6) set(EXECUTABLE_OUTPUT_PATH "${CMAKE_CURRENT_BINARY_DIR}") add_executable(dot_test dot_test.c) #add_executable( ) +add_executable(simulate_dot simulate_dot.c) #add_executable( ) ### Add definitions for compile target_link_libraries(dot_test simgrid m pthread -fprofile-arcs) #target_link_libraries( ) +target_link_libraries(simulate_dot simgrid m pthread -fprofile-arcs) #target_link_libraries( ) diff --git a/examples/simdag/dot/dag_with_bad_schedule.dot b/examples/simdag/dot/dag_with_bad_schedule.dot new file mode 100644 index 0000000000..2182a0e8fc --- /dev/null +++ b/examples/simdag/dot/dag_with_bad_schedule.dot @@ -0,0 +1,24 @@ +digraph G { +end [size="10000000129.452715" performer="100" order="1"]; +0 [size="10000000129.452715" category="taskA" performer="1" order="1"]; +1 [size="10000000131.133657" category="taskA" performer="0"]; +2 [size="10000000121.12487" category="taskA" performer="1" order="1"]; +3 [size="10000000230.608025" category="taskA" order="1"]; +4 [size="10000000004.994019" category="taskB" performer="1" order="2"]; +5 [size="10000000046.016401" category="taskB" performer="1" order="3"]; +6 [size="10000000091.598791" category="taskB" performer="1" order="4"]; +7 [size="10000000040.679438" category="taskB" performer="1" order="5"]; +8 [size="10000000250.490017" category="taskC" performer="1" order="6"]; +9 [size="10000000079.267649" category="taskC" performer="1" order="9"]; +0->1 [size="10001.389601075407" category="oi"]; +1->2 [size="10004.164631264117"]; +2->3 [size="10001.781644976922"]; +3->4 [size="-1"]; +4->5 [size="10029.262823275711"]; +5->6 [size="0.0"]; +6->7 [size="10004.920415194067"]; +7->8 [size="10000.234048984707"]; +8->9 ; +7->end [size="10014000.0"]; +root->5 [size="10014000.0"]; +} diff --git a/examples/simdag/dot/dag_with_cycle.dot b/examples/simdag/dot/dag_with_cycle.dot new file mode 100644 index 0000000000..1233fd316d --- /dev/null +++ b/examples/simdag/dot/dag_with_cycle.dot @@ -0,0 +1,25 @@ +digraph G { +end [size="10000000129.452715"]; +0 [size="10000000129.452715" category="taskA"]; +1 [size="10000000131.133657" category="taskA"]; +2 [size="10000000121.12487" category="taskA"]; +3 [size="10000000230.608025" category="taskA"]; +4 [size="10000000004.994019" category="taskB"]; +5 [size="10000000046.016401" category="taskB"]; +6 [size="10000000091.598791" category="taskB"]; +7 [size="10000000040.679438" category="taskB"]; +8 [size="10000000250.490017" category="taskC"]; +9 [size="10000000079.267649" category="taskC"]; +0->2 [size="10001.389601075407" category="oi"]; +1->2 [size="10004.164631264117"]; +2->3 [size="10001.781644976922"]; +3->4 [size="-1"]; +4->5 [size="10029.262823275711"]; +5->6 [size="0.0"]; +6->7 [size="10004.920415194067"]; +7->8 [size="10000.234048984707"]; +6->1; +8->9 ; +7->end [size="10014000.0"]; +root->5 [size="10014000.0"]; +} diff --git a/examples/simdag/dot/dag_with_good_schedule.dot b/examples/simdag/dot/dag_with_good_schedule.dot new file mode 100644 index 0000000000..daf183f594 --- /dev/null +++ b/examples/simdag/dot/dag_with_good_schedule.dot @@ -0,0 +1,25 @@ +digraph G { +end [size="10000000129.452715" performer="0" order="7"]; +root [performer="0" order="1"]; +0 [size="10000000129.452715" category="taskA" performer="1" order="1"]; +1 [size="10000000131.133657" category="taskA" performer="0" order="2"]; +2 [size="10000000121.12487" category="taskA" performer="1" order="2"]; +3 [size="10000000230.608025" category="taskA" performer="1" order="3"]; +4 [size="10000000004.994019" category="taskB" performer="0" order="3"]; +5 [size="10000000046.016401" category="taskB" performer="0" order="4"]; +6 [size="10000000091.598791" category="taskB" performer="0" order="5"]; +7 [size="10000000040.679438" category="taskB" performer="0" order="6"]; +8 [size="10000000250.490017" category="taskC" performer="1" order="4"]; +9 [size="10000000079.267649" category="taskC" performer="1" order="5"]; +0->2 [size="10001.389601075407" category="oi"]; +1->2 [size="10004.164631264117"]; +2->3 [size="10001.781644976922"]; +3->4 [size="-1"]; +4->5 [size="10029.262823275711"]; +5->6 [size="0.0"]; +6->7 [size="10004.920415194067"]; +7->8 [size="10000.234048984707"]; +8->9 ; +7->end [size="10014000.0"]; +root->5 [size="10014000.0"]; +} diff --git a/examples/simdag/dot/simulate_dot.c b/examples/simdag/dot/simulate_dot.c new file mode 100644 index 0000000000..a28aa8fa02 --- /dev/null +++ b/examples/simdag/dot/simulate_dot.c @@ -0,0 +1,112 @@ +/* simple test trying to load a DOT file. */ + +/* Copyright (c) 2010. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include +#include +#include "simdag/simdag.h" +#include "xbt/log.h" +#include "xbt/ex.h" +#include + +XBT_LOG_NEW_DEFAULT_CATEGORY(test, + "Logging specific to this SimDag example"); + +int main(int argc, char **argv) +{ + xbt_dynar_t dot, changed; + unsigned int cursor; + SD_task_t task; + + /* initialisation of SD */ + SD_init(&argc, argv); + + /* Check our arguments */ + if (argc < 3) { + INFO1("Usage: %s platform_file dot_file [trace_file]", argv[0]); + INFO1("example: %s ../2clusters.xml dag.dot dag.mytrace", argv[0]); + exit(1); + } + char *tracefilename; + if (argc == 3) { + char *last = strrchr(argv[2], '.'); + + tracefilename = + bprintf("%.*s.trace", + (int) (last == NULL ? strlen(argv[2]) : last - argv[2]), + argv[2]); + } else { + tracefilename = xbt_strdup(argv[3]); + } + + /* creation of the environment */ + SD_create_environment(argv[1]); + + /* load the DOT file and schedule tasks */ + dot = SD_dotload(argv[2]); + + /* Display all the tasks */ + INFO0 + ("------------------- Display all tasks of the loaded DAG ---------------------------"); + xbt_dynar_foreach(dot, cursor, task) { + SD_task_dump(task); + } + + FILE *dotout = fopen("dot.dot", "w"); + fprintf(dotout, "digraph A {\n"); + xbt_dynar_foreach(dot, cursor, task) { + SD_task_dotty(task, dotout); + } + fprintf(dotout, "}\n"); + fclose(dotout); + + INFO0 + ("------------------- Run the schedule ---------------------------"); + changed = SD_simulate(-1); + xbt_dynar_free_container(&changed); + INFO0 + ("------------------- Produce the trace file---------------------------"); + INFO1("Producing the trace of the run into %s", tracefilename); + FILE *out = fopen(tracefilename, "w"); + xbt_assert1(out, "Cannot write to %s", tracefilename); + free(tracefilename); + + xbt_dynar_foreach(dot, cursor, task) { + int kind = SD_task_get_kind(task); + SD_workstation_t *wsl = SD_task_get_workstation_list(task); + switch (kind) { + case SD_TASK_COMP_SEQ: + fprintf(out, "[%f] %s compute %f # %s\n", + SD_task_get_start_time(task), + SD_workstation_get_name(wsl[0]), SD_task_get_amount(task), + SD_task_get_name(task)); + break; + case SD_TASK_COMM_E2E: + fprintf(out, "[%f] %s send %s %f # %s\n", + SD_task_get_start_time(task), + SD_workstation_get_name(wsl[0]), + SD_workstation_get_name(wsl[1]), SD_task_get_amount(task), + SD_task_get_name(task)); + fprintf(out, "[%f] %s recv %s %f # %s\n", + SD_task_get_finish_time(task), + SD_workstation_get_name(wsl[1]), + SD_workstation_get_name(wsl[0]), SD_task_get_amount(task), + SD_task_get_name(task)); + break; + default: + xbt_die(bprintf + ("Task %s is of unknown kind %d", SD_task_get_name(task), + SD_task_get_kind(task))); + } + SD_task_destroy(task); + } + fclose(out); + + /* exit */ + SD_exit(); + return 0; +} diff --git a/include/xbt/dynar.h b/include/xbt/dynar.h index 78851d2135..a1ff0f6924 100644 --- a/include/xbt/dynar.h +++ b/include/xbt/dynar.h @@ -161,7 +161,7 @@ XBT_PUBLIC(void *) xbt_dynar_pop_ptr(xbt_dynar_t const dynar); /** @brief Quick setting of scalar content * @hideinitializer */ # define xbt_dynar_set_as(dynar,idx,type,val) \ - (*(type*)xbt_dynar_get_ptr((dynar),(idx))) = val + (*(type*)xbt_dynar_set_at_ptr((dynar),(idx))) = val /** @brief Quick retrieval of scalar content * @hideinitializer */ # define xbt_dynar_getlast_as(dynar,type) \ diff --git a/src/simdag/private.h b/src/simdag/private.h index aab3cd6044..efbabab215 100644 --- a/src/simdag/private.h +++ b/src/simdag/private.h @@ -13,6 +13,7 @@ #include "simdag/simdag.h" #include "simdag/datatypes.h" #include "surf/surf.h" +#include #define SD_INITIALISED() (sd_global != NULL) #define SD_CHECK_INIT_DONE() xbt_assert0(SD_INITIALISED(), "Call SD_init() first"); @@ -84,6 +85,7 @@ typedef struct SD_task { int fifo_checked; /* used by SD_task_just_done to make sure we evaluate the task only once */ + int marked; /* used to check if the task DAG has some cycle*/ /* dependencies */ xbt_dynar_t tasks_before; @@ -126,6 +128,7 @@ void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state); void __SD_task_really_run(SD_task_t task); int __SD_task_try_to_run(SD_task_t task); void __SD_task_just_done(SD_task_t task); +bool acyclic_graph_detection(xbt_dynar_t dag); /* Functions to test if the task is in a given state. */ diff --git a/src/simdag/sd_daxloader.c b/src/simdag/sd_daxloader.c index c8778b9a25..c17e7f0159 100644 --- a/src/simdag/sd_daxloader.c +++ b/src/simdag/sd_daxloader.c @@ -205,6 +205,7 @@ xbt_dynar_t SD_daxload(const char *filename) } } + acyclic_graph_detection(result); return result; } diff --git a/src/simdag/sd_dotloader.c b/src/simdag/sd_dotloader.c index 1974cb86e0..18716862ac 100644 --- a/src/simdag/sd_dotloader.c +++ b/src/simdag/sd_dotloader.c @@ -8,15 +8,16 @@ #include "simdag/simdag.h" #include "xbt/misc.h" #include "xbt/log.h" +#include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_dotparse, sd, "Parsing DOT files"); #undef CLEANUP #ifdef HAVE_CGRAPH_H - #include +#include #elif HAVE_AGRAPH_H - #include +#include #endif void dot_add_task(Agnode_t * dag_node); @@ -42,7 +43,7 @@ static int dot_parse_int(const char *string) if (string == NULL) return -10; int ret = 0; - int value; + int value = -1; ret = sscanf(string, "%d", &value); if (ret != 1) @@ -53,8 +54,10 @@ static int dot_parse_int(const char *string) static xbt_dynar_t result; static xbt_dict_t jobs; static xbt_dict_t files; +static xbt_dict_t computers; static SD_task_t root_task, end_task; static Agraph_t *dag_dot; +static bool schedule = true; static void dump_res() { @@ -66,6 +69,93 @@ static void dump_res() } } +bool child_are_marked(SD_task_t task){ + SD_task_t child_task = NULL; + bool all_marked = true; + SD_dependency_t depafter = NULL; + int count; + xbt_dynar_foreach(task->tasks_after,count,depafter){ + child_task = depafter->dst; + //test marked + if(child_task->marked == 0) { + all_marked = false; + break; + } + child_task = NULL; + } + return all_marked; +} + +bool acyclic_graph_detection(xbt_dynar_t dag){ + int count=0, count_current=0; + bool all_marked = true; + SD_task_t task = NULL, parent_task = NULL; + SD_dependency_t depbefore = NULL; + xbt_dynar_t next = NULL, current = xbt_dynar_new(sizeof(SD_task_t),NULL); + + xbt_dynar_foreach(dag,count,task){ + if(task->kind == SD_TASK_COMM_E2E) continue; + task->marked = 0; + if(xbt_dynar_length(task->tasks_after) == 0){ + xbt_dynar_push(current, &task); + } + } + task = NULL; + count = 0; + //test if something has to be done for the next iteration + while(xbt_dynar_length(current) != 0){ + next = xbt_dynar_new(sizeof(SD_task_t),NULL); + //test if the current iteration is done + count_current=0; + xbt_dynar_foreach(current,count_current,task){ + if (task == NULL) continue; + count = 0; + //push task in next + task->marked = 1; + int count = 0; + xbt_dynar_foreach(task->tasks_before,count,depbefore){ + parent_task = depbefore->src; + if(parent_task->kind == SD_TASK_COMM_E2E){ + int j=0; + parent_task->marked = 1; + xbt_dynar_foreach(parent_task->tasks_before,j,depbefore){ + parent_task = depbefore->src; + if(child_are_marked(parent_task)) + xbt_dynar_push(next, &parent_task); + } + } else{ + if(child_are_marked(parent_task)) + xbt_dynar_push(next, &parent_task); + } + parent_task = NULL; + } + task = NULL; + count = 0; + } + xbt_dynar_free(¤t); + current = next; + next = NULL; + } + xbt_dynar_free(¤t); + current = NULL; + all_marked = true; + xbt_dynar_foreach(dag,count,task){ + if(task->kind == SD_TASK_COMM_E2E) continue; + //test if all tasks are marked + if(task->marked == 0){ + WARN1("test %d",task->name); + all_marked = false; + break; + } + } + task = NULL; + if(all_marked){ + WARN0("there are no cycle in your DAG"); + }else{ + WARN0("there are a cycle in your DAG"); + } +} + static void dot_task_free(void *task) { SD_task_t t = task; @@ -108,6 +198,7 @@ xbt_dynar_t SD_dotload_FILE(FILE * in_file) result = xbt_dynar_new(sizeof(SD_task_t), dot_task_free); files = xbt_dict_new(); jobs = xbt_dict_new(); + computers = xbt_dict_new(); root_task = SD_task_create_comp_seq("root", NULL, 0); /* by design the root task is always SCHEDULABLE */ __SD_task_set_state(root_task, SD_SCHEDULABLE); @@ -119,11 +210,12 @@ xbt_dynar_t SD_dotload_FILE(FILE * in_file) Agnode_t *dag_node = NULL; for (dag_node = agfstnode(dag_dot); dag_node; - #ifdef HAVE_CGRAPH_H - dag_node = agnxtnode(dag_dot, dag_node)) { - #elif HAVE_AGRAPH_H - dag_node = agnxtnode(dag_node)) { - #endif +#ifdef HAVE_CGRAPH_H + dag_node = agnxtnode(dag_dot, dag_node) +#elif HAVE_AGRAPH_H + dag_node = agnxtnode(dag_node) +#endif + ) { dot_add_task(dag_node); } @@ -181,6 +273,34 @@ xbt_dynar_t SD_dotload_FILE(FILE * in_file) /* Free previous copy of the files */ xbt_dict_free(&files); + if(schedule == false){ + WARN0("No scheduling provided"); + }else{ + xbt_dynar_t computer = NULL; + xbt_dict_cursor_t dict_cursor; + char *computer_name; + const SD_workstation_t *workstations = SD_workstation_get_list (); + xbt_dict_foreach(computers,dict_cursor,computer_name,computer){ + int count_computer = dot_parse_int(computer_name); + int count=0; + SD_task_t task; + SD_task_t task_previous = NULL; + xbt_dynar_foreach(computer,count,task){ + // add dependency between the previous and the task to avoid + // parallel execution + if(task != NULL ){ + if(task_previous != NULL && + !SD_task_dependency_exists(task_previous, task)) + SD_task_dependency_add(NULL, NULL, task_previous, task); + SD_task_schedulel(task, 1, workstations[count_computer]); + task_previous = task; + } + } + xbt_dynar_free(&computer); + } + xbt_dict_free(&computers); + } + acyclic_graph_detection(result); return result; } @@ -193,14 +313,13 @@ void dot_add_task(Agnode_t * dag_node) char *name = agnameof(dag_node); SD_task_t current_job; double runtime = dot_parse_double(agget(dag_node, (char *) "size")); - long performer = - (long) dot_parse_int((char *) agget(dag_node, (char *) "performer")); - INFO3("See ", name, + + DEBUG3("See ", name, agget(dag_node, (char *) "size"), runtime); current_job = xbt_dict_get_or_null(jobs, name); if (current_job == NULL) { current_job = - SD_task_create_comp_seq(name, (void *) performer, runtime); + SD_task_create_comp_seq(name, NULL , runtime); #ifdef HAVE_TRACING TRACE_sd_dotloader (current_job, agget (dag_node, (char*)"category")); #endif @@ -210,11 +329,12 @@ void dot_add_task(Agnode_t * dag_node) Agedge_t *e; int count = 0; - #ifdef HAVE_CGRAPH_H - for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e)) { - #elif HAVE_AGRAPH_H - for (e = agfstin(dag_node); e; e = agnxtin(e)) { - #endif +#ifdef HAVE_CGRAPH_H + for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e)) +#elif HAVE_AGRAPH_H + for (e = agfstin(dag_node); e; e = agnxtin(e)) +#endif + { dot_add_input_dependencies(current_job, e); count++; } @@ -222,11 +342,12 @@ void dot_add_task(Agnode_t * dag_node) SD_task_dependency_add(NULL, NULL, root_task, current_job); } count = 0; - #ifdef HAVE_CGRAPH_H - for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e)) { - #elif HAVE_AGRAPH_H - for (e = agfstout(dag_node); e; e = agnxtout(e)) { - #endif +#ifdef HAVE_CGRAPH_H + for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e)) +#elif HAVE_AGRAPH_H + for (e = agfstout(dag_node); e; e = agnxtout(e)) +#endif + { dot_add_output_dependencies(current_job, e); count++; @@ -234,6 +355,61 @@ void dot_add_task(Agnode_t * dag_node) if (count == 0 && current_job != end_task) { SD_task_dependency_add(NULL, NULL, current_job, end_task); } + + if(schedule || true){ + /* try to take the information to schedule the task only if all is + * right*/ + // performer is the computer which execute the task + unsigned long performer = -1; + char * char_performer = agget(dag_node, (char *) "performer"); + if (char_performer != NULL) + performer = (long) dot_parse_int(char_performer); + + // order is giving the task order on one computer + unsigned long order = -1; + char * char_order = agget(dag_node, (char *) "order"); + if (char_order != NULL) + order = (long) dot_parse_int(char_order); + xbt_dynar_t computer = NULL; + //INFO2("performer = %d, order=%d",performer,order); + if(performer != -1 && order != -1){ + //necessary parameters are given + computer = xbt_dict_get_or_null(computers, char_performer); + if(computer == NULL){ + computer = xbt_dynar_new(sizeof(SD_task_t), NULL); + xbt_dict_set(computers, char_performer, computer, NULL); + } + if(performer < sd_global->workstation_count){ + // the wanted computer is available + SD_task_t *task_test = NULL; + if(order < computer->used) + task_test = xbt_dynar_get_ptr(computer,order); + if(task_test != NULL && *task_test != NULL && *task_test != current_job){ + /*the user gives the same order to several tasks*/ + schedule = false; + WARN0("scheduling does not take into account, several task has\ + the same order"); + }else{ + //the parameter seems to be ok + xbt_dynar_set_as(computer, order, SD_task_t, current_job); + } + }else{ + /*the platform has not enough processors to schedule the DAG like + *the user wants*/ + schedule = false; + WARN0("scheduling does not take into account, not enough computers"); + } + } + else if((performer == -1 && order != -1) || + (performer != -1 && order == -1)){ + //one of necessary parameters are not given + schedule = false; + WARN0("scheduling does not take into account"); + } else { + //No schedule available + schedule = false; + } + } } /* dot_add_output_dependencies create the dependencies between a task @@ -247,9 +423,8 @@ void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge) char name[80]; sprintf(name, "%s->%s", agnameof(agtail(edge)), agnameof(aghead(edge))); double size = dot_parse_double(agget(edge, (char *) "size")); - INFO2("size : %e, get size : %s", size, agget(edge, (char *) "size")); - //int sender = dot_parse_int(agget(edge,(char*)"sender")); - //int reciever = dot_parse_int(agget(edge,(char*)"reciever")); + DEBUG2("size : %e, get size : %s", size, agget(edge, (char *) "size")); + if (size > 0) { file = xbt_dict_get_or_null(files, name); if (file == NULL) { @@ -283,11 +458,8 @@ void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge) char name[80]; sprintf(name, "%s->%s", agnameof(agtail(edge)), agnameof(aghead(edge))); double size = dot_parse_double(agget(edge, (char *) "size")); - INFO2("size : %e, get size : %s", size, agget(edge, (char *) "size")); - //int sender = dot_parse_int(agget(edge,(char*)"sender")); - //int reciever = dot_parse_int(agget(edge,(char*)"reciever")); + DEBUG2("size : %e, get size : %s", size, agget(edge, (char *) "size")); - //INFO2("See ",A_dot__uses_file,(is_input?"in":"out")); if (size > 0) { file = xbt_dict_get_or_null(files, name); if (file == NULL) { -- 2.20.1