[trace] verbose comments to connect simulator parameters with type hierarchy definition

[simgrid.git] / doc / gtut-introduction.doc

/** 
@page GRAS_tut_intro Introduction to the GRAS framework

\htmlinclude .gtut-introduction.doc.toc

\section GRAS_tut_intro_toc What will you find here

 - The section \ref GRAS_tut_intro_what explains what the GRAS framework and how it
   relates to other existing solutions.
 - The section \ref GRAS_tut_intro_model presents somehow formaly the programmation
   model used in GRAS.

\section GRAS_tut_intro_further Further readings

After this page, you may find these one interesting: 
\ref GRAS_howto_design. If you're new to GRAS, you may want to read the
initiatic tour first, begining with \ref GRAS_tut_tour_install or
\ref GRAS_tut_tour_setup.

<hr>

\section GRAS_tut_intro_what What is GRAS

GRAS is a framework to implement and study distributed algorithms. It
provides a simple communication API to allow several processes to
interoperate through the exchange of messages. This is quite classical, and
GRAS differs from the other existing messaging API by several points:

  - \ref GRAS_tut_intro_what_2ways
  - \ref GRAS_tut_intro_what_dist
  - \ref GRAS_tut_intro_what_grid
  - \ref GRAS_tut_intro_what_target
  - \ref GRAS_tut_intro_what_simple
  
We now detail each of these points.

\subsection GRAS_tut_intro_what_2ways GRAS allows you to run both in simulation mode and on real platforms

We wrote two implementations of the interface: the first one is built on top
of the SimGrid simulator, allowing you to run your application in a
controled environment, which reveals precious to debug and study algorithms.
Everyone who tried to run even simple tests on more than 100 real machines
will consider a simulator as a nirvana.
    
The experiments can be reproduced in the exact same conditions (which is
somehow hard in real settings), allowing for example to reproduce a bug as
many times as you want while debugging. You can also test your algorithm
under experimental conditions which you couldn't achieve on a real platform
(like a network topology and/or size you do don't have access to). Under
some conditions, SimGrid simulations are also much faster than real
executions, allowing you to run more experiments in less time.
 
Once you assessed the quality of your algorithm in the simulator, you can
deploy it on real platforms using the second implementation of the library.
Usually, taking an algorithm out of a simulator implies an almost complete
rewrite. There is no need to modify your program for this in GRAS. You don't
even need to recompile it, but simply to relink your program it against the
right library.

GRAS applications running on real hardware deliver high performance.
The sequential parts of your code are not mediated by GRAS or slowed down
anyhow. The communications use advanced data exchange and conversion
mecanism ensuring that you are likely to get performance at least comparable
to other communication solutions (FIXME: cite the paper once it gets
accepted). 

GRAS applications are portable on several operating systems (Linux, MacOS X,
Solaris, IRIX, AIX and soon Windows) and several processor architectures
(x86, amd64, ppc, sparc, etc). Moreover, GRAS processes can interoperate
efficiently even when deployed on differing material. You can for example
have a process deployed on ppc/MacOS X interacting transparently with
another one deployed on alpha/Linux.
    
The simulation mode of GRAS is called usually SG (for SimGrid) while the in
situ execution mode is called RL (for Real Life).
    
\subsection GRAS_tut_intro_what_dist GRAS was designed for distributed computing, not parallel computing

In GRAS, you build your algorithm as a set of independent processes
interacting through messages. This is the well known MPMD model (multiple
program, multiple data). It contrasts to the SPMD model (simple program,
multiple data) and communications solutions such as MPI or PVM, where you
build an uniq program with conditionnals here and there specifying what each
processes should do (something like "If I'm process number 0, then send data
to the others, else get the data sent to me").

None of these models are inherently better than the other, and there is a
plenty of algorithms betterly expressed in the SPMD paradigm. If your
program falls into that category, then GRAS may not be the right tool for
you. We think however that most non-sequential algorithms can be expressed
gracefully in a MPMD way where some are really difficult to express in a
SPMD way.

There is no parallelism in GRAS, and it is discouraged to introduce threads
in GRAS (althrough it should be possible in some months). This is an explict
choice since threads are so hard to use (see the section \ref
GRAS_tut_intro_what_simple below). The framework itself do use threads to
achieve good performances, but I don't want to impose this to users (FIXME:
actually, GRAS is not multi-threaded yet internally, but I plan to do so
really soon).

\subsection GRAS_tut_intro_what_grid GRAS was designed for large scale computing

Another difference to the MPI communication libraries is that GRAS was not
designed for static small-sized platforms such as clusters, but to dynamic
larger-scale platforms such as grids. That is why GRAS do include static
membership solutions such as the MPI channels. Support for fault-tolerance
is also provided through the timeouts on communication primitives and
through an exception mecanism.

GRAS also comes with a sister library called AMOK containing several usefull
building block for large scale network aware applications. The most
proheminent one allows to assess the network availabilities through active
testing, just like the classical NWS tool in the grid research community. We
are actively working on a network topology discovery mecanism and a
distributed locking solution. Some other modules are planned, such as
reliable broacasting in open environments.

\subsection GRAS_tut_intro_what_target GRAS targets at applicative overlay rather than end-user application

The application class targeted by GRAS is constituted of so called overlays.
They do not constitute a complete application by themselves, but can be seen
as a "distributed library", a thing offering offering a service to another
application through a set of physically distributed entities. An example of
such overlay could be a monitoring system allowing you to retrieve the
available bandwidth between two remote hosts. It could be used in a
network-aware parallel matrix multiplication library assigning more work to
well interconnected nodes. I wouldn't advice to build a physical or
biological compututation program on top of GRAS, even if it would be
possible in theory. 

In other words, GRAS is not a grid middleware in the common understanding of
the world, but rather a tool to constitute the building bricks of such a
middleware. GRAS is thus a sort of "underware" ;)

\subsection GRAS_tut_intro_what_simple GRAS tries to remain simple to use

A lot of effort was put into the framework so that it remains simple to the
users. For example, you can exchange structured data (any kind of C data
structure) just by passing its address, and the framework will create the
exact same structure on the receiver side.

There is no threads like the pthread ones in GRAS, and it is not planned to
introduce this in the future. This is an explicit choice since I consider
multi-threading as too complicated for usual users. There is too much
non-determinism, too many race conditions, and too few language-level
constructs to keep yourself from screwing up. This idea is well expressed 
by John Ousterhout in <i>Why Threads Are a Bad Idea (for most purposes)</i>,
published at USENIX'96. See section \ref GRAS_tut_intro_what_dist for
platform performance consideration.

For the user code, I plan to allow the co-existance of several "gras
processes" within the same regular unix process. The communication semantic
will still be message-oriented, even if implemented using the shared memory
for efficiency.

Likewise, there is no interuption mecanism in GRAS which could break the
user code execution flow. When you write a function, you can be absolutely
sure that nothing will happen between each lines of it. This assumption
considerably simplify the code written in GRAS. The main use of of
interruptions in a distributed application is to timeout communications when
they fail. GRAS communication calls allow to setup a timeout value, and
handle it internally (see below). 

The only interruption mecanism used is constituted by exceptions, just like
in C++ or Java (but implemented directly in C). They are propagated from the
point where they are raised to a point where they will be trapped, if any,
or abort the execution when not trapped. You can still be certain that
nothing will happen between two lines of your code, but the second line may
never be executed if the first one raises an exception ;) 

This exception mecanism was introduced because without it, user code has to
be loaded by tons of non-functional code to check whether an operation was
properly performed or whether you have to pass the error condition to your
caller.

<hr>

\section GRAS_tut_intro_model The model provided by GRAS

From a more formal point of view, GRAS overlays (=applications) can be seen
as a set of state machines mainly interacting with messages. Because of the
distributed setting of overlays, the internal state of each process cannot
be accessed or modified directly by other processes. Even when it would be
possible pratically (like in SG), it is forbidden by the model. This makes
it difficult to gain a complete knowledge on the global system state. This
global system state can still be defined by agregating the states of each
processes, but this remains theoretical and impratical because of the
probable combinatorial explosion.

 - \ref GRAS_tut_intro_model_events
 - \ref GRAS_tut_intro_model_commmodel
 - \ref GRAS_tut_intro_model_timing_policy
 - \ref GRAS_tut_intro_model_exception
 - \ref GRAS_tut_intro_model_rpc

\subsection GRAS_tut_intro_model_events Event types

Two main types of events may change the internal state of a given process:

 - <b>Incomming messages</b>. Messages are somehow strongly typed: a message
   type is described by its name (a string), and the C datatype of its
   payload. Any message of the same type will convey the same datatype, but
   of course the actual content of the payload may change from message to
   message of the same type.\n
   \n
   Processes may attach <b>callback functions</b> to the arrival of messages
   of a given type. They describe the action to achieve to handle the
   messages during the transition associated to this event.\n
   \n
   Incoming messages are not handled as soon as they arrive, but only when
   the process declares to be ready to accept incomming events (using \ref
   gras_msg_handle or related functions). It ensures that the treatment of a
   given message won't run in parallel to any other callback, so that
   process globals (its state) can be accessed and modified without
   locking.\n
   \n
   Messages received when the process is not ready to consume them are
   queued, and will be processed in order in the subsequent calls to \ref
   gras_msg_handle.\n
   \n
   Processes can also wait explicitely for incoming messages matching some
   given criterions (using \ref gras_msg_wait). Any messages received before the
   one matching the criterions will be added to the incomming messages'
   queue for further use. This may breaks the message delivery order.
   Moreover, there is no restriction on when this can be done. So, a
   callback to a given message can consume messages of other types. There is
   also no restriction on the criterion: you can specify a function in charge
   of examinating the messages either incoming or already in the queue and
   decide based on their meta-data (sender and message type) or their actual
   content whether they match your criterions.\n
   \n
   It is even possible to program processes so that they only explicitely
   wait for messages without using \ref gras_msg_handle to accept messages
   and start the callbacks associated to them. GRAS thus supports both the
   pure event-based programming model and the more classical message passing
   model.\n
 
 - <b>Internal timers</b>. There is two types of timers: delayed actions and
   repetitive actions. The former happen only once when the delay expires
   while the second happen regularly each time that a period expires.\n
   \n
   Like incoming messages, timer treatments are not prehemptive. Ie, the
   function attached to a given timer will not start as soon as the period
   expires, but only when the process declares to be ready to accept
   incoming events. This also done in the \ref gras_msg_handle function, and
   expired timers are prioritaire with regard to incoming messages.

Messages are sent using the \ref gras_msg_send function. You should specify
the receiver, the message type and the actual payload. This operation can
happen at any time of your program. Message sending is not considered as a
process state change, but rather as a reaction to an incoming event. It
changes the state of another process, though. Trying to send messages to
yourself will deadlock (althrough it may change in the future).

\subsection GRAS_tut_intro_model_commmodel Communication model

Send operations are <b>as synchronous as possible pratically</b>. They block
the process until the message actually gets delivered to the receiving
process. An acknoledgment is awaited in SG, and we consider the fact that RL
does not the same as a bug to be fixed one day. We thus have an <b>1-port model
in emission</b>. This limitation allows the framework to signal error condition
to the user code in the section which asked for the transmission, without
having to rely on an interuption mecanism to signal errors asynchronously.
This communication model is not completely synchronous in that sense that the
receiver cannot be sure that the acknoledgment has been delivered (this is the
classical byzantin generals problem). Pratically, the acknoledgment is so small
that there is a good probability that the message where delivered. If you need
more guaranty, you will need to implement better solutions in the user space.

As in SimGrid v3.3, receive operations are done in a separated thread, but they
are done sequentially by this thread. The model is thus <b>1-port in
reception</b>, but something like 2-port in general. Moreover, the messages not
matching the criterion in explicite receive (see for example \ref
gras_msg_wait) are queued for further use. Thanks to this specific
thread, the emission and reception are completely decorelated. Ie, the
main thread can perfectly send a message while the listener is
receiving something. We thus have a classical <b>1-port model</b>.

Here is a graphical representation of a scenario involving two processes A and
B.  Both are naturally composed of two threads: the one running user code, and
the listener in charge of listening incoming messages from the network. Both
processes also have a queue for the communication between the two threads, even
if only the queue of process B is depicted in the graph. 

The experimental scenario is as follows: <ul>

<li>Process A sends a first message (depicted in red) with gras_msg_send(), do
    some more computation, and then send another message (depicted in
    yellow). Then, this process handles any incomming message with
    gras_msg_handle(). Since no message is already queued in process A at this
    point, this is a blocking call until the third message (depicted in
    magenta) arrives from the other process.</li>

<li>On its side, the process B explicitely wait for the second message with
    gras_msg_wait(), do some computation with it, and then call
    gras_msg_handle() to handle any incomming message. This will pop the red
    message from the queue, and start the callback attached to that kind of
    messages. This callback sends back a new message (depicted in magenta) back
    to process A.</li>
</ul>

<img src="gras_comm.png">

This figure is a bit dense, and there is several point to detail here:<ul>

<li>The timings associated to a given data exchange are detailed for the first
message. The time (1) corresponds to the network latency. That is the time to
reach the machine on which B is running from the machine running on A. The time
(2) is mainly given by the network bandwidth. This is the time for all bytes of
the messages to travel from one machine to the other. Please note that the
models used by SimGrid are a bit more complicated to keep realistic, as
explained in <a href="http://www.loria.fr/~quinson/articles/simgrid-tutorial.pdf">the 
tutorial slides</a>, but this not that important here. The time (3) is mainly
found in the SG version and not in RL (and that's a bug). This is the time to
make sure that message were received on machine B. In real life, some buffering
at system and network level may give the illusion to machine A that the message
were already received before it's actually delivered to the listener of machine
B (this would reduce the time (3)). To circumvent this, machine B should send a
little acknoledgment message when it's done, but this is not implemented yet.</li>

<li>As you can see on the figure, sending is blocking until the message is
received by the listener on the other side, but the main thread of the receiver
side is not involved in this operation. Sender will get released from its send
even if the main thread of receiver is occuped elsewhere.</li>

<li>Incomming messages not matching the expectations of a gras_msg_wait() (such
as the red one) are queued for further use. The next message receiving
operation will explore this queue in order, and if empty, block on the
network. The order of unexpected messages and subsequent ones is thus preserved
from the receiver point of view.</li>

<li>gras_msg_wait() and gras_msg_handle() accept timeouts as argument to
specify how long you are willing to wait at most for incomming messages. These
were ignored here to not complexify the example any further. It is worth
mentionning that the send operation cannot be timeouted. The existance of the
listener should make it useless.</li>

</ul>

\subsection GRAS_tut_intro_model_timing_policy Timing policy

All communication primitives allow 3 timout policies: one can only poll for
incomming events (using timeout=0), wait endlessly for the communication to
be performed (using timeout<0) or specify a maximal delay to wait for the
communication to proceed (using timeout>0, being a number of seconds).

Again, this describes the targeted model. The current implementation does
not allow to specify a delay for the outgoing communication. In SG, the
delay is then hardcoded to 60 seconds while outgoing communication wait for
ever to proceed in RL.

Another timing policy we plan to implement in the future is "adaptative
timeouts", where the timeout is computed automatically by the framework
according to performance of previous communications. This was demonstrated
for example in the NWS tool.

\subsection GRAS_tut_intro_model_exception Error handling through exceptions

As explained in section \ref GRAS_tut_intro_what_simple, any function may
raise exceptions breaking their execution. No support is provided by the
framework to ensure that the internal state remains consistent when
exceptions are raised. Changing this would imply that we are able to
checkpoint the internal state to provide a transaction service, which seems
quite difficult to achieve efficiently.

\subsection GRAS_tut_intro_model_rpc RPC messaging

In addition to the one-way messages described above, GRAS supports RPC
communication. Using this, a client process asks for the execution of a
callback on a server process. RPC types are close to regular message types:
they are described by a type (a string), a payload type for the request, but
in addition, they also have a payload type for the answer from the server to
the client.

RPC can be either synchronous (the function blocks until an answer is
received) or asynchronous (you send the request and wait later for the
anwer). They accept the same timing policies than regular messages.

If the callback raises an exception on the server side, this exception will
be trapped by the framework on the server side, sent back to the client
side, and revived on the client side. So, if the client calls a RPC which
raises an error, it will have to deal with the exception itself. No
provision is given concerning the state consistency on the server side when
an exception arise. The <tt>host</tt> fields of the exception structure
indicates the name of the host on which it was raised.

The callback performing the treatment associated to a RPC can perform any
kind of communication itself, including RPC. In the case where A calls a RPC
on B, leading to B calling a RPC on C (ie, A->B->C), if an exception is
raised on C, it will be forwarded back to A. The <tt>host</tt> field will
indicate C.

<hr>

\section GRAS_tut_intro_next What's next?

Now that you know what GRAS is and the communication model used, it is time
to move to the \ref GRAS_tut_tour section. There, you will build
incrementally a full-featured GRAS application demonstrating most of the
aspects of the framework.

*/