Synchronisation primitives for highly parallel discrete event simulations

Kerridge, J.; Welch, P.; Wood, D.

Abstract

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.

Citation

Kerridge, J., Welch, P., & Wood, D. (1999, January). Synchronisation primitives for highly parallel discrete event simulations. Presented at HICSS 32 - 32nd Annual Hawaii International Conference on System Sciences, Maui, HI, USA

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: HICSS 32 - 32nd Annual Hawaii International Conference on System Sciences
• Start Date: Jan 5, 1999
• End Date: Jan 8, 1999
• Online Publication Date: Aug 6, 2002
• Publication Date: 1999
• Deposit Date: Jul 24, 2019
• Publisher: Institute of Electrical and Electronics Engineers
• Book Title: Proceedings of the 32nd Annual Hawaii International Conference on Systems Sciences. 1999. HICSS-32.
• ISBN: 0769500013
• DOI: https://doi.org/10.1109/hicss.1999.773084
• Keywords: synchronisation, communicating sequential processes, traffic engineering computing, road traffic, discrete event simulation, parallel programming
• Public URL: http://researchrepository.napier.ac.uk/Output/1992503