Rumor Has It: Optimizing the Belief Propagation Algorithm for Parallel Processing
Rumor Has It: Optimizing the Belief Propagation Algorithm for Parallel Processing
复制标题
有传言：优化并行处理的置信传播算法
DOI：
10.1145/3409390.3409401
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Huang, H. Howie
中科院分区：
文献类型：
--
作者：
Trotter, Michael;Wood, Timothy;Huang, H. Howie
通过对个人状态的概率分布如何随着新信息流经网络而演变进行建模，信念传播具有广泛的适用性，从图像校正到病毒传播，甚至社交网络。然而，其很少的实现主要局限于小型贝叶斯网络领域。因此不幸的是，该算法在大规模图上的应用是遥不可及的。为了促进其广泛接受，我们利用 GPU 处理为小型和大规模图启用置信传播。因此，我们探索了一系列优化，包括一种新的简单但可扩展的输入格式，使信念传播能够大规模运行，以及重要的工作负载处理更新和细致的内存管理，使我们的实现在单台机器上的原始执行时间和输入大小方面优于先前的工作。利用一套针对不同图形集的并行化技术和技巧，我们证明了我们的实现甚至可以有效地处理大规模网络，与我们的控制但优化的单线程实现相比，实现了近 121 倍的加速，同时支持大小超过一千万个节点的图形，而之前的工作使用基于 CPU 的多核和主机解决方案支持数千个节点。为了帮助选择给定图的最佳实现，我们提供了一种有前途的方法，利用随机森林分类器和图元数据，从我们的初始基准测试来看，该方法的 F1 分数接近 95%，并且可移植到不同的 GPU 架构，以实现超过 72% 的准确率的 F1 分数，与我们在这个新环境中运行的控制相比，加速了近 183 倍。
By modelling how the probability distributions of individuals’ states evolve as new information flows through a network, belief propagation has broad applicability ranging from image correction to virus propagation to even social networks. Yet, its scant implementations confine themselves largely to the realm of small Bayesian networks. Applications of the algorithm to graphs of large scale are thus unfortunately out of reach.To promote its broad acceptance, we enable belief propagation for both small and large scale graphs utilizing GPU processing. We therefore explore a host of optimizations including a new simple yet extensible input format enabling belief propagation to operate at massive scale, along with significant workload processing updates and meticulous memory management to enable our implementation to outperform prior works in terms of raw execution time and input size on a single machine. Utilizing a suite of parallelization technologies and techniques against a diverse set of graphs, we demonstrate that our implementations can efficiently process even massive networks, achieving up to nearly 121x speedups versus our control yet optimized single threaded implementations while supporting graphs of over ten million nodes in size in contrast to previous works’ support for thousands of nodes using CPU-based multi-core and host solutions. To assist in choosing the optimal implementation for a given graph, we provide a promising method utilizing a random forest classifier and graph metadata with a nearly 95% F1-score from our initial benchmarking and is portable to different GPU architectures to achieve over an F1-score of over 72% accuracy and a speedup of nearly 183x versus our control running in this new environment.
登录
查看更多内容
并行飞溅置信传播
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
Joseph Gonzalez;Yucheng Low;Carlos Guestrin
通讯作者：
Carlos Guestrin
DOI：
10.1136/ebmh.11.4.102
发表时间：
2008-10
期刊：
Evidence Based Mental Health
影响因子：
--
作者：
P. Cochat;L. Vaucoret;J. Sarles
通讯作者：
P. Cochat;L. Vaucoret;J. Sarles
使用 GPGPU 优化连接树中置信传播的内存管理
DOI：
--
发表时间：
2014
期刊：
International Conference on Parallel and Distributed Systems
影响因子：
--
作者：
Filippo Bistaffa;A. Farinelli;N. Bombieri
通讯作者：
N. Bombieri
DOI：
--
发表时间：
2011
期刊：
IEEE International Conference on Data Engineering
影响因子：
--
作者：
U. Kang;Duen Horng Chau;C. Faloutsos
通讯作者：
C. Faloutsos