Parallel Distributed Simulation¶

Introduction to Parallel Discrete Event Simulation¶

OMNeT++ supports parallel execution of large simulations. This section provides a brief overview of the problems and methods of parallel discrete event simulation (PDES). Interested readers are strongly encouraged to refer to the literature.

For parallel execution, the model is divided into several LPs (logical processes) that are simulated independently on different hosts or processors. Each LP maintains its own local Future Event Set and simulation time. The main issue with parallel simulations is synchronizing the LPs to avoid violating event causality. 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 disrupt event causality in the receiving LP.

There are two broad categories of parallel simulation algorithms that differ in how they handle the aforementioned causality problems:

1. Conservative algorithms: These algorithms prevent incausalities from occurring. The Null Message Algorithm utilizes knowledge of when LPs send messages to other LPs and uses special null messages to propagate this information. If an LP knows it won’t receive any messages from other LPs until \(t+\Delta t\), it can advance until \(t+\Delta t\) without external synchronization. Conservative simulation tends to converge to sequential simulation, albeit slowed down by communication between LPs, if there is insufficient parallelism in the model or if parallelism is not exploited by sending a sufficient number of null messages.

2. Optimistic synchronization: These algorithms allow incausalities to occur but detect and repair them. Repairing may involve rollbacks to a previous state, sending out anti-messages to cancel messages sent during the rolled-back period, and so on. Implementing optimistic synchronization is extremely difficult as it requires periodic state saving and the ability to restore previous states. Furthermore, enabling optimistic synchronization in OMNeT++ would require a more complex simulation kernel and significantly more complex simple module code from the user. Optimistic synchronization may be slow in cases of excessive rollbacks.

Assessing Available Parallelism in a Simulation Model¶

OMNeT++ currently supports conservative synchronization via the classic Chandy-Misra-Bryant (or null message) algorithm (Chandy and Misra 1979). To assess how efficiently a simulation can be parallelized with this algorithm, we’ll need the following variables:

• \(P\) performance represents the number of events processed per second (ev/sec). [1] \(P\) depends on the performance of the hardware and the computational intensity of processing an event. \(P\) is independent of the size of the model. Depending on the nature of the simulation model and the performance of the computer, \(P\) is usually in the range of 20,000 to 500,000 ev/sec.

• \(E\) event density is the number of events that occur per simulated second (ev/simsec). \(E\) depends on the model only, and not where the model is executed. \(E\) is determined by the size, the detail level, and also the nature of the simulated system (e.g., cell-level ATM models produce higher \(E\) values than call center simulations.)

• \(R\) relative speed measures the simulation time advancement per second (simsec/sec). \(R\) strongly depends on both the model and on the software/hardware environment where the model executes. Note that \(R = P/E\).

• \(L\) lookahead is measured in simulated seconds (simsec). When simulating telecommunication networks and using link delays as lookahead, \(L\) is typically in the range of milliseconds to microseconds.

• \(\tau\) latency (sec) characterizes the parallel simulation hardware. \(\tau\) is the latency of sending a message from one LP to another. \(\tau\) can be determined using simple benchmark programs. The authors’ measurements on a Linux cluster interconnected via a 100Mb Ethernet switch using MPI yielded \(\tau = 22\mu\)s which is consistent with measurements reported in (Ong and Farrell 2000). Specialized hardware such as Quadrics Interconnect (Quadrics Home Page, n.d.) can provide \(\tau = 5\mu\)s or better.

In large simulation models, \(P\), \(E\), and \(R\) usually stay relatively constant (that is, display little fluctuations over time). They are also intuitive and easy to measure. The OMNeT++ displays these values on the GUI while the simulation is running, see Fig. 16.1. Cmdenv can also be configured to display these values.

After obtaining approximate values of \(P\), \(E\), \(L\), and \(\tau\), calculate the \(\lambda\) coupling factor as the ratio of \(LE\) and \(\tau P\):

\(\lambda = (LE) / (\tau P)\)

