article

Free access

Unboundedly parallel simulations via recurrence relations

Authors:

Albert G. Greenberg,

Boris D. Lubachevsky,

Isi MitraniAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 18, Issue 1

Pages 1 - 12

https://doi.org/10.1145/98460.98492

Published: 01 April 1990 Publication History

Abstract

New methods are presented for parallel simulation of discrete event systems that, when applicable, can usefully employ a number of processors much larger than the number of objects in the system being simulated. Abandoning the distributed event list approach, the simulation problem is posed using recurrence relations. We bring three algorithmic ideas to bear on parallel simulation: parallel prefix computation, parallel merging, and iterative folding. Efficient parallel simulations are given for (in turn) the G/G/1 queue, a variety of queueing networks having a global first come first served structure (e.g., a series of queues with finite buffers), acyclic networks of queues, and networks of queues with feedbacks and cycles. In particular, the problem of simulating the arrival and departure times for the first N jobs to a single G/G/1 queue is solved in time proportional to N/P + log P using P processors.

References

[1]

K.M. Chandy and J. Misra. Distributed simulation" a case study in design and verification of distributed programs. IEEE Transactions on Software Engineering, SE-5(5), 1979.

Digital Library

[2]

B.D. Lubachevsky. Efficient distributed eventdriven simulation of multiple-loop networks. Communications of the ACM, 32(1):111, January 1989.

Digital Library

[3]

J. Misra. Distributed-discrete event simulation. ACM Computing Surveys, 18(1):39-66, March 1986.

Digital Library

[4]

D.M. Nichol. Parallel discrete-event simulation of FCFS queueing networks. In Parallel Programming: Experience with Applicalions, Languages, and Systems, pages 124-137. ACM SIGPLAN, July 1988.

Digital Library

[5]

D.B. Wagner and E.D. Lazowska. Parallel simulation of queueing networks" Limitations and potentials. In 1989 ACM Sigmetrics Performance Evaluation Review and Performance '89, volume 17, pages 146-155, Berkeley, CA, May 1989. ACM Press.

Digital Library

[6]

D.R. Jefferson. Virtual time. A CM Transactions on Programming Languages and Systems, 7(3):404- 425, July 1985.

Digital Library

[7]

Thinking Machines Corporation, Cambridge, Mass. Connection Machine, Model CM-2 Technical Summary, Version 5.1, May 1989.

[8]

R. Grondalski. A chip set for a massively parallel architecture. In IEEE International Solid Sta~e Circuils Conference, New York, February 1987.

[9]

R.E. Ladner and M.J. Fischer. Parallel prefix computation. Journal of the ACM, 27:831-838, 1980.

Digital Library

[10]

A.G. Greenberg, R.E. Ladner, M. Paterson, and Z. Galil. Efficient parallel algorithms for linear recurrence computation. Information Processing Letlers, 15(1):31-35, August 1982.

[11]

L. Hyafil and H.T. Kung. The complexity of parallel evaluation of recurrences. Journal of the A CM, 24:513-521, 1977.

Digital Library

[12]

F. Baccelli, W. Massey, and D. Towsley. Acyclic fork-join queueing networks, journal of the ACM, 36(3):615-642, July 1989.

Digital Library

[13]

D. Mitra and I. Mitrani. Control and coordination policies for systems with buffers. In 1989 A CM Sigmetrics Performance Evaluation Review and Performance '89, volume 17, pages 156-164, Berkeley, CA, May 1989. ACM Press.

Digital Library

[14]

B.D. Lubachevsky. Efficient parallel simulations of asynchronous cellular arrays. Complex Systems, 1:1099-1123, 1987.

[15]

N. Abrahamson. Development of the ALOHANET. IEEE Transactions on Information Theory, IT- 31(2):119-123, March 1985.

[16]

L. Kleinrock. Queueing Systems, Volume 1: Theory. Wiley, New York, 1975.

Digital Library

[17]

D.P. Gaver and G.L. Thompson. Programming and Probability Models in Operations Research. Brooks/Cole division of Wadsworth, Monterey, Cal., 1973.

[18]

F. Baccelli. Ergodic theory of stochastic petri nets. Technical Report 1037, INRIA-Sophia Antipolis, INRIA-Sophia 06565 Valbonne, France, May 1989.

[19]

K.M. Chandy and B. Sherman. Space-time and simulation. In Distributed Simulation 1989, pages 53-57. The Society for Computer Simulation, 1989.

[20]

P. Heidelberger. Statistical analysis of parallel simulations. In 1986 Win~er Simulation Conference. IEEE, December 1986. also IBM Research Report RC 12072.

Digital Library

[21]

W. Whitt. The efficiency of one long run versus independent replications in steady state simulation. preprint, 1989.

[22]

T. Leighton. An introduction to the theory of networks, parallel computation and VLSI design, 1989. draft.

[23]

I. Mitrani. Simulation Techniques for Discrete Event Systems. Cambridge University Press, 1982.

Digital Library

[24]

C. P. Kruskal, L. Rudolph, and M. Snir. The power of parallel prefix. IEEE Transactions on Computers, C-34(10), October 1985.

[25]

A.G. Greenberg and B.D. Lubachevsky. A simple efficient asynchronous parallel prefix algorithm. In 1987 International Conference on Parallel Processing, pages 66-69, 1987.

[26]

A. Aho, J. ttopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison Wesley, New York, 1974.

Digital Library

[27]

S.G. Akl. The Design and Analysis of Parallel Algorithms. Prentice Hall, Englewood Cliffs, 1989.

Digital Library

[28]

K.E. Batcher. Sorting networks and their applications. In AFIPS 1968 Spring Joint Computer Conference, pages 307-314, Atlantic City,NJ, May 1968. AFIPS Press; Montvale, NJ.

