More Web Proxy on the site http://driver.im/

research-article

Parallel Expanded Event Simulation of Tightly Coupled Systems

Authors:

Mirko Stoffers,

Olaf Landsiedel,

James GrossAuthors Info & Claims

ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 26, Issue 2

Article No.: 12, Pages 1 - 26

https://doi.org/10.1145/2832909

Published: 06 January 2016 Publication History

Abstract

The technical evolution of wireless communication technology and the need for accurately modeling these increasingly complex systems causes a steady growth in the complexity of simulation models. At the same time, multi-core systems have become the de facto standard hardware platform. Unfortunately, wireless systems pose a particular challenge for parallel execution due to a tight coupling of network entities in space and time. Moreover, model developers are often domain experts with no in-depth understanding of parallel and distributed simulation. In combination, both aspects severely limit the performance and the efficiency of existing parallelization techniques. We address these challenges by presenting parallel expanded event simulation, a novel modeling paradigm that extends discrete events with durations that span a period in simulated time. The resulting expanded events form the basis for a conservative synchronization scheme that considers overlapping expanded events eligible for parallel processing. We then put these concepts into practice by implementing Horizon, a parallel expanded event simulation framework specifically tailored to the characteristics of multi-core systems. Our evaluation shows that Horizon achieves considerable speedups in synthetic as well as real-world simulation models and considerably outperforms the current state-of-the-art in distributed simulation.

References

[1]

R. L. Bagrodia and M. Takai. 2002. Performance evaluation of conservative algorithms in parallel simulation languages. IEEE Transactions on Parallel and Distributed Systems 11, 4 (2002), 395--411.

Digital Library

[2]

P. D. Barnes, J. M. Brase, T. W. Canale, M. M. Damante, M. A. Horsley, D. R. Jefferson, and R. A. Soltz. 2012. A benchmark model for parallel ns-3. In Proceedings of the 5th International ICST Conference on Simulation Tools and Techniques.

Digital Library

[3]

R. Barr, H. Zygmunt, and R. van Renesse. 2004. JiST: Embedding simulation time into a virtual machine. In Proceedings of EuroSim Congress on Modelling and Simulation.

[4]

L. Bononi, M. Di Felice, M. Bertini, and E. Croci. 2006. Parallel and distributed simulation of wireless vehicular ad hoc networks. In Proceedings of the 9th International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems.

Digital Library

[5]

V. Cadambe and S. Jafar. 2008. Interference alignment and degrees of freedom of the k-user interference channel. IEEE Transactions on Information Theory 54, 8 (2008), 3425.

Digital Library

[6]

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

Digital Library

[7]

G. Chen and B. K. Szymanski. 2005. DSIM: Scaling time warp to 1,033 processors. In Proceedings of the 37th Winter Simulation Conference.

Digital Library

[8]

L. Chen, Y. Lu, Y. Yao, S. Peng, and L. Wu. 2011. A well-balanced time warp system on multi-core environments. In Proceedings of IEEE Workshop on Principles of Advanced and Distributed Simulation (PADS).

Digital Library

[9]

J. Cowie, A. Ogielski, and D. M. Nicol. 2002. The SSFNet Network Simulator. Software on-line: http://www.ssfnet.org/homePage.html. (2002).

[10]

J. H. Cowie, D. M. Nicol, and A. T. Ogielski. 1999. Modeling the global internet. Computing in Science & Engineering 1, 1 (Jan. 1999), 42--50.

Digital Library

[11]

G. D’Angelo, S. Ferretti, and M. Marzolla. 2012. Time warp on the go. In Proceedings of the 5th International ICST Conference on Simulation Tools and Techniques.

Digital Library

[12]

R. M. Fujimoto. 1990a. Parallel discrete event simulation. Communications of the ACM 33, 10 (1990), 30--53.

Digital Library

[13]

R. M. Fujimoto. 1990b. Performance of time warp under synthetic workloads. In Proceedings of the SCS Multiconference on Distributed Simulation.

[14]

R. M. Fujimoto. 1999. Exploiting temporal uncertainty in parallel and distributed simulations. In Proceedings of the 13th Workshop on Parallel and Distributed Simulation.

Digital Library

[15]

R. M. Fujimoto, K. S. Perumalla, A. Park, H. Wu, M. H. Ammar, and G. F. Riley. 2003. Large-scale network simulation: How big? How fast? In Proceedings of 11th International IEEE Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems.