Without going into the details: if the resulting \(\lambda\) value is at least larger than one, but rather in the range of 10 to 100, there is a good chance that the simulation will perform well when run in parallel. With \(\lambda < 1\), poor performance is guaranteed. For details see the paper (Varga et al. 2003).

Parallel Distributed Simulation Support in OMNeT++¶

Overview¶

This chapter presents the parallel simulation architecture of OMNeT++. The design allows simulation models to be executed in parallel without code modification – it only requires configuration. The implementation relies on the approach of placeholder modules and proxy gates to instantiate the model on different LPs – the placeholder approach allows simulation techniques such as topology discovery and direct message sending to work unmodified with PDES. The architecture is modular and extensible, so it can serve as a framework for research on parallel simulation.

The OMNeT++ design places a strong emphasis on the separation of models from experiments. The main rationale is that a large number of simulation experiments usually need to be performed on a single model before any conclusion can be drawn about the real system. Experiments tend to be ad-hoc and change much more frequently than simulation models; thus, it is a natural requirement to be able to carry out experiments without disrupting the simulation model itself.

Following this principle, OMNeT++ allows simulation models to be executed in parallel without modification. No special instrumentation of the source code or the topology description is required, as partitioning and other PDES configurations are fully described in the configuration files.

OMNeT++ supports the Null Message Algorithm with static topologies, using link delays as lookahead. The laziness of null message sending can be adjusted. The Ideal Simulation Protocol (ISP) introduced by Bagrodia in 2000 (Bagrodia and Takai 2000) is also supported. ISP is a powerful research vehicle for measuring the efficiency of PDES algorithms, both optimistic and conservative. Specifically, it helps determine the maximum achievable speedup by any PDES algorithm for a particular model and simulation environment. In OMNeT++, ISP can be used to benchmark the performance of the Null Message Algorithm. Additionally, models can be executed without any synchronization, which can be useful for educational purposes (to demonstrate the need for synchronization) or for simple testing.

For communication between LPs (logical processes), OMNeT++ primarily uses MPI, the Message Passing Interface standard (Forum 1994). An alternative communication mechanism is based on named pipes, which can be used on shared memory multiprocessors without the need to install MPI. Additionally, a file system-based communication mechanism is also available. It communicates via text files created in a shared directory, and can be useful for educational purposes (to analyze or demonstrate messaging in PDES algorithms) or to debug PDES algorithms. The implementation of a shared memory-based communication mechanism is also planned for the future to fully exploit the power of multiprocessors without the overhead and the need to install MPI.

For the model to be able to make use of parallel simulation, it must meet the following requirements:

• Modules may communicate only via sending messages (no direct method calls or member access) unless mapped to the same processor.

• No global variables are allowed.

• There are some limitations on direct sending (no sending to a submodule of another module, unless mapped to the same processor).

• Lookahead must be present in the form of link delays.

• Currently, only static topologies are supported (we are working on a research project aimed at eliminating this limitation).

PDES support in OMNeT++ follows a modular and extensible architecture. New communication mechanisms can be added by implementing a compact API (expressed as a C++ class) and registering the implementation. After that, the new communication mechanism can be selected for use in the configuration.

New PDES synchronization algorithms can be added in a similar way. PDES algorithms are also represented by C++ classes that have to implement a very small API to integrate with the simulation kernel. Setting up the model on various LPs as well as relaying model messages across LPs is already taken care of and not something the implementation of the synchronization algorithm needs to worry about (although it can intervene if needed because the necessary hooks are provided).

The implementation of the Null Message Algorithm is also modular in itself, as the lookahead discovery can be plugged in via a defined API. Currently, implemented lookahead discovery uses link delays, but it is possible to implement more sophisticated approaches and select them in the configuration.

Parallel Simulation Example¶

We will use the Parallel CQN example simulation to demonstrate the PDES capabilities of OMNeT++. The model consists of \(N\) tandem queues where each tandem consists of a switch and \(k\) single-server queues with exponential service times (Fig. 16.2). The last queues are looped back to their switches. Each switch randomly chooses the first queue of one of the tandems as the destination, using a uniform distribution. The queues and switches are connected with links that have nonzero propagation delays. Our OMNeT++ model for CQN wraps tandems into compound modules.

