IEEE/ACM DS‐RT 2016
September 2016

Parallel Discrete‐Event Simulation
on Data Processing Engines
Kazuyuki Shudo, Yuya Kato,
Takahiro Sugino, Masatoshi Hanai
Tokyo Institute of Technology

Tokyo Tech

Proposal:

Parallel simulator on
data processing engine• Development of a decent
parallel simulator is challenging work.
2005 ~– with BSD socket API, message passing or shared memory– 47.46 sec with PeerSim, but 1 hour 6 min with dPeerSim. 80x ~ slower.

• Data processing engines help it much.
– Performance

Moderate» Comparable with a serial simulator– Scalability~ Thousands of servers» Hadoop runs on 4500 servers and Spark runs on 4000 cores– Fault tolerance

Automatic reexecution
1 / 15

This work
• Parallel simulators on data processing engines
are demonstrated.
– Gnutella, a distributed system, is simulated on it.
– It shows good scalability and a moderate performance.

Architecture
Simulation targets
Simulator
Data processing
engineimplemented in this work

Implementation
Gnutella
P2P

PC cluster

Wireless network Traffic

Simulator

Simulator

HadoopSpark

MapReduce

Hadoop YARN…

Contribution
We demonstrate that• Parallel Discrete‐Event Simulation (PDES)
works on data processing engines.
– Cf. Existing work [20‐23] adopted time‐step‐based synchronization with
MapReduce processing model.

• Optimistic parallel simulation withTime Warp shows a moderate performance.
– The performance is about 20x of an existing parallel simulator.
It is comparable with a serial simulator while enabling large‐scale simulation.

• Distributed systems aremodeled on MapReduce processing model.
– Peer‐to‐peer systems (our target), wireless networks, ...

3 / 15

MapReduce
programming / processing model
Background:• Most data processing engines support it.
Shufflephase

Mapphase

WorkerReduce
phase
Iterated

Input

k0, v0k5, v1…

k0, v0k0, v…
k0, v…

OutputInput

k8, v…
k0, v…
…

k5, v1k5, v6k5, v…

OutputInput

k5, v6k3, v0…

k3, v0k3, v…
k8, v…

Output…

Key-value pairs

4 / 15Modeling of peer‐to‐peer systems
on MapReduce
WorkerShuffleReduce<node 0, …><node 0, node 0 info.><node 0, node 0 info.><node 1, message A><node 0, message B><node 1, …
<node 1, node 1 info.><node 1, node 1 info.><node 1, message A><node 0, message B>
Communication
Event processing
between nodes……
……

Message A• Communication‐intensive.
–Node 0……
……

Node 1
Message B

Different from,for example,
traffic simulation

Simulated system

5 / 15Modeling of wireless networks
on MapReduce

WorkerShuffle

Reduce<area 0-0, node 0 info.><area 0-0, node 0 …>

<area 0-0, message A><area 0-0, message A><area 0-0, node 0 …>

<area 0-1, message A><area 1-0, message A><area 1-1, message A><area 0-1, node 1 info.><area 0-1, node 1 …>
<area 0-1, message A>

Communication
between nodes<area 0-1, node 1 …>

Event processing

Area 0-1

Area 0-0

Radio range

Node 0…
…

• Note: Designed but

not implemented

Node 1
Area 0-1

Area 1-1

Simulated system

6 / 15

Details about design and impl.
• Models provide API to simulation targets.
– Gnutella uses peer‐to‐peer (message passing) API.

• Simulation scenarios and simulated environment
are also supplied.
– From Hadoop Distributed File System– E.g. Network topology, bandwidth, latency and jitter• Non‐optimistic and optimistic synchronization
protocols are implemented.
– Null Message algorithm [Chandy 1979] and Time Warp [Jefferson 1985]– Optimization techniques for Time Warp: Lazy cancellation,
Moving Time Window (MTW) and Adaptive Time Warp (ATW) 7 / 15

Evaluation and results
1. Comparison among data processing engines– Spark was faster than Hadoop MapReduce.

2. Scalability– Our simulators could simulate 10^8 nodes with 10 commodity
computers.

3. Optimistic parallel simulation– It worked.
– Lazy cancellation was always effective.
– Moving Time Window (MTW) and Adaptive Time Warp (ATW)
reduced memory consumption at the cost of execution time.