[16]

D. Gesbert, M. Shafi, D. Shiu, P. J. Smith, and A. Naguib. 2003. From theory to practice: An overview of mimo space-time coded wireless systems. IEEE Journal on Selected Areas in Communications 21, 3 (April 2003), 281--302.

Digital Library

[17]

D. Halperin, T. Anderson, and D. Wetherall. 2008. Taking the sting out of carrier sense: Interference cancellation for wireless LANs. In Proceedings of the 14th ACM Internatinoal Conference on Mobile Computing and Networking.

Digital Library

[18]

T. R. Henderson, S. Roy, S. Floyd, and G. F. Riley. 2006. ns-3 project goals. In Proceedings of the 2006 Workshop on ns-2: The IP Network Simulator.

Digital Library

[19]

M. Hybinette and R. M. Fujimoto. 1997. Cloning: A novel method for interactive parallel simulation. In Proceedings of the 29th Winter Simulation Conference.

Digital Library

[20]

M. Hybinette and R. M. Fujimoto. 2001. Cloning parallel simulations. ACM Transactions on Modeling and Computer Simulation 11, 4 (Oct. 2001), 378--407.

Digital Library

[21]

D. Jagtap, N. Abu-Ghazaleh, and D. Ponomarev. 2012. Optimization of parallel discrete event simulator for multi-core systems. In Proceedings of the IEEE 26th Internatiaonal Parallel and Distributed Processing Symposium.

Digital Library

[22]

I. Koffman, V. Roman, and R. Technol. 2002. Broadband wireless access solutions based on OFDM access in IEEE 802.16. IEEE Communications Magazine 40, 4 (2002), 96--103.

Digital Library

[23]

G. Kunz. 2013. Exploiting Multi-core Systems for Parallel Network Simulation. Shaker Verlag. PhD Dissertation.

[24]

G. Kunz, O. Landsiedel, J. Gross, S. Götz, F. Naghibi, and K. Wehrle. 2010. Expanding the event horizon in parallelized network simulations. In Proceedings of the 18th International IEEE Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems.

Digital Library

[25]

G. Kunz, O. Landsiedel, and K. Wehrle. 2009. Poster abstract: Horizon - exploiting timing information for parallel network simulation. In Proceedings of the 17th International IEEE Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems.

[26]

G. Kunz, M. Stoffers, J. Gross, and K. Wehrle. 2011. Runtime efficient event scheduling in muti-threaded network simulation. In Proceedings of the 4th International Workshop on OMNeT++.

Digital Library

[27]

G. Kunz, M. Stoffers, J. Gross, and K. Wehrle. 2012. Know thy simulation model: Analyzing event interactions for probabilistic synchronization in parallel simulations. In Proceedings of the 5th International ICST Conf. on Simulation Tools and Techniques.

Digital Library

[28]

Z. Li, X. Li, L. Wang, and W. Cai. 2014. Hierarchical resource management for enhancing performance of large-scale simulations on data centers. In Proceedings of the 2nd Conference on Principles of Advanced Discrete Simulation.

Digital Library

[29]

J. Liu. 2009. Parallel Discrete-Event Simulation. John Wiley & Sons.

[30]

J. Liu, Y. Li, and Y. He. 2009. A large-scale real-time network simulation study using PRIME. In Proceedings of the 2009 Winter Simulation Conference.

Digital Library

[31]

J. Liu and D. M. Nicol. 2001. Learning not to share. In Proceedings 15th Workshop on Parallel and Distributed Simulation.

Digital Library

[32]

J. Liu and D. M. Nicol. 2002. Lookahead revisited in wireless network simulations. In Proceedings of the 16th Workshop on Parallel and Distributed Simulation.

Digital Library

[33]

M. Loper and R. M. Fujimoto. 2000. Pre-sampling as an approach for exploiting temporal uncertainty. In Proceedings of the 14th Workshop on Parallel and Distributed Simulation.

Digital Library

[34]

M. Loper and R. M. Fujimoto. 2004. A case study in exploiting temporal uncertainty in parallel simulations. In Proceedings of the 2004 International Conference on Parallel Processing.

Digital Library

[35]

