From 85f2d2b7075a3104ccf23b83f926c0513cac9600 Mon Sep 17 00:00:00 2001 From: Adrien Gougeon Date: Tue, 9 May 2023 14:45:25 +0200 Subject: [PATCH] add dag scheduling lab --- docs/source/Tutorial_DAG.rst | 194 +++++++++++++++++++++++++++++++++++ 1 file changed, 194 insertions(+) diff --git a/docs/source/Tutorial_DAG.rst b/docs/source/Tutorial_DAG.rst index 621eaf27fa..37217f2256 100644 --- a/docs/source/Tutorial_DAG.rst +++ b/docs/source/Tutorial_DAG.rst @@ -148,6 +148,7 @@ The execution of this code should give you the following output: .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.tesh :language: none :lines: 4- + Lab 2: Import a DAG from a file ------------------------------- @@ -214,3 +215,196 @@ It can be imported as a vector of Activities into Simgrid using :cpp:func:`simgr .. literalinclude:: ../../examples/cpp/dag-from-dax-simple/s4u-dag-from-dax-simple.cpp :language: cpp + +Lab 3: Scheduling with the Min-Min algorithm +-------------------------------------------- + +In this lab we present how to schedule activities imported from a DAX file using the +`Min-Min algorithm `_. + +The source code for this lab can be found `here `_. + +For code readability we first create the `sg4` namespace. + +.. code-block:: cpp + + namespace sg4 = simgrid::s4u; + +The core mechanism of the algorithm lies in three functions. +They respectively serve the purpose of finding tasks to schedule, +finding the best host to execute them and properly scheduling them. + +Find Tasks to Schedule +...................... + +The role of this function is to retrieve tasks that are ready to be scheduled, i.e, that have their dependencies solved. + +.. literalinclude:: ../../examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp + :language: cpp + :lines: 15-38 + +Find the Best Placement +....................... + +Once we have a task ready to be scheduled, we need to find the best placement for it. +This is done by evaluating the earliest finish time among all hosts. +It depends on the duration of the data transfers of the parents of this task to this host. + +.. literalinclude:: ../../examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp + :language: cpp + :lines: 40-91 + +Schedule a Task +............... + +When the best host has been found, the task is scheduled on it: + +* it sets the host of the task to schedule +* it stores the finish time of this task on the host +* it sets the destination of parents communication +* it sets the source of any child communication. + +.. literalinclude:: ../../examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp + :language: cpp + :lines: 93-113 + +Mixing it all Together +...................... + +Now that we have the key components of the algorithm let's merge them inside the main function. + +.. code-block:: cpp + + int main(int argc, char** argv) + { + ... + +First, we initialize the Simgrid Engine. + +.. code-block:: cpp + + sg4::Engine e(&argc, argv); + +The Min-Min algorithm schedules unscheduled tasks. +To keep track of them we make use of the method :cpp:func:`simgrid::s4u::Engine::track_vetoed_activities`. + +.. code-block:: cpp + + std::set vetoed; + e.track_vetoed_activities(&vetoed); + +We add the following callback that will be triggered at the end of execution activities. +This callback stores the finish time of the execution, +to use it as a start time for any subsequent communications. + +.. code-block:: cpp + + sg4::Activity::on_completion_cb([](sg4::Activity const& activity) { + // when an Exec completes, we need to set the potential start time of all its ouput comms + const auto* exec = dynamic_cast(&activity); + if (exec == nullptr) // Only Execs are concerned here + return; + for (const auto& succ : exec->get_successors()) { + auto* comm = dynamic_cast(succ.get()); + if (comm != nullptr) { + auto* finish_time = new double(exec->get_finish_time()); + // We use the user data field to store the finish time of the predecessor of the comm, i.e., its potential start + // time + comm->set_data(finish_time); + } + } + }); + +We load the platform and force sequential execution on hosts. + +.. code-block:: cpp + + e.load_platform(argv[1]); + + /* Mark all hosts as sequential, as it ought to be in such a scheduling example. + * + * It means that the hosts can only compute one thing at a given time. If an execution already takes place on a given + * host, any subsequently started execution will be queued until after the first execution terminates */ + for (auto const& host : e.get_all_hosts()) { + host->set_concurrency_limit(1); + host->set_data(new double(0.0)); + } + +The tasks are imported from a DAX file. + +.. code-block:: cpp + + /* load the DAX file */ + auto dax = sg4::create_DAG_from_DAX(argv[2]); + +We look for the best host for the root task and schedule it. +We then advance the simulation to unlock next schedulable tasks. + +.. code-block:: cpp + + /* Schedule the root first */ + double finish_time; + auto* root = static_cast(dax.front().get()); + auto host = get_best_host(root, &finish_time); + schedule_on(root, host); + e.run(); + +Then, we get to the major loop of the algorithm. +This loop goes on until all tasks have been scheduled and executed. +It starts by finding ready tasks using `get_ready_tasks`. +It iteratively looks for the task that will finish first among ready tasks using `get_best_host`, and place it using `schedule_on`. +When no more tasks can be placed, we advance the simulation. + +.. code-block:: cpp + + while (not vetoed.empty()) { + XBT_DEBUG("Start new scheduling round"); + /* Get the set of ready tasks */ + auto ready_tasks = get_ready_tasks(dax); + vetoed.clear(); + + if (ready_tasks.empty()) { + /* there is no ready exec, let advance the simulation */ + e.run(); + continue; + } + /* For each ready exec: + * get the host that minimizes the completion time. + * select the exec that has the minimum completion time on its best host. + */ + double min_finish_time = std::numeric_limits::max(); + sg4::Exec* selected_task = nullptr; + sg4::Host* selected_host = nullptr; + + for (auto exec : ready_tasks) { + XBT_DEBUG("%s is ready", exec->get_cname()); + double finish_time; + host = get_best_host(exec, &finish_time); + if (finish_time < min_finish_time) { + min_finish_time = finish_time; + selected_task = exec; + selected_host = host; + } + } + + XBT_INFO("Schedule %s on %s", selected_task->get_cname(), selected_host->get_cname()); + schedule_on(selected_task, selected_host, min_finish_time); + + ready_tasks.clear(); + e.run(); + } + +Finally, we clean up the memory. + +.. code-block:: cpp + + /* Cleanup memory */ + for (auto const& h : e.get_all_hosts()) + delete h->get_data(); + + + + + + + -- 2.20.1