Merge branch 'master' of scm.gforge.inria.fr:/gitroot/simgrid/simgrid

[simgrid.git] / docs / source / tuto_s4u.rst

.. _usecase_simalgo:

Simulating Algorithms
=====================

SimGrid was conceived as a tool to study distributed algorithms. Its
modern S4U interface makes it easy to assess Cloud, P2P, HPC, IoT and
similar settings.

A typical SimGrid simulation is composed of several **Actors**
|api_s4u_Actor|_ , that execute user-provided functions. The actors
have to explicitly use the S4U interface to express their computation,
communication, disk usage and other **Activities** |api_s4u_Activity|_
, so that they get reflected within the simulator. These activities
take place on **Resources** (CPUs, links, disks). SimGrid predicts the
time taken by each activity and orchestrates accordingly the actors
waiting for the completion of these activities.

.. |api_s4u_Actor| image:: /images/extlink.png
   :align: middle
   :width: 12
.. _api_s4u_Actor: api/classsimgrid_1_1s4u_1_1Actor.html#class-documentation

.. |api_s4u_Activity| image:: /images/extlink.png
   :align: middle
   :width: 12
.. _api_s4u_Activity: api/classsimgrid_1_1s4u_1_1Activity.html#class-documentation


Each actor executes a user-provided function on a simulated **Host**
|api_s4u_Host|_ with which it can interact. Communications are not
directly sent to actors, but posted onto **Mailboxes**
|api_s4u_Mailbox|_ that serve as rendez-vous points between
communicating processes. 

.. |api_s4u_Host| image:: /images/extlink.png
   :align: middle
   :width: 12
.. _api_s4u_Host: api/classsimgrid_1_1s4u_1_1Host.html#class-documentation

.. |api_s4u_Mailbox| image:: /images/extlink.png
   :align: middle
   :width: 12
.. _api_s4u_Mailbox: api/classsimgrid_1_1s4u_1_1Mailbox.html#class-documentation


Discover the Master/Workers
---------------------------

This section introduces a first example of SimGrid simulation. This
simple application is composed of two kind of actors: the **master**
is in charge of distributing some computational tasks to a set of
**workers** that execute them. 

.. image:: /images/tuto-masterworkers-intro.svg
   :align: center

We first present a round-robin version of this application, where the
master dispatches the tasks to the workers, one after the other, until
all tasks are dispatched. Later in this tutorial, you will be given
the opportunity to improve this scheme.

The Actors
..........

Let's start with the code of the worker. It is represented by the
*master* function below. This simple function takes at least 3
parameters (the amount of tasks to dispatch, their computational size
in flops to compute and their communication size in bytes to
exchange). Every parameter after the third one must be the name of an
host on which a worker is waiting for something to compute.

Then, the tasks are sent one after the other, each on a mailbox named
after the worker's hosts. On the other side, a given worker (which
code is given below) wait for incoming tasks on its own
mailbox.



At the end, once all tasks are dispatched, the master dispatches
another task per worker, but this time with a negative amount of flops
to compute. Indeed, this application decided by convention, that the
workers should stop when encountering such a negative compute_size.

At the end of the day, the only SimGrid specific functions used in
this example are :cpp:func:`simgrid::s4u::Mailbox::by_name` and
:cpp:func:`simgrid::s4u::Mailbox::put`. Also, :c:macro:`XBT_INFO` is used
as a replacement to printf() or to cout to ensure that the messages
are nicely logged along with the simulated time and actor name.
 
     
.. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers-fun.cpp
   :language: c++
   :start-after: master-begin
   :end-before: master-end

Here comes the code of the worker actors. This function expects no
parameter from its vector of strings. Its code is very simple: it
expects messages on the mailbox that is named after its own host. As long as it gets valid
computation requests (whose compute_amount is positive), it compute
this task and waits for the next one.

The worker retrieves its own host with
:cpp:func:`simgrid::s4u::this_actor::get_host`. The
:ref:`simgrid::s4u::this_actor <namespace_simgrid__s4u__this_actor>`
namespace contains many such helping functions.

.. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers-fun.cpp
   :language: c++
   :start-after: worker-begin
   :end-before: worker-end

Starting the Simulation
.......................
                
And this is it. In only a few lines, we defined the algorithm of our
master/workers examples.

That being said, an algorithm alone is not enough to define a
simulation: SimGrid is a library, not a program. So you need to define
your own ``main()`` function as follows. This function is in charge of
creating a SimGrid simulation engine (on line 3), register the actor
functions to the engine (on lines 7 and 8), load the virtual platform
from its description file (on line 11), map actors onto that platform
(on line 12) and run the simulation until its completion on line 15.

.. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers-fun.cpp
   :language: c++
   :start-after: main-begin
   :end-before: main-end
   :linenos:

As you can see, this also requires a platform file and a deployment
file.

Platform File
.............

Platform files define the virtual platform on which the provided
application will take place. In contains one or several **Network
Zone** |api_s4u_NetZone|_ that contain both **Host-** |api_s4u_Host|_
and **Link-** |api_s4u_Link|_ Resources, as well as routing
information.

Such files can get rather long and boring, so the example below is
only an excerpts of the full ``examples/platforms/small_platform.xml``
file. For example, most routing information are missing, and only the
route between the hosts Tremblay and Fafard is given. This path
traverses 6 links (named 4, 3, 2, 0, 1 and 8). There are several
examples of platforms in the archive under ``examples/platforms``.
                
.. |api_s4u_NetZone| image:: /images/extlink.png
   :align: middle
   :width: 12
.. _api_s4u_NetZone: api/classsimgrid_1_1s4u_1_1NetZone.html#class-documentation

.. |api_s4u_Link| image:: /images/extlink.png
   :align: middle
   :width: 12
.. _api_s4u_Link: api/classsimgrid_1_1s4u_1_1Link.html#class-documentation

.. literalinclude:: ../../examples/platforms/small_platform.xml
   :language: xml
   :lines: 1-10,12-20,56-62,192-
   :caption: (excerpts of the small_platform.xml file)

Deployment File
...............

Deployment files specify the execution scenario: it lists the actors
that should be started, along with their parameter. In the following
example, we start 6 actors: one master and 5 workers.

.. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers_d.xml
   :language: xml

Execution Example
.................

This time, we have all parts: once the program is compiled, we can
execute it as follows. Note how the XBT_INFO() requests turned into
informative messages.
              
.. literalinclude:: ../../examples/s4u/app-masterworkers/s4u-app-masterworkers.tesh
   :language: shell
   :start-after: s4u-app-masterworkers-fun
   :prepend: $$$ ./masterworkers platform.xml deploy.xml
   :append: $$$
   :dedent: 2
              

Improve it Yourself
-------------------

In this section, you will modify the example presented earlier to
explore the quality of the proposed algorithm. For now, it works and
the simulation prints things, but the truth is that we have no idea of
whether this is a good algorithm to dispatch tasks to the workers.
This very simple setting raises many interesting questions:

.. image:: /images/tuto-masterworkers-question.svg
   :align: center

- Which algorithm should the master use? Or should the worker decide
  by themselves?

    Round Robin is not an efficient algorithm when all tasks are not
    processed at the same speed.  It would probably be more efficient
    if the workers were asking for tasks when ready.

- Should tasks be grouped in batches or sent separately?

    The workers will starve if they don't get the tasks fast
    enough. One possibility to reduce latency would be to send tasks
    in pools instead of one by one. But if the pools are too big, the
    load balancing will likely get uneven, in particular when
    distributing the last tasks.

- How does the quality of such algorithm dependent on the platform
  characteristics and on the task characteristics?

    Whenever the input communication time is very small compared to
    processing time and workers are homogeneous, it is likely that the
    round-robin algorithm performs very well. Would it still hold true
    when transfer time is not negligible? What if some tasks are
    performed faster on some specific nodes?
           
- The network topology interconnecting the master and the workers
  may be quite complicated. How does such a topology impact the
  previous result?

    When data transfers are the bottleneck, it is likely that a good
    modeling of the platform becomes essential. The SimGrid platform
    models are particularly handy to account for complex platform
    topologies.

- What is the best applicative topology?

    Is a flat master worker deployment sufficient? Should we go for a
    hierarchical algorithm, with some forwarders taking large pools of
    tasks from the master, each of them distributing their tasks to a
    sub-pool of workers? Or should we introduce super-peers,
    dupplicating the master's role in a peer-to-peer manner?  Do the
    algorithms require a perfect knowledge of the network?

- How is such an algorithm sensitive to external workload variation?

    What if bandwidth, latency and computing speed can vary with no
    warning?  Shouldn't you study whether your algorithm is sensitive
    to such load variations?

- Although an algorithm may be more efficient than another, how does
  it interfere with unrelated applications executing on the same
  facilities?

**SimGrid was invented to answer such questions.** Do not believe the
fools saying that all you need to study such settings is a simple
discrete event simulator. Do you really want to reinvent the wheel,
debug and optimize your own tool, and validate its models against real
settings for ages, or do you prefer to sit on the shoulders of a
giant? With SimGrid, you can focus on your algorithm. The whole
simulation mechanism is already working.

Here is the visualization of a SimGrid simulation of two master worker
applications (one in light gray and the other in dark gray) running in
concurrence and showing resource usage over a long period of time. It
was obtained with the Triva software.

.. image:: /images/tuto-masterworkers-result.png
   :align: center

Prerequisite
............

Before your proceed, you need to :ref:`install SimGrid <install>`, a
C++ compiler and also ``pajeng`` to visualize the traces. The provided
code template requires cmake to compile. On Debian and Ubuntu for
example, you can get them as follows:

.. code-block:: shell

   sudo apt install simgrid pajeng cmake g++

An initial version of the source code is provided on framagit. This
template compiles with cmake. If SimGrid is correctly installed, you
should be able to clone the `repository
<https://framagit.org/simgrid/simgrid-template-s4u>`_ and recompile
everything as follows:

.. code-block:: shell

   git clone git@framagit.org:simgrid/simgrid-template-s4u.git
   cd simgrid-template-s4u/
   cmake .
   make

If you struggle with the compilation, then you should double check
your :ref:`SimGrid installation <install>`.  On need, please refer to
the :ref:`Troubleshooting your Project Setup
<install_yours_troubleshooting>` section.

Discovering the Provided Code
.............................

Please compile and execute the provided simulator as follows:


.. code-block:: shell

   make master-workers
   ./master-workers small_platform.xml master-workers_d.xml

For a more "fancy" output, you can use simgrid-colorizer. 

.. code-block:: shell

   ./master-workers small_platform.xml master-workers_d.xml 2>&1 | simgrid-colorizer

If you installed SimGrid to a non-standard path, you may have to
specify the full path to simgrid-colorizer on the above line, such as
``/opt/simgrid/bin/simgrid-colorizer``. If you did not install it at all,
you can find it in <simgrid_root_directory>/bin/colorize.

.. todo::

   Explain how to generate a Gantt-Chart with S4U and pajeng.

Exercise 1: Simplifying the deployment file
...........................................

In the provided example, adding more workers quickly becomes a pain:
You need to start them (at the bottom of the file), and to inform the
master of its availability with an extra parameter. This is mandatory
if you want to inform the master of where the workers are running. But
actually, the master does not need to have this information.

We could leverage the mailbox mechanism flexibility, and use a sort of
yellow page system: Instead of sending data to the worker running on
Fafard, the master could send data to the third worker. Ie, instead of
using the worker location (which should be filled in two locations),
we could use their ID (which should be filled in one location
only).

This could be done with the following deployment file. It's clearly
not shorter than the previous one, but it's still simpler because the
information is only written once. It thus follows the `DRY
<https://en.wikipedia.org/wiki/Don't_repeat_yourself>`_ `SPOT
<http://wiki.c2.com/?SinglePointOfTruth>`_ design principle.

.. literalinclude:: tuto_s4u/deployment1.xml
   :language: xml


