Transparent implementation of conservative algorithms in parallel simulation languages

Parallel discrete event simulation offers significant speedup over the traditional sequential event list algorithm. A number of conservative and optimistic algorithms have been proposed and studied for parallel simulation. We examine the problem of transparent execution of a simulation model using conservative algorithms, and present experimental results on the performance of these transparent implementations. The conservative algorithms implemented and compared include the null message algorithm, the conditional-event algorithm, and a new algorithm which is a combination of these. We describe how dynamic topology can be supported by conservative algorithms. Language constructs to express looliahead are discussed. Finally, performance measurements on a variety of benchmarks are presented, along with a study of the relationship between model characteristics like lookahead, communication topology and the performance of conservative algorithms. 1 q We describe conservative implementations using three different algorithms-null message algorithm (Misra 1986), conditional-event algorithm (Chandy and Sherman 1989), and a new conservative algorithm that combines the preceding approaches. Although, the performance of null message algorithm is generally better than that of conditional-event algorithm, the latter has the nice property of not requiring lookahead for progress(under the assumption that events with the same timestamp can be processed in an arbitrary order). A combination of the two has almost the same performance as the null message algorithm and would in addition, also not reqmre lookahead for progress. On certain kind of applications, the combination could potentially perform better than the null message algorithm.