The authors study the adaptation of an optimistic Time Warp kernel to cross-cluster computing on the Grid. Wide-area communication, the primary source of overhead, is offloaded onto dedicated routing processes. This allows the simulation processes to run at full speed and thus significantly decreases the performance gap caused by the wide-area distribution. Further improvements are obtained by employing message aggregation on the wide-area links and using a distributed global virtual time algorithm. The authors achieve many of their objectives for a cellular automaton simulation with lazy cancellation and moderate communication. High communication rates, especially with aggressive cancellation, present a challenge. This is confirmed by the experiments with synthetic loads. Even then, a satisfactory speedup can be achieved, provided that the computational grain of events is large enough.
Jefferson, D. R.1985. Virtual time . ACM Transactions on Programming Languages and Systems7 (3): 404-425 .
2.
Fujimoto, R. M.2000. Parallel and distributed simulation systems. New York: John Wiley .
3.
Foster, I. , and C. Kesselman , eds. 1999. The Grid: Blueprint for a future computing infrastructure. New York: Morgan-Kaufmann .
4.
Foster, I. , C. Kesselman , J. Nick , and S. Tuecke . 2002. The physiology of the Grid: An open grid services architecture for distributed systems integration. In Open Grid Service Infrastructure WG, Global Grid Forum, June.
5.
Glazer, D. W. , and C. Tropper . 1993. On process migration and load balancing in time warp . IEEE Transactions on Parallel and Distributed Systems4 (3): 318-327 .
6.
Schlagenhaft, R. , M. Ruhwandl , C. Sporrer , and H. Bauer . 1995. Dynamic load balancing of a multi-cluster simulator on a network of workstations . In Proceedings of the 9th Workshop on Parallel and Distributed Simulation, June, Lake Placid, NY, pp. 175-180 .
7.
Carothers, C. D. , and R. M. Fujimoto . 2000. Efficient execution of time warp programs on heterogeneous, NOW platforms . IEEE Transactions on Parallel and Distributed Systems11 (3): 299-317 .
8.
Agrawal, D. , and J. R. Agre . 1992. Replicated objects in time warp simulations . In Proceedings of the 1992 Winter Simulation Conference, December, Arlington, VA, pp. 657-664 .
9.
Damani, O. P. , and V. K. Garg . 1998. Fault-tolerant distributed simulation . In Proceedings of the 12th Workshop on Parallel and Distributed Simulation, May, Banff, AB, Canada, pp. 38-45 .
10.
Overeinder, B. J. 2000. Distributed event-driven simulation: Scheduling strategies and resource management. Ph.D. diss., Universiteit van Amsterdam, the Netherlands.
11.
Iskra, K. A. , G. D. van Albada , and P. M. A. Sloot . 2003. Time warp cancellation optimisations on high latency networks . In Proceedings of the 7th International Symposium on Distributed Simulation and Real Time Applications, October, Delft, the Netherlands, pp. 128-135 .
12.
Boukerche, A. , A. Fabbri , and A. R. Mikler . 2000. Distributed simulation over loosely coupled domains . In Proceedings of the 4th International Workshop on Distributed Simulation and Real-Time Applications, August, San Francisco, pp. 18-25 .
13.
Carothers, C. D. , R. M. Fujimoto , and P. England . 1994.The effect of communication overheads on time warp performance: An experimental study . In Proceedings of the 8th Workshop on Parallel and Distributed Simulation, July, Edinburgh, Scotland, pp. 118-125 .
14.
Müller, M. , M. Hess , and E. Gabriel . 2003. Grid enabled MPI solutions for clusters . In Proceedings of the 3rd International Symposium on Cluster Computing and the Grid, May, Tokyo, Japan, pp. 18-25 .
15.
Gabriel, E. , M. Resch , and R. Rühle . 1999. Implementing MPI with optimized algorithms for metacomputing . In Proceedings of the 3rd MPI Developers’ and Users’ Conference, March, Starkville, MS, pp. 31-42 .
16.
Kimura, T. , and H. Takemiya . 1998. Local area metacomputing for multidisciplinary problems: A case study for fluid/structure coupled simulation . In Proceedings of the 12th International Conference on Supercomputing, July, Melbourne, Australia, pp. 149-156 .
17.
Karonis, N. , B. Toonen , and I. Foster . 2003. MPICH-G2: A Grid-enabled implementation of the message passing interface . Journal of Parallel and Distributed Computing63 (5): 551-563 .
18.
Chetlur, M. , N. Abu-Ghazaleh , R. Radhakrishnan , and P. A. Wilsey . 1998. Optimizing communication in time-warp simulators . In Proceedings of the 12th Workshop on Parallel and Distributed Simulation, May, Banff, AB, Canada, pp. 64-71 .
19.
Pham, C. D. 2000. Comparison of message aggregation strategies for parallel simulations on a high performance cluster . In Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, August-September, San Francisco, pp. 358-365 .
20.
Liang, L. A. H. , W. Cai , B.-S. Lee , and S. J. Turner . 1999. Performance analysis of packet bundling techniques in DIS . In Proceedings of the 3rd International Workshop on Distributed Interactive Simulation and Real-Time Applications, March, College Park, MD, pp. 75-82 .
21.
Mattern, F.1993. Efficient algorithms for distributed snapshots and global virtual time approximation . Journal of Parallel and Distributed Computing18 (4): 423-434 .
22.
Bauer, H. , and C. Sporrer . 1992. Distributed logic simulation and an approach to asynchronous GVT-calculation . In Proceedings of the 6thWorkshop on Parallel and Distributed Simulation, January, Newport Beach, CA, pp. 205-208 .
23.
Concepcion, A. I. , and S. G. Kelly . 1991. Computing global virtual time using the multi-level token passing algorithm . In Proceedings of the SCS Multiconference on Advances in Parallel and Distributed Simulation, January, Anaheim, CA, pp. 63-68 .
24.
Balsamo, M. S. , and C. Manconi . 1998. Rollback overhead reduction methods for time warp distributed simulation . Simulation Practice and Theory6 (8): 689-702 .
25.
Fujimoto, R. M. 1990. Performance of time warp under synthetic workloads . In Proceedings of the SCS Multiconference on Distributed Simulation, January, San Diego, CA, pp. 23-28 .
26.
Overeinder, B. J. , A. Schoneveld , and P. M. A. Sloot . 2001. Spatio-temporal correlations and rollback distributions in optimistic simulations . In Proceedings of the 15th Workshop on Parallel and Distributed Simulation, May, Lake Arrowhead, CA, pp. 145-152 .
27.
Sloot, P. M. A. , B. J. Overeinder , and A. Schoneveld . 2001. Self-organized criticality in simulated correlated systems . Computer Physics Communications142 (1-3): 76-81 .