B. D. Lubachevsky. 1988. Efficient distributed event driven simulations of multiple-loop networks. In Proceedings of the ACM SIGMETRICS Conferenece on Measurement and Modeling of Computer Systems.

Digital Library

[36]

A. Markopoulou, F. Tobagi, and M. Karam. 2006. Loss and delay measurements of internet backbones. Computer Communications 29, 10 (June 2006), 1590--1604.

Digital Library

[37]

R. A. Meyer and R. L. Bagrodia. 1998. Improving lookahead in parallel wireless network simulation. In Proceedings of the 6th International IEEE Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems.

Digital Library

[38]

R. A. Meyer and R. L. Bagrodia. 1999. Path lookahead: A data flow view of PDES models. In Proceedings of the 13th Workshop on Parallel and Distributed Simulation.

Digital Library

[39]

F. Naghibi and J. Gross. 2010. How bad is interference in IEEE 802.16e systems? In Proceedings of the 16th European Wireless Conference.

[40]

D. M. Nicol. 1996. Principles of conservative parallel simulation. In Proceedings of the 28th Winter Simulation Conference.

Digital Library

[41]

D. M. Nicol. 2003. Darpa Network Modeling and Simulation (NMS) Baseline Network Topology. Last accessed November 28, 2014. (2003). http://www.ssfnet.org/Exchange/gallery/baseline/index.html.

[42]

D. M. Nicol and J. Liu. 2002. Composite synchronization in parallel discrete-event simulation. IEEE Transactions on Parallel Distributed Systems 13, 5 (May 2002), 433--446.

Digital Library

[43]

K. S. Perumalla. 2006. Parallel and distributed simulation: Traditional techniques and recent advances. In Proceedings of the 38th Winter Simulation Conference.

Digital Library

[44]

P. Peschlow, T. Honecker, and P. Martini. 2007. A flexible dynamic partitioning algorithm for optimistic distributed simulation. In Proceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation.

Digital Library

[45]

P. Peschlow, P. Martini, and J. Liu. 2008. Interval branching. In Proc. of the 22nd Workshop on Principles of Advanced and Distributed Simulation.

Digital Library

[46]

P. Peschlow, A. Voss, and P. Martini. 2009. Good news for parallel wireless network simulations. In Proceedings of the 12th International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems.

Digital Library

[47]

O. Punal, H. Escudero, and J. Gross. 2011. Performance comparison of loading algorithms for 80 MHz IEEE 802.11 WLANs. In Proceedings of the 73rd IEEE Vehicular Technology Conference.

[48]

G. F. Riley. 2003. The georgia tech network simulator. In Proceedings of the ACM SIGCOMM Workshop on Models, Methods and Tools for Reproducible Network Research.

Digital Library

[49]

G. Seguin. 2009. Multi-core Parallelism for ns-3 Simulator. Technical Report. INRIA Sophia-Antipolis.

[50]

A. Sekercioglu, A. Varga, and G. Egan. 2003. Parallel simulation made easy with OMNeT++. In Proceedings of the European Simulation Symposium.

[51]

M. Stoffers, R. Bettermann, J. Gross, and K. Wehrle. 2014a. Enabling distributed simulation of OMNeT++ INET models. In Proceedings of the 1st OMNeT++ Community Summit.

[52]

M. Stoffers, S. Schmerling, G. Kunz, J. Gross, and K. Wehrle. 2014b. Large-scale network simulation: Leveraging the strengths of modern smp-based compute clusters. In Proceedings of the 7th Internatiaonal ICST Conference on Simulation Tools and Techniques (SIMUTools’14).

Digital Library

[53]

A. Varga. 2001. The OMNeT++ discrete event simulation system. In Proceedings of the 15th European Simulation Multiconference.

[54]

A. Varga. 2014. OMNeT++ Website. Retrieved November 28, 2014 from http://www.omnetpp.org.

[55]

R. Vitali, A. Pellegrini, and F. Quaglia. 2012. Towards symmetric multi-threaded optimistic simulation kernels. In Proceedings of IEEE Workshop on Principles of Advanced and Distributed Simulation (PADS).

Digital Library

[56]

C.-X. Wang, M. Pätzold, and Q. Yao. 2007. Stochastic modeling and simulation of frequency-correlated wideband fading channels. IEEE Transactions on Vehicular Technology 56, 3 (2007).

[57]

