BULK SYNCHRONOUS PARALLEL ALGORITHMS FOR CONSERVATIVE DISCRETE EVENT SIMULATION∗

∗This work was supported by a Soros/Foreign Commonwealth Office scholarship.

Abstract

All the parallel discrete event simulation algorithms developed so far have been designed to suit a specific parallel model (e.g., a PRAM model, a MP-RAM model, etc.). This paper presents several versions of conservative parallel discrete event simulation algorithms developed around a unifying model for general purpose parallel computer design and programming, namely around the Bulk Synchronous Parallel (BSP) model. The new algorithms are analysed in terms of the BSP model parameters and the effectiveness of simulators based on these algorithms is evaluated. The performance achieved even for a loosely coupled distributed system is comparable with that reported in previous research work, while the generality of the BSP model provides portability to the new approaches.

KEY WORDS:

• Bulk synchronous parallel computers
• conservative parallel simulation algorithms
• discrete event dynamical systems
• general purpose parallel computing

C.R. CATEGORIES:

• D.1.3
• D.4.1
• D.4.14
• I.6.0
• I.6.1
• I.6.8

Notes

∗This work was supported by a Soros/Foreign Commonwealth Office scholarship.