PTVS: ParallelTrafficViewSimulator

Team members: Sanziana Mazilu, Mihaela Teler

Project description: Parallelize VNSim, an existing traffic and network simulator.

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 coment 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 occurence 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 speadup 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 comming 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:
  

START:

-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)

DO LOOP or WHILE LOOP:

While (ending condition is false) do

-set clock to next event time

-process next event and remove from the event-queue

-update statistics

END:

-generate statistics

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