Algorithms for unboundedly parallel simulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for unboundedly parallel simulations

Full text

Pdf (1.40 MB)

Source

ACM Transactions on Computer Systems (TOCS) archive
Volume 9 , Issue 3 (August 1991) table of contents

Pages: 201 - 221

Year of Publication: 1991

ISSN:0734-2071

Authors

Albert G. Greenberg	AT&T Bell Laboratories, Murray Hill, NJ
Boris D. Lubachevsky	University of Newcastle, Newcastle upon Tyne, NE1 7RU, UK
Isi Mitrani

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 29, Citation Count: 22

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/128738.128739 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ABRAHAMSON, N Development of the ALOHANET. IEEE Trans. Inf. Theor. 17'-31, 2 (Mar. 1985), 119-123.
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	Selim G. Akl, The design and analysis of parallel algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	4	BACCELLI, F Ergodic theory of stochastic petri nets. Tech. Rep 1037, INRIA-Sophia Antipolis, INRIA-Sophia 06565 Valbonne, France, May 1989.
	5	François Baccelli , William A. Massey , Don Towsley, Acyclic fork-join queuing networks, Journal of the ACM (JACM), v.36 n.3, p.615-642, July 1989 [doi>10.1145/65950.65957]
	6	BATCnER, K. E. Sorting networks and their apphcations. In AF{PS 1968 Spring Joznt Computer Conference (Atlantic City, NJ, May 1968). AFIPS Press, Montvale, NJ, pp. 307-314.
	7	CHANDY, K. M, AND MmRA, J. Distributed simulation: a case study in design and verification of distributed programs. IEEE Trans. Softw. Eng SE-5, 5 (1979), 440-452.
	8	CHANDY, K. M. AND SHERMAN, B Space-time and simulation. In Distributed Simulation 1989, Socmty for Computer Simulation, 1989, pp. 53-57.
	9	Connectton Machine, Model CM-2 Technical Summary, Version 5.1. Thinking Machines Corporation, Cambridge, Mass., May 1989.
	10	FENa, T.Y. A survey of interconnection networks. Computer 14 (1981), 12-27.
	11	GAVER, D. P., AND TttOMPSON, G. L Programming and Probabthty Models zn Operations Research. Brooks/Cole division of Wadsworth, Monterey, Calif., 1973
	12	GREENBERG, A. G., LADNER, R. E., PATERSON, M., AND GALm, Z. Efficient parallel algorithms for linear recurrence computation. Inf Process Lett. 15, I (Aug. 1982), 31-35.
	13	GREENBERG, A. G., AND LUBACHEVSK~, B. D. A simple efficient asynchronous parallel prefix algorithm. In 1987 International Conference on Parallel Processing (Penn State Univ., Aug. 1987), pp 66-69.
	14	GROrqDALSKI, R. A chip set for a masswely parallel architecture. In IEEE Internattonal Sohd State Ctrcuits Conference (New York, Feb. 1987).
	15	Philip Heidelberger, Discrete event simulations and parallel processing: statistical properties, SIAM Journal on Scientific and Statistical Computing, v.9 n.6, p.1114-1132, November 1988 [doi>10.1137/0909077]
	16	Philip Heidelberger, Statistical analysis of parallel simulations, Proceedings of the 18th conference on Winter simulation, p.290-295, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318448]
	17	L. Hyafil , H. T. Kung, The Complexity of Parallel Evaluation of Linear Recurrences, Journal of the ACM (JACM), v.24 n.3, p.513-521, July 1977 [doi>10.1145/322017.322030]
	18	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]
	19	Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
	20	K~USKAL, C. P Searching, merging, and sorting in parallel computation. IEEE Trans. Comput. TC-32 (Oct. 1983), 942-946.
	21	KRUSKAL, C. P., RUDOLPH, L., AND SNm, M. The power of parallel prefix. IEEE Trans. Comput. C-34, 10 (Oct. 1985), 965-968.
	22	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	23	LEIGHTON, T. An introduction to the theory of networks, parallel computation and VLSI design, 1989. Draft.
	24	B. D. Lubachevsky, Efficient distributed event-driven simulations of multiple-loop networks, Communications of the ACM, v.32 n.1, p.111-123, Jan. 1989 [doi>10.1145/63238.63247]
	25	LUBACHEVSKY, B. D. Efficient parallel simulations of asynchronous cellular arrays. Complex Syst. I (1987), 1099-1123.
	26	Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
	27	D. Mitra , I. Mitrani, Control and coordination policies for systems with buffers, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.156-164, May 1989
	28	I. Mitrani, Simulation Techniques for Discrete Event Systems, Cambridge University Press, New York, NY, 1982
	29	David M. Nicol, Parallel discrete-event simulation of FCFS stochastic queueing networks, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.124-137, July 19-21, 1988, New Haven, Connecticut, United States
	30	SIEGEL, H. J., NATION, W., KRUSKAL, C. P., AND NAPOLITANO, L.M. Uses of the multistage cube network topology. To appear in the Proceedings of the IEEE, 1989.
	31	D. B. Wagner , E. D. Lazowska, Parallel simulation of queueing networks: limitations and potentials, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.146-155, May 1989
	32	WHITT, W. The efficiency of one long run versus independent replications in steady state simulation. Preprint, 1989.

