Simultaneous Events and Lookahead in Simulation Protocols

被引：17

作者：

Jha, Vikas ^{[1
]}

Bagrodia, Rajive ^{[1
]}

机构：

[1] Department of Computer Science, 3532 Boelter Hall, Univ. of California at Los Angeles, Los Angeles

来源：

ACM Transactions on Modeling and Computer Simulation | 2000年 / 10卷 / 03期

关键词：

Conditional event; Conservative; Lookahead; Null message; Optimistic; Simulation protocols; Simultaneous events; Time ties; Time warp;

D O I：

10.1145/361026.361032

中图分类号：

学科分类号：

摘要：

A discrete event simulation model may contain several events that have the same timestamp, referred to as simultaneous events. In general, the results of a simulation depend on the order in which simultaneous events are executed. Simulation languages and protocols use different, sometimes ad hoc, tie-breaking mechanisms to order simultaneous events. As a result, it may be impossible to reproduce the results of a simulation model across different simulators. This article presents a systematic analysis of the lookahead requirements for sequential and parallel simulation protocols, utilizing the process-oriented world view, with respect to their ability to execute models with simultaneous events in a deterministic order. In particular, the article shows that most protocols, including the global event list protocol and commonly used parallel conservative and optimistic protocols, require that the simulation model provide some form of lookahead guarantee to enforce deterministic ordering of simultaneous events. The article also shows that the lookahead requirements for many protocols can be weakened if the model allows simultaneous events to be processed in a nondeterministic order. Finally, the lookahead properties that must be satisfied by a model in order for its execution to make guaranteed progress are derived using various simulation protocols.

引用

页码：241 / 267

页数：26

共 28 条

[1]

Bagrodia R., Chandy K.M., Liao W.T., A unifying framework for distributed simulation, ACM Trans. Model. Comput. Simul., 1, 4 OCT., pp. 348-385, (1991)

[2]

Bagrodia R., Meyer R., Park B., Song H., Chen Y., Zeng X., Takai M., Martin J., PARSEC: A parallel simulation environment for complex systems, IEEE Computer, 31, 10 OCT., pp. 77-85, (1998)

[3]

Chandy K.M., Sherman R., The conditional event approach to distributed simulation, Proceedings of the Conference on Distributed Simulation, (1989)

[4]

Chandy K.M., Sherman R., Space-time and simulation, Proceedings of the Conference on Distributed Simulation, (1989)

[5]

Cota B.A., Sargent R.G., Simultaneous events and distributed simulation, Proceedings of the 1990 Winter Conference on Simulation, pp. 436-440, (1990)

[6]

Fishman G.S., Concepts and Methods in Discrete Event Digital Simulation, (1973)

[7]

Fujimoto R.M., Time warp on a shared memory multiprocessor, Proceedings of the International Conference on Parallel Processing, (1989)

[8]

Fujimoto R.M., Parallel discrete event simulation, Commun. ACM, 33, 10 OCT., pp. 30-53, (1990)

[9]

Fujimoto R.M., Nicol D.M., State of the art in parallel simulation, Proceedings of the Winter Conference on Simulation, (1992)

[10]

Gai S., Montessoro P.L., Somenzi F., Mozart: A concurrent multilevel simulator, IEEE Trans. Comput.-aided Des. Integr. Circuits Syst., 7, 9 SEPT., (1988)

← 1 2 3 →