A low-overhead constant-time Lowest-Timestamp-First CPU scheduler for high-performance optimistic simulation platforms

An approach to high-performance discrete event simulation consists of exploiting parallelization techniques. These rely on partitioning the simulation model into multiple, interacting simulation objects, also known as Logical Processes (LPs), which concurrently execute events on different CPUs and/or multiple CPU-cores. However, despite the tendency towards high degree of hardware parallelism, for relatively large models, multi-programming schemes are still needed in order to share a single CPU-core across multiple LPs. Consequently, priority management and CPU-scheduling remain central issues for the effectiveness of any parallel simulation environment. This article focuses on the optimistic approach to parallelism, which is based on speculative processing and maintains event-causality across concurrent LPs via rollback techniques. Specifically, the article presents a low-overhead constant-time implementation of the well known Lowest-Timestamp-First algorithm for the identification of the next LP to be CPU-dispatched. This proposal is suited for contexts where the optimistic simulation system conforms to the best-practice of keeping separate event lists for the hosted LPs. The implementation has been integrated in the open source ROOT-Sim (ROme OpTimistic Simulator) package. The effectiveness of the presented proposal is assessed via an extended performance study, carried out by relying on the game of life as the test-bed application. © 2015 Elsevier B.V. All rights reserved.