Version 9 (modified by sinziana.mazilu, 14 years ago) (diff)


<< Home


What has happened? What's been going on?

The adoption of simulation techniques for the analysis of large-scale, dynamic and complex vehicular networks and related wireless communication-based services, creates severe problems in terms of simulation resources and simulation performance.

In a simulation, the individual evolution of a massive number of entities, the dynamic correlation effects due to mobility and the local broadcast nature of the wireless signal propagation effects in urban scenarios greatly increase computational requirements.

A sequential simulation of a real scenario with a large number of complex model entities (like vehicles running distributed services and their wireless communications) may become computationally infeasible on a single physi- cal execution unit. This is why solutions based on parallel computing architectures like SIMD architectures have been considered, but they are useful only for homogeneous models.

Parallel and HPC architectures have high cost and require expertise in parallel programming to exploit the archi- tecture potential. The Parallel and Distributed Simulation (PADS) exploit concurent computation over different execution units.

So What?

What should we do? Why this?

Single-threaded simulation engines based on instantaneous events have just one current event. In contrast, multi- threaded simulation engines supporting an interval based event model may have multiple current events. In both cases there are significant problems with synchronization between current events.

VNSim is a discrete event simulator, which means that the simulation time advances with a fixed time resolution after executing the application code for the current comment of the simulation time. This means that at every moment of the simulation time, all the current events are pulled from the queue of events and handeled in a random order.

In event based simulators time increases variably, based on the occurrence of events. When the engine advances the simulation time, it pulls out from the main event queue that it manages all the events for the new moment of time.

We want to find a solution for using multi-threading processing in order to obtain increased performances and speedup in the event-queue processing. First we split the map in independent regions. We want to keep multiple event -queues and in every queue we hold only events associated to a certain region of the map, independent from others regions. Based on the location where the event was produced, this event is introduced in a certain event-queue. Different thread will process different event-queues.

What we need is a priority queue algorithm. The pending event queue is organized as a priority queue sorted by event time. This means that regardless of the order in which events are added, they are removed in strictly chronological order. Events are then scheduled dynamically as the simulation proceeds.

Every event has a reference to a thread who will process it, and when that event is pulled off from the queue that thread is restarted/ awaken. So the events coming from independent intersections will be processed in parallel, because they are associated to different threads.

A simulation engine may have the following logic:

  • the main loop of the event-discrete simulator:


  • initialize ending condition to false
  • initialize system state variables
  • initialize clock (usually starts at simulation time zero)
  • schedule an initial event (put some initial event into the event queue)


WHILE (ending condition is false) DO

  • set clock to next event time
  • process next event and remove from the event-queue
  • update statistics


  • generate statistics

We will introduce parallelism at the level of process next event.

Now what?

After couple of brainstorming sessions with our teachers, we decided that the better choice to parallelize the VNSim simulator (the present source code), is to make more parallel computing queues (each queue contains events with messages and data to be computed). Now, VNSim has a single queue with events, running on a single thread (events are sequentially computed). Using more event queues, we want to assign on every queue a running thread. This is a very good idea to parallelize, but we have some issues with that:

  1. we don't have an infinite number of processors (the limit is 8)
  2. how we divide the events per queue (must find some rules)

However, there is one more solution, a simple one - to make only other two queues, and to take only the receive and send events and put into special queues. So, we will have three parallel threads: the principal (for gps and other kind of events), for receive events and for send events.

TODO write those two ideas of implementation

  • use threads per intersections area
  • and use threads per lane