Bounds and approximations for self-initiating distributed simulation without lookahead

ABSTRACT

We provide upper and lower bounds and an approximation for speedup of an optimistic self-initiated distributed simulation using a very simple model. We assume an arbitrary number of processors and a uniform connection topology. By showing that the lower bound increases essentially linearly with P, the number of processors, we find that the optimistic approach scales well as P increases. The model tracks the progress of Global Virtual Time (GVT) and eliminates the need to know the virtual time positions of all processors, thus making the analysis quite straightforward.

REFERENCES

• 1: C~ANC, C. S., AND NELSON, R. Bounds on the speedup and efficiency of partial synchronization in parallel processing systems. Tech. Rep. RC 16474, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., Jan. 1991.
• 2: Robert Edman Felderman, Performance analysis of distributed processing synchronization algorithms, University of California at Los Angeles, Los Angeles, CA, 1992
• 3: FELDERMAN, R. E., AND KLEINROCK, L. Two processor time warp analysis: Capturing the effects of message queueing and rollback/state saving costs. Tech. Rep. 920035, Dept. of Computer Science, Univ. of California, Los Angeles, 1992.
• 4: FELDERMAN, R. E., AND KLEINROCK, L. Two processor time warp analysis: Some results on a unifying approach. In Proceedings of the 5th Workshop on Parallel and Distributed S~rnulatton (PADS91), vol. 23, Society for Computer Simulation, Jan. 1991, pp. 3-10.
• 5: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 6: A. Gupta , I. F. Akyildiz , R. M. Fujimoto, Performance Analysis of Time Warp with Multiple Homogeneous Processors, IEEE Transactions on Software Engineering, v.17 n.10, p.1013-1027, October 1991 [doi>10.1109/32.99190]
• 7: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 8: JOLLEY, L. B.W. Surnrnatton of Series. 2d ed Dover, 1961.
• 9: KLEINROCK, L. On distributed systems performance. Comput. Netw. ISDN Syst. 20, 1 5 (Dec. 1990), 206 215.
• 10: KLEINROCK, L., AND FELDERMAN, R. E. Two processor time warp analysis: A unifying approach. Tech Rep. 920034, Computer Science Dept, Unlv of California, Los Angeles Also Int J. Comput. Stmul.
• 11: Stephen S. Lavenberg , Richard R. Muntz , Behrokh Samadi, Performance Analysis of a Rollback Method for Distributed Simulation, Proceedings of the 9th International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.117-132, May 25-27, 1983
• 12: Yi-Bing Lin , Edward D. Lazowska, A study of time warp rollback mechanisms, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.51-72, Jan. 1991 [doi>10.1145/102810.102813]
• 13: LIN, YI-B., AND LAZOWSKA, E.D. Effect of process scheduhng in parallel simulation. Int. J Cornput. Szmul. 2, 1 (1992), 107-121.
• 14: LIN, YI-B., AND L~ZOWSKA, E.D. Reducing the state saving' overhead for time warp parallel simulation. Tech. Rep. 90-02-03, Dept. of Computer Science and Engineering, Univ. of Washington, Feb. 1990.
• 15: LIN, YI-B., AND LAZOWSKA, E D. Optimality considerations for "time warp" parallel simulation. In Proceedzngs of the SCS Mult~conference on Dzstrlbuted Slmulatzon, vol. 22, 1, Society for Computer Simulation, Jan. 1990, pp. 29-34.
• 16: LIN, YI-B., LAZOWSKA, E. D., AND BAER, J.-L. Parallel trace-driven simulation ofmultiprocessor cache performance: Algorithms and analysis. Tecb. Rep. 89-07-06, Dept. of Computer Science and Engineering, Univ. of Washington, Seattle, July 1989.
• 17: LUBACHEVSKY, B.D. Efficient parallel simulations of asynchronous cellular arrays. Complex Syst I (1987), 1099 1123.
• 18: B. Lubachevsky , A. Shwartz , A. Weiss, Rollback sometimes works...if filtered, Proceedings of the 21st conference on Winter simulation, p.630-639, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76819]
• 19: MADISETTI, V.K. SelLsynchronizing concurrent computing systems Tech. Rep. UCB/ERL M89/122, Electronics Research Laboratory, College of Engineering, Univ. of California, Berkeley, Oct. 1989.
• 20: MADISETTI, V, WALED, J., AND MESSERSCHMITT, D. Synchronization m message-passing computers: Models, algorithms, and analysis. In Proceedzngs of the SCS Multwonference on Dzstnbuted Slmulatmn, vol. 22, 1, Society for Computer Simulation, Jan. 1990, pp. 35 48.
• 21: Debasis Mitra , Isi Mitrani, Analysis and Optimum Performance of Two Message-Passing Parallel Processors Synchronized by Rollback, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.35-50, December 19-21, 1984
• 22: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 23: David M. Nicol, Performance bounds on parallel self-initiating discrete-event simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.24-50, Jan. 1991 [doi>10.1145/102810.102812]
• 24: Shioupyn Shen, The virtual-time data-parallel machine, University of California at Los Angeles, Los Angeles, CA, 1992

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Performance attributes

General Terms:
Algorithms, Performance

Keywords:
Global Virtual Time, Time Warp, bounds, discrete-event simulation, distributed processing, optimal, optimistic simulation, parallel processing, performance analysis, speedup, virtual time