Logo AND Algorithmique Numérique Distribuée

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