\chapter{Parallel Execution}
\label{cha:parallel-execution}

\section{{\opp} support for parallel execution}

\subsection{Introduction to Parallel Discrete Event Simulation}

{\opp} supports parallel execution\index{parallel simulation} of large
simulations. The following paragraphs provide a brief picture
of the problems and methods of parallel
discrete event simulation (PDES\index{PDES}). Interested readers are
strongly encouraged to look into the literature.

For parallel execution, the model is to be partitioned to several
LPs that will be simulated independently on different hosts or
processors. Each LP will have its own local Future Event Set,
thus they will maintain local simulation times. The main issue with
parallel simulations is keeping LPs synchronized in order to
avoid violating causality of events. Without synchronization, a
message sent by one LP could arrive in another LP when the
simulation time in the receiving LP has already passed the
timestamp (arrival time) of the message. This would break
causality\index{event!causality} of events in the receiving LP.

There are two broad categories of parallel simulation algorithms
that differ in the way they solve the causality problem outlined
above:

\begin{enumerate}
  \item{\textbf{Conservative algorithms}\index{parallel simulation!conservative}
    prevents incausalities from happening. The Null Message Algorithm
    exploits knowledge about when LPs send messages to other LPs,
    and uses `null' messages to propagate this info to other LPs.
    If a LP knows it won't receive any messages from other
    LPs until $t+\Delta t$ simulation time, it may advance until
    $t+\Delta t$ without the need for external synchronization.
    Conservative simulation tends to converge to sequential simulation
    (slowed down by communication between LPs) if there's not
    enough parallelism in the model, or parallelism is not exploited
    by sending enough `null' messages.}

  \item{\textbf{Optimistic synchronization}\index{parallel simulation!optimistic}
    allows incausalities to occur, but detects and
    repairs them. Repairing involves rollbacks to a previous state,
    sending out anti-messages to cancel messages sent out during the
    period that is being rolled back, etc.  Optimistic synchronization
    is extremely difficult to implement, because it requires periodic
    state saving and the ability to restore previous states. In any
    case, implementing optimistic synchronization in {\opp} would
    require -- in addition to a more complicated simulation kernel --
    writing significantly more complex simple\index{module!simple}
    module code from the user.  Optimistic synchronization may be slow
    in cases of excessive rollbacks.}
\end{enumerate}


\subsection{In work}

Parallel simulation support in {\opp} has recently been reimplemented.
The new code is currently being refined and tested, and it will be
available in the following releases.


%%   \item{\textbf{Statistical synchronization}\index{statistical
%%       synchronization} is a compromise where LPs do not exchange
%%     individual messages but distributions of the traffic flow
%%     characteristics. While conservative and optimistic synchronization
%%     are exact methods (they produce exactly the same results as the
%%     corresponding sequential simulation would), this is certainly not
%%     true for statistical synchronization where the results may contain
%%     error introduced by the statistical nature of the synchronization.
%%     Statistical synchronization does not require changes to existing
%%     models, only the insertion of extra modules, called
%%     \textit{''statistical interfaces''}, therefore it is significantly
%%     easier to implement than either conservative or optimistic. In
%%     addition to easier implementation, there is a potential for much
%%     larger speedup than with conservative or optimistic, because the
%%     method is much less sensitive to communication delay between
%%     processors running the LPs. Therefore, for parallel
%%     simulation on a cluster of workstations, statistical
%%     synchronisation may be the only feasible method.}
%%
%%
%% \subsection{Setting up PVM}
%%
%% \subsubsection{The PVM virtual machine}
%%
%%
%% The \ttt{pvmhosts} file is used by PVM to describe what computers will
%% participate in the virtual machine, where the executables (in our
%% case, the {\opp} programs) are located on each computer, what working
%% directories should be set etc.
%%
%%
%% It is advisable to have a common, shared directory mounted on all
%% participating hosts; this eliminates the tedious work of having to
%% copy files to all hosts again and again.
%%
%%
%% If using {\opp}, it is a good idea to write separate \texttt{pvmhosts}
%% files for each simulation program. Since simulation programs are
%% typically in separate directories, the \texttt{pvmhosts} file in each
%% directory can name that directory as executables directory and working
%% directory for each host. This way, there is no need to create soft
%% links or explicitly name directories in the {\opp} ini files.
%%
%%
%% Each line in the \texttt{pvmhosts} file describes one host. An example
%% line (this all should be a \textit{single line}!):
%%
%% \ begin{verbatim}
%% whale ip=whale.hit.bme.hu lo=andras
%%    dx=/home/andras/pvm/pvm
%%    ep=/home/andras/omnetpp/projects/fddi
%%    wd=/home/andras/omnetpp/projects/fddi
%% \ end{verbatim}
%%
%% To start PVM with this configuration:
%%
%% \ begin{verbatim}
%% cd ~/omnetpp/projects/fddi
%% pvm pvmhosts
%% \ end{verbatim}
%%
%%
%%
%% \section{Statistical synchronization}
%%
%% Similarly to other parallel discrete event simulation methods, the
%% model to be simulated - which is more or less a precise representation
%% of a real system - is divided into LPs, where the LPs
%% usually describe the behaviour of functional units of the real system.
%% The communication of the LPs can be represented by sending and
%% receiving various messages. The simulators of the LPs are
%% executed by separate processors.
%%
%% The communication of these LPs is simulated with appropriate
%% interfaces. The messages generated in a given LP and to be
%% processed in a different LP are not transmitted there, but the
%% output interfaces collect the statistical data of them.  If the input
%% interfaces generate messages for the LPs according to the
%% statistical characteristics of the messages collected by the proper
%% output interfaces, the LPs with their input- and output
%% interfaces can be simulated separately, giving statistically correct
%% results. The events in one LP have not the same effect in other
%% LPs as in the original model, so the results collected during the
%% SSM\index{SSM} are not exact. The precision depends on the
%% LPation, on the accuracy of statistics collection and
%% regeneration, and on the frequency of the statistics exchange among
%% the processors.
%%
%%
%%
%% \subsubsection{LPation}
%%
%%
%% The LPs of the simulator\index{simulation!parallel LPs} are
%% executed by separate processors, they have their own, independent
%% virtual times. Because the interactions among LPs are performed
%% by the statistical parameters of these interactions, the LPation
%% should be done so, that the overwhelming majority of the interactions
%% should happen within the LPs and not among them. This speeds up
%% the so-called inter-LP transients\index{inter-LP transients}
%% and improves the accuracy as well.
%%
%% \subsubsection{Timing of statistics exchange}
%%
%%
%% Asynchronous statistics exchange\index{statistic!asynchronous
%%   exchange} means, that whenever a statistical result collection in an
%% output interface is ready, it is applied - after mapping and
%% correction - in the proper input interface.  This is clearly more
%% efficient, than the so-called synchronous statistics
%% exchange\index{statistic!synchronous exchange}, which means, that we
%% delay the application of collected values until all the output
%% interfaces get ready with the result collection. Frequent statistics
%% exchange makes the inter-LP transient faster, but the lower
%% sample numbers makes the estimation - and the whole simulation - less
%% precise.
%%
%% To learn more about SSM, see [PON92] and [PON93].


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "usman"
%%% End:
