Parallel Discrete-Event Simulation on Data Processing Engines
Pages 69 - 76
Abstract
Development of a decent parallel simulator is challenging work. It should achieve enough performance, scalability and fault tolerance. Our proposal is utilizing general-purpose data processing engines such as MapReduce implementations for parallel simulation. Widely used and mature engines take away a large part of the development effort and support scalability and fault tolerance. We demonstrate that a parallel discrete-event simulator can be implemented on such engines, Apache Hadoop and Apache Spark, by modeling message passing of distributed systems on MapReduce key-value processing model. Implemented simulators could handle 108 nodes with 10 computers. Preliminary evaluation showed that our Spark-based simulator is about 20 times as fast as an existing simulator thanks to Time Warp.
References
[1]
"Apache Hadoop," http://hadoop.apache.org/.
[2]
"Apache Spark," http://spark.apache.org/.
[3]
J. Dean and S. Ghemawat, "MapReduce: Simplified data processing on large clusters," in Proc. OSDI'04, Dec. 2004.
[4]
T. Klingberg and R. Manfredi, "Gnutella 0.6," Jun. 2002, http://rfc-gnutella.sourceforge.net/src/rfc-0_6-draft.html.
[5]
D. R. Jefferson, "Virtual time," ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 7, no. 3, pp. 404--425, Jul. 1985.
[6]
L. M. Sokol, D. P. Briscoe, and A. P. Wieland, "MTW: A strategy for scheduling discrete simulation events for concurrent execution," Proc. SCS Multiconference on Distributed Simulation, vol. 19, no. 3, pp. 34--42, Jul. 1988.
[7]
K. S. Panesar and R. M. Fujimoto, "Adaptive flow control in Time Warp," in Proc. PADS'97, Jun. 1997, pp. 108--115.
[8]
K. Shudo, Y. Tanaka, and S. Sekiguchi, "Overlay Weaver: An overlay construction toolkit," Computer Communications (Special Issue on Foundations of Peer-to-Peer Computing), vol. 31, no. 2, pp. 402--412, Feb. 2008.
[9]
K. Shudo, "Overlay Weaver: An overlay construction toolkit," http://overlayweaver.sf.net/.
[10]
T. T. A. Dinh, M. Lees, G. Theodoropoulos, and R. Minson, "Large scale distributed simulation of p2p networks," in Proc. PDP 2008, Feb. 2008, pp. 499--507.
[11]
K. M. Chandy and J. Misra, "Distributed simulation: A case study in the design and verification of distributed programs," IEEE Transactions on Software Engineering, vol. SE-5, no. 5, pp. 440--452, Sep. 1979.
[12]
"ns-3," https://www.nsnam.org/.
[13]
Q. Bragard, A. Ventresque, and L. Murphy, "dSUMO: Towards a distributed SUMO," in Proc. SUMO2013, May 2013, pp. 132--146.
[14]
M. Behrisch, L. Bieker, J. Erdmann, and D. Krajzweicz, "SUMO - Simulation of Urban MObility: An overview," in Proc. SIMUL 2011, Oct. 2011, pp. 63--68.
[15]
R. L. Graham, G. M. Shipman, B. W. Barrett, R. H. Castain, G. Bosilca, and A. Lumsdaine, "Open MPI: A high-performance, heterogeneous mpi," in Proc. IEEE Cluster 2006, Sep. 2006.
[16]
T. Suzumura and H. Kanezashi, "Highly scalable X10-based agent simulation platform and its application to large-scale traffic simulation," in Proc. IEEE/ACM DS-RT 2012, Oct. 2012, pp. 243--250.
[17]
V. A. Saraswat, V. Sarkar, and C. von Praun, "X10: Concurrent programming for modern architectures," in Proc. PPoPP'07, Mar. 2007, p. 271.
[18]
T. Suzumura, S. Kato, T. Imamichi, and M. Takeuchi, "X10-based massive parallel large-scale traffic flow simulation," in Proc. X10'12 (in conj. with PLDI'12), Jun. 2012.
[19]
C. Xie, Z. Hao, and H. Chen, "X10-FT: Transparent fault tolerance for APGAS language and runtime," Parallel Computing, vol. 40, no. 2, pp. 136--156, Feb. 2014.
[20]
Y. Liu, Y. Ren, L. Liu, and Z. Li, "A Spark-based parallel simulation approach for repairable system," in Proc. RAMS 2016, Jan. 2016.
[21]
T. Yu, M. Dou, and M. Zhu, "A data parallel approach to modelling and simulation of large crowd," Cluster Computing, vol. 18, no. 3, pp. 1307--1316, Sep. 2015.
[22]
A. Radenski, "Using MapReduce Streaming for distributed life simulation on the cloud," in Proc. ECAL 2013, Sep. 2013.
[23]
G. Pratx and L. Xing, "Monte Carlo simulation of photon migration in a cloud computing environment with MapReduce," Journal of Biomedical Optics, vol. 16, no. 12, p. 125003, Dec. 2011.
[24]
M. Hanai and K. Shudo, "Optimistic parallel simulation of very large-scale peer-to-peer systems," in Proc. IEEE/ACM DS-RT 2014, Oct. 2014, pp. 35--42.
[25]
"Hadoop Wiki - PoweredBy," http://wiki.apache.org/hadoop/PoweredBy.
[26]
"NTT DATA: Operating Spark clusters at thousands-core scale and use cases for Telco and IoT," https://databricks.com/blog/2015/05/14/ntt-data-operating-spark-clusters-at-thousands-core-scale-and-use-cases-for-telco-and-iot.html.
[27]
B. Lubachevsky, "Bounded lag distributed discrete event simulation," Proc. SCS Multiconference on Distributed Simulation, vol. 19, no. 3, pp. 183--193, 1988.
[28]
M. Ripeanu, A. Iamnitchi, and I. Foster, "Mapping the Gnutella network," IEEE Internet Computing, vol. 6, no. 1, pp. 50--57, Jan. 2002.
[29]
A.-L. Barabasi and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509--512, 1999.
[30]
"Spark on Superdome X previews in-memory on The Machine," http://www.nextplatform.com/2016/04/11/spark-superdome-x-previews-memory-machine/.
[31]
K. Jünemann, P. Andelfinger, J. Dinger, and H. Hartenstein, "BitMON: A tool for automated monitoring of the BitTorrent DHT," in Proc. IEEE P2P'10, Aug. 2010.
[32]
"BitMon," https://dsn.tm.kit.edu/english/bitmon.php.
[33]
"Gartner says 6.4 billion connected "Things" will be in use in 2016, up 30 percent from 2015," Nov. 2015, http://www.gartner.com/newsroom/id/3165317.
[34]
L. G. Valiant, "A bridging model for parallel computation," Communications of the ACM, no. 8, pp. 103--111, Aug. 1990.
[35]
A. Gafni, "Rollback mechanisms for optimistic distributed simulation systems," Proc. SCS Multiconference on Distributed Simulation, vol. 19, no. 3, pp. 61--67, Jul. 1988.
[36]
M. Hanai and K. Shudo, "Simulation of large-scale distributed systems with a distributed graph processing system," Tech. Report of IEICE, vol. 112, no. 173, CPSY2012-27, pp. 109--114, Aug. 2012, (in Japanese, not peer-reviewed).
Recommendations
Parallel Discrete-Event Simulation (PDES): a case study in design, development, and performance using SPEEDES
Can parallel simulations efficiently exploit a network of workstations? Why haven't PDES models followed standard modeling methodologies? Will the field of PDES survive, and if so, in what form? Researchers in the PDES field have addressed these ...
Parallel Discrete-Event Simulation (PDES): a case study in design, development, and performance using SPEEDES
PADS '95: Proceedings of the ninth workshop on Parallel and distributed simulationCan parallel simulations efficiently exploit a network of workstations? Why haven't PDES models followed standard modeling methodologies? Will the field of PDES survive, and if so, in what form? Researchers in the PDES field have addressed these ...
Partitioning parallel discrete event simulation
CompSysTech '08: Proceedings of the 9th International Conference on Computer Systems and Technologies and Workshop for PhD Students in ComputingParallel Discrete Event Simulation (PDES) allows to speed up the execution of a simulation by distributing the simulation's workload between multiple processors. The mapping of the simulation entities over the processors is very important with regard to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2016
205 pages
ISBN:9781509035045
Sponsors
Publisher
IEEE Press
Publication History
Published: 21 September 2016
Check for updates
Author Tags
Qualifiers
- Tutorial
- Research
- Refereed limited
Conference
DS-RT '16: International Symposium on Distributed Simulation and Real-Time Applications
September 21 - 23, 2016
Uxbridge, United Kingdom
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 26Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)1
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in