X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/ce354758f86f0fad1ea536f1cbc0a337267b9987..ab5814bd4ea6117ecf9ac2df328333e89eb45f5f:/docs/source/Tutorial_DAG.rst diff --git a/docs/source/Tutorial_DAG.rst b/docs/source/Tutorial_DAG.rst index 621eaf27fa..4bddc09040 100644 --- a/docs/source/Tutorial_DAG.rst +++ b/docs/source/Tutorial_DAG.rst @@ -3,7 +3,7 @@ Simulating DAG ============== -This tutorial presents the basics to understand how DAG are represented in Simgrid and how to simulate their workflow. +This tutorial presents the basics to understand how DAG are represented in SimGrid and how to simulate their workflow. Definition of a DAG ------------------- @@ -77,7 +77,7 @@ The goal of this lab is to describe the following DAG: In this DAG we want ``c1`` to compute 1e9 flops, ``c2`` to compute 5e9 flops and ``c3`` to compute 2e9 flops. There is also a data transfer of 5e8 bytes between ``c1`` and ``c3``. -First of all, include the Simgrid library and define the log category. +First of all, include the SimGrid library and define the log category. .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp :language: cpp @@ -148,10 +148,11 @@ 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 ------------------------------- -In this lab we present how to import a DAG into you Simgrid simulation, either using a DOT file, a JSON file, or a DAX file. +In this lab we present how to import a DAG into you SimGrid simulation, either using a DOT file, a JSON file, or a DAX file. The files presented in this lab describe the following DAG: @@ -168,7 +169,7 @@ The following DOT file describes the workflow presented at the beginning of this .. literalinclude:: ../../examples/cpp/dag-from-dot-simple/dag.dot :language: dot -It can be imported as a vector of Activities into Simgrid using :cpp:func:`simgrid::s4u::create_DAG_from_DOT`. Then, you have to assign hosts to your Activities. +It can be imported as a vector of Activities into SimGrid using :cpp:func:`simgrid::s4u::create_DAG_from_DOT`. Then, you have to assign hosts to your Activities. .. literalinclude:: ../../examples/cpp/dag-from-dot-simple/s4u-dag-from-dot-simple.cpp :language: cpp @@ -189,7 +190,7 @@ The following JSON file describes the workflow presented at the beginning of thi .. literalinclude:: ../../examples/cpp/dag-from-json-simple/dag.json :language: json -It can be imported as a vector of Activities into Simgrid using :cpp:func:`simgrid::s4u::create_DAG_from_json`. +It can be imported as a vector of Activities into SimGrid using :cpp:func:`simgrid::s4u::create_DAG_from_json`. .. literalinclude:: ../../examples/cpp/dag-from-json-simple/s4u-dag-from-json-simple.cpp :language: cpp @@ -210,7 +211,200 @@ The following DAX file describes the workflow presented at the beginning of this .. literalinclude:: ../../examples/cpp/dag-from-dax-simple/dag.xml :language: xml -It can be imported as a vector of Activities into Simgrid using :cpp:func:`simgrid::s4u::create_DAG_from_DAX`. +It can be imported as a vector of Activities into SimGrid using :cpp:func:`simgrid::s4u::create_DAG_from_DAX`. .. 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(); + + + + + + +