4. Performance evaluation– 20 times of dPeerSim (parallel) and 1/4 of PeerSim (serial)

8 / 15

Hadoop MapReduce v.s. Spark• 10 worker computers with32 GB of memory running
YARN’s NodeManager.
–

In all the experiments.

• Gnutella with a complex
network generated by
Barabasi‐Albert (BA) model (m = 1)–100 queries• Non‐optimisticsynchronization–Although the simulator
processes a large number ofevents because timings ofmessage reception are aligned.

• Spark is faster than Hadoop MapReduce.
– It eliminates various overheads of Hadoop MapReduce and utilizes memory well.

• Faster engines will show further better results. E.g. Spark4TM

9 / 15

Scalability• Gnutella with a complex network
generated by BA model (m = 2)–100 queries• Non‐optimistic synchronization• Our simulators could handle 10^8 nodes
with 10 commodity computers with 32 GB of memory.
– We just confirmed. It will not be the limit.
– dPeerSim could simulate 5.75 x 10^6 nodes on a single computer with 1.5 GB ofmemory and 84 x 10^6 nodes on 16 computers. Chord is simulated, not Gnutella.

• They can simulate– BitTorrent DHT, one of the largest distributed system (〜 10^7) on a singlecomputer– All the things connected to Internet (10^10 〜 in 2020 estimated by Gartner) with
10 / 151000 computers Optimistic parallel simulation• Our simulator can process very limited number of message‐
sending events in a MapReduce iteration
without an optimistic synchronization protocol. – At worst, a single message. Because …
– In MapReduce, communication between nodes is simulated by
shuffle phase. Because of it, in an iteration, each node sends
messages and then receives messages.
– A discrete‐event simulator processes only the earliest events.
Iteration

MapReduce
process

Map
phase

Simulation

Message Message
sending receiving…
…

Simulated nodeReduce
phase

Shuffle
phase

…
…

Map
phase

Time
Messageprocessing…
…

11 / 15

Optimistic parallel simulation• Time Warp [Jefferson 1985]– Each computer processes events speculatively.
– It rollbacks processed events if they should be cancelled.

Computers(logical processes (LPs))

…
…

…
…

1. Processes a (message‐sending) event speculatively

2. Notices a message‐receiving event
happened before the processed event
3. Rollbacks the processed event
EventTime• It requires memory / storage to save simulation states
and/or events after global virtual time (GVT) = commitment horizon.
– For rollbacks.

• We try MTW and ATW to control (reduce) memory consumption.
– It is important because Spark basically places data in memory.

12 / 15

Optimistic parallel simulation• It works.

• 2D mesh network with10^6 nodes–10000 queries during 100 sec• Optimistic synchronization–with lazy cancellation

With MTW• Moving Time Window (MTW) reduced # of messages inmemory at the cost of execution time.
– MTW limits speculative event processing.
– The best size of time window depends on a simulation target.

• Adaptive Time Window (ATW) also works as expected. See the paper.

Performance evaluation• # of events / second– Our Spark‐based simulator

1.41

10^4x 20

• Optimistic• 10 computers– dPeerSim (parallel)

7.39• Non‐optimistic ‐ Null message algorithm• 16 computers– PeerSim (serial)

10^2x 1/4
6.17

10^4

• This result is very preliminary.
–Simulation target Computers– Our work Gnutella 2.4 GHz Xeon
– (d)PeerSim Chord
3.0 GHz Xeon

22

10, Gigabit Ethernet (2010)
16, Gigabit Ethernet + Myrinet (~2004)
14 / 15

Summary• Parallel Discrete‐Event Simulation (PDES)
on data processing engines was demonstrated.
– On Hadoop MapReduce and Spark– Our Spark‐based simulator showed x20 performance of dPeerSimthanks to Time Warp, a optimistic synchronization protocol.
– Optimization techniques for Time Warp worked as expected• Lazy cancellation, MTW and ATW.

• Future work
– Scalability challenge with thousands of computers– Confirmation of fault‐tolerance features of data processing engines– Other simulation targets– Comprehensive evaluation:
Performance, comparison with non‐optimistic simulation, … 15 / 15