Shared-memory multi-core platforms are changing the nature of Parallel Discrete Event Simulation (PDES) because of the possibility to fully share the workload of events to be processed across threads. In this context, one rising PDES paradigm - referred to as share-everything PDES - is no longer based on the concept of (temporary) biding of simulation objects to worker threads. Rather, each worker threads can - at any time - pick from a fully shared event pool an event to process which can be destined to whatever simulation object.
While attention has been posed on the design of concurrent shared pools, allowing non-blocking parallel operations, the scenario where two (or more) threads pick events destined to the same simulation object still lacks adequate synchronization support.
In fact, these events are currently sequentialized and processed in a critical section touching the simulation object state, thus leading threads to mutually block each other.
In this research project, we aim to design and implement a share-everything speculative PDES engine that prevents mutual thread blocks because of the access to a same object state relying on disjoint LP accesses.
However, avoiding threads to mutually block each other is only a step versus a fully non-blocking PDES. Along this path, this research project aims to design mechanisms able to manage the same state in a non-blocking way. This task is orthogonal to the previous one, providing effects on the progress of the simulation itself.
During this project, the non-blocking property will be seen as a vertical attribute of the engine (not only of the event pool). This vertical view demands for both innovative event-dispatching schemes and, at the same time, innovative interactions with (and management of) the fully-shared event pool, which are features that we will embed in our innovative design.
As aforementioned, almost all parallel discrete event simulation research is focused on the development of platforms based on a distributed execution model. This project will put in place a change of direction sliding the execution model from the distributed to the share-everything one, then following an almost unexplored direction. In this sense, this project will be a source of stimuli for the whole research community, paving the way for numerous new solutions. In fact, although this project contrasts with what is the historical trend, it does not exclude the possibility to combine its outcomes with the distributed approach, with the goal to devise efficient distributed platform based on share-everything multiple kernels.
In addition, as happened with the works in [1], [2], non-blocking solutions designed for specific simulation problems will be easily exportable and adaptable to more general scenarios.
The outcome of this project will be the design and the implementation of a share-everything PDES platform where no thread is ever blocked because of a conflicting concurrent access to some engine/application data structure. This result will be achieved by fully revising the CPU-dispatching rules that are put in place by worker threads, which will be no longer based on extracting the element with the current minimum timestamp from the fully-shared event pool (as an individual action) and then on locking the destination object (as a final action for CPU-dispatching the event). Rather, the pool will be accessed in non-blocking fashion by selecting for processing an event destined to a simulation object that is currently not active - not already CPU-dispatched by any other worker thread. This will be achieved by completely merging the pending event queue with the simulation platform dispatching layer in order to exploit ordinary operations (e.g. enqueue, dequeue) to support multiple functionalities. This can be done, for example, by introducing signaling mechanisms based on pool metadata that could be used to indicate the state of each object (already CPU-dispatched or not). In this way, just traversing the event pool will be possible to extract an event destined to a free simulation object and concurrently compute useful information, e.g. the causal consistency of the extracted event. Overall, our project for the achievement of a non-blocking share-everything PDES engine will rely on a vertical approach where the state of the event pool, in combination with the augmented metadata, will express the current state of the simulation.
Moreover, the possibility to access a simulation object regardless of whether or not it has been booked by another thread will be pursued, so as to ensure the progress of the simulation. It is important to note that this aspect is orthogonal with respect the previous one, not directly considering system performance, but rather its progress, namely the completion of the simulation in scenarios where threads can be blocked or delayed.
During this project, the non-blocking property will be seen as a vertical attribute of the engine (not only of the event pool) with the final goal to produce a fully non-blocking share-everything PDES platform.
In fact, the implementation of an efficient simulation platform based on lock-free/wait-free solutions, can provide a significant scalability improvement with a direct threefold effect: the execution run faster, so the results can be obtained in shorter time, by increasing the number of processors while maintaining fixed the problem size (this property is often referred to as weak scalability). At the same time, the execution of larger simulations can be made tractable, by increasing at the same time the problem size and the number of processors (a property often referred to as strong scalability). At the same time, the reduction of the time spent in synchronization tasks, by explicitly avoiding remaining blocked waiting the execution of another thread, allows to reduce the energy footprint of high-scale computing systems, making parallel simulation as well energy-efficient.
References
[1] R. Marotta, M. Ianni, A. Pellegrini, and F. Quaglia
"A lockfree O(1) event pool and its application to share-everything pdes platforms"
in DS-RT, 2016.
[2] R. Marotta, M. Ianni, A. Pellegrini, and F. Quaglia
"A conflict-resilient lock-free calendar queue for scalable share-everything PDES platforms"
in PADS, 2017.