A Globally Optimized Checkpointing Scheme for Time Warp

Abstract

Time warp (TW) protocol executes simulation events without considering event safety, and a rollback mechanism is used to correct out-of-order event execution. For the simulator to perform the. roll-back operation, the system state must be checkpointed. Although decreasing the checkpointing frequency reduces the state saving cost, this is done at the risk of escalating the coast forward effort when, a large number of executed events are redone. In this article we improve the TW performance by optimizing its recovery cost. ProbabiiixStic model and combinatorial analysis are used, and logical processes of the TW simulation and their processing elements are assumed to be homogeneous. Given a set of system states, our scheme selects the best combination of checkpointing positions based on the sum of coast forward cost and state saving cost. Our experiments show that the proposed checkpointing scheme reduces the simulation elapsed time by 35% compared to saving the system state after each event execution, and by 20% as compared to infrequent approach.

Key Words:

• Performance optimization
• optimistic simulation
• state saving
• rollback
• cost model
• combinatorial analysis

Additional information

Notes on contributors

S.C. Tay

Seng Chuan Tay graduated from the National University of Singapore (NUS) with an M.Sc. (computer and information sciences) and Ph.D. in 1994 and 1999, respectively. He is currently the Deputy Director of the Centre for Remote Imaging, Sensing and Processing (CRISP) in NUS. Prior to if working in CRISP, Dr. Tay taught computing science in the Faculty of Science for 11 years and managed an undergraduate program in scientific computations and multimedia communication. He is also the project manager and lecturer for computer courses organized for the Ministry of Education, Singapore. Dr. Tay has received three teaching awards and published over 50 papers in parallel computing. His research interests include satellite image processing, parallel simulation, and performance modelling.

Y.M. Teo

Yong Meng Teo graduated from the University of Manchester in UK with an M.Sc. and Ph.D. in computer science in 1987 and 1989, respectively. He is currently Associate Professor with the Department of Computer Science at the National University of Singapore. His research interests include grid computing, parallel simulation, and performance evaluation.