6 This tutorial presents the basics to understand how DAG are represented in Simgrid and how to simulate their workflow.
11 Directed Acyclic Graph:
15 \mathcal{G} = (\mathcal{V},\mathcal{E})
17 Set of vertices representing :ref:`Activities <API_s4u_Activity>`:
21 \mathcal{V} = {v_i | i = 1, ..., V}
23 Set of edges representing precedence constraints between :ref:`Activities <API_s4u_Activity>`:
27 \mathcal{E} = {e_i,j | (i,j) \in {1, ..., V} x {1, ..., V}}
29 .. image:: /img/dag.svg
32 Representing Vertices/Activities
33 ................................
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.
38 An Exec represents the execution of an amount of flop on a :ref:`Host <API_s4u_Host>` of your platform.
42 ExecPtr exec = Exec::init();
43 exec->set_flops_amount(int);
44 exec->set_host(Host*);
47 A Comm represents a data transfer between two :ref:`Hosts <API_s4u_Host>` of your platform.
51 CommPtr comm = Comm::sendto_init();
52 comm->set_source(Host*);
53 comm->set_destination(Host*);
56 Representing Edges/Dependencies
57 ...............................
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`.
65 exec->add_successor(comm);
67 The Activity ``comm`` will not start until ``exec`` has been completed.
72 The goal of this lab is to describe the following DAG:
74 .. image:: /img/dag1.svg
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``.
80 First of all, include the Simgrid library and define the log category.
82 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
86 Inside the ``main`` function create an instance of :ref:`Engine <API_s4u_Engine>` and load the platform.
88 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
92 Retrieve pointers to some hosts.
94 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
98 Initiate the activities.
100 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
104 Give names to thoses activities.
106 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
110 Set the amount of work for each activity.
112 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
116 Define the dependencies between the activities.
118 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
122 Set the location of each Exec activity and source and destination for the Comm activity.
124 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
128 Start the executions of Activities without dependencies.
130 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
134 Add a callback to monitor the activities.
136 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
140 Finally, run the simulation.
142 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.cpp
146 The execution of this code should give you the following output:
148 .. literalinclude:: ../../examples/cpp/dag-tuto/s4u-dag-tuto.tesh
152 Lab 2: Import a DAG from a file
153 -------------------------------
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.
157 The files presented in this lab describe the following DAG:
159 .. image:: /img/dag2.svg
165 A DOT file describes a workflow in accordance with the graphviz format.
167 The following DOT file describes the workflow presented at the beginning of this lab:
169 .. literalinclude:: ../../examples/cpp/dag-from-dot-simple/dag.dot
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.
174 .. literalinclude:: ../../examples/cpp/dag-from-dot-simple/s4u-dag-from-dot-simple.cpp
177 The execution of this code should give you the following output:
179 .. literalinclude:: ../../examples/cpp/dag-from-dot-simple/s4u-dag-from-dot-simple.tesh
186 A JSON file describes a workflow in accordance with the `wfformat <https://github.com/wfcommons/wfformat>`_ .
188 The following JSON file describes the workflow presented at the beginning of this lab:
190 .. literalinclude:: ../../examples/cpp/dag-from-json-simple/dag.json
193 It can be imported as a vector of Activities into Simgrid using :cpp:func:`simgrid::s4u::create_DAG_from_json`.
195 .. literalinclude:: ../../examples/cpp/dag-from-json-simple/s4u-dag-from-json-simple.cpp
198 The execution of this code should give you the following output:
200 .. literalinclude:: ../../examples/cpp/dag-from-json-simple/s4u-dag-from-json-simple.tesh
204 From a DAX file [deprecated]
205 ............................
207 A DAX file describes a workflow in accordance with the `Pegasus <http://pegasus.isi.edu/>`_ format.
209 The following DAX file describes the workflow presented at the beginning of this lab:
211 .. literalinclude:: ../../examples/cpp/dag-from-dax-simple/dag.xml
214 It can be imported as a vector of Activities into Simgrid using :cpp:func:`simgrid::s4u::create_DAG_from_DAX`.
216 .. literalinclude:: ../../examples/cpp/dag-from-dax-simple/s4u-dag-from-dax-simple.cpp
219 Lab 3: Scheduling with the Min-Min algorithm
220 --------------------------------------------
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>`_.
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>`_.
227 For code readability we first create the `sg4` namespace.
231 namespace sg4 = simgrid::s4u;
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.
237 Find Tasks to Schedule
238 ......................
240 The role of this function is to retrieve tasks that are ready to be scheduled, i.e, that have their dependencies solved.
242 .. literalinclude:: ../../examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp
246 Find the Best Placement
247 .......................
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.
253 .. literalinclude:: ../../examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp
260 When the best host has been found, the task is scheduled on it:
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.
267 .. literalinclude:: ../../examples/cpp/dag-scheduling/s4u-dag-scheduling.cpp
271 Mixing it all Together
272 ......................
274 Now that we have the key components of the algorithm let's merge them inside the main function.
278 int main(int argc, char** argv)
282 First, we initialize the Simgrid Engine.
286 sg4::Engine e(&argc, argv);
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`.
293 std::set<sg4::Activity*> vetoed;
294 e.track_vetoed_activities(&vetoed);
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.
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
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
313 comm->set_data(finish_time);
318 We load the platform and force sequential execution on hosts.
322 e.load_platform(argv[1]);
324 /* Mark all hosts as sequential, as it ought to be in such a scheduling example.
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));
333 The tasks are imported from a DAX file.
337 /* load the DAX file */
338 auto dax = sg4::create_DAG_from_DAX(argv[2]);
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.
345 /* Schedule the root first */
347 auto* root = static_cast<sg4::Exec*>(dax.front().get());
348 auto host = get_best_host(root, &finish_time);
349 schedule_on(root, host);
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.
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);
366 if (ready_tasks.empty()) {
367 /* there is no ready exec, let advance the simulation */
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.
375 double min_finish_time = std::numeric_limits<double>::max();
376 sg4::Exec* selected_task = nullptr;
377 sg4::Host* selected_host = nullptr;
379 for (auto exec : ready_tasks) {
380 XBT_DEBUG("%s is ready", exec->get_cname());
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;
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);
397 Finally, we clean up the memory.
402 for (auto const& h : e.get_all_hosts())
403 delete h->get_data<double>();