CITED BY 22

	François Baccelli , Miguel Canales, Parallel simulation of stochastic Petri nets using recurrence equations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.1, p.20-41, Jan. 1993
	Pirooz Vakili, Massively parallel and distributed simulation of a class of discrete event systems: a different perspective, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.2 n.3, p.214-238, July 1992
	Richard Fujimoto , David Nicol, State of the art in parallel simulation, Proceedings of the 24th conference on Winter simulation, p.246-254, December 13-16, 1992, Arlington, Virginia, United States
	Richard M. Fujimoto, Parallel simulation: parallel and distributed simulation systems, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
	Richard M. Fujimoto, Parallel and distributed discrete event simulation: algorithms and applications, Proceedings of the 25th conference on Winter simulation, p.106-114, December 12-15, 1993, Los Angeles, California, United States
	Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Superfast parallel discrete event simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.2, p.107-136, April 1996
	A. K. Agrawala , B. N. Jain, Deterministic Model and Transient Analysis of Virtual Circuits, IEEE Transactions on Software Engineering, v.19 n.2, p.187-197, February 1993
	A. S. McGough , I. Mitrani, Efficient distributed simulation of a communication switch with bursty sources and losses, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.85-92, May 28-31, 2000, Bologna, Italy
	Sigrún Andradóttir , Teunis J. Ott, Time-segmentation parallel simulation of networks of queues with loss or communication blocking, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.4, p.269-305, Oct. 1995
	François Baccelli , Nathalie Furmento , Bruno Gaujal, Parallel and distributed simulation of free choice Petri Nets, ACM SIGSIM Simulation Digest, v.25 n.1, p.3-10, July 1995
	Ioanis Nikolaidis , Richard Fujimoto , C. Anthony Cooper, Time-parallel simulation of cascaded statistical multiplexers, ACM SIGMETRICS Performance Evaluation Review, v.22 n.1, p.231-240, May 1994
	Boris D. Lubachevsky, Several unsolved problems in large-scale discrete event simulations, ACM SIGSIM Simulation Digest, v.23 n.1, p.60-67, July 1993
	A. S. McGough , I. Mitrani, Efficient parallel simulation of a sliding window protocol, Performance Evaluation, v.48 n.1-4, p.237-246, May 2002
	Richard M. Fujimoto, Parallel and distributed simulation, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.122-131, December 05-08, 1999, Phoenix, Arizona, United States
	Tobias Kiesling , Siegfried Pohl, Time-parallel simulation with approximative state matching, Proceedings of the eighteenth workshop on Parallel and distributed simulation, May 16-19, 2004, Kufstein, Austria
	Tobias Kiesling, Using Approximation with Time-Parallel Simulation, Simulation, v.81 n.4, p.255-266, April 2005
	Liang Chen, Parallel simulation by multi-instruction, longest-path algorithms, Queueing Systems: Theory and Applications, v.27 n.1-2, p.37-54, 1997
	Tobias Kiesling , Thomas Krieger, Efficient parallel queuing system simulation, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	Tobias Kiesling, Approximate time-parallel cache simulation, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
	Tobias Kiesling, Progressive Time-Parallel Simulation, Proceedings of the 20th Workshop on Principles of Advanced and Distributed Simulation, p.82-91, May 24-26, 2006
	Tobias Kiesling , Johannes Luthi, Towards Time-Parallel Road Traffic Simulation, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.7-15, June 01-03, 2005
	Hao Wu , Richard M. Fujimoto , Mostafa Ammar, Time-Parallel Trace-Driven Simulation of CSMA/CD, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.105, June 10-13, 2003