This paper studies the space complexity of an optimistic parallelsimulation protocol called Time Warp. We evaluate four Time Warp memory management algorithms: fossil collection, message sendback. cancelback, and art...
This paper studies the space complexity of an optimistic parallelsimulation protocol called Time Warp. We evaluate four Time Warp memory management algorithms: fossil collection, message sendback. cancelback, and artificial rollback. We identify two criteria in designing Time Warp memory management algorithms. Criterion 1 tests if a memory management algorithm ensures that Time Warp simulation always stops (either completes or terminates when memory is exhausted). If an algorithm does not satisfy this criterion, then the simulation may be trapped in an infinite loop. Criterion 2 tests if a memory management algorithm is independent of processor parameters (e.g., number of processors available for the parallelsimulation, processor speed, and interprocessor communication costs). We show that if an algorithm satisfies this second criterion, then the amount of memory consumed by Time Warp simulation is bounded by the amount consumed by sequential simulation. For algorithms that do not have full control of uncommitted objects (e.g., fossil collection and message sendback), Criterion 2 is not satisfied in general. For algorithms that have full control of uncommitted objects (e.g., cancelback and artificial rollback), special treatments are necessary to satisfy Criterion 1 (i.e., to ensure that the algorithms do not cancel future objects such that global virtual time never advances).
The following topics are dealt with: conservative simulation using distributed shared memory; parallelsimulation; optimistic simulation; virtual environments and HLA; network simulation; distributedsimulation; and d...
The following topics are dealt with: conservative simulation using distributed shared memory; parallelsimulation; optimistic simulation; virtual environments and HLA; network simulation; distributedsimulation; and discrete event simulation.
暂无评论