PREEMPT: Scalable Epidemic Interventions Using Submodular Optimization on Multi-GPU Systems
PREEMPT: Scalable Epidemic Interventions Using Submodular Optimization on Multi-GPU Systems
复制标题
DOI：
10.1109/sc41405.2020.00059
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Marco Minutoli;Prathyush Sambaturu;M. Halappanavar;Antonino Tumeo;A. Kalyanaraman;A. Vullikanti
中科院分区：
文献类型：
--
作者：
Marco Minutoli;Prathyush Sambaturu;M. Halappanavar;Antonino Tumeo;A. Kalyanaraman;A. Vullikanti
预防和减缓流行病的传播是通过疫苗接种和社交距离等技术来实现的。鉴于疫苗数量和管理成本的实际限制，优化成为必要。先前使用数学规划方法的方法已被证明是有效的，但受到计算成本的限制。在这项工作中，我们提出了 PREEMPT，这是一种通过最大化接种疫苗的节点对网络的影响来进行干预的新方法。我们证明了与我们方法的目标函数相关的子模属性，以便它有助于构建有效的贪婪逼近策略。因此，我们提出了一种新的基于贪婪爬山的 PREEMPT 并行算法，并提出了分布式 CPU-GPU 异构平台的高效并行实现。我们的结果表明，PREEMPT 能够显着降低（高达 6.75 倍）感染人数百分比，并将城市规模网络的感染高峰降低高达 98%。我们还在 Summit 超级计算机的多达 128 个节点上展示了 PREEMPT 的强大扩展结果。我们的并行实施能够显着缩短解决问题的时间，在大型网络上从几小时缩短到几分钟。这项工作代表了并行贪婪爬山并将其应用于设计流行病有效干预措施的首次尝试。
Preventing and slowing the spread of epidemics is achieved through techniques such as vaccination and social distancing. Given practical limitations on the number of vaccines and cost of administration, optimization becomes a necessity. Previous approaches using mathematical programming methods have shown to be effective but are limited by computational costs. In this work, we present PREEMPT, a new approach for intervention via maximizing the influence of vaccinated nodes on the network. We prove submodular properties associated with the objective function of our method so that it aids in construction of an efficient greedy approximation strategy. Consequently, we present a new parallel algorithm based on greedy hill climbing for PREEMPT, and present an efficient parallel implementation for distributed CPU-GPU heterogeneous platforms. Our results demonstrate that PREEMPT is able to achieve a significant reduction (up to 6.75×) in the percentage of people infected and up to 98% reduction in the peak of the infection on a city-scale network. We also show strong scaling results of PREEMPT on up to 128 nodes of the Summit supercomputer. Our parallel implementation is able to significantly reduce time to solution, from hours to minutes on large networks. This work represents a first-of-its-kind effort in parallelizing greedy hill climbing and applying it toward devising effective interventions for epidemics.