S. B. Yoginath and K. S. Perumalla. 2013. Optimized hypervisor scheduler for parallel discrete event simulations on virtual machine platforms. In Proceedings of the 6th International ICST Conf. on Simulation Tools and Techniques.

Digital Library

Cited By

Mahdi MWalshe RFarrell SPandit H(2024)Comprehensive Review and Future Research Directions on ICT StandardisationInformation10.3390/info1511069115:11(691)Online publication date: 2-Nov-2024
https://doi.org/10.3390/info15110691
Buse DEchterling GDressler F(2022)Asynchronous Background Processing for accelerated simulation of wireless communication on multi-core systemsComputer Communications10.1016/j.comcom.2022.07.032193:C(396-409)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.comcom.2022.07.032
Buse DEchterling GDressler FIgartua MGiannelli CZheng J(2021)Accelerating the Simulation of Wireless Communication Protocols using Asynchronous ParallelismProceedings of the 24th International ACM Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems10.1145/3479239.3485683(57-66)Online publication date: 22-Nov-2021
https://dl.acm.org/doi/10.1145/3479239.3485683
Show More Cited By

Index Terms

Parallel Expanded Event Simulation of Tightly Coupled Systems
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation types and techniques
      1. Discrete-event simulation
      2. Massively parallel and high-performance simulations

Recommendations

Parallel shared-memory simulator performance for large ATM networks

A performance comparison between an optimistic and a conservative parallel simulation kernel is presented. Performance of the parallel kernels is also compared to a central-event-list sequential kernel. A spectrum of ATM network and traffic scenarios ...
Parallel discrete event simulation for DEVS cellular models using a GPU
HPC '12: Proceedings of the 2012 Symposium on High Performance Computing

The discrete event systems specification (DEVS) simulation has been studied to analyze complex homogeneous systems which is represented by the cellular models. In the simulation of large-scale DEVS cellular model, it requires a high-performance ...
Parallel VHDL simulation
DATE '98: Proceedings of the conference on Design, automation and test in Europe

In this paper we evaluate parallel VHDL simulation based on conservative parallel discrete event simulation (conservative PDES) algorithms. We focus on a conservative simulation algorithm based on critical and external distances. This algorithm exploits ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation

ACM Transactions on Modeling and Computer Simulation Volume 26, Issue 2

January 2016

152 pages

ISSN:1049-3301

EISSN:1558-1195

DOI:10.1145/2875131

Editor:
Adelinde M. Uhrmacher
University of Rostock, Germany

Issue’s Table of Contents

Copyright © 2016 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 the author(s) 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: 06 January 2016

Accepted: 01 September 2015

Revised: 01 July 2015

Received: 01 March 2014

Published in TOMACS Volume 26, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

DFG Cluster of Excellence on Ultra High-Speed Mobile Information and Communication (UMIC)
German Research Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
212
Total Downloads

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

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mahdi MWalshe RFarrell SPandit H(2024)Comprehensive Review and Future Research Directions on ICT StandardisationInformation10.3390/info1511069115:11(691)Online publication date: 2-Nov-2024
https://doi.org/10.3390/info15110691
Buse DEchterling GDressler F(2022)Asynchronous Background Processing for accelerated simulation of wireless communication on multi-core systemsComputer Communications10.1016/j.comcom.2022.07.032193:C(396-409)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.comcom.2022.07.032
Buse DEchterling GDressler FIgartua MGiannelli CZheng J(2021)Accelerating the Simulation of Wireless Communication Protocols using Asynchronous ParallelismProceedings of the 24th International ACM Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems10.1145/3479239.3485683(57-66)Online publication date: 22-Nov-2021
https://dl.acm.org/doi/10.1145/3479239.3485683
Obermaier CRiebl RFacchi CAl-Bayatti AKhan SDiallo STolk AGiabbanelli P(2021)COSIDIA: An Approach for Real-Time Parallel Discrete Event Simulations Tailored for Wireless NetworksProceedings of the 2021 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3437959.3459250(165-171)Online publication date: 21-May-2021
https://dl.acm.org/doi/10.1145/3437959.3459250
Fujimoto R(2016)Research Challenges in Parallel and Distributed SimulationACM Transactions on Modeling and Computer Simulation10.1145/286657726:4(1-29)Online publication date: 2-May-2016
https://dl.acm.org/doi/10.1145/2866577

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents