Operated by the Universities Space Research Association ", " I

This paper considers the use of massively parallel architectures to execute discrete-event simulations of what we term "self-initiating " models. A logical process in a self-initiating model schedules its own state re-evaluation times, independently of any other logical process, and sends its new state to other logical processes following the re-evaluation. Our interest is in the effects of that communication on synchronization. We consider the performance of various synchronization protocols by deriving upper and lower bounds on optimal performance, upper bounds on Time Warp's performance, and lower bounds on the performance of a new conservative protocol. Our analysis of Time Warp includes the overhead costs of state-saving and rollback. The analysis points out sufficient conditions for the conservative protocol to outperform Time Warp. The analysis also quantifies the sensitivity of performance to message fan-out, lookahead ability, and the probability distributions underlying the simulation. ( *A preliminary version of this pap-r appears in the lroweoding, of Ihe I,) ' rq1(.PI.AN F'Pol'l ' Svrnp-..iuni