Performance analysis of "time warp" with lirnitecl memory

The behavior of n interacting processes synchronized by the "Time Warp" rollback mechanism is analyzed under the constraint that the total amount of memory to execute the program is limited. In Time Warp, a protocol called "cancelback" has been proposed tc) reclaim storage when the system runs out of memory. A discrete state, continuous time Markov chain model for Time Warp augmented with the cancelback protocol is developed for a shared memory system with n hc,mogeneous processors and homogeneous workload. The model allows one to predict speedup as the amount of available memory is varied. To our knowIedge, this is the first model to achieve this result. The performance predicted by the model is validated through direct performance measurements on an operational Time VVarp system executing on a shared-memory multiprocessor using a workload similar to that in the model. It iz observed that Time Warp with only a few additional message buffers per processor over that required in the corresponding sequential execution can achieve approximately the same or even greater performance than Time Warp with unlimited memory, if GVT computation and fossiI collection can be efficiently implemented.