To run the model in parallel, we assign tandems to different LPs (Fig. 16.3). Lookahead is provided by delays on the marked links.

To run the CQN model in parallel, we have to configure it for parallel execution. In OMNeT++, the configuration is in the omnetpp.ini file. For configuration, first we have to specify partitioning, that is, assign modules to processors. This is done by the following lines:

[General]
*.tandemQueue[0]**.partition-id = 0
*.tandemQueue[1]**.partition-id = 1
*.tandemQueue[2]**.partition-id = 2

The numbers after the equal sign identify the LP.

Then we have to select the communication library and the parallel simulation algorithm, and enable parallel simulation:

[General]
parallel-simulation = true
parsim-communications-class = "cMPICommunications"
parsim-synchronization-class = "cNullMessageProtocol"

When the parallel simulation is run, LPs are represented by multiple running instances of the same program. When using LAM-MPI (LAM-MPI Home Page, n.d.), the mpirun program (part of LAM-MPI) is used to launch the program on the desired processors. When named pipes or file communications is selected, the opp_prun OMNeT++ utility can be used to start the processes. Alternatively, one can run the processes manually (the -p flag tells OMNeT++ the index of the given LP and the total number of LPs):

./cqn -p0,3 &
./cqn -p1,3 &
./cqn -p2,3 &

For PDES, one will usually want to select the command-line user interface, and redirect the output to files. (OMNeT++ provides the necessary configuration options.)

The graphical user interface of OMNeT++ can also be used (as evidenced by Fig. 16.4), independently of the selected communication mechanism. The GUI interface can be useful for educational or demonstration purposes. OMNeT++ displays debugging output about the Null Message Algorithm, EITs and EOTs can be inspected, etc.

Placeholder Modules, Proxy Gates¶

When setting up a model partitioned into several LPs, OMNeT++ uses placeholder modules and proxy gates. In the local LP, placeholders represent sibling submodules that are instantiated on other LPs. With placeholder modules, every module has all of its siblings present in the local LP – either as a placeholder or as the “real thing”. Proxy gates take care of forwarding messages to the LP where the module is instantiated (see Fig. 16.5).

The main advantage of using placeholders is that algorithms such as topology discovery embedded in the model can be used with PDES unmodified. Also, modules can use direct message sending to any sibling module, including placeholders. This is because the destination of direct message sending is an input gate of the destination module – if the destination module is a placeholder, the input gate will be a proxy gate that transparently forwards the messages to the LP where the “real” module was instantiated. A limitation is that the destination of direct message sending cannot be a submodule of a sibling (which is probably a bad practice anyway, as it violates encapsulation), simply because placeholders are empty and thus, their submodules are not present in the local LP.

Instantiation of compound modules is slightly more complicated. Since submodules can be on different LPs, the compound module may not be “fully present” on any given LP, and it may have to be present on several LPs (wherever it has submodules instantiated). Thus, compound modules are instantiated wherever they have at least one submodule instantiated and are represented by placeholders anywhere else (Fig. 16.6).

Configuration¶

Parallel simulation configuration is set in the [General] section of omnetpp.ini.

The parallel distributed simulation feature can be enabled with the parallel-simulation boolean option.

The parsim-communications-class option selects the class that implements communication between partitions. The class must implement the cParsimCommunications interface.

The parsim-synchronization-class option selects the parallel simulation algorithm. The class must implement the cParsimSynchronizer interface.

The following two options configure the Null Message Algorithm, so they are only effective if cNullMessageProtocol has been selected as the synchronization class:

• parsim-nullmessageprotocol-lookahead-class selects the lookahead class for the NMA; the class must be subclassed from cNMPLookahead. The default class is cLinkDelayLookahead.

• parsim-nullmessageprotocol-laziness expects a number in the \((0,1)\) interval (the default is 0.5), and it controls how often NMA should send out null messages; the value is understood in proportion to the lookahead, e.g., 0.5 means every \(lookahead/2\) simsec.

