Synchronisation Primitives for Highly Parallel Discrete Event Simulations

A new set of synchronisation primitives is described that simplifies the control of very large numbers of fine-grained parallel processes. The new primitives are derived from the multi-way event synchronisation and choice defined in communicating sequential processes (CSP). EVENT provides for dynamically structured and multiple barrier synchronisation that is completely deterministic in its semantics. BUCKET provides for an explicitly non-deterministic version of an EVENT, where the non-determinism is triggered by a programmable internal action. These primitives may be combined with standard CSP channel communication to design and implement a highly parallel model of (e.g.) an urban traffic network. The model is simple to create and understand, being object-oriented with components that directly reflect objects on the ground. The performance and scalability both of the primitives and of the traffic model are discussed in terms of their implementation on a DEC Alpha-based multiprocessor. Overheads for managing channel communications and the EVENT/BUCKET primitives are very light, so that the direct execution of highly parallel designs remains efficient down to very fine levels of granularity. An example is presented that operates more than 100 times faster than real time on a single processor, context switching at more than 250,000 times per second. Going multiprocessor allows larger models to be executed at similar speeds. Feedback from such models enables different kinds of analysis to tried ahead of real time, so that the most effective remedial strategies can be found and adopted within real time.