Digital Library

[29]

C.P. Kruskal. Searching, merging, and sorting in parallel computation. IEEE Transactions on Computers, TC-32:942-946, 1983.

Digital Library

[30]

T.Y. Feng. A survey of interconnection networks. Computer, 14:12-27, 1981.

Digital Library

[31]

H.J. Siegel, W. Nation, C.P. Kruskal, and L.M. Napolitano. Uses of the multistage cube network topology, to appear in the Proceedings of the IEEE, 1989.

Cited By

Heidelberger PNicol D(1993)Conservative Parallel Simulation of Continuous Time Markov Chains Using UniformizationIEEE Transactions on Parallel and Distributed Systems10.1109/71.2386254:8(906-921)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1109/71.238625
Abrams MPage ENance RNelson BKelton WClark G(1991)Linking simulation model specification and parallel execution through UNITYProceedings of the 23rd conference on Winter simulation10.5555/304238.304283(223-232)Online publication date: 1-Dec-1991
https://dl.acm.org/doi/10.5555/304238.304283
Gupta AAkyildiz IFujimoto R(1991)Performance analysis of Time Warp with homogeneous processors and exponential task timesACM SIGMETRICS Performance Evaluation Review10.1145/107972.10798319:1(101-110)Online publication date: 2-Apr-1991
https://dl.acm.org/doi/10.1145/107972.107983
Show More Cited By

Index Terms

Unboundedly parallel simulations via recurrence relations

Recommendations

Unboundedly parallel simulations via recurrence relations
SIGMETRICS '90: Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems

New methods are presented for parallel simulation of discrete event systems that, when applicable, can usefully employ a number of processors much larger than the number of objects in the system being simulated. Abandoning the distributed event list ...
Recurrence Relations for Two-Channel Queuing Systems with Erlangian Service Time

We propose a method to investigate M / Es / 2 / m and M / Es / 2 /ź queueing systems including the case of random dropping of customers. Recurrence relations are obtained for computing the stationary distribution of the number of customers in the system ...
How Hard are Steady-State Queueing Simulations?
Special Issue on Don Iglehart

Some queueing systems require tremendously long simulation runlengths to obtain accurate estimators of certain steady-state performance measures when the servers are heavily utilized. However, this is not uniformly the case. We analyze a number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 18, Issue 1

May 1990

269 pages

ISSN:0163-5999

DOI:10.1145/98460

Editor:
M. K. Vernon

Issue’s Table of Contents

SIGMETRICS '90: Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems
April 1990
273 pages
ISBN:0897913590
DOI:10.1145/98457
Chairman:
Gary J. Nutt
Univ. of Colorado, Boulder, CO

Copyright © 1990 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1990

Published in SIGMETRICS Volume 18, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
525
Total Downloads

Downloads (Last 12 months)77
Downloads (Last 6 weeks)12

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Heidelberger PNicol D(1993)Conservative Parallel Simulation of Continuous Time Markov Chains Using UniformizationIEEE Transactions on Parallel and Distributed Systems10.1109/71.2386254:8(906-921)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1109/71.238625
Abrams MPage ENance RNelson BKelton WClark G(1991)Linking simulation model specification and parallel execution through UNITYProceedings of the 23rd conference on Winter simulation10.5555/304238.304283(223-232)Online publication date: 1-Dec-1991
https://dl.acm.org/doi/10.5555/304238.304283
Gupta AAkyildiz IFujimoto R(1991)Performance analysis of Time Warp with homogeneous processors and exponential task timesACM SIGMETRICS Performance Evaluation Review10.1145/107972.10798319:1(101-110)Online publication date: 2-Apr-1991
https://dl.acm.org/doi/10.1145/107972.107983
Gupta AAkyildiz IFujimoto RKeller T(1991)Performance analysis of Time Warp with homogeneous processors and exponential task timesProceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems10.1145/107971.107983(101-110)Online publication date: 2-Apr-1991
https://dl.acm.org/doi/10.1145/107971.107983
Greenberg ASchlunk OWhitt W(2009)Using Distributed-Event Parallel Simulation to Study Departures from Many Queues in SeriesProbability in the Engineering and Informational Sciences10.1017/S02699648000028507:02(159)Online publication date: 27-Jul-2009
https://doi.org/10.1017/S0269964800002850
Hoseyni-Nasab MAndradóttir S(1997)Efficiency of time segmentation parallel simulation of queueing networks as a function of the size of the networkProceedings of the 29th conference on Winter simulation10.1145/268437.268474(181-186)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1145/268437.268474
Teo YChin WTan SHong HKaltofen E(1997)Deriving efficient parallel programs for complex recurrencesProceedings of the second international symposium on Parallel symbolic computation10.1145/266670.266697(101-110)Online publication date: 20-Jul-1997
https://dl.acm.org/doi/10.1145/266670.266697
Chen L(1997)Parallel simulation by multi-instruction, longest-path algorithmsQueueing Systems: Theory and Applications10.1023/A:101914971201927:1/2(37-54)Online publication date: 14-Dec-1997
https://dl.acm.org/doi/10.1023/A%3A1019149712019
Hoseyni-Nasab MAndradóttir S(1996)Parallel simulation by time segmentationProceedings of the 28th conference on Winter simulation10.1145/256562.256659(376-381)Online publication date: 8-Nov-1996
https://dl.acm.org/doi/10.1145/256562.256659
Kumaran KLubachevsky BElwalid A(1996)Massively parallel simulations of ATM systemsACM SIGSIM Simulation Digest10.1145/238793.23881026:1(39-46)Online publication date: 1-Jul-1996
https://dl.acm.org/doi/10.1145/238793.238810
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents