Transcript ppt

Interaction-Based HPC Modeling of
Social, Biological, and Economic
Contagions Over Large Networks
Jiangzhuo Chen
Joint work with Keith Bisset, Chris J. Kuhlman,
V.S. Anil Kumar, and Madhav Marathe
Winter Simulation Conference
December 13, 2011
Network Dynamics & Simulation Science Laboratory
Talk Outline
• Background
– Contagions and large networks
– Motivations for HPC ABMS
– Challenges for HPC ABMS methodology
• GDS (graphic dynamical system)
• Our HPC simulation tools for large-scale GDS’s :
–
–
–
–
InterSim
EpiSimdemics
EpiFast
Performance and examples
• Summarize
Network Dynamics & Simulation Science Laboratory
Contagions over Large Interaction Networks
• Contagions
– Spread of infectious disease in a population
– Spread of opinions, fads, rumors, trends, norms, social movements in a
population
– Packet diffusion, worm propagation in computer networks
– Spread of marketing information
• Large interaction networks
–
–
–
–
Millions of nodes, billions of edges
Unstructured
Heterogeneous individuals with behavior
Dynamic: co-evolving with contagion dynamics, individual behavior, and
public policy
• HPC agent-based modeling and simulation (ABMS): appropriate
methodology to study contagions over realistic large networks
– Analytical methods require unrealistic assumptions on network structure
– Macro-level methods do not capture heterogeneity
– Many problems in interest are computationally intractable
Network Dynamics & Simulation Science Laboratory
Challenges with HPC ABMS Tools
• Performance
– Scalability of running time and memory usage: e.g. epidemics in the
global population with 7 billion agents
– High communication cost for synchronizations
• Capability
– Representation of complicated contagion processes
– Representation of complex behavior & policy
– Representation of coupled multi-networks with multiple contagions
• Demand for short overall time-to-solution
– Large simulation configuration space: huge factorial design
– Randomness: many replicates
– Often require efficient (adaptive) experiment design
• Motivation for multiple tools in the performance-capability
spectrum: choose the right tool for the right problem
Network Dynamics & Simulation Science Laboratory
Graph Dynamical System (GDS)
• G(V=agents, E=interactions)
• B: set of state values; each node has a state
• F: set of local transition functions; each node vi has a
function fi in F
– Typical fi depends on history of states of vi and its neighbors
in G
• R: update scheme for local transition functions and
state updates
– E.g. synchronous scheme (SyDS): good for parallelization;
sequential scheme (SDS)
Output of GDS: sequence of configurations C(t)= state of
each node at time t
Network Dynamics & Simulation Science Laboratory
Extensions to The Basic GDS
• Probabilistic state transitions
• Multiple networks with multiple contagions (multiple sets
of local transition functions)
• State vector
• Asymmetric interactions
• Agents come and go
• Interventions
– Change node or edge properties
– Cannot be modeled by local transition functions
Network Dynamics & Simulation Science Laboratory
An Example of GDS
Infectious disease propagation in social contact network with SEIR model
• G: social contact network
S
E
I
R
• B: {Susceptible, Exposed, Infectious, Removed}
• F: transitions with between-host disease propagation and within-host
disease progression
– SE probabilistically if any neighbor is in I; independent disease
transmissions, prob. depends on properties of: infectious node, susceptible
node, and their interaction
– Probabilistic timed transition EIR
• R: synchronous update
school
home
Network Dynamics & Simulation Science Laboratory
Interventions in an epidemiological GDS
• Pharmaceutical interventions: vaccination or
antiviral changes an individual’s role in the
transmission chain
– Lower susceptibility or infectiousness
• Non-pharmaceutical interventions: social
distancing measures change people activities and
hence the social network
– Sick leave, school closure, isolation, etc.
Network Dynamics & Simulation Science Laboratory
Example of Interventions: Vaccination
school
home
Network Dynamics & Simulation Science Laboratory
Example of Interventions: No School
school
home
Network Dynamics & Simulation Science Laboratory
Example of Interventions: Work Closure
school
home
Network Dynamics & Simulation Science Laboratory
Talk Outline
• Background
– Contagions and large networks
– Motivations for HPC ABMS
– Challenges for HPC ABMS methodology
• GDS (graphic dynamical system)
• Our HPC simulation tools for large-scale GDS’s :
–
–
–
–
InterSim
EpiSimdemics
EpiFast
Performance and examples
• Summarize
Network Dynamics & Simulation Science Laboratory
InterSim, EpiSimdemics, EpiFast:
Overview
• Common properties:
– Agent based simulation of diffusion over networks (GDS)
– Synchronous state updates
– Implementation: C++/MPI parallel code; runs on any distributed memory
system
• Differences:
–
–
–
–
–
–
–
–
–
Scope of contagion modeling: InterSim > EpiSimdemics > EpiFast
Intervention modeling: EpiSimdemics > EpiFast > InterSim
Performance: EpiFast > EpiSimdemics > InterSim
Software extendibility: InterSim > EpiSimdemics > EpiFast
Network representation: InterSim ≈ EpiFast  EpiSimdemics
Preciseness of simulation: EpiSimdemics > (InterSim, EpiFast)
Parallel communication model: InterSim ≈ EpiSimdemics ≠ EpiFast
Communication cost: InterSim > EpiSimdemics > EpiFast
Memory requirement: InterSim > EpiSimdemics > EpiFast
Network Dynamics & Simulation Science Laboratory
Some Other Simulation Tools
•
Epidemiological agent based simulation frameworks:
–
–
–
•
Ferguson et al. 2003. Planning for smallpox outbreaks. Nature 425 (6959): 681–685.
Longini et al. 2005. Containing Pandemic Influenza at the Source. Science 309 (5737):
1083–1087.
Parker and Epstein 2011. A Distributed Platform for Global-Scale Agent-Based Models of
Disease Transmission. ACM Transactions on Modeling and Computer Simulation 22.
General purpose simulators:
–
–
–
–
–
–
Perumalla 2005. μsik: A Micro-Kernel for Parallel/Distributed Simulation Systems. In
Proceedings of the 19th PADS.
Hybinette et al. 2006. SASSY: A Design for Scalable Agent-Basd Simulation System Using a
Distributed Discrete Event Infrastructure. In Proceedings of the 2006 WSC.
North and Macal 2009. Foundations of and Recent Advances in Artificial Life Modeling
with Repast 3 and Repast Simphony. In Artificial Life Models in Software, 37–60.
Springer.
Perumalla and Seal 2011. Discrete Event Modeling and Massively Parallel Execution of
Epidemic Outbreak Phenomena. SIMULATION, to appear.
D’Souza et al. 2007. SugarScape on Steroids: Simulating over a Million Agents at
Interactive Rates. In Proceedings of Agent2007 Conference.
Aaby et al. 2010. Efficient Simulation of Agent-Based Models on Multi-GPU and Multi-Core
Clusters. In Proceedings of SIMUTools ’10.
Network Dynamics & Simulation Science Laboratory
Scopes of NDSSL Tools
GDS
InterSim
EpiSimdemics
EpiFast
Intervention
Network Dynamics & Simulation Science Laboratory
InterSim: Interaction Simulation
More details about InterSim were presented: Monday (Dec.
12th)
A General Purpose Graph Dynamical System Modeling Framework
(InterSim)
Chris J. Kuhlman, V.S. Anil Kumar, Madhav Marathe, Henning Mortveit,
S.S. Ravi, Daniel J. Rosenkrantz, Samarth Swarup, Gaurav Tuli
Network Dynamics & Simulation Science Laboratory
InterSim
• Modeling of diffusion dynamics
– Most general, can be used for any GDS
– Open software framework which can be easily extended
with user supplied node interaction models (NIM’s)
– Already implemented: SEIR model, different threshold
models, generalized cellular automata, computer network
communication algorithms
• Software implementation
–
–
–
–
C++/MPI implementation
Agent-to-agent interaction graph as input
Symmetric computation model
Communications between each pair of PE’s
Network Dynamics & Simulation Science Laboratory
InterSim
• Performance
– High versatility (general local transition functions)
– Fast turn-around time: time from problem
specification to simulation results
• NIM can be implemented and verified within hours
– Large memory usage: a NIM instance for each agent
– Large communication cost
• Limitations
– Very limited interventions based on local data
– Difficult to scale to very large scale networks (e.g. NYC
contact network)
Network Dynamics & Simulation Science Laboratory
EpiSimdemics
• Modeling of diffusion dynamics
–
–
–
–
Discrete event & discrete time simulation
second-by-second details
Ordered interactions among agents
Local state transition functions: probabilistic timed transition systems
• highly configurable disease model
– Diffusion through co-location of agents
• Software implementation
– C++/MPI implementation
– Agent-location graph as input
• agent-agent interactions are computed on-the-fly
– Symmetric computation model; communications between each pair
of PE’s
– Very sophisticated interventions
• Change infectivity/vulnerability of agents
• Change agents’ activity schedules (hence interactions)
Network Dynamics & Simulation Science Laboratory
Disease Model in EpiSimdemics: An
Example
Network Dynamics & Simulation Science Laboratory
EpiSimdemics Algorithm
Generate the population
Set initial infections
Based on activities move
the people to the locations
Compute interactions
among the people at the
locations
Some exposed people
may become infected
After their activities, the
people are moved back
to their home PE
Update state of person at
his home PE
Network Dynamics & Simulation Science Laboratory
EpiSimdemics
• Performance
– Scalable to very large networks (106~109 agents)
– Simulation running time: magnitude of minutes for large urban
populations
• Limitations
–
–
–
–
Interactions occur only through co-location
Local transition functions must be PTTS
System synchronization at every time step (every simulation day)
Interventions are based on either local or global information, not
neighborhood information
– There must exist a minimum latent period
• Between agent’s state transition and that the transition can affect other
agents
Christopher Barrett, Keith Bisset, Stephen Eubank, Xizhou Feng, Madhav Marathe.
EpiSimdemics: an efficient and scalable framework for simulating the spread of infectious
disease on large social networks. In Proceedings of ACM/IEEE conference on
SuperComputing (SC'08), 2008.
Network Dynamics & Simulation Science Laboratory
EpiFast: Fast Epidemic Simulation
• Modeling of diffusion dynamics
– Discrete time simulation
– Local state transition function: SEIR (a simple PTTS)
– Diffusion through agent-agent contacts: independent transmissions
• Software implementation
– Highly portable C++/MPI implementation
– Master-workers model
• One master PE: communication & coordination
• Many worker PE: diffusion computation
• Each agent is assigned to single worker PE
– Communications between master PE and each worker PE
– Predefined adaptive/conditional interventions
• Pharmaceutical or non-pharmaceutical: change properties of existing nodes
and edges in network
• On day <t> or when a given threshold <x> is met, apply intervention <i> on
subpopulation <s>
– Extremely fast and scalable
Network Dynamics & Simulation Science Laboratory
EpiFast
•
Performance
–
–
–
–
•
Among the fastest epidemic simulations that can handle realistic synthetic populations
and provide comparable support for realistic intervention measures.
Network of 16 million nodes and 900 million edges: <20 minutes per replicate on as few
as 32 processors
Scales well on distributed memory systems
Good strong and weak scaling properties
Limitations
–
–
–
–
–
SEIR only
Network edges (contacts) are not ordered by time
Network remains the same from day to day unless with interventions
Synchronizes every simulation day
Interventions directly change existing edges in contact network; changes are
approximate
Keith Bisset, Jiangzhuo Chen, Xizhou Feng, V. S. Anil Kumar, and Madhav Marathe.
EpiFast: A Fast Algorithm for Large Scale Realistic Epidemic Simulations on Distributed
Memory Systems. In Proceedings of the 23rd International Conference on Supercomputing
(ICS), 2009.
Network Dynamics & Simulation Science Laboratory
Strong Scaling of EpiFast
Relative Speedup with Increasing Number of Processors
(50% infected, no intervention, total running time)
2.8
1.8
Miami
2.4
DC
1.6
2
1.4
1.6
1.2
1.2
1
0
1.2
1.16
1.12
1.08
1.04
1
8
16
24
Chicago
16
24
32
40
8
16
24
32
40
1.25
NYC
1.2
1.15
1.1
1.05
1
32 40 48 56 64 72 80
Network Dynamics & Simulation Science Laboratory
Performance Comparison
Execution time (in seconds) for one diffusion instance
Region
Agents
(million)
Contacts
(billion)
InterSim
EpiSimdemics
EpiFast
PE
Time
PE
Time
PE
Time
Miami
2.09
0.1
80
131
8
875
8
18
DC
3.75
0.2
80
248
16
812
16
23
Chicago
9.04
0.5
160
636
40
852
40
44
NYC
17.88
0.9
NA
NA
72
122
4
72
82
Network Dynamics & Simulation Science Laboratory
Network Dynamics & Simulation Science Laboratory
Example: Epidemic Curves from Simulations
Network Dynamics & Simulation Science Laboratory
Summary
• Study of contagions over large realistic
interaction networks needs high performance
computing and agent based modeling and
simulation methodology
• Various HPC ABMS tools complement each other
w.r.t. range of applicability and performance: no
single tool can satisfy all simulation needs;
choose the right tool
Network Dynamics & Simulation Science Laboratory
To Be Continued…
Wednesday (Dec. 14th) 10:30-12:00
Efficient Implementation of Complex Interventions in Large Scale Epidemic
Simulations (Indemics)
Yifei Ma, Keith Bisset, Jiangzhuo Chen, Suruchi Deodhar, Madhav Marathe
InterSim
DBMS
EpiSimdemics
Indemics
EpiFast
interventions
user
Network Dynamics & Simulation Science Laboratory