We present a computational modeling framework for data-driven simulations and analysis of infectious disease spread in large populations. For the purpose of efficient simulations, we devise a parallel solution algorithm targeting multi-socket shared-memory architectures. The model integrates infectious dynamics as continuous-time Markov chains and available data such as animal movements or aging are incorporated as externally defined events. To bring out parallelism and accelerate the computations, we decompose the spatial domain and optimize cross-boundary communication using dependency-aware task scheduling. Using registered livestock data at a high spatiotemporal resolution, we demonstrate that our approach not only is resilient to varying model configurations but also scales on all physical cores at realistic workloads. Finally, we show that these very features enable the solution of inverse problems on national scales.
AndreevKRäckeH (2004) Balanced graph partitioning. In: Proceedings of the 16th ACM SPAA, SPAA ‘04. New York, NY, USA, 27–30 June 2004, pp. 120–124. New York: ACM.
2.
Anonymous (2000) Regulation (EC) No 1760/2000 of the European Parliament and of the Council of 17 July 2000 establishing a system for the identification and registration of bovine animals and regarding the labelling of beef and beef products. Official Journal of the European Union L204: 1–10.
3.
Anonymous (2004) Commission Regulation (EC) No 911/2004 of 29 April 2004 implementing Regulation (EC) No 1760/2000 of the European Parliament and of the Council as regards eartags, passports and holding registers. Official Journal of the European Union L163: 65–70.
4.
AugonnetCThibaultSNamystR. (2011) StarPU: a unified platform for task scheduling on heterogeneous multicore architectures. Concurrency and Computation Practice and Experience23(2): 187–198.
5.
BarrettCBissetKEubankS. (2008) EpiSimdemics: an efficient algorithm for simulating the spread of infectious disease over large realistic social networks. In: Proceedings of Supercomputing 2008, Austin, TX, 15–21 November 2008, pp. 1–12. Piscatway, NJ: IEEE.
6.
BerryLAElwasifWReynolds-BarredoJM. (2012) Event-based parareal: a data-flow based implementation of parareal. Journal of Computational Physics231(17): 5945–5954.
BüttnerKKrieterJTraulsenA. (2016) Epidemic spreading in an animal trade network - comparison of distance-based and network-based control measures. Transboundary and Emerging Diseases63: e122–e134.
9.
CarothersCDPerumallaKSFujimotoRM (1999) Efficient optimistic parallel simulations using reverse computation. ACM Transactions on Modeling and Computer Simulation9(3): 224–253.
10.
CassandrasCGLafortuneS (2008) Systems and models. In: Introduction to Discrete Event Systems. Boston, MA: Springer, pp. 1–51.
11.
CrayWCMoonHW (1995) Experimental infection of calves and adult cattle with Escherichia coli O157: H7. Applied and Environmental Microbiology61(4): 1586–1590.
12.
DavisMARiceDHShengH. (2006) Comparison of cultures from rectoanal-junction mucosal swabs and feces for detection of Escherichia coli O157 in dairy heifers. Applied and Environmental Microbiology72(5): 3766–3770.
13.
DrawertBEngblomSHellanderA (2012) URDME: a modular framework for stochastic simulation of reaction-transport processes in complex geometries. BMCSystems Biology6(1): 76.
14.
DrozdowskiM (2009) Parallel tasks. In: SammesAJ (ed.) Scheduling for Parallel Processing (Computer Communications and Networks). London: Springer, pp. 87–208.
15.
DuranAAyguadéEBadiaRM. (2011) OmpSs: a proposal for programming heterogeneous multi-core architectures. Parallel Processing Letters21(02): 173–193.
16.
EngblomS (2015) Strong convergence for split-step methods in stochastic jump kinetics. SIAM Journal on Numerical Analysis53(6): 2655–2676.
17.
EngblomSFermLHellanderA. (2009) Simulation of stochastic reaction-diffusion processes on unstructured meshes. SIAM Journal on Scientific Computing31(3): 1774–1797.
18.
FujimotoRM (1990) Parallel discrete event simulation. Communications of the ACM33(10): 30–53.
19.
FujimotoRM (1999) Parallel and Distribution Simulation Systems. 1st ed.New York: John Wiley & Sons, Inc.
20.
GerasoulisAYangT (1993) On the granularity and clustering of directed acyclic task graphs. IEEE Transactions on Parallel and Distributed Systems4(6): 686–701.
21.
GibsonMABruckJ (2000) Efficient exact stochastic simulation of chemical systems with many species and many channels. Journal of Physical Chemistry A104(9): 1876–1889.
22.
GillespieDT (1977) Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry81(25): 2340–2361.
23.
GreenwoodPEGordilloLF (2009) Stochastic epidemic modeling. In: ChowellGHymanJMBettencourtLMA. (eds) Mathematical and Statistical Estimation Approaches in Epidemiology. Amsterdam, Netherlands: Springer, pp. 31–52.
24.
HaidarATomovSDongarraJ. (2014) A novel hybrid CPU-GPU generalized eigensolver for electronic structure calculations based on fine-grained memory aware tasks. International Journal of High Performance Computing Applications28(2): 196–209.
25.
HancockDBesserTLejeuneJ. (2001) The control of VTEC in the animal reservoir. International Journal of Food Microbiology66(1-2): 71–78.
26.
HarveyNReevesASchoenbaumMA. (2007) The North American animal disease spread model: a simulation model to assist decision making in evaluating animal disease incursions. Preventive Veterinary Medicine82(3–4): 176–197.
27.
HasonovaLPavlikI (2006) Economic impact of paratuberculosis in dairy cattle herds: a review. Veterinarni Medicina-Czech51(5): 193–211.
28.
HeidelbergerPNicolD (1993) Conservative parallel simulation of continuous time Markov chains using uniformization. IEEETransactions on Parallel and Distributed Systems4(8): 906–921.
29.
HookeRJeevesTA (1961) Direct search: solution of numerical and statistical problems. Journal of the ACM8(2): 212–229.
30.
JeffersonDR (1985) Virtual time. ACM Transactions on Programming Languages and Systems7(3): 404–425.
KarmaliMASteeleBTPetricM. (1983b) Sporadic cases of haemolytic-uraemic syndrome associated with faecal cytotoxin and cytotoxin-producing escherichia coli in stools. Lancet1(8325): 619–620.
33.
KeelingMJ (2005) Models of foot-and-mouth disease. Proceedings of the Royal Society B272(1569): 1195–1202.
34.
KermackWOMcKendrickAG (1927) A contribution to the mathematical theory of epidemics. Proceedings of the Royal Society A115: 700–721.
35.
KieferJ (1953) Sequential minimax search for a maximum. Proceedings of the American Mathematical Society4(3): 502–506.
36.
Knight-JonesTJDRushtonJ (2013) The economic impacts of foot and mouth disease – what are they, how big are they and where do they occur?Preventive Veterinary Medicine112(3-4): 161–173.
37.
LeijenDSchulteWBurckhardtS (2009) The design of a task parallel library. In: Proceedings of the 24th ACM SIGPLAN Conference on object oriented programming systems languages and applications, OOPSLA. New York, NY, USA, pp. 227–242. New York: ACM.
38.
MasudaNHolmeP (2013) Predicting and controlling infectious disease epidemics using temporal networks. F1000Prime Reports5: 6.
39.
MengQBerzinsM (2014) Scalable large-scale fluid–structure interaction solvers in the uintah framework via hybrid task-based parallelism algorithms. Concurrency and Computation Practice and Experience26(7): 1388–1407.
40.
NicolDLiuJ (2002) Composite synchronization in parallel discrete-event simulation. IEEE Transactions on Parallel and Distributed Systems13(5): 433–446.
41.
OpenMP Architecture Review Board (2013) OpenMP 4.0 Application Program Interface, p. 117, Lines 14–15.
42.
PellisLBallFBansalS. (2015) Eight challenges for network epidemic models. Epidemics10: 58–62.
43.
PerezJBadiaRLabartaJ (2008) A dependency-aware task-based programming environment for multi-core architectures. In: 2008 IEEE International Conference on Cluster Computing, Tsukuba, 29 September–1 October 2008, pp. 142–151. IEEE.
44.
RileyLWRemisRSHelgersonSD. (1983) Hemorrhagic colitis associated with a rare Escherichia coli serotype. New England Journal of Medicine308(12): 681–685.
45.
ShirleyMDRushtonSP (2005) The impacts of network topology on disease spread. Ecological Complexity2(3): 287–299.
46.
StevensonMASansonRLSternMW. (2013) InterSpread plus: a spatial and stochastic simulation model of disease in animal populations. Preventive Veterinary Medicine109(1–2): 10–24.
47.
SubhlokJStichnothJMO’HallaronDR. (1993) Exploiting task and data parallelism on a multicomputer. In: Proceedings of the 4th PPOPP, New York, NY, USA: ACM, pp. 13–22.
48.
TilleniusM (2015) SuperGlue: a shared memory framework using data version-ing for dependency-aware task-based parallelization. SIAM Journal on Scientific Computing37(6): C617–C642.
49.
WidgrenSEngblomSBauerP. (2016) Data-driven network modeling of VTEC O157 transmission in Swedish cattle using complete population movement data. Under revision.
50.
WillebergPGrubbeTWeberS. (2011) The world organisation for animal health and epidemiological modelling: background and objectives. Revue Scientifique et Technique30(2): 391–405.
51.
XiaoZUngerBSimmondsR. (1999) Scheduling critical channels in conservative parallel discrete event simulation. In: Proceedings of the 13th Workshop of PADS, Atlanta, GA, 1–4 May, 1999, pp. 20–28. Washington, DC: IEEE.
52.
YeomJSBhateleABissetK. (2014) Overcoming the scalability challenges of epidemic simulations on Blue Waters. In: Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium, Phoenix, AZ, pp. 755–764.
53.
ZafariATilleniusMLarssonE (2012) Programming models based on data versioning for dependency-aware task-based parallelisation. In: Proceedings of the 15th International Conference on Computational Science and Engineering, Nicosia, Cyprus, 5–7 December 2012, pp. 275–280. Los Alamitos: IEEE Computer Society.
