Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
various ignorable cosmetics
[simgrid.git] / docs / source / Tutorial_Algorithms.rst
1 .. _usecase_simalgo:
2
3 Simulating Algorithms
4 =====================
5
6 SimGrid was conceived as a tool to study distributed algorithms. Its
7 modern :ref:`S4U interface <S4U_doc>` makes it easy to assess Cloud,
8 P2P, HPC, IoT and similar settings.
9
10 A typical SimGrid simulation is composed of several |Actors|_, that
11 execute user-provided functions. The actors have to explicitly use the
12 S4U interface to express their computation, communication, disk usage
13 and other |Activities|_, so that they get reflected within the
14 simulator. These activities take place on **Resources** (|Hosts|_,
15 |Links|_, |Storages|_). SimGrid predicts the time taken by each
16 activity and orchestrates accordingly the actors waiting for the
17 completion of these activities.
18
19 Each actor executes a user-provided function on a simulated |Host|_
20 with which it can interact. Communications are not directly sent to
21 actors, but posted onto a |Mailbox|_ that serve as rendez-vous point
22 between communicating actors.
23
24 .. |Actors| replace:: **Actors**
25 .. _Actors: app_s4u.html#s4u-actor
26
27 .. |Activities| replace:: **Activities**
28 .. _Activities: app_s4u.html#s4u-activity
29
30 .. |Hosts| replace:: **Hosts**
31 .. _Hosts: app_s4u.html#s4u-host
32
33 .. |Links| replace:: **Links**
34 .. _Links: app_s4u.html#s4u-link
35
36 .. |Storages| replace:: **Storages**
37 .. _Storages: app_s4u.html#s4u-storage
38
39 .. |VirtualMachines| replace:: **VirtualMachines**
40 .. _VirtualMachines: app_s4u.html#s4u-virtualmachine
41
42 .. |Host| replace:: **Host**
43 .. _Host: app_s4u.html#s4u-host
44
45 .. |Link| replace:: **Link**
46 .. _Link: app_s4u.html#s4u-link
47
48 .. |Mailbox| replace:: **Mailbox**
49 .. _Mailbox: app_s4u.html#s4u-mailbox
50
51 .. |Barrier| replace:: **Barrier**
52 .. _Barrier: app_s4u.html#s4u-barrier
53
54 .. |ConditionVariable| replace:: **ConditionVariable**
55 .. _ConditionVariable: app_s4u.html#s4u-conditionvariable
56
57 .. |Mutex| replace:: **Mutex**
58 .. _Mutex: app_s4u.html#s4u-mutex
59
60 **In the remainder of this tutorial**, you will discover a simple yet
61 fully functioning example of SimGrid simulation: the Master/Workers
62 application. We will detail each part of the code and necessary
63 configuration to make it working.  After this tour, several exercises
64 are proposed to let you discover some of the SimGrid features, hands
65 on the keyboard. This practical session will be given in C++, that you
66 are supposed to know beforehand.
67
68
69 Discover the Master/Workers
70 ---------------------------
71
72 This section introduces a first example of SimGrid simulation. This
73 simple application is composed of two kind of actors: the **master**
74 is in charge of distributing some computational tasks to a set of
75 **workers** that execute them.
76
77 .. image:: /tuto_s4u/img/intro.svg
78    :align: center
79
80 We first present a round-robin version of this application, where the
81 master dispatches the tasks to the workers, one after the other, until
82 all tasks are dispatched. Later in this tutorial, you will be given
83 the opportunity to improve this scheme.
84
85 The Actors
86 ..........
87
88 Let's start with the code of the worker. It is represented by the
89 *master* function below. This simple function takes at least 3
90 parameters (the amount of tasks to dispatch, their computational size
91 in flops to compute and their communication size in bytes to
92 exchange). Every parameter after the third one must be the name of an
93 host on which a worker is waiting for something to compute.
94
95 Then, the tasks are sent one after the other, each on a mailbox named
96 after the worker's hosts. On the other side, a given worker (which
97 code is given below) wait for incoming tasks on its own
98 mailbox.
99
100
101
102 At the end, once all tasks are dispatched, the master dispatches
103 another task per worker, but this time with a negative amount of flops
104 to compute. Indeed, this application decided by convention, that the
105 workers should stop when encountering such a negative compute_size.
106
107 At the end of the day, the only SimGrid specific functions used in
108 this example are :cpp:func:`simgrid::s4u::Mailbox::by_name` and
109 :cpp:func:`simgrid::s4u::Mailbox::put`. Also, :c:macro:`XBT_INFO` is used
110 as a replacement to printf() or to cout to ensure that the messages
111 are nicely logged along with the simulated time and actor name.
112
113
114 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers-fun.cpp
115    :language: c++
116    :start-after: master-begin
117    :end-before: master-end
118
119 Here comes the code of the worker actors. This function expects no
120 parameter from its vector of strings. Its code is very simple: it
121 expects messages on the mailbox that is named after its own host. As long as it gets valid
122 computation requests (whose compute_amount is positive), it compute
123 this task and waits for the next one.
124
125 The worker retrieves its own host with
126 :cpp:func:`simgrid::s4u::this_actor::get_host`. The
127 :ref:`simgrid::s4u::this_actor <API_s4u_this_actor>`
128 namespace contains many such helping functions.
129
130 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers-fun.cpp
131    :language: c++
132    :start-after: worker-begin
133    :end-before: worker-end
134
135 Starting the Simulation
136 .......................
137
138 And this is it. In only a few lines, we defined the algorithm of our
139 master/workers examples.
140
141 That being said, an algorithm alone is not enough to define a
142 simulation: SimGrid is a library, not a program. So you need to define
143 your own ``main()`` function as follows. This function is in charge of
144 creating a SimGrid simulation engine (on line 3), register the actor
145 functions to the engine (on lines 7 and 8), load the simulated platform
146 from its description file (on line 11), map actors onto that platform
147 (on line 12) and run the simulation until its completion on line 15.
148
149 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers-fun.cpp
150    :language: c++
151    :start-after: main-begin
152    :end-before: main-end
153    :linenos:
154
155 As you can see, this also requires a platform file and a deployment
156 file.
157
158 Platform File
159 .............
160
161 Platform files define the simulated platform on which the provided
162 application will take place. In contains one or several **Network
163 Zone** |api_s4u_NetZone|_ that contain both |Host|_ and |Link|_
164 Resources, as well as routing information.
165
166 Such files can get rather long and boring, so the example below is
167 only an excerpts of the full ``examples/platforms/small_platform.xml``
168 file. For example, most routing information are missing, and only the
169 route between the hosts Tremblay and Fafard is given. This path
170 traverses 6 links (named 4, 3, 2, 0, 1 and 8). There are several
171 examples of platforms in the archive under ``examples/platforms``.
172
173 .. |api_s4u_NetZone| image:: /img/extlink.png
174    :align: middle
175    :width: 12
176 .. _api_s4u_NetZone: app_s4u.html#s4u-netzone
177
178 .. |api_s4u_Link| image:: /img/extlink.png
179    :align: middle
180    :width: 12
181 .. _api_s4u_Link: app_s4u.html#s4u-link
182
183 .. literalinclude:: ../../examples/platforms/small_platform.xml
184    :language: xml
185    :lines: 1-10,12-20,56-62,192-
186    :caption: (excerpts of the small_platform.xml file)
187
188 Deployment File
189 ...............
190
191 Deployment files specify the execution scenario: it lists the actors
192 that should be started, along with their parameter. In the following
193 example, we start 6 actors: one master and 5 workers.
194
195 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers_d.xml
196    :language: xml
197
198 Execution Example
199 .................
200
201 This time, we have all parts: once the program is compiled, we can
202 execute it as follows. Note how the XBT_INFO() requests turned into
203 informative messages.
204
205 .. "WARNING: Over dedent has detected" is expected here as we remove the $ marker this way
206
207 .. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers.tesh
208    :language: shell
209    :start-after: s4u-app-masterworkers-fun
210    :prepend: $$$ ./masterworkers platform.xml deploy.xml
211    :append: $$$
212    :dedent: 2
213
214
215 Improve it Yourself
216 -------------------
217
218 In this section, you will modify the example presented earlier to
219 explore the quality of the proposed algorithm. For now, it works and
220 the simulation prints things, but the truth is that we have no idea of
221 whether this is a good algorithm to dispatch tasks to the workers.
222 This very simple setting raises many interesting questions:
223
224 .. image:: /tuto_s4u/img/question.svg
225    :align: center
226
227 - Which algorithm should the master use? Or should the worker decide
228   by themselves?
229
230     Round Robin is not an efficient algorithm when all tasks are not
231     processed at the same speed.  It would probably be more efficient
232     if the workers were asking for tasks when ready.
233
234 - Should tasks be grouped in batches or sent separately?
235
236     The workers will starve if they don't get the tasks fast
237     enough. One possibility to reduce latency would be to send tasks
238     in pools instead of one by one. But if the pools are too big, the
239     load balancing will likely get uneven, in particular when
240     distributing the last tasks.
241
242 - How does the quality of such algorithm dependent on the platform
243   characteristics and on the task characteristics?
244
245     Whenever the input communication time is very small compared to
246     processing time and workers are homogeneous, it is likely that the
247     round-robin algorithm performs very well. Would it still hold true
248     when transfer time is not negligible? What if some tasks are
249     performed faster on some specific nodes?
250
251 - The network topology interconnecting the master and the workers
252   may be quite complicated. How does such a topology impact the
253   previous result?
254
255     When data transfers are the bottleneck, it is likely that a good
256     modeling of the platform becomes essential. The SimGrid platform
257     models are particularly handy to account for complex platform
258     topologies.
259
260 - What is the best applicative topology?
261
262     Is a flat master worker deployment sufficient? Should we go for a
263     hierarchical algorithm, with some forwarders taking large pools of
264     tasks from the master, each of them distributing their tasks to a
265     sub-pool of workers? Or should we introduce super-peers,
266     dupplicating the master's role in a peer-to-peer manner?  Do the
267     algorithms require a perfect knowledge of the network?
268
269 - How is such an algorithm sensitive to external workload variation?
270
271     What if bandwidth, latency and computing speed can vary with no
272     warning?  Shouldn't you study whether your algorithm is sensitive
273     to such load variations?
274
275 - Although an algorithm may be more efficient than another, how does
276   it interfere with unrelated applications executing on the same
277   facilities?
278
279 **SimGrid was invented to answer such questions.** Do not believe the
280 fools saying that all you need to study such settings is a simple
281 discrete event simulator. Do you really want to reinvent the wheel,
282 debug and optimize your own tool, and validate its models against real
283 settings for ages, or do you prefer to sit on the shoulders of a
284 giant? With SimGrid, you can focus on your algorithm. The whole
285 simulation mechanism is already working.
286
287 Here is the visualization of a SimGrid simulation of two master worker
288 applications (one in light gray and the other in dark gray) running in
289 concurrence and showing resource usage over a long period of time. It
290 was obtained with the Triva software.
291
292 .. image:: /tuto_s4u/img/result.png
293    :align: center
294
295 Using Docker
296 ............
297
298 The easiest way to take the tutorial is to use the dedicated Docker
299 image. Once you `installed Docker itself
300 <https://docs.docker.com/install/>`_, simply do the following:
301
302 .. code-block:: shell
303
304    docker pull simgrid/tuto-s4u
305    docker run -it --rm --name simgrid --volume ~/simgrid-tutorial:/source/tutorial simgrid/tuto-s4u bash
306
307 This will start a new container with all you need to take this
308 tutorial, and create a ``simgrid-tutorial`` directory in your home on
309 your host machine that will be visible as ``/source/tutorial`` within the
310 container.  You can then edit the files you want with your favorite
311 editor in ``~/simgrid-tutorial``, and compile them within the
312 container to enjoy the provided dependencies.
313
314 .. warning::
315
316    Any change to the container out of ``/source/tutorial`` will be lost
317    when you log out of the container, so don't edit the other files!
318
319 All needed dependencies are already installed in this container
320 (SimGrid, a C++ compiler, cmake, pajeng and R). Vite being only
321 optional in this tutorial, it is not installed to reduce the image
322 size.
323
324 The code template is available under ``/source/simgrid-template-s4u.git``
325 in the image. You should copy it to your working directory and
326 recompile it when you first log in:
327
328 .. code-block:: shell
329
330    cp -r /source/simgrid-template-s4u.git/* /source/tutorial
331    cd /source/tutorial
332    cmake .
333    make
334
335 Using your Computer Natively
336 ............................
337
338 To take the tutorial on your machine, you first need to :ref:`install 
339 a recent version of SimGrid <install>`, a C++ compiler and also
340 ``pajeng`` to visualize the traces. You may want to install `Vite
341 <http://vite.gforge.inria.fr/>`_ to get a first glance at the traces.
342 The provided code template requires cmake to compile. On Debian and
343 Ubuntu for example, you can get them as follows:
344
345 .. code-block:: shell
346
347    sudo apt install simgrid pajeng cmake g++ vite
348
349 For R analysis of the produced traces, you may want to install R,
350 and the `pajengr <https://github.com/schnorr/pajengr#installation/>`_ package.
351
352 .. code-block:: shell
353
354    sudo apt install r-base r-cran-devtools cmake flex bison
355    Rscript -e "library(devtools); install_github('schnorr/pajengr');"
356
357 An initial version of the source code is provided on framagit. This
358 template compiles with cmake. If SimGrid is correctly installed, you
359 should be able to clone the `repository
360 <https://framagit.org/simgrid/simgrid-template-s4u>`_ and recompile
361 everything as follows:
362
363 .. code-block:: shell
364
365    # (exporting SimGrid_PATH is only needed if SimGrid is installed in a non-standard path)
366    export SimGrid_PATH=/where/to/simgrid
367
368    git clone https://framagit.org/simgrid/simgrid-template-s4u.git
369    cd simgrid-template-s4u/
370    cmake .
371    make
372
373 If you struggle with the compilation, then you should double check
374 your :ref:`SimGrid installation <install>`.  On need, please refer to
375 the :ref:`Troubleshooting your Project Setup
376 <install_yours_troubleshooting>` section.
377
378 Discovering the Provided Code
379 .............................
380
381 Please compile and execute the provided simulator as follows:
382
383 .. code-block:: shell
384
385    make master-workers
386    ./master-workers small_platform.xml master-workers_d.xml
387
388 For a more "fancy" output, you can use simgrid-colorizer.
389
390 .. code-block:: shell
391
392    ./master-workers small_platform.xml master-workers_d.xml 2>&1 | simgrid-colorizer
393
394 If you installed SimGrid to a non-standard path, you may have to
395 specify the full path to simgrid-colorizer on the above line, such as
396 ``/opt/simgrid/bin/simgrid-colorizer``. If you did not install it at all,
397 you can find it in <simgrid_root_directory>/bin/colorize.
398
399 For a classical Gantt-Chart vizualisation, you can use `Vite
400 <http://vite.gforge.inria.fr/>`_ if you have it installed, as
401 follows. But do not spend too much time installing Vite, because there
402 is a better way to visualize SimGrid traces (see below).
403
404 .. code-block:: shell
405
406    ./master-workers small_platform.xml master-workers_d.xml --cfg=tracing:yes --cfg=tracing/msg/process:yes
407    vite simgrid.trace
408
409 .. image:: /tuto_s4u/img/vite-screenshot.png
410    :align: center
411
412 If you want the full power to visualize SimGrid traces, you need
413 to use R. As a start, you can download this `starter script
414 <https://framagit.org/simgrid/simgrid/raw/master/docs/source/tuto_s4u/draw_gantt.R>`_
415 and use it as follows:
416
417 .. code-block:: shell
418
419    ./master-workers small_platform.xml master-workers_d.xml --cfg=tracing:yes --cfg=tracing/msg/process:yes
420    Rscript draw_gantt.R simgrid.trace
421
422 It produces a ``Rplots.pdf`` with the following content:
423
424 .. image:: /tuto_s4u/img/Rscript-screenshot.png
425    :align: center
426
427
428 Lab 1: Simpler Deployments
429 --------------------------
430
431 In the provided example, adding more workers quickly becomes a pain:
432 You need to start them (at the bottom of the file), and to inform the
433 master of its availability with an extra parameter. This is mandatory
434 if you want to inform the master of where the workers are running. But
435 actually, the master does not need to have this information.
436
437 We could leverage the mailbox mechanism flexibility, and use a sort of
438 yellow page system: Instead of sending data to the worker running on
439 Fafard, the master could send data to the third worker. Ie, instead of
440 using the worker location (which should be filled in two locations),
441 we could use their ID (which should be filled in one location
442 only).
443
444 This could be done with the following deployment file. It's clearly
445 not shorter than the previous one, but it's still simpler because the
446 information is only written once. It thus follows the `DRY
447 <https://en.wikipedia.org/wiki/Don't_repeat_yourself>`_ `SPOT
448 <http://wiki.c2.com/?SinglePointOfTruth>`_ design principle.
449
450 .. literalinclude:: tuto_s4u/deployment1.xml
451    :language: xml
452
453
454 Copy your ``master-workers.cpp`` into ``master-workers-lab1.cpp`` and
455 add a new executable into ``CMakeLists.txt``. Then modify your worker
456 function so that it gets its mailbox name not from the name of its
457 host, but from the string passed as ``args[1]``. The master will send
458 messages to all workers based on their number, for example as follows:
459
460 .. code-block:: cpp
461
462    for (int i = 0; i < tasks_count; i++) {
463      std::string worker_rank          = std::to_string(i % workers_count);
464      std::string mailbox_name         = std::string("worker-") + worker_rank;
465      simgrid::s4u::Mailbox* mailbox = simgrid::s4u::Mailbox::by_name(mailbox_name);
466
467      mailbox->put(...);
468
469      ...
470    }
471
472
473 Wrap up
474 .......
475
476 The mailboxes are a very powerful mechanism in SimGrid, allowing many
477 interesting application settings. They may feel surprising if you are
478 used to BSD sockets or other classical systems, but you will soon
479 appreciate their power. They are only used to match the
480 communications, but have no impact on the communication
481 timing. ``put()`` and ``get()`` are matched regardless of their
482 initiators' location and then the real communication occures between
483 the involved parties.
484
485 Please refer to the full `Mailboxes' documentation
486 <app_s4u.html#s4u-mailbox>`_ for more details.
487
488
489 Lab 2: Using the Whole Platform
490 -------------------------------
491
492 It is now easier to add a new worker, but you still has to do it
493 manually. It would be much easier if the master could start the
494 workers on its own, one per available host in the platform. The new
495 deployment file should be as simple as:
496
497 .. literalinclude:: tuto_s4u/deployment2.xml
498    :language: xml
499
500
501 Creating the workers from the master
502 ....................................
503
504 For that, the master needs to retrieve the list of hosts declared in
505 the platform with :cpp:func:`simgrid::s4u::Engine::get_all_hosts`.
506 Then, the master should start the worker actors with
507 :cpp:func:`simgrid::s4u::Actor::create`.
508
509 ``Actor::create(name, host, func, params...)`` is a very flexible
510 function. Its third parameter is the function that the actor should
511 execute. This function can take any kind of parameter, provided that
512 you pass similar parameters to ``Actor::create()``. For example, you
513 could have something like this:
514
515 .. code-block:: cpp
516
517   void my_actor(int param1, double param2, std::string param3) {
518     ...
519   }
520   int main(int argc, char argv**) {
521      ...
522      simgrid::s4u::ActorPtr actor;
523      actor = simgrid::s4u::Actor::create("name", simgrid::s4u::Host::by_name("the_host"),
524                                          &my_actor, 42, 3.14, "thevalue");
525      ...
526   }
527
528
529 Master-Workers Communication
530 ............................
531
532 Previously, the workers got from their parameter the name of the
533 mailbox they should use. We can still do so: the master should build
534 such a parameter before using it in the ``Actor::create()`` call. The
535 master could even pass directly the mailbox as a parameter to the
536 workers.
537
538 Since we want later to study concurrent applications, it is advised to
539 use a mailbox name that is unique over the simulation even if there is
540 more than one master.
541
542 One possibility for that is to use the actor ID (aid) of each worker
543 as a mailbox name. The master can retrieve the aid of the newly
544 created actor with ``actor->get_pid()`` while the actor itself can
545 retrieve its own aid with ``simgrid::s4u::this_actor::get_pid()``.
546 The retrieved value is an ``aid_t``, which is an alias for ``long``.
547
548 Instead of having one mailbox per worker, you could also reorganize
549 completely your application to have only one mailbox per master. All
550 the workers of a given master would pull their work from the same
551 mailbox, which should be passed as parameter to the workers.  This
552 reduces the amount of mailboxes, but prevents the master from taking
553 any scheduling decision. It really depends on how you want to organize
554 your application and what you want to study with your simulator. In
555 this tutorial, that's probably not a good idea.
556
557 Wrap up
558 .......
559
560 In this exercise, we reduced the amount of configuration that our
561 simulator requests. This is both a good idea, and a dangerous
562 trend. This simplification is another application of the good old DRY/SPOT
563 programming principle (`Don't Repeat Yourself / Single Point Of Truth
564 <https://en.wikipedia.org/wiki/Don%27t_repeat_yourself>`_), and you
565 really want your programming artefacts to follow these software
566 engineering principles.
567
568 But at the same time, you should be careful in separating your
569 scientific contribution (the master/workers algorithm) and the
570 artefacts used to test it (platform, deployment and workload). This is
571 why SimGrid forces you to express your platform and deployment files
572 in XML instead of using a programming interface: it forces a clear
573 separation of concerns between things of very different nature.
574
575 Lab 3: Fixed Experiment Duration
576 --------------------------------
577
578 In the current version, the number of tasks is defined through the
579 worker arguments. Hence, tasks are created at the very beginning of
580 the simulation. Instead, have the master dispatching tasks for a
581 predetermined amount of time.  The tasks must now be created on demand
582 instead of beforehand.
583
584 Of course, usual time functions like ``gettimeofday`` will give you the
585 time on your real machine, which is prety useless in the
586 simulation. Instead, retrieve the time in the simulated world with
587 :cpp:func:`simgrid::s4u::Engine::get_clock`.
588
589 You can still stop your workers with a specific task as previously,
590 or you may kill them forcefully with
591 :cpp:func:`simgrid::s4u::Actor::kill` (if you already have a reference
592 to the actor you want to kill) or
593 :cpp:func:`void simgrid::s4u::Actor::kill(aid_t)` (if you only have its ID).
594
595
596 Anyway, the new deployment `deployment3.xml` file should thus look
597 like this:
598
599 .. literalinclude:: tuto_s4u/deployment3.xml
600    :language: xml
601
602 Controlling the message verbosity
603 .................................
604
605 Not all messages are equally informative, so you probably want to
606 change some of the ``XBT_INFO`` into ``XBT_DEBUG`` so that they are
607 hidden by default. For example, you may want to use ``XBT_INFO`` once
608 every 100 tasks and ``XBT_DEBUG`` when sending all the other tasks. Or
609 you could show only the total number of tasks processed by
610 default. You can still see the debug messages as follows:
611
612 .. code-block:: shell
613
614    ./master-workers-lab3 small_platform.xml deployment3.xml --log=msg_test.thres:debug
615
616
617 Lab 4: Competing Applications
618 -----------------------------
619
620 It is now time to start several applications at once, with the following ``deployment4.xml`` file.
621
622 .. literalinclude:: tuto_s4u/deployment4.xml
623    :language: xml
624
625 Things happen when you do so, but it remains utterly difficult to
626 understand what's happening exactely. Even Gantt visualizations
627 contain too much information to be useful: it is impossible to
628 understand which task belong to which application. To fix this, we
629 will categorize the tasks.
630
631 Instead of starting the execution in one function call only with
632 ``this_actor::execute(cost)``, you need to
633 create the execution activity, set its tracing category, and then start
634 it and wait for its completion, as follows:
635
636 .. code-block:: cpp
637
638    simgrid::s4u::ExecPtr exec = simgrid::s4u::this_actor::exec_init(compute_cost);
639    exec->set_tracing_category(category);
640    // exec->start() is optional here as wait() starts the activity on need
641    exec->wait();
642
643 You can make the same code shorter as follows:
644
645 .. code-block:: cpp
646
647    simgrid::s4u::this_actor::exec_init(compute_cost)->set_tracing_category(category)->wait();
648
649 Visualizing the result
650 .......................
651
652 vite is not enough to understand the situation, because it does not
653 deal with categorization. This time, you absolutely must switch to R,
654 as explained on `this page
655 <https://simgrid.org/contrib/R_visualization.html>`_.
656
657 .. todo::
658
659    Include here the minimal setting to view something in R.
660
661
662 Lab 5: Better Scheduling
663 ------------------------
664
665 You don't need a very advanced visualization solution to notice that
666 round-robin is completely suboptimal: most of the workers keep waiting
667 for more work. We will move to a First-Come First-Served mechanism
668 instead.
669
670 For that, your workers should explicitely request for work with a
671 message sent to a channel that is specific to their master. The name
672 of that private channel can be the one used to categorize the
673 executions, as it is already specific to each master.
674
675 The master should serve in a round-robin manner the requests it
676 receives, until the time is up. Changing the communication schema can
677 be a bit hairy, but once it works, you will see that such as simple
678 FCFS schema allows to double the amount of tasks handled over time
679 here. Things may be different with another platform file.
680
681 Further Improvements
682 ....................
683
684 From this, many things can easily be added. For example, you could:
685
686 - Allow workers to have several pending requests so as to overlap
687   communication and computations as much as possible. Non-blocking
688   communication will probably become handy here.
689 - Add a performance measurement mechanism, enabling the master to make smart scheduling choices.
690 - Test your code on other platforms, from the ``examples/platforms``
691   directory in your archive.
692
693   What is the largest number of tasks requiring 50e6 flops and 1e5
694   bytes that you manage to distribute and process in one hour on
695   ``g5k.xml`` ?
696 - Optimize not only for the amount of tasks handled, but also for the
697   total energy dissipated.
698 - And so on. If you come up with a really nice extension, please share
699   it with us so that we can extend this tutorial.
700
701 After this Tutorial
702 -------------------
703
704 This tutorial is now terminated. You could keep reading the [online documentation][fn:4] or
705 [tutorials][fn:7], or you could head up to the example section to read some code.
706
707 .. todo::
708
709    Things to improve in the future:
710
711    - Propose equivalent exercises and skeleton in java (and Python once we have a python binding).
712
713 ..  LocalWords:  SimGrid