Copy your ``master-workers.cpp`` into ``master-workers-exo1.cpp`` and
add a new executable into ``CMakeLists.txt``. Then modify your worker
function so that it gets its mailbox name not from the name of its
host, but from the string passed as ``args[1]``. The master will send
messages to all workers based on their number, for example as follows:

.. code-block:: cpp

   for (int i = 0; i < tasks_count; i++) {
     std::string worker_rank          = std::to_string(i % workers_count);
     std::string mailbox_name         = std::string("worker-") + worker_rank;
     simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::by_name(mailbox_name);

     mailbox->put(...);

     ...
   }
   

Wrap up
^^^^^^^

The mailboxes are a very powerful mechanism in SimGrid, allowing many
interesting application settings. They may feel surprising if you are
used to BSD sockets or other classical systems, but you will soon
appreciate their power. They are only used to match the
communications, but have no impact on the communication
timing. ``put()`` and ``get()`` are matched regardless of their
initiators' location and then the real communication occures between
the involved parties.

Please refer to the full `API of Mailboxes
<api/classsimgrid_1_1s4u_1_1Mailbox.html#class-documentation>`_
|api_s4u_Mailbox|_ for more details.


Exercise 2: Using the whole platform
....................................

It is now easier to add a new worker, but you still has to do it
manually. It would be much easier if the master could start the
workers on its own, one per available host in the platform. The new
deployment file should be as simple as:

.. literalinclude:: tuto_s4u/deployment2.xml
   :language: xml


Creating the workers from the master
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

For that, the master needs to retrieve the list of hosts declared in
the platform with :cpp:func:`simgrid::s4u::Engine::get_all_host()`.
Then, the master should start the worker processes with
:cpp:func:`simgrid::s4u::Actor::create`.

``Actor::create(name, host, func, params...)`` is a very flexible
function. Its third parameter is the function that the actor should
execute. This function can take any kind of parameter, provided that
you pass similar parameters to ``Actor::create()``. For example, you
could have something like this:

.. code-block:: cpp

  void my_actor(int param1, double param2, std::string param3) {
    ...
  }
  int main(int argc, char argv**) {
     ...
     simgrid::s4u::ActorPtr actor;
     actor = simgrid::s4u::Actor::create("name", simgrid::s4u::Host::by_name("the_host"),
                                         &my_actor, 42, 3.14, "thevalue");
     ...
  }


Master-Workers Communication
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Previously, the workers got from their parameter the name of the
mailbox they should use. We can still do so: the master should build
such a parameter before using it in the ``Actor::create()`` call. The
master could even pass directly the mailbox as a parameter to the
workers. 

Since we want later to study concurrent applications, it is advised to
use a mailbox name that is unique over the simulation even if there is
more than one master. 

One possibility for that is to use the actor ID (aid) of each worker
as a mailbox name. The master can retrieve the aid of the newly
created actor with ``actor->get_pid()`` while the actor itself can
retrieve its own aid with ``simgrid::s4u::this_actor::get_pid()``.
The retrieved value is an ``aid_t``, which is an alias for ``long``.

Instead of having one mailbox per worker, you could also reorganize
completely your application to have only one mailbox per master. All
the workers of a given master would pull their work from the same
mailbox, which should be passed as parameter to the workers.  This
reduces the amount of mailboxes, but prevents the master from taking
any scheduling decision. It really depends on how you want to organize
your application and what you want to study with your simulator.

Wrap up
^^^^^^^

In this exercise, we reduced the amount of configuration that our
simulator requests. This is both a good idea, and a dangerous
trend. This simplification is another application of the good old DRY/SPOT
programming principle (`Don't Repeat Yourself / Single Point Of Truth
<https://en.wikipedia.org/wiki/Don%27t_repeat_yourself>`_), and you
really want your programming artefacts to follow these software
engineering principles.

But at the same time, you should be careful in separating your
scientific contribution (the master/workers algorithm) and the
artefacts used to test it (platform, deployment and workload). This is
why SimGrid forces you to express your platform and deployment files
in XML instead of using a programming interface: it forces a clear
separation of concerns between things of very different nature.


..  LocalWords:  SimGrid