Dag Consistent Parallel Simulation: a Predictable and Robust Conservative Algorithm

This paper presents a novel approach to parallel discrete event simulation based on a provably efficient scheduler for multithreaded programming. The "Cilk" runtime system provides the user with an algorithmic model of performance which can be used to predict the runtime of a parallel application accurately. Moreover, a Cilk application can "scale down" to run on a single processor with nearly the same performance as serial code. A conservative parallel discrete event simulation algorithm has been developed in which communication between logical processes is achieved using Cilk's virtual memory model: dag consistent shared memory. The simulation involves a divide and conquer style of execution which does not require the use of null messages or deadlock detection. The algorithm is therefore robust, in that it can be used for simulation applications where local lookahead is small or zero or where lookahead information is difficult to extract. Keywords: parallel simulation, conservative ..