docs/source/Tutorial_DAG.rst

   1 .. _simdag:
   2
   3 Simulating DAG
   4 ==============
   5
   6 This tutorial presents the basics to understand how DAG are represented in SimGrid and how to simulate their workflow.
   7
   8 Definition of a DAG
   9 -------------------
  10
  11 Directed Acyclic Graph:
  12
  13 .. math::
  14
  15    \mathcal{G} = (\mathcal{V},\mathcal{E})
  16
  17 Set of vertices representing :ref:`Activities <API_s4u_Activity>`:
  18
  19 .. math::
  20
  21    \mathcal{V} = {v_i | i = 1, ..., V}
  22
  23 Set of edges representing precedence constraints between :ref:`Activities <API_s4u_Activity>`:
  24
  25 .. math::
  26
  27    \mathcal{E} = {e_i,j | (i,j) \in {1, ..., V} x {1, ..., V}}
  28
  29 .. image:: /img/dag.svg
  30    :align: center
  31
  32 Representing Vertices/Activities
  33 ................................
  34
  35 There is two types of :ref:`Activities <API_s4u_Activity>` that can represent Vertices: :ref:`Exec <API_s4u_Exec>` and :ref:`Comm <API_s4u_Comm>`.
  36 Thoses activities must be initiated and configured to properly describe your worflow.
  37
  38 An Exec represents the execution of an amount of flop on a :ref:`Host <API_s4u_Host>` of your platform.
  39
  40 .. code-block:: cpp
  41
  42    ExecPtr exec = Exec::init();
  43    exec->set_flops_amount(int);
  44    exec->set_host(Host*);
  45    exec->start();
  46
  47 A Comm represents a data transfer between two :ref:`Hosts <API_s4u_Host>` of your platform.
  48
  49 .. code-block:: cpp
  50
  51    CommPtr comm = Comm::sendto_init();
  52    comm->set_source(Host*);
  53    comm->set_destination(Host*);
  54    comm->start();
  55
  56 Representing Edges/Dependencies
  57 ...............................
  58
  59 An activity will not start until all of its dependencies have been completed.
  60 Activities may have any number of successors.
  61 Dependencies between Activities are created using :cpp:func:`simgrid::s4u::Activity::add_successor`.
  62
  63 .. code-block:: cpp
  64
  65    exec->add_successor(comm);
  66
  67 The Activity ``comm`` will not start until ``exec`` has been completed.
  68
  69 Lab 1: Basics
  70 ---------------
  71
  72 The goal of this lab is to describe the following DAG:
  73
  74 .. image:: /img/dag1.svg
  75    :align: center
  76
  77 In this DAG we want ``c1`` to compute 1e9 flops, ``c2`` to compute 5e9 flops and ``c3`` to compute 2e9 flops.
  78 There is also a data transfer of 5e8 bytes between ``c1`` and ``c3``.
  79
  80 First of all, include the SimGrid library and define the log category.
  81
  82 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
  83    :language: cpp
  84    :lines: 6-8
  85
  86 Inside the ``main`` function create an instance of :ref:`Engine <API_s4u_Engine>` and load the platform.
  87
  88 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
  89    :language: cpp
  90    :lines: 12-13
  91
  92 Retrieve pointers to some hosts.
  93
  94 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
  95    :language: cpp
  96    :lines: 15-16
  97
  98 Initiate the activities.
  99
 100 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
 101    :language: cpp
 102    :lines: 18-21
 103
 104 Give names to thoses activities.
 105
 106 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
 107    :language: cpp
 108    :lines: 23-26
 109
 110 Set the amount of work for each activity.
 111
 112 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
 113    :language: cpp
 114    :lines: 28-31
 115
 116 Define the dependencies between the activities.
 117
 118 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
 119    :language: cpp
 120    :lines: 33-35
 121
 122 Set the location of each Exec activity and source and destination for the Comm activity.
 123
 124 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
 125    :language: cpp
 126    :lines: 37-41
 127
 128 Start the executions of Activities without dependencies.
 129
 130 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
 131    :language: cpp
 132    :lines: 43-44
 133
 134 Add a callback to monitor the activities.
 135
 136 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
 137    :language: cpp
 138    :lines: 46-49
 139
 140 Finally, run the simulation.
 141
 142 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
 143    :language: cpp
 144    :lines: 51
 145
 146 The execution of this code should give you the following output:
 147
 148 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.tesh
 149    :language: none
 150    :lines: 4-
 151
 152 Lab 2: Import a DAG from a file
 153 -------------------------------
 154
 155 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.
 156
 157 The files presented in this lab describe the following DAG:
 158
 159 .. image:: /img/dag2.svg
 160    :align: center
 161
 162 From a DOT file
 163 ...............
 164
 165 A DOT file describes a workflow in accordance with the graphviz format.
 166
 167 The following DOT file describes the workflow presented at the beginning of this lab:
 168
 169 .. literalinclude:: ../../examples/cpp/dag-from-dot-simple/dag.dot
 170    :language: dot
 171
 172 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.
 173
 174 .. literalinclude:: ../../examples/cpp/dag-from-dot-simple/s4u-dag-from-dot-simple.cpp
 175    :language: cpp
 176
 177 The execution of this code should give you the following output:
 178
 179 .. literalinclude:: ../../examples/cpp/dag-from-dot-simple/s4u-dag-from-dot-simple.tesh
 180    :language: none
 181    :lines: 4-
 182
 183 From a JSON file
 184 ................
 185
 186 A JSON file describes a workflow in accordance with the `wfformat <https://github.com/wfcommons/wfformat>`_ .
 187
 188 The following JSON file describes the workflow presented at the beginning of this lab:
 189
 190 .. literalinclude:: ../../examples/cpp/dag-from-json-simple/dag.json
 191    :language: json
 192
 193 It can be imported as a vector of Activities into SimGrid using :cpp:func:`simgrid::s4u::create_DAG_from_json`.
 194
 195 .. literalinclude:: ../../examples/cpp/dag-from-json-simple/s4u-dag-from-json-simple.cpp
 196    :language: cpp
 197
 198 The execution of this code should give you the following output:
 199
 200 .. literalinclude:: ../../examples/cpp/dag-from-json-simple/s4u-dag-from-json-simple.tesh
 201    :language: none
 202    :lines: 4-
 203
 204 From a DAX file [deprecated]
 205 ............................
 206
 207 A DAX file describes a workflow in accordance with the `Pegasus <http://pegasus.isi.edu/>`_ format.
 208
 209 The following DAX file describes the workflow presented at the beginning of this lab:
 210
 211 .. literalinclude:: ../../examples/cpp/dag-from-dax-simple/dag.xml
 212    :language: xml
 213
 214 It can be imported as a vector of Activities into SimGrid using :cpp:func:`simgrid::s4u::create_DAG_from_DAX`.
 215
 216 .. literalinclude:: ../../examples/cpp/dag-from-dax-simple/s4u-dag-from-dax-simple.cpp
 217    :language: cpp
 218
 219 Lab 3: Scheduling with the Min-Min algorithm
 220 --------------------------------------------
 221
 222 In this lab we present how to schedule activities imported from a DAX file using the
 223 `Min-Min algorithm <https://www.researchgate.net/figure/The-Traditional-Min-Min-Scheduling-Algorithm_fig5_236346423>`_.
 224
 225 The source code for this lab can be found `here <https://framagit.org/simgrid/simgrid/-/blob/stable/examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp>`_.
 226
 227 For code readability we first create the `sg4` namespace.
 228
 229 .. code-block:: cpp
 230
 231    namespace sg4 = simgrid::s4u;
 232
 233 The core mechanism of the algorithm lies in three functions.
 234 They respectively serve the purpose of finding tasks to schedule,
 235 finding the best host to execute them and properly scheduling them.
 236
 237 Find Tasks to Schedule
 238 ......................
 239
 240 The role of this function is to retrieve tasks that are ready to be scheduled, i.e, that have their dependencies solved.
 241
 242 .. literalinclude:: ../../examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp
 243    :language: cpp
 244    :lines: 15-38
 245
 246 Find the Best Placement
 247 .......................
 248
 249 Once we have a task ready to be scheduled, we need to find the best placement for it.
 250 This is done by evaluating the earliest finish time among all hosts.
 251 It depends on the duration of the data transfers of the parents of this task to this host.
 252
 253 .. literalinclude:: ../../examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp
 254    :language: cpp
 255    :lines: 40-91
 256
 257 Schedule a Task
 258 ...............
 259
 260 When the best host has been found, the task is scheduled on it:
 261
 262 * it sets the host of the task to schedule
 263 * it stores the finish time of this task on the host
 264 * it sets the destination of parents communication
 265 * it sets the source of any child communication.
 266
 267 .. literalinclude:: ../../examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp
 268    :language: cpp
 269    :lines: 93-113
 270
 271 Mixing it all Together
 272 ......................
 273
 274 Now that we have the key components of the algorithm let's merge them inside the main function.
 275
 276 .. code-block:: cpp
 277
 278    int main(int argc, char** argv)
 279    {
 280    ...
 281
 282 First, we initialize the SimGrid Engine.
 283
 284 .. code-block:: cpp
 285
 286    sg4::Engine e(&argc, argv);
 287
 288 The Min-Min algorithm schedules unscheduled tasks.
 289 To keep track of them we make use of the method :cpp:func:`simgrid::s4u::Engine::track_vetoed_activities`.
 290
 291 .. code-block:: cpp
 292
 293    std::set<sg4::Activity*> vetoed;
 294    e.track_vetoed_activities(&vetoed);
 295
 296 We add the following callback that will be triggered at the end of execution activities.
 297 This callback stores the finish time of the execution,
 298 to use it as a start time for any subsequent communications.
 299
 300 .. code-block:: cpp
 301
 302   sg4::Activity::on_completion_cb([](sg4::Activity const& activity) {
 303     // when an Exec completes, we need to set the potential start time of all its ouput comms
 304     const auto* exec = dynamic_cast<sg4::Exec const*>(&activity);
 305     if (exec == nullptr) // Only Execs are concerned here
 306       return;
 307     for (const auto& succ : exec->get_successors()) {
 308       auto* comm = dynamic_cast<sg4::Comm*>(succ.get());
 309       if (comm != nullptr) {
 310         auto* finish_time = new double(exec->get_finish_time());
 311         // We use the user data field to store the finish time of the predecessor of the comm, i.e., its potential start
 312         // time
 313         comm->set_data(finish_time);
 314       }
 315     }
 316   });
 317
 318 We load the platform and force sequential execution on hosts.
 319
 320 .. code-block:: cpp
 321
 322    e.load_platform(argv[1]);
 323
 324   /* Mark all hosts as sequential, as it ought to be in such a scheduling example.
 325    *
 326    * It means that the hosts can only compute one thing at a given time. If an execution already takes place on a given
 327    * host, any subsequently started execution will be queued until after the first execution terminates */
 328   for (auto const& host : e.get_all_hosts()) {
 329     host->set_concurrency_limit(1);
 330     host->set_data(new double(0.0));
 331   }
 332
 333 The tasks are imported from a DAX file.
 334
 335 .. code-block:: cpp
 336
 337   /* load the DAX file */
 338   auto dax = sg4::create_DAG_from_DAX(argv[2]);
 339
 340 We look for the best host for the root task and schedule it.
 341 We then advance the simulation to unlock next schedulable tasks.
 342
 343 .. code-block:: cpp
 344
 345   /* Schedule the root first */
 346   double finish_time;
 347   auto* root = static_cast<sg4::Exec*>(dax.front().get());
 348   auto host  = get_best_host(root, &finish_time);
 349   schedule_on(root, host);
 350   e.run();
 351
 352 Then, we get to the major loop of the algorithm.
 353 This loop goes on until all tasks have been scheduled and executed.
 354 It starts by finding ready tasks using `get_ready_tasks`.
 355 It iteratively looks for the task that will finish first among ready tasks using `get_best_host`, and place it using `schedule_on`.
 356 When no more tasks can be placed, we advance the simulation.
 357
 358 .. code-block:: cpp
 359
 360   while (not vetoed.empty()) {
 361     XBT_DEBUG("Start new scheduling round");
 362     /* Get the set of ready tasks */
 363     auto ready_tasks = get_ready_tasks(dax);
 364     vetoed.clear();
 365
 366     if (ready_tasks.empty()) {
 367       /* there is no ready exec, let advance the simulation */
 368       e.run();
 369       continue;
 370     }
 371     /* For each ready exec:
 372      * get the host that minimizes the completion time.
 373      * select the exec that has the minimum completion time on its best host.
 374      */
 375     double min_finish_time   = std::numeric_limits<double>::max();
 376     sg4::Exec* selected_task = nullptr;
 377     sg4::Host* selected_host = nullptr;
 378
 379     for (auto exec : ready_tasks) {
 380       XBT_DEBUG("%s is ready", exec->get_cname());
 381       double finish_time;
 382       host = get_best_host(exec, &finish_time);
 383       if (finish_time < min_finish_time) {
 384         min_finish_time = finish_time;
 385         selected_task   = exec;
 386         selected_host   = host;
 387       }
 388     }
 389
 390     XBT_INFO("Schedule %s on %s", selected_task->get_cname(), selected_host->get_cname());
 391     schedule_on(selected_task, selected_host, min_finish_time);
 392
 393     ready_tasks.clear();
 394     e.run();
 395   }
 396
 397 Finally, we clean up the memory.
 398
 399 .. code-block:: cpp
 400
 401    /* Cleanup memory */
 402    for (auto const& h : e.get_all_hosts())
 403      delete h->get_data<double>();
 404
 405
 406
 407
 408
 409
 410