From: Frederic Suter Date: Fri, 16 Sep 2016 12:03:19 +0000 (+0200) Subject: simplify and fix cycle detection X-Git-Tag: v3_14~401 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/810552c500b2aec788fd2a3401ae79a4132e0aea simplify and fix cycle detection updating tesh as some tasks outside a detected cycle were listed in the output. --- diff --git a/examples/simdag/dag-dotload/sd_dag-dotload.tesh b/examples/simdag/dag-dotload/sd_dag-dotload.tesh index 687feb3697..e1fc0a1978 100644 --- a/examples/simdag/dag-dotload/sd_dag-dotload.tesh +++ b/examples/simdag/dag-dotload/sd_dag-dotload.tesh @@ -217,7 +217,6 @@ $ rm -f ${srcdir:=.}/dag-dotload/dag.trace ${srcdir:=.}/dot.dot $ $SG_TEST_EXENV ${bindir:=.}/dag-dotload/sd_dag-dotload --log=no_loc ${srcdir:=.}/../platforms/two_clusters.xml ${srcdir:=.}/dag-dotload/dag_with_cycle.dot > [0.000000] [xbt_cfg/INFO] Switching to the L07 model to handle parallel tasks. > [0.000000] [sd_daxparse/WARNING] the task root is not marked -> [0.000000] [sd_daxparse/WARNING] the task 0 is in a cycle > [0.000000] [sd_daxparse/WARNING] the task 1 is in a cycle > [0.000000] [sd_daxparse/WARNING] the task 2 is in a cycle > [0.000000] [sd_daxparse/WARNING] the task 3 is in a cycle diff --git a/examples/simdag/daxload/sd_daxload.tesh b/examples/simdag/daxload/sd_daxload.tesh index ef0c988c80..f081afd037 100644 --- a/examples/simdag/daxload/sd_daxload.tesh +++ b/examples/simdag/daxload/sd_daxload.tesh @@ -130,7 +130,6 @@ $ $SG_TEST_EXENV ${bindir:=.}/daxload/sd_daxload --log=no_loc ${srcdir:=.}/../pl > [0.000000] [xbt_cfg/INFO] Switching to the L07 model to handle parallel tasks. > [0.000000] [sd_daxparse/WARNING] the task root is not marked > [0.000000] [sd_daxparse/WARNING] the task 1@task1 is in a cycle -> [0.000000] [sd_daxparse/WARNING] the task 2@task2 is in a cycle > [0.000000] [sd_daxparse/WARNING] the task 3@task3 is in a cycle > [0.000000] [sd_daxparse/ERROR] The DAX described in simple_dax_with_cycle.xml is not a DAG. It contains a cycle. > [0.000000] [test/ERROR] A problem occurred during DAX parsing (cycle or syntax). Do not continue this test diff --git a/src/simdag/sd_daxloader.cpp b/src/simdag/sd_daxloader.cpp index 2c8ced7649..c2c1ac1172 100644 --- a/src/simdag/sd_daxloader.cpp +++ b/src/simdag/sd_daxloader.cpp @@ -56,109 +56,85 @@ static bool parents_are_marked(SD_task_t task){ } bool acyclic_graph_detail(xbt_dynar_t dag){ - unsigned int count, count_current=0; + unsigned int count; bool all_marked = true; SD_task_t task = nullptr; - xbt_dynar_t next = nullptr, current = xbt_dynar_new(sizeof(SD_task_t),nullptr); - + std::vector current; xbt_dynar_foreach(dag,count,task){ - if(task->kind == SD_TASK_COMM_E2E) - continue; - task->marked = 0; - if(task->successors->empty() && task->outputs->empty()) - xbt_dynar_push(current, &task); + if(task->kind != SD_TASK_COMM_E2E){ + task->marked = 0; + if(task->successors->empty() && task->outputs->empty()) + current.push_back(task); + } } - //test if something has to be done for the next iteration - while(!xbt_dynar_is_empty(current)){ - next = xbt_dynar_new(sizeof(SD_task_t),nullptr); - //test if the current iteration is done - xbt_dynar_foreach(current,count_current,task){ - if (task == nullptr) - continue; - //push task in next - task->marked = 1; - for (SD_task_t it : *task->inputs){ - it->marked = 1; + while(!current.empty()){ + std::vector next; + for (auto t: current){ + //Mark task + t->marked = 1; + for (SD_task_t input : *t->inputs){ + input->marked=1; // Inputs are communication, hence they can have only one predecessor - SD_task_t input_pred = *(it->predecessors->begin()); + SD_task_t input_pred = *(input->predecessors->begin()); if (children_are_marked(input_pred)) - xbt_dynar_push(next, &input_pred); + next.push_back(input_pred); } - for (SD_task_t it : *task->predecessors) { - if (children_are_marked(it)) - xbt_dynar_push(next, &it); + for (SD_task_t pred : *t->predecessors) { + if (children_are_marked(pred)) + next.push_back(pred); } } - xbt_dynar_free(¤t); + current.clear(); current = next; - next = nullptr; } - xbt_dynar_free(¤t); + all_marked = true; + //test if all tasks are marked xbt_dynar_foreach(dag,count,task){ - if(task->kind == SD_TASK_COMM_E2E) - continue; - //test if all tasks are marked - if(task->marked == 0){ + if(task->kind != SD_TASK_COMM_E2E && task->marked == 0){ XBT_WARN("the task %s is not marked",task->name); all_marked = false; break; } } + if(!all_marked){ XBT_VERB("there is at least one cycle in your task graph"); - - current = xbt_dynar_new(sizeof(SD_task_t),nullptr); - xbt_dynar_foreach(dag,count,task){ - if(task->kind == SD_TASK_COMM_E2E) - continue; - if(task->predecessors->empty() && task->inputs->empty()){ - xbt_dynar_push(current, &task); - } - } - xbt_dynar_foreach(dag,count,task){ - if(task->kind == SD_TASK_COMM_E2E) - continue; - if(task->predecessors->empty() && task->inputs->empty()){ - task->marked = 1; - xbt_dynar_push(current, &task); + if(task->kind != SD_TASK_COMM_E2E) { + if(task->predecessors->empty() && task->inputs->empty()){ + task->marked = 1; + current.push_back(task); + } } } //test if something has to be done for the next iteration - while(!xbt_dynar_is_empty(current)){ - next = xbt_dynar_new(sizeof(SD_task_t),nullptr); + while(!current.empty()){ + std::vector next; //test if the current iteration is done - xbt_dynar_foreach(current,count_current,task){ - if (task == nullptr) - continue; - //push task in next - task->marked = 1; - for (SD_task_t it : *task->outputs) { - it->marked = 1; + for (auto t: current){ + t->marked = 1; + for (SD_task_t output : *t->outputs) { + output->marked = 1; // outputs are communication, hence they can have only one successor - SD_task_t output_succ = *(it->successors->begin()); + SD_task_t output_succ = *(output->successors->begin()); if (parents_are_marked(output_succ)) - xbt_dynar_push(next, &output_succ); + next.push_back(output_succ); } - for (SD_task_t it : *task->predecessors) { - if (parents_are_marked(it)) - xbt_dynar_push(next, &it); + for (SD_task_t succ : *t->successors) { + if (parents_are_marked(succ)) + next.push_back(succ); } - xbt_dynar_free(¤t); + current.clear(); current = next; - next = nullptr; } - xbt_dynar_free(¤t); - 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){ - XBT_WARN("the task %s is in a cycle",task->name); - all_marked = false; - } + } + + all_marked = true; + xbt_dynar_foreach(dag,count,task){ + if(task->kind != SD_TASK_COMM_E2E && task->marked == 0){ + XBT_WARN("the task %s is in a cycle",task->name); + all_marked = false; } } }