The parsim-debug boolean option enables/disables printing log messages about the parallel simulation algorithm. It is turned on by default, but for production runs, we recommend turning it off.

Other configuration options configure MPI buffer sizes and other details; see options that begin with parsim- in Appendix Appendix: Configuration Options.

When using cross-mounted home directories (where the simulation’s directory is on a disk mounted on all nodes of the cluster), a useful configuration setting is:

[General]
fname-append-host = true

This setting will cause the host names to be appended to the names of all output vector files, so that partitions don’t overwrite each other’s output files. (See section Using Shared File Systems)

Design of PDES Support in OMNeT++¶

The design of PDES support in OMNeT++ follows a layered approach, with a modular and extensible architecture. The overall architecture is depicted in Fig. 16.7.

The parallel simulation subsystem is an optional component that can be removed from the simulation kernel if not needed. It consists of three layers, from bottom up: the Communications Layer, Partitioning Layer, and Synchronization Layer.

The Communications Layer¶

The purpose of the Communications Layer is to provide elementary messaging services between partitions for the upper layer. The services include send, blocking receive, nonblocking receive, and broadcast. The send/receive operations work with buffers, which encapsulate packing and unpacking operations for primitive C++ types. The message class and other classes in the simulation library can pack and unpack themselves into such buffers. The Communications Layer API is defined in the cParsimCommunications interface (abstract class); specific implementations like the MPI one (cMPICommunications) subclass this interface, encapsulating MPI send/receive calls. The matching buffer class cMPICommBuffer encapsulates MPI pack/unpack operations.

The Partitioning Layer¶

The Partitioning Layer is responsible for instantiating modules on different LPs according to the partitioning specified in the configuration and for configuring proxy gates. During the simulation, this layer also ensures that cross-partition simulation messages reach their destinations. It intercepts messages that arrive at proxy gates and transmits them to the destination LP using the services of the Communications Layer. The receiving LP unpacks the message and injects it at the gate the proxy gate points at. The implementation basically encapsulates the cParsimSegment, cPlaceholderModule, and cProxyGate classes.

The Synchronization Layer¶

The Synchronization Layer encapsulates the parallel simulation algorithm. Parallel simulation algorithms are also represented by classes, subclassed from the cParsimSynchronizer abstract class. The parallel simulation algorithm is invoked on the following hooks: event scheduling, processing model messages outgoing from the LP, and messages (model messages or internal messages) arriving from other LPs. The first hook, event scheduling, is a function invoked by the simulation kernel to determine the next simulation event; it also has full access to the future event set (FES) and can add/remove events for its own use. Conservative parallel simulation algorithms will use this hook to block the simulation if the next event is unsafe, e.g., the null message algorithm implementation (cNullMessageProtocol) blocks the simulation if an EIT has been reached until a null message arrives (see (Bagrodia and Takai 2000) for terminology); it also uses this hook to periodically send null messages. The second hook is invoked when a model message is sent to another LP; the null message algorithm uses this hook to piggyback null messages on outgoing model messages. The third hook is invoked when any message arrives from other LPs, and it allows the parallel simulation algorithm to process its own internal messages from other partitions; the null message algorithm processes incoming null messages here.

The Null Message Protocol implementation itself is modular; it employs a separate, configurable lookahead discovery object. Currently, only link delay-based lookahead discovery has been implemented, but it is possible to implement more sophisticated types.

The Ideal Simulation Protocol (ISP; see (Bagrodia and Takai 2000)) implementation consists of two parallel simulation protocol implementations: the first one is based on the null message algorithm and additionally records the external events (events received from other LPs) to a trace file; the second one executes the simulation using the trace file to determine which events are safe and which are not.

Note that although we implemented a conservative protocol, the provided API itself would allow implementing optimistic protocols as well. The parallel simulation algorithm has access to the executing simulation model, so it could perform saving/restoring model state if model objects support this [2].

We also expect that due to the modularity, extensibility, and clean internal architecture of the parallel simulation subsystem, the OMNeT++ framework has the potential to become the preferred platform for PDES research.