From: Frederic Suter Date: Thu, 21 Jul 2016 14:34:39 +0000 (+0200) Subject: change the way dependencies are handled X-Git-Tag: v3_14~738 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/8d49fc33cc147f3b7ddac64e3076348003d020a9 change the way dependencies are handled kill 2 never used functions kill the SD_dependency_t structure more simplifications are needed but it's a mess --- diff --git a/examples/simdag/dag-dotload/sd_dag-dotload.tesh b/examples/simdag/dag-dotload/sd_dag-dotload.tesh index 58f4773550..095e851cd2 100644 --- a/examples/simdag/dag-dotload/sd_dag-dotload.tesh +++ b/examples/simdag/dag-dotload/sd_dag-dotload.tesh @@ -10,8 +10,8 @@ $ $SG_TEST_EXENV ${bindir:=.}/dag-dotload/sd_dag-dotload --log=no_loc ${srcdir:= > [0.000000] [sd_task/INFO] - amount: 0 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 0 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] root->5 > [0.000000] [sd_task/INFO] 0 +> [0.000000] [sd_task/INFO] root->5 > [0.000000] [sd_task/INFO] Displaying task 0 > [0.000000] [sd_task/INFO] - state: not scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation @@ -63,8 +63,8 @@ $ $SG_TEST_EXENV ${bindir:=.}/dag-dotload/sd_dag-dotload --log=no_loc ${srcdir:= > [0.000000] [sd_task/INFO] - amount: 10000000046 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 2 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] 4->5 > [0.000000] [sd_task/INFO] root->5 +> [0.000000] [sd_task/INFO] 4->5 > [0.000000] [sd_task/INFO] - post-dependencies: > [0.000000] [sd_task/INFO] 6 > [0.000000] [sd_task/INFO] Displaying task 6 @@ -84,8 +84,8 @@ $ $SG_TEST_EXENV ${bindir:=.}/dag-dotload/sd_dag-dotload --log=no_loc ${srcdir:= > [0.000000] [sd_task/INFO] - pre-dependencies: > [0.000000] [sd_task/INFO] 6->7 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] 7->8 > [0.000000] [sd_task/INFO] 7->end +> [0.000000] [sd_task/INFO] 7->8 > [0.000000] [sd_task/INFO] Displaying task 8 > [0.000000] [sd_task/INFO] - state: not scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation @@ -182,8 +182,8 @@ $ $SG_TEST_EXENV ${bindir:=.}/dag-dotload/sd_dag-dotload --log=no_loc ${srcdir:= > [0.000000] [sd_task/INFO] - amount: 10000000129 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 2 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] 7->end > [0.000000] [sd_task/INFO] 9 +> [0.000000] [sd_task/INFO] 7->end > [0.000000] [test/INFO] ------------------- Schedule tasks --------------------------- > [0.000000] [test/INFO] ------------------- Run the schedule --------------------------- > [110.006082] [test/INFO] ------------------- Produce the trace file--------------------------- diff --git a/examples/simdag/daxload/sd_daxload.tesh b/examples/simdag/daxload/sd_daxload.tesh index fbb6c252ff..ece11729e1 100644 --- a/examples/simdag/daxload/sd_daxload.tesh +++ b/examples/simdag/daxload/sd_daxload.tesh @@ -12,8 +12,8 @@ $ $SG_TEST_EXENV ${bindir:=.}/daxload/sd_daxload --log=no_loc ${srcdir:=.}/../pl > [0.000000] [sd_task/INFO] - amount: 0 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 0 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] root_i2_2@task2 > [0.000000] [sd_task/INFO] root_i1_1@task1 +> [0.000000] [sd_task/INFO] root_i2_2@task2 > [0.000000] [sd_task/INFO] Displaying task 1@task1 > [0.000000] [sd_task/INFO] - state: not scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation @@ -40,10 +40,10 @@ $ $SG_TEST_EXENV ${bindir:=.}/daxload/sd_daxload --log=no_loc ${srcdir:=.}/../pl > [0.000000] [sd_task/INFO] - amount: 42000000000 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 4 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] 1@task1 > [0.000000] [sd_task/INFO] 2@task2 -> [0.000000] [sd_task/INFO] 1@task1_o1_3@task1 +> [0.000000] [sd_task/INFO] 1@task1 > [0.000000] [sd_task/INFO] 2@task2_o2_3@task1 +> [0.000000] [sd_task/INFO] 1@task1_o1_3@task1 > [0.000000] [sd_task/INFO] - post-dependencies: > [0.000000] [sd_task/INFO] 3@task1_o3_end > [0.000000] [sd_task/INFO] Displaying task root_i2_2@task2 diff --git a/examples/simdag/ptg-dotload/sd_ptg-dotload.tesh b/examples/simdag/ptg-dotload/sd_ptg-dotload.tesh index 116eef3ef2..6c08678d28 100644 --- a/examples/simdag/ptg-dotload/sd_ptg-dotload.tesh +++ b/examples/simdag/ptg-dotload/sd_ptg-dotload.tesh @@ -11,8 +11,8 @@ $ $SG_TEST_EXENV ${bindir:=.}/ptg-dotload/sd_ptg-dotload ${srcdir:=.}/../platfo > [0.000000] [sd_task/INFO] - alpha: 0.00 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 0 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] root->c1 > [0.000000] [sd_task/INFO] root->c2 +> [0.000000] [sd_task/INFO] root->c1 > [0.000000] [sd_task/INFO] Displaying task c1 > [0.000000] [sd_task/INFO] - state: not scheduled not runnable > [0.000000] [sd_task/INFO] - kind: parallel computation following Amdahl's law @@ -40,8 +40,8 @@ $ $SG_TEST_EXENV ${bindir:=.}/ptg-dotload/sd_ptg-dotload ${srcdir:=.}/../platfo > [0.000000] [sd_task/INFO] - alpha: 0.00 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 2 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] c1->c3 > [0.000000] [sd_task/INFO] c2 +> [0.000000] [sd_task/INFO] c1->c3 > [0.000000] [sd_task/INFO] - post-dependencies: > [0.000000] [sd_task/INFO] c3->end > [0.000000] [sd_task/INFO] Displaying task c1->c3 diff --git a/examples/simdag/schedule-dotload/sd_schedule-dotload.tesh b/examples/simdag/schedule-dotload/sd_schedule-dotload.tesh index b59adcbe61..ab26689820 100644 --- a/examples/simdag/schedule-dotload/sd_schedule-dotload.tesh +++ b/examples/simdag/schedule-dotload/sd_schedule-dotload.tesh @@ -21,9 +21,9 @@ $ $SG_TEST_EXENV ${bindir:=.}/schedule-dotload/sd_schedule-dotload --log=no_loc > [0.000000] [sd_task/INFO] - amount: 0 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 0 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] root->5 -> [0.000000] [sd_task/INFO] 0 > [0.000000] [sd_task/INFO] 1 +> [0.000000] [sd_task/INFO] 0 +> [0.000000] [sd_task/INFO] root->5 > [0.000000] [sd_task/INFO] Displaying task 0 > [0.000000] [sd_task/INFO] - state: scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation @@ -32,8 +32,8 @@ $ $SG_TEST_EXENV ${bindir:=.}/schedule-dotload/sd_schedule-dotload --log=no_loc > [0.000000] [sd_task/INFO] - pre-dependencies: > [0.000000] [sd_task/INFO] root > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] 0->2 > [0.000000] [sd_task/INFO] 2 +> [0.000000] [sd_task/INFO] 0->2 > [0.000000] [sd_task/INFO] Displaying task 1 > [0.000000] [sd_task/INFO] - state: scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation @@ -42,31 +42,31 @@ $ $SG_TEST_EXENV ${bindir:=.}/schedule-dotload/sd_schedule-dotload --log=no_loc > [0.000000] [sd_task/INFO] - pre-dependencies: > [0.000000] [sd_task/INFO] root > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] 1->2 > [0.000000] [sd_task/INFO] 4 +> [0.000000] [sd_task/INFO] 1->2 > [0.000000] [sd_task/INFO] Displaying task 2 > [0.000000] [sd_task/INFO] - state: scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation > [0.000000] [sd_task/INFO] - amount: 10000000121 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 3 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] 0->2 -> [0.000000] [sd_task/INFO] 1->2 > [0.000000] [sd_task/INFO] 0 +> [0.000000] [sd_task/INFO] 1->2 +> [0.000000] [sd_task/INFO] 0->2 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] 2->3 > [0.000000] [sd_task/INFO] 3 +> [0.000000] [sd_task/INFO] 2->3 > [0.000000] [sd_task/INFO] Displaying task 3 > [0.000000] [sd_task/INFO] - state: scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation > [0.000000] [sd_task/INFO] - amount: 10000000231 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 2 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] 2->3 > [0.000000] [sd_task/INFO] 2 +> [0.000000] [sd_task/INFO] 2->3 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] 4 > [0.000000] [sd_task/INFO] 8 +> [0.000000] [sd_task/INFO] 4 > [0.000000] [sd_task/INFO] Displaying task 4 > [0.000000] [sd_task/INFO] - state: scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation @@ -76,17 +76,17 @@ $ $SG_TEST_EXENV ${bindir:=.}/schedule-dotload/sd_schedule-dotload --log=no_loc > [0.000000] [sd_task/INFO] 3 > [0.000000] [sd_task/INFO] 1 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] 4->5 > [0.000000] [sd_task/INFO] 5 +> [0.000000] [sd_task/INFO] 4->5 > [0.000000] [sd_task/INFO] Displaying task 5 > [0.000000] [sd_task/INFO] - state: scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation > [0.000000] [sd_task/INFO] - amount: 10000000046 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 3 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] root->5 -> [0.000000] [sd_task/INFO] 4->5 > [0.000000] [sd_task/INFO] 4 +> [0.000000] [sd_task/INFO] 4->5 +> [0.000000] [sd_task/INFO] root->5 > [0.000000] [sd_task/INFO] - post-dependencies: > [0.000000] [sd_task/INFO] 6 > [0.000000] [sd_task/INFO] Displaying task 6 @@ -97,28 +97,28 @@ $ $SG_TEST_EXENV ${bindir:=.}/schedule-dotload/sd_schedule-dotload --log=no_loc > [0.000000] [sd_task/INFO] - pre-dependencies: > [0.000000] [sd_task/INFO] 5 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] 6->7 > [0.000000] [sd_task/INFO] 7 +> [0.000000] [sd_task/INFO] 6->7 > [0.000000] [sd_task/INFO] Displaying task 7 > [0.000000] [sd_task/INFO] - state: scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation > [0.000000] [sd_task/INFO] - amount: 10000000041 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 2 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] 6->7 > [0.000000] [sd_task/INFO] 6 +> [0.000000] [sd_task/INFO] 6->7 > [0.000000] [sd_task/INFO] - post-dependencies: -> [0.000000] [sd_task/INFO] 7->8 -> [0.000000] [sd_task/INFO] 7->end > [0.000000] [sd_task/INFO] end +> [0.000000] [sd_task/INFO] 7->end +> [0.000000] [sd_task/INFO] 7->8 > [0.000000] [sd_task/INFO] Displaying task 8 > [0.000000] [sd_task/INFO] - state: scheduled not runnable > [0.000000] [sd_task/INFO] - kind: sequential computation > [0.000000] [sd_task/INFO] - amount: 10000000250 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 2 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] 7->8 > [0.000000] [sd_task/INFO] 3 +> [0.000000] [sd_task/INFO] 7->8 > [0.000000] [sd_task/INFO] - post-dependencies: > [0.000000] [sd_task/INFO] 9 > [0.000000] [sd_task/INFO] Displaying task 9 @@ -208,9 +208,9 @@ $ $SG_TEST_EXENV ${bindir:=.}/schedule-dotload/sd_schedule-dotload --log=no_loc > [0.000000] [sd_task/INFO] - amount: 10000000129 > [0.000000] [sd_task/INFO] - Dependencies to satisfy: 3 > [0.000000] [sd_task/INFO] - pre-dependencies: -> [0.000000] [sd_task/INFO] 7->end > [0.000000] [sd_task/INFO] 9 > [0.000000] [sd_task/INFO] 7 +> [0.000000] [sd_task/INFO] 7->end > [0.000000] [test/INFO] ------------------- Run the schedule --------------------------- > [100.003561] [test/INFO] ------------------- Produce the trace file--------------------------- > [100.003561] [test/INFO] Producing the trace of the run into dag_with_good_schedule.trace diff --git a/include/simgrid/simdag.h b/include/simgrid/simdag.h index 77f9ea6eee..48eff33ca2 100644 --- a/include/simgrid/simdag.h +++ b/include/simgrid/simdag.h @@ -154,8 +154,6 @@ XBT_PUBLIC(void) SD_task_schedulel(SD_task_t task, int count, ...); */ XBT_PUBLIC(void) SD_task_dependency_add(const char *name, void *data, SD_task_t src, SD_task_t dst); XBT_PUBLIC(void) SD_task_dependency_remove(SD_task_t src, SD_task_t dst); -XBT_PUBLIC(const char *) SD_task_dependency_get_name(SD_task_t src, SD_task_t dst); -XBT_PUBLIC(void *) SD_task_dependency_get_data(SD_task_t src, SD_task_t dst); XBT_PUBLIC(int) SD_task_dependency_exists(SD_task_t src, SD_task_t dst); /** @} */ diff --git a/src/simdag/sd_daxloader.cpp b/src/simdag/sd_daxloader.cpp index 9d542db6a0..d8e0a91d34 100644 --- a/src/simdag/sd_daxloader.cpp +++ b/src/simdag/sd_daxloader.cpp @@ -25,58 +25,47 @@ extern "C" { void uniq_transfer_task_name(SD_task_t task) { - SD_task_t child; - SD_task_t parent; - - xbt_dynar_t children = SD_task_get_children(task); - xbt_dynar_t parents = SD_task_get_parents(task); - - xbt_dynar_get_cpy(children, 0, &child); - xbt_dynar_get_cpy(parents, 0, &parent); + SD_task_t child = *(task->successors->begin()); + SD_task_t parent = *(task->predecessors->begin()); char *new_name = bprintf("%s_%s_%s", SD_task_get_name(parent), SD_task_get_name(task), SD_task_get_name(child)); SD_task_set_name(task, new_name); - xbt_dynar_free_container(&children); - xbt_dynar_free_container(&parents); free(new_name); } static bool children_are_marked(SD_task_t task){ - SD_dependency_t depafter = nullptr; - unsigned int count; - - xbt_dynar_foreach(task->tasks_after,count,depafter){ - if(depafter->dst->marked == 0) + for (std::set::iterator it=task->successors->begin(); it!=task->successors->end(); ++it) + if ((*it)->marked == 0) + return false; + for (std::set::iterator it=task->outputs->begin(); it!=task->outputs->end(); ++it) + if ((*it)->marked == 0) return false; - } return true; } static bool parents_are_marked(SD_task_t task){ - SD_dependency_t depbefore = nullptr; - unsigned int count; - xbt_dynar_foreach(task->tasks_before,count,depbefore){ - if(depbefore->src->marked == 0) + for (std::set::iterator it=task->predecessors->begin(); it!=task->predecessors->end(); ++it) + if ((*it)->marked == 0) + return false; + for (std::set::iterator it=task->inputs->begin(); it!=task->inputs->end(); ++it) + if ((*it)->marked == 0) return false; - } return true; } bool acyclic_graph_detail(xbt_dynar_t dag){ unsigned int count, count_current=0; bool all_marked = true; - SD_task_t task = nullptr, parent_task = nullptr, child_task = nullptr; - SD_dependency_t depbefore = nullptr, depafter = nullptr; + SD_task_t task = nullptr; xbt_dynar_t next = nullptr, current = xbt_dynar_new(sizeof(SD_task_t),nullptr); xbt_dynar_foreach(dag,count,task){ if(task->kind == SD_TASK_COMM_E2E) continue; task->marked = 0; - if(xbt_dynar_is_empty(task->tasks_after)){ + if(task->successors->empty() && task->outputs->empty()) xbt_dynar_push(current, &task); - } } //test if something has to be done for the next iteration while(!xbt_dynar_is_empty(current)){ @@ -87,22 +76,16 @@ bool acyclic_graph_detail(xbt_dynar_t dag){ continue; //push task in next task->marked = 1; - xbt_dynar_foreach(task->tasks_before,count,depbefore){ - parent_task = depbefore->src; - if(parent_task->kind == SD_TASK_COMM_E2E){ - unsigned int j=0; - parent_task->marked = 1; - SD_task_t parent_task_2 = nullptr; - xbt_dynar_foreach(parent_task->tasks_before,j,depbefore){ - parent_task_2 = depbefore->src; - if(children_are_marked(parent_task_2)) - xbt_dynar_push(next, &parent_task_2); - } - } else{ - if(children_are_marked(parent_task)) - xbt_dynar_push(next, &parent_task); - } - parent_task = nullptr; + for (std::set::iterator it=task->inputs->begin(); it!=task->inputs->end(); ++it){ + (*it)->marked = 1; + // Inputs are communication, hence they can have only one predecessor + SD_task_t input_pred = *((*it)->predecessors->begin()); + if (children_are_marked(input_pred)) + xbt_dynar_push(next, &input_pred); + } + for (std::set::iterator it=task->predecessors->begin(); it!=task->predecessors->end(); ++it){ + if (children_are_marked(*it)) + xbt_dynar_push(next, &(*it)); } } xbt_dynar_free(¤t); @@ -128,15 +111,15 @@ bool acyclic_graph_detail(xbt_dynar_t dag){ xbt_dynar_foreach(dag,count,task){ if(task->kind == SD_TASK_COMM_E2E) continue; - if(xbt_dynar_is_empty(task->tasks_before)){ + 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(xbt_dynar_is_empty(task->tasks_before)){ + continue; + if(task->predecessors->empty() && task->inputs->empty()){ task->marked = 1; xbt_dynar_push(current, &task); } @@ -150,37 +133,31 @@ bool acyclic_graph_detail(xbt_dynar_t dag){ continue; //push task in next task->marked = 1; - xbt_dynar_foreach(task->tasks_after,count,depafter){ - child_task = depbefore->dst; - if(child_task->kind == SD_TASK_COMM_E2E){ - unsigned int j=0; - child_task->marked = 1; - SD_task_t child_task_2 = nullptr; - xbt_dynar_foreach(child_task->tasks_after,j,depafter){ - child_task_2 = depbefore->dst; - if(parents_are_marked(child_task_2)) - xbt_dynar_push(next, &child_task_2); - } - } else{ - if(parents_are_marked(child_task)) - xbt_dynar_push(next, &child_task); - } - child_task = nullptr; + for (std::set::iterator it=task->outputs->begin(); it!=task->outputs->end(); ++it){ + (*it)->marked = 1; + // outputs are communication, hence they can have only one successor + SD_task_t output_succ = *((*it)->successors->begin()); + if (parents_are_marked(output_succ)) + xbt_dynar_push(next, &output_succ); + } + for (std::set::iterator it=task->predecessors->begin(); it!=task->predecessors->end(); ++it){ + if (parents_are_marked(*it)) + xbt_dynar_push(next, &(*it)); } + xbt_dynar_free(¤t); + current = next; + next = nullptr; } xbt_dynar_free(¤t); - 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) + 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; + } } } } @@ -240,36 +217,31 @@ xbt_dynar_t SD_daxload(const char *filename) */ xbt_dict_foreach(files, cursor, name, file) { - unsigned int cpt1; - unsigned int cpt2; SD_task_t newfile; - SD_dependency_t depbefore; - SD_dependency_t depafter; - if (xbt_dynar_is_empty(file->tasks_before)) { - xbt_dynar_foreach(file->tasks_after, cpt2, depafter) { + if (file->predecessors->empty()) { + for (std::set::iterator it=file->successors->begin(); it!=file->successors->end(); ++it){ newfile = SD_task_create_comm_e2e(file->name, nullptr, file->amount); SD_task_dependency_add(nullptr, nullptr, root_task, newfile); - SD_task_dependency_add(nullptr, nullptr, newfile, depafter->dst); + SD_task_dependency_add(nullptr, nullptr, newfile, (*it)); xbt_dynar_push(result, &newfile); } - } else if (xbt_dynar_is_empty(file->tasks_after)) { - xbt_dynar_foreach(file->tasks_before, cpt2, depbefore) { + } else if (file->successors->empty()) { + for (std::set::iterator it=file->predecessors->begin(); it!=file->predecessors->end(); ++it){ newfile = SD_task_create_comm_e2e(file->name, nullptr, file->amount); - SD_task_dependency_add(nullptr, nullptr, depbefore->src, newfile); + SD_task_dependency_add(nullptr, nullptr, (*it), newfile); SD_task_dependency_add(nullptr, nullptr, newfile, end_task); xbt_dynar_push(result, &newfile); } } else { - xbt_dynar_foreach(file->tasks_before, cpt1, depbefore) { - xbt_dynar_foreach(file->tasks_after, cpt2, depafter) { - if (depbefore->src == depafter->dst) { - XBT_WARN - ("File %s is produced and consumed by task %s." - "This loop dependency will prevent the execution of the task.", file->name, depbefore->src->name); + for (std::set::iterator it=file->predecessors->begin(); it!=file->predecessors->end(); ++it){ + for (std::set::iterator it2=file->successors->begin(); it2!=file->successors->end(); ++it2){ + if (*it == *it2) { + XBT_WARN ("File %s is produced and consumed by task %s." + "This loop dependency will prevent the execution of the task.", file->name, (*it)->name); } newfile = SD_task_create_comm_e2e(file->name, nullptr, file->amount); - SD_task_dependency_add(nullptr, nullptr, depbefore->src, newfile); - SD_task_dependency_add(nullptr, nullptr, newfile, depafter->dst); + SD_task_dependency_add(nullptr, nullptr, (*it), newfile); + SD_task_dependency_add(nullptr, nullptr, newfile, (*it2)); xbt_dynar_push(result, &newfile); } } @@ -289,10 +261,10 @@ xbt_dynar_t SD_daxload(const char *filename) /* If some tasks do not take files as input, connect them to the root * if they don't produce files, connect them to the end node. */ - if ((file != root_task) && xbt_dynar_is_empty(file->tasks_before)) - SD_task_dependency_add(nullptr, nullptr, root_task, file); - if ((file != end_task) && xbt_dynar_is_empty(file->tasks_after)) - SD_task_dependency_add(nullptr, nullptr, file, end_task); + if ((file != root_task) && file->inputs->empty()) + SD_task_dependency_add(nullptr, nullptr, root_task, file); + if ((file != end_task) && file->outputs->empty()) + SD_task_dependency_add(nullptr, nullptr, file, end_task); } else { THROW_IMPOSSIBLE; } @@ -351,7 +323,7 @@ void STag_dax__uses(void) SD_task_dependency_add(nullptr, nullptr, file, current_job); } else { SD_task_dependency_add(nullptr, nullptr, current_job, file); - if (xbt_dynar_length(file->tasks_before) > 1) { + if ((file->predecessors->size() + file->inputs->size()) > 1) { XBT_WARN("File %s created at more than one location...", file->name); } } diff --git a/src/simdag/sd_dotloader.cpp b/src/simdag/sd_dotloader.cpp index 98024df194..5a35d52f27 100644 --- a/src/simdag/sd_dotloader.cpp +++ b/src/simdag/sd_dotloader.cpp @@ -194,12 +194,12 @@ xbt_dynar_t SD_dotload_generic(const char * filename, seq_par_t seq_or_par, bool /* Connect entry tasks to 'root', and exit tasks to 'end'*/ xbt_dynar_foreach (result, i, task){ - if (xbt_dynar_is_empty(task->tasks_before) && task != root) { + if (task->predecessors->empty() && task->inputs->empty() && task != root) { XBT_DEBUG("Task '%s' has no source. Add dependency from 'root'", task->name); SD_task_dependency_add(nullptr, nullptr, root, task); } - if (xbt_dynar_is_empty(task->tasks_after) && task != end) { + if (task->successors->empty() && task->outputs->empty() && task != end) { XBT_DEBUG("Task '%s' has no destination. Add dependency to 'end'", task->name); SD_task_dependency_add(nullptr, nullptr, task, end); } diff --git a/src/simdag/sd_global.cpp b/src/simdag/sd_global.cpp index bb652b3dce..93d7cb6a66 100644 --- a/src/simdag/sd_global.cpp +++ b/src/simdag/sd_global.cpp @@ -119,9 +119,8 @@ xbt_dynar_t SD_simulate(double how_long) { /* we stop the simulation when total_time >= how_long */ double total_time = 0.0; SD_task_t task, dst; - SD_dependency_t dependency; surf_action_t action; - unsigned int iter, depcnt; + unsigned int iter; XBT_VERB("Run simulation for %f seconds", how_long); sd_global->watch_point_reached = 0; @@ -169,15 +168,13 @@ xbt_dynar_t SD_simulate(double how_long) { } /* remove the dependencies after this task */ - xbt_dynar_foreach(task->tasks_after, depcnt, dependency) { - dst = dependency->dst; + for (std::set::iterator it=task->successors->begin(); it!=task->successors->end(); ++it){ + dst=*it; dst->unsatisfied_dependencies--; if (dst->is_not_ready > 0) dst->is_not_ready--; - XBT_DEBUG("Released a dependency on %s: %d remain(s). Became schedulable if %d=0", SD_task_get_name(dst), dst->unsatisfied_dependencies, dst->is_not_ready); - if (dst->unsatisfied_dependencies == 0) { if (SD_task_get_state(dst) == SD_SCHEDULED) SD_task_set_state(dst, SD_RUNNABLE); @@ -188,25 +185,32 @@ xbt_dynar_t SD_simulate(double how_long) { if (SD_task_get_state(dst) == SD_NOT_SCHEDULED && dst->is_not_ready == 0) { SD_task_set_state(dst, SD_SCHEDULABLE); } + if (SD_task_get_state(dst) == SD_RUNNABLE && !sd_global->watch_point_reached) { + XBT_VERB("Executing task '%s'", SD_task_get_name(dst)); + SD_task_run(dst); + xbt_dynar_push(sd_global->return_set, &dst); + } + } - if (SD_task_get_kind(dst) == SD_TASK_COMM_E2E) { - SD_dependency_t comm_dep; - SD_task_t comm_dst; - xbt_dynar_get_cpy(dst->tasks_after, 0, &comm_dep); - comm_dst = comm_dep->dst; - if (SD_task_get_state(comm_dst) == SD_NOT_SCHEDULED && comm_dst->is_not_ready > 0) { - comm_dst->is_not_ready--; + for (std::set::iterator it=task->outputs->begin(); it!=task->outputs->end(); ++it){ + dst=*it; + dst->unsatisfied_dependencies = 0; + dst->is_not_ready = 0; + if (SD_task_get_state(dst) == SD_SCHEDULED) + SD_task_set_state(dst, SD_RUNNABLE); + else + SD_task_set_state(dst, SD_SCHEDULABLE); + SD_task_t comm_dst = *(dst->successors->begin()); + if (SD_task_get_state(comm_dst) == SD_NOT_SCHEDULED && comm_dst->is_not_ready > 0) { + comm_dst->is_not_ready--; XBT_DEBUG("%s is a transfer, %s may be ready now if %d=0", - SD_task_get_name(dst), SD_task_get_name(comm_dst), comm_dst->is_not_ready); + SD_task_get_name(dst), SD_task_get_name(comm_dst), comm_dst->is_not_ready); - if (comm_dst->is_not_ready == 0) { - SD_task_set_state(comm_dst, SD_SCHEDULABLE); - } + if (comm_dst->is_not_ready == 0) { + SD_task_set_state(comm_dst, SD_SCHEDULABLE); } } - - /* is dst runnable now? */ if (SD_task_get_state(dst) == SD_RUNNABLE && !sd_global->watch_point_reached) { XBT_VERB("Executing task '%s'", SD_task_get_name(dst)); SD_task_run(dst); @@ -231,8 +235,7 @@ xbt_dynar_t SD_simulate(double how_long) { } if (!sd_global->watch_point_reached && how_long<0 && !sd_global->initial_tasks->empty()) { - XBT_WARN("Simulation is finished but %zu tasks are still not done", - sd_global->initial_tasks->size()); + XBT_WARN("Simulation is finished but %zu tasks are still not done", sd_global->initial_tasks->size()); static const char* state_names[] = { "SD_NOT_SCHEDULED", "SD_SCHEDULABLE", "SD_SCHEDULED", "SD_RUNNABLE", "SD_RUNNING", "SD_DONE","SD_FAILED" }; for (std::set::iterator it=sd_global->initial_tasks->begin(); diff --git a/src/simdag/sd_task.cpp b/src/simdag/sd_task.cpp index e90ce7d9d7..9b677f8866 100644 --- a/src/simdag/sd_task.cpp +++ b/src/simdag/sd_task.cpp @@ -12,29 +12,6 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd, "Logging specific to SimDag (task)"); -/* Destroys a dependency between two tasks. */ -static void __SD_task_dependency_destroy(void *dependency) -{ - xbt_free(((SD_dependency_t)dependency)->name); - xbt_free(dependency); -} - -/* Remove all dependencies associated with a task. This function is called when the task is destroyed. */ -static void __SD_task_remove_dependencies(SD_task_t task) -{ - /* we must destroy the dependencies carefully (with SD_dependency_remove) because each one is stored twice */ - SD_dependency_t dependency; - while (xbt_dynar_is_empty(task->tasks_before) == 0) { - xbt_dynar_get_cpy(task->tasks_before, 0, &dependency); - SD_task_dependency_remove(dependency->src, dependency->dst); - } - - while (xbt_dynar_is_empty(task->tasks_after) == 0) { - xbt_dynar_get_cpy(task->tasks_after, 0, &dependency); - SD_task_dependency_remove(dependency->src, dependency->dst); - } -} - /* Destroys the data memorized by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE. */ static void __SD_task_destroy_scheduling_data(SD_task_t task) { @@ -50,9 +27,11 @@ static void __SD_task_destroy_scheduling_data(SD_task_t task) void* SD_task_new_f() { SD_task_t task = xbt_new0(s_SD_task_t, 1); - task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), nullptr); - task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), nullptr); + task->inputs = new std::set(); + task->outputs = new std::set(); + task->predecessors = new std::set(); + task->successors = new std::set(); return task; } @@ -73,11 +52,14 @@ void SD_task_recycle_f(void *t) task->watch_points = 0; /* dependencies */ - xbt_dynar_reset(task->tasks_before); - xbt_dynar_reset(task->tasks_after); task->unsatisfied_dependencies = 0; task->is_not_ready = 0; + task->inputs->clear(); + task->outputs->clear(); + task->predecessors->clear(); + task->successors->clear(); + /* scheduling parameters */ task->host_count = 0; task->host_list = nullptr; @@ -90,8 +72,11 @@ void SD_task_free_f(void *t) { SD_task_t task = static_cast(t); - xbt_dynar_free(&task->tasks_before); - xbt_dynar_free(&task->tasks_after); + delete task->inputs; + delete task->outputs; + delete task->predecessors; + delete task->successors; + xbt_free(task); } @@ -228,7 +213,15 @@ void SD_task_destroy(SD_task_t task) { XBT_DEBUG("Destroying task %s...", SD_task_get_name(task)); - __SD_task_remove_dependencies(task); + /* First Remove all dependencies associated with the task. */ + while (!task->predecessors->empty()) + SD_task_dependency_remove(*(task->predecessors->begin()), task); + while (!task->inputs->empty()) + SD_task_dependency_remove(*(task->inputs->begin()), task); + while (!task->successors->empty()) + SD_task_dependency_remove(task, *(task->successors->begin())); + while (!task->outputs->empty()) + SD_task_dependency_remove(task, *(task->outputs->begin())); if (task->state == SD_SCHEDULED || task->state == SD_RUNNABLE) __SD_task_destroy_scheduling_data(task); @@ -335,7 +328,7 @@ void SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state) } break; case SD_RUNNABLE: - idx = std::find(sd_global->initial_tasks->begin(), sd_global->initial_tasks->end(), task); + idx = sd_global->initial_tasks->find(task); if (idx != sd_global->initial_tasks->end()) { sd_global->executable_tasks->insert(*idx); sd_global->initial_tasks->erase(idx); @@ -394,13 +387,13 @@ void SD_task_set_name(SD_task_t task, const char *name) xbt_dynar_t SD_task_get_parents(SD_task_t task) { - unsigned int i; - SD_dependency_t dep; - xbt_dynar_t parents = xbt_dynar_new(sizeof(SD_task_t), nullptr); - xbt_dynar_foreach(task->tasks_before, i, dep) { - xbt_dynar_push(parents, &(dep->src)); - } + + for (std::set::iterator it=task->predecessors->begin(); it!=task->predecessors->end(); ++it) + xbt_dynar_push(parents, &(*it)); + for (std::set::iterator it=task->inputs->begin(); it!=task->inputs->end(); ++it) + xbt_dynar_push(parents, &(*it)); + return parents; } @@ -411,13 +404,13 @@ xbt_dynar_t SD_task_get_parents(SD_task_t task) */ xbt_dynar_t SD_task_get_children(SD_task_t task) { - unsigned int i; - SD_dependency_t dep; - xbt_dynar_t children = xbt_dynar_new(sizeof(SD_task_t), nullptr); - xbt_dynar_foreach(task->tasks_after, i, dep) { - xbt_dynar_push(children, &(dep->dst)); - } + + for (std::set::iterator it=task->successors->begin(); it!=task->successors->end(); ++it) + xbt_dynar_push(children, &(*it)); + for (std::set::iterator it=task->outputs->begin(); it!=task->outputs->end(); ++it) + xbt_dynar_push(children, &(*it)); + return children; } @@ -507,9 +500,6 @@ e_SD_task_kind_t SD_task_get_kind(SD_task_t task) /** @brief Displays debugging information about a task */ void SD_task_dump(SD_task_t task) { - unsigned int counter; - SD_dependency_t dependency; - XBT_INFO("Displaying task %s", SD_task_get_name(task)); char *statename = bprintf("%s%s%s%s%s%s%s", (task->state == SD_NOT_SCHEDULED ? " not scheduled" : ""), @@ -548,25 +538,27 @@ void SD_task_dump(SD_task_t task) if (task->kind == SD_TASK_COMP_PAR_AMDAHL) XBT_INFO(" - alpha: %.2f", task->alpha); XBT_INFO(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies); - if (xbt_dynar_is_empty(task->tasks_before) == 0) { + if ((task->inputs->size()+ task->predecessors->size()) > 0) { XBT_INFO(" - pre-dependencies:"); - xbt_dynar_foreach(task->tasks_before, counter, dependency) { - XBT_INFO(" %s", SD_task_get_name(dependency->src)); - } + for (std::set::iterator it=task->predecessors->begin(); it!=task->predecessors->end(); ++it) + XBT_INFO(" %s", SD_task_get_name(*it)); + + for (std::set::iterator it=task->inputs->begin(); it!=task->inputs->end(); ++it) + XBT_INFO(" %s", SD_task_get_name(*it)); } - if (xbt_dynar_is_empty(task->tasks_after)== 0) { + if ((task->outputs->size() + task->successors->size()) > 0) { XBT_INFO(" - post-dependencies:"); - xbt_dynar_foreach(task->tasks_after, counter, dependency) { - XBT_INFO(" %s", SD_task_get_name(dependency->dst)); - } + + for (std::set::iterator it=task->successors->begin(); it!=task->successors->end(); ++it) + XBT_INFO(" %s", SD_task_get_name(*it)); + for (std::set::iterator it=task->outputs->begin(); it!=task->outputs->end(); ++it) + XBT_INFO(" %s", SD_task_get_name(*it)); } } /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */ void SD_task_dotty(SD_task_t task, void *out) { - unsigned int counter; - SD_dependency_t dependency; FILE *fout = static_cast(out); fprintf(fout, " T%p [label=\"%.20s\"", task, task->name); switch (task->kind) { @@ -582,9 +574,10 @@ void SD_task_dotty(SD_task_t task, void *out) xbt_die("Unknown task type!"); } fprintf(fout, "];\n"); - xbt_dynar_foreach(task->tasks_before, counter, dependency) { - fprintf(fout, " T%p -> T%p;\n", dependency->src, dependency->dst); - } + for (std::set::iterator it=task->predecessors->begin(); it!=task->predecessors->end(); ++it) + fprintf(fout, " T%p -> T%p;\n", (*it), task); + for (std::set::iterator it=task->inputs->begin(); it!=task->inputs->end(); ++it) + fprintf(fout, " T%p -> T%p;\n", (*it), task); } /** @@ -601,75 +594,58 @@ void SD_task_dotty(SD_task_t task, void *out) */ void SD_task_dependency_add(const char *name, void *data, SD_task_t src, SD_task_t dst) { - bool found = false; - SD_dependency_t dependency; - - unsigned long length = xbt_dynar_length(src->tasks_after); if (src == dst) THROWF(arg_error, 0, "Cannot add a dependency between task '%s' and itself", SD_task_get_name(src)); e_SD_task_state_t state = SD_task_get_state(src); - if (state != SD_NOT_SCHEDULED && state != SD_SCHEDULABLE && state != SD_RUNNING && state != SD_SCHEDULED && - state != SD_RUNNABLE) + if (state == SD_DONE || state == SD_FAILED) THROWF(arg_error, 0, "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNABLE, or SD_RUNNING", SD_task_get_name(src)); state = SD_task_get_state(dst); - if (state != SD_NOT_SCHEDULED && state != SD_SCHEDULABLE && state != SD_SCHEDULED && state != SD_RUNNABLE) + if (state == SD_DONE || state == SD_FAILED || state == SD_RUNNING) THROWF(arg_error, 0, "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED, or SD_RUNNABLE", SD_task_get_name(dst)); - XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src), SD_task_get_name(dst)); - for (unsigned long i = 0; i < length && !found; i++) { - xbt_dynar_get_cpy(src->tasks_after, i, &dependency); - found = (dependency->dst == dst); - XBT_DEBUG("Dependency %lu: dependency->dst = %s", i, SD_task_get_name(dependency->dst)); - } - - if (found) + if (src->successors->find(dst) != src->successors->end() || + dst->predecessors->find(src) != dst->predecessors->end() || + dst->inputs->find(src) != dst->inputs->end() || + src->outputs->find(dst) != src->outputs->end()) THROWF(arg_error, 0, "A dependency already exists between task '%s' and task '%s'", SD_task_get_name(src), SD_task_get_name(dst)); - dependency = xbt_new(s_SD_dependency_t, 1); + XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src), SD_task_get_name(dst)); - dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with nullptr args itself */ - dependency->data = data; - dependency->src = src; - dependency->dst = dst; + e_SD_task_kind_t src_kind = SD_task_get_kind(src); + e_SD_task_kind_t dst_kind = SD_task_get_kind(dst); - /* src must be executed before dst */ - xbt_dynar_push(src->tasks_after, &dependency); - xbt_dynar_push(dst->tasks_before, &dependency); + if (src_kind == SD_TASK_COMM_E2E || src_kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){ + if (dst_kind == SD_TASK_COMP_SEQ || dst_kind == SD_TASK_COMP_PAR_AMDAHL){ + dst->inputs->insert(src); + } else { + dst->predecessors->insert(src); + } + src->successors->insert(dst); + } else { + if (dst_kind == SD_TASK_COMM_E2E|| dst_kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){ + src->outputs->insert(dst); + } else { + src->successors->insert(dst); + } + dst->predecessors->insert(src); + } dst->unsatisfied_dependencies++; dst->is_not_ready++; - /* if the task was runnable, then dst->tasks_before is not empty anymore, so we must go back to state SD_SCHEDULED */ + /* if the task was runnable, the task goes back to SD_SCHEDULED because of the new dependency*/ if (SD_task_get_state(dst) == SD_RUNNABLE) { XBT_DEBUG("SD_task_dependency_add: %s was runnable and becomes scheduled!", SD_task_get_name(dst)); SD_task_set_state(dst, SD_SCHEDULED); } } -/** - * \brief Returns the name given as input when dependency has been created. - * - * \param src a task - * \param dst a task depending on \a src - */ -const char *SD_task_dependency_get_name(SD_task_t src, SD_task_t dst) -{ - unsigned int i; - SD_dependency_t dependency; - - xbt_dynar_foreach(src->tasks_after, i, dependency){ - if (dependency->dst == dst) - return dependency->name; - } - return nullptr; -} - /** * \brief Indicates whether there is a dependency between two tasks. * @@ -685,17 +661,12 @@ int SD_task_dependency_exists(SD_task_t src, SD_task_t dst) if (src) { if (dst) { - unsigned int counter; - SD_dependency_t dependency; - xbt_dynar_foreach(src->tasks_after, counter, dependency) { - if (dependency->dst == dst) - return 1; - } + return (src->successors->find(dst) != src->successors->end() || src->outputs->find(dst) != src->outputs->end()); } else { - return xbt_dynar_length(src->tasks_after); + return src->successors->size() + src->outputs->size(); } } else { - return xbt_dynar_length(dst->tasks_before); + return dst->predecessors->size() + dst->inputs->size(); } return 0; } @@ -709,43 +680,39 @@ int SD_task_dependency_exists(SD_task_t src, SD_task_t dst) */ void SD_task_dependency_remove(SD_task_t src, SD_task_t dst) { - unsigned long length; - bool found = false; - SD_dependency_t dependency; - - /* remove the dependency from src->tasks_after */ - length = xbt_dynar_length(src->tasks_after); - - for (unsigned long i = 0; i < length && !found; i++) { - xbt_dynar_get_cpy(src->tasks_after, i, &dependency); - if (dependency->dst == dst) { - xbt_dynar_remove_at(src->tasks_after, i, nullptr); - found = true; - } - } - if (!found) + + XBT_DEBUG("SD_task_dependency_remove: src = %s, dst = %s", SD_task_get_name(src), SD_task_get_name(dst)); + + if (src->successors->find(dst) == src->successors->end() && + src->outputs->find(dst) == src->outputs->end()) THROWF(arg_error, 0, "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'", SD_task_get_name(src), SD_task_get_name(dst), SD_task_get_name(dst), SD_task_get_name(src)); - /* remove the dependency from dst->tasks_before */ - length = xbt_dynar_length(dst->tasks_before); - found = false; - - for (unsigned long i = 0; i < length && !found; i++) { - xbt_dynar_get_cpy(dst->tasks_before, i, &dependency); - if (dependency->src == src) { - xbt_dynar_remove_at(dst->tasks_before, i, nullptr); - __SD_task_dependency_destroy(dependency); - dst->unsatisfied_dependencies--; - dst->is_not_ready--; - found = true; + if (dst->predecessors->find(src) != dst->predecessors->end() || + dst->inputs->find(src) != dst->inputs->end()){ + dst->unsatisfied_dependencies--; + dst->is_not_ready--; + } + + e_SD_task_kind_t src_kind = SD_task_get_kind(src); + e_SD_task_kind_t dst_kind = SD_task_get_kind(dst); + if (src_kind == SD_TASK_COMM_E2E || src_kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){ + if (dst_kind == SD_TASK_COMP_SEQ || dst_kind == SD_TASK_COMP_PAR_AMDAHL){ + dst->inputs->erase(src); + } else { + dst->predecessors->erase(src); + } + src->successors->erase(dst); + } else { + if (dst_kind == SD_TASK_COMM_E2E|| dst_kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){ + src->outputs->erase(dst); + } else { + src->successors->erase(dst); } + dst->predecessors->erase(src); } - /* should never happen... */ - xbt_assert(found, "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'", - SD_task_get_name(dst), SD_task_get_name(src), SD_task_get_name(src), SD_task_get_name(dst)); - /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */ + /* if the task was scheduled and dependencies are satisfied, we can make it runnable */ if (dst->unsatisfied_dependencies == 0) { if (SD_task_get_state(dst) == SD_SCHEDULED) SD_task_set_state(dst, SD_RUNNABLE); @@ -757,31 +724,6 @@ void SD_task_dependency_remove(SD_task_t src, SD_task_t dst) SD_task_set_state(dst, SD_SCHEDULABLE); } -/** - * \brief Returns the user data associated with a dependency between two tasks - * - * \param src a task - * \param dst a task depending on \a src - * \return the user data associated with this dependency (can be \c nullptr) - * \see SD_task_dependency_add() - */ -void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst) -{ - bool found = false; - SD_dependency_t dependency; - - unsigned long length = xbt_dynar_length(src->tasks_after); - - for (unsigned long i = 0; i < length && !found; i++) { - xbt_dynar_get_cpy(src->tasks_after, i, &dependency); - found = (dependency->dst == dst); - } - if (!found) - THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'", - SD_task_get_name(src), SD_task_get_name(dst)); - return dependency->data; -} - /** * \brief Adds a watch point to a task * @@ -1056,9 +998,8 @@ void SD_task_distribute_comp_amdahl(SD_task_t task, int ws_count) */ void SD_task_schedulev(SD_task_t task, int count, const sg_host_t * list) { - int i, j; - SD_dependency_t dep; - unsigned int cpt; + int i; + int j; xbt_assert(task->kind != 0, "Task %s is not typed. Cannot automatically schedule it.", SD_task_get_name(task)); switch (task->kind) { case SD_TASK_COMP_PAR_AMDAHL: @@ -1085,140 +1026,135 @@ void SD_task_schedulev(SD_task_t task, int count, const sg_host_t * list) sg_host_get_name(task->host_list[0]), sg_host_get_name(task->host_list[1]), task->bytes_amount[2]); } - /* Iterate over all children and parents being COMM_E2E to say where I am located (and start them if runnable) */ + /* Iterate over all inputs and outputs to say where I am located (and start them if runnable) */ if (task->kind == SD_TASK_COMP_SEQ) { XBT_VERB("Schedule computation task %s on %s. It costs %.f flops", SD_task_get_name(task), sg_host_get_name(task->host_list[0]), task->flops_amount[0]); - xbt_dynar_foreach(task->tasks_before, cpt, dep) { - SD_task_t before = dep->src; - if (before->kind == SD_TASK_COMM_E2E) { - before->host_list[1] = task->host_list[0]; - - if (before->host_list[0] && (SD_task_get_state(before) < SD_SCHEDULED)) { - SD_task_do_schedule(before); - XBT_VERB ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes", SD_task_get_name(before), - sg_host_get_name(before->host_list[0]), sg_host_get_name(before->host_list[1]), before->bytes_amount[2]); - } + for (std::set::iterator it=task->inputs->begin(); it!=task->inputs->end(); ++it){ + SD_task_t input = *it; + input->host_list[1] = task->host_list[0]; + if (input->host_list[0] && (SD_task_get_state(input) < SD_SCHEDULED)) { + SD_task_do_schedule(input); + XBT_VERB ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes", SD_task_get_name(input), + sg_host_get_name(input->host_list[0]), sg_host_get_name(input->host_list[1]), input->bytes_amount[2]); } } - xbt_dynar_foreach(task->tasks_after, cpt, dep) { - SD_task_t after = dep->dst; - if (after->kind == SD_TASK_COMM_E2E) { - after->host_list[0] = task->host_list[0]; - if (after->host_list[1] && (SD_task_get_state(after) < SD_SCHEDULED)) { - SD_task_do_schedule(after); - XBT_VERB ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes", SD_task_get_name(after), - sg_host_get_name(after->host_list[0]), sg_host_get_name(after->host_list[1]), after->bytes_amount[2]); - } + + for (std::set::iterator it=task->outputs->begin(); it!=task->outputs->end(); ++it){ + SD_task_t output = *it; + output->host_list[0] = task->host_list[0]; + if (output->host_list[1] && (SD_task_get_state(output) < SD_SCHEDULED)) { + SD_task_do_schedule(output); + XBT_VERB ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes", SD_task_get_name(output), + sg_host_get_name(output->host_list[0]), sg_host_get_name(output->host_list[1]), + output->bytes_amount[2]); } } } + /* Iterate over all children and parents being MXN_1D_BLOCK to say where I am located (and start them if runnable) */ if (task->kind == SD_TASK_COMP_PAR_AMDAHL) { XBT_VERB("Schedule computation task %s on %d workstations. %.f flops will be distributed following Amdahl's Law", SD_task_get_name(task), task->host_count, task->flops_amount[0]); - xbt_dynar_foreach(task->tasks_before, cpt, dep) { - SD_task_t before = dep->src; - if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){ - if (!before->host_list){ - XBT_VERB("Sender side of Task %s is not scheduled yet", SD_task_get_name(before)); - before->host_list = xbt_new0(sg_host_t, count); - before->host_count = count; - XBT_VERB("Fill the workstation list with list of Task '%s'", SD_task_get_name(task)); - for (i=0;ihost_list[i] = task->host_list[i]; - } else { - XBT_VERB("Build communication matrix for task '%s'", SD_task_get_name(before)); - int src_nb, dst_nb; - double src_start, src_end, dst_start, dst_end; - src_nb = before->host_count; - dst_nb = count; - before->host_list = static_cast(xbt_realloc(before->host_list, (before->host_count+count)*sizeof(sg_host_t))); - for(i=0; ihost_list[before->host_count+i] = task->host_list[i]; - - before->host_count += count; - xbt_free(before->flops_amount); - xbt_free(before->bytes_amount); - before->flops_amount = xbt_new0(double, before->host_count); - before->bytes_amount = xbt_new0(double, before->host_count* before->host_count); - - for(i=0;iamount/src_nb; - src_end = src_start + before->amount/src_nb; - for(j=0; jamount/dst_nb; - dst_end = dst_start + before->amount/dst_nb; - XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)", sg_host_get_name(before->host_list[i]), - sg_host_get_name(before->host_list[src_nb+j]), src_start, src_end, dst_start, dst_end); - if ((src_end <= dst_start) || (dst_end <= src_start)) { - before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0; - } else { - before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] = MIN(src_end, dst_end) - MAX(src_start, dst_start); - } - XBT_VERB("==> %.2f", before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]); + for (std::set::iterator it=task->inputs->begin(); it!=task->inputs->end(); ++it){ + SD_task_t input = *it; + if (!input->host_list){ + XBT_VERB("Sender side of Task %s is not scheduled yet", SD_task_get_name(input)); + input->host_list = xbt_new0(sg_host_t, count); + input->host_count = count; + XBT_VERB("Fill the workstation list with list of Task '%s'", SD_task_get_name(task)); + for (i=0;ihost_list[i] = task->host_list[i]; + } else { + XBT_VERB("Build communication matrix for task '%s'", SD_task_get_name(input)); + int src_nb, dst_nb; + double src_start, src_end, dst_start, dst_end; + src_nb = input->host_count; + dst_nb = count; + input->host_list = static_cast(xbt_realloc(input->host_list, (input->host_count+count)*sizeof(sg_host_t))); + for(i=0; ihost_list[input->host_count+i] = task->host_list[i]; + + input->host_count += count; + xbt_free(input->flops_amount); + xbt_free(input->bytes_amount); + input->flops_amount = xbt_new0(double, input->host_count); + input->bytes_amount = xbt_new0(double, input->host_count* input->host_count); + + for(i=0;iamount/src_nb; + src_end = src_start + input->amount/src_nb; + for(j=0; jamount/dst_nb; + dst_end = dst_start + input->amount/dst_nb; + XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)", sg_host_get_name(input->host_list[i]), + sg_host_get_name(input->host_list[src_nb+j]), src_start, src_end, dst_start, dst_end); + if ((src_end <= dst_start) || (dst_end <= src_start)) { + input->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0; + } else { + input->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] = MIN(src_end, dst_end) - MAX(src_start, dst_start); } + XBT_VERB("==> %.2f", input->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]); } + } - if (SD_task_get_state(before)< SD_SCHEDULED) { - SD_task_do_schedule(before); - XBT_VERB ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.", - SD_task_get_name(before),before->amount, src_nb, dst_nb); - } + if (SD_task_get_state(input)< SD_SCHEDULED) { + SD_task_do_schedule(input); + XBT_VERB ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.", + SD_task_get_name(input),input->amount, src_nb, dst_nb); } } } - xbt_dynar_foreach(task->tasks_after, cpt, dep) { - SD_task_t after = dep->dst; - if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){ - if (!after->host_list){ - XBT_VERB("Receiver side of Task '%s' is not scheduled yet", SD_task_get_name(after)); - after->host_list = xbt_new0(sg_host_t, count); - after->host_count = count; - XBT_VERB("Fill the workstation list with list of Task '%s'", SD_task_get_name(task)); - for (i=0;ihost_list[i] = task->host_list[i]; - } else { - int src_nb, dst_nb; - double src_start, src_end, dst_start, dst_end; - src_nb = count; - dst_nb = after->host_count; - after->host_list = static_cast(xbt_realloc(after->host_list, (after->host_count+count)*sizeof(sg_host_t))); - for(i=after->host_count - 1; i>=0; i--) - after->host_list[count+i] = after->host_list[i]; - for(i=0; ihost_list[i] = task->host_list[i]; - - after->host_count += count; - - xbt_free(after->flops_amount); - xbt_free(after->bytes_amount); - - after->flops_amount = xbt_new0(double, after->host_count); - after->bytes_amount = xbt_new0(double, after->host_count* after->host_count); - - for(i=0;iamount/src_nb; - src_end = src_start + after->amount/src_nb; - for(j=0; jamount/dst_nb; - dst_end = dst_start + after->amount/dst_nb; - XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)", i, j, src_start, src_end, dst_start, dst_end); - if ((src_end <= dst_start) || (dst_end <= src_start)) { - after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0; - } else { - after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] = MIN(src_end, dst_end)- MAX(src_start, dst_start); - } - XBT_VERB("==> %.2f", after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]); + + for (std::set::iterator it=task->outputs->begin(); it!=task->outputs->end(); ++it){ + SD_task_t output = *it; + if (!output->host_list){ + XBT_VERB("Receiver side of Task '%s' is not scheduled yet", SD_task_get_name(output)); + output->host_list = xbt_new0(sg_host_t, count); + output->host_count = count; + XBT_VERB("Fill the workstation list with list of Task '%s'", SD_task_get_name(task)); + for (i=0;ihost_list[i] = task->host_list[i]; + } else { + int src_nb, dst_nb; + double src_start, src_end, dst_start, dst_end; + src_nb = count; + dst_nb = output->host_count; + output->host_list = static_cast(xbt_realloc(output->host_list, (output->host_count+count)*sizeof(sg_host_t))); + for(i=output->host_count - 1; i>=0; i--) + output->host_list[count+i] = output->host_list[i]; + for(i=0; ihost_list[i] = task->host_list[i]; + + output->host_count += count; + + xbt_free(output->flops_amount); + xbt_free(output->bytes_amount); + + output->flops_amount = xbt_new0(double, output->host_count); + output->bytes_amount = xbt_new0(double, output->host_count* output->host_count); + + for(i=0;iamount/src_nb; + src_end = src_start + output->amount/src_nb; + for(j=0; jamount/dst_nb; + dst_end = dst_start + output->amount/dst_nb; + XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)", i, j, src_start, src_end, dst_start, dst_end); + if ((src_end <= dst_start) || (dst_end <= src_start)) { + output->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0; + } else { + output->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] = MIN(src_end, dst_end)- MAX(src_start, dst_start); } + XBT_VERB("==> %.2f", output->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]); } + } - if (SD_task_get_state(after)< SD_SCHEDULED) { - SD_task_do_schedule(after); - XBT_VERB ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.", - SD_task_get_name(after),after->amount, src_nb, dst_nb); - } + if (SD_task_get_state(output)< SD_SCHEDULED) { + SD_task_do_schedule(output); + XBT_VERB ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.", + SD_task_get_name(output),output->amount, src_nb, dst_nb); } } } diff --git a/src/simdag/simdag_private.h b/src/simdag/simdag_private.h index d2345567e0..331a2c394c 100644 --- a/src/simdag/simdag_private.h +++ b/src/simdag/simdag_private.h @@ -49,11 +49,14 @@ typedef struct SD_task { int marked; /* used to check if the task DAG has some cycle*/ /* dependencies */ - xbt_dynar_t tasks_before; - xbt_dynar_t tasks_after; int unsatisfied_dependencies; unsigned int is_not_ready; + std::set *inputs; + std::set *outputs; + std::set *predecessors; + std::set *successors; + /* scheduling parameters (only exist in state SD_SCHEDULED) */ int host_count; sg_host_t *host_list; @@ -65,15 +68,6 @@ typedef struct SD_task { char *category; /* sd task category for instrumentation */ } s_SD_task_t; -/* Task dependencies */ -typedef struct SD_dependency { - char *name; - void *data; - SD_task_t src; - SD_task_t dst; - /* src must be finished before dst can start */ -} s_SD_dependency_t, *SD_dependency_t; - /* SimDag private functions */ XBT_PRIVATE void SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state); XBT_PRIVATE void SD_task_run(SD_task_t task);