基于多核CPU的快速贝叶斯网络推理方法

425→POSTER：贝叶斯网络上的快速并行精确推理Jiantong Jiang< $，Zeyi Wen Xiang，§，Atif Mansoor< $，Ajmal Mian<$西澳大利亚大学University of Western香港科技大学（广州）;香港科技大学jiantong. research.uwa.edu.au，wenzeyi@ust.hk，{atif.mansoor，ajmal.mian}@uwa.edu.au摘要贝叶斯网络（BN）很有吸引力，因为它们是图形化和可解释的机器学习模型。然而，对BN的精确推理是耗时的，特别是对于复杂的问题。为了提高推理效率，本文提出了一种基于多核CPU的快速BN精确推理方案Fast-BNIFast-BNI通过紧密集成粗粒度并行和细粒度并行的混合并行来提高精确推理的效率我们还提出了进一步简化BN精确推理瓶颈操作的 Fast-BNI源代码可在www.example.com上免费获得https://github.com/jjiantong/FastBN。CCS概念：·计算方法并行算法;机器学习算法。关键词：贝叶斯网络，推理，连接树1引言贝叶斯网络（BN）是一种概率图模型。BN使用有向无环图（DAG），通常从数据中学习[2]，以表示随机变量及其条件依赖关系。BN上的精确推理是计算某些查询变量的条件概率的基本任务，给定其他变量的一些值称为BN的知识。联合树（JT）是最重要的BN精确推理算法之一。关键思想是首先将BN转换为称为连接树的二级结构，其中树中的每个节点（称为团）和边（称为分隔符）包含变量的子集，并维护变量的潜在表。然后，它传递消息（即，对变量函数），并更新所有可能的表。然而，BN上的精确推理被证明是NP难的。JT的复杂性随着集团的出现而急剧增加允许制作部分或全部本作品的数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用。本作品的第三方组件的版权必须得到尊重。对于所有其他用途，请联系所有者/作者。PPoPP©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577476尺寸（即，集团的潜在表大小），这阻碍了BN在复杂问题中的使用在多核CPU上加速JT的方法主要有两第一种类型使用粗粒度的集团间并行性，它并行化不同集团的消息传递[3]。然而，团间并行是负载不平衡的，因为各种团的工作负载是高度不同的。这一类中的一些方法利用指针跳转技术，但是引入了由reroot或合并操作引起的额外开销。第二种类型的方法是细粒度的团内并行性，其并行化每个团内的潜在表操作[4]。Zheng [5]使用类似的想法在GPU上加速JT然而，由于频繁地调用表操作，这种类型的方法具有来自大的并行化开销的效率问题此外，团间并行对于具有少量团的树表现出有限的性能，并且团内并行对于具有许多小团的树具有效率问题。因此，两者只能在某些连接树结构下更有效。2我们的Fast-BNI设计为了解决效率问题，直接使用只有集团间或集团内的并行性，我们提出了快速BNI，一个快速和并行BN精确推理解决方案与混合集团间和集团内并行。对于集团间的并行性，我们首先开发了一种基于广度优先搜索的遍历方法，以利用并行化的机会，在树结构。我们的遍历方法将所有的集团和分隔符视为树的节点，并标记它们各自所在的层其次，我们采用根选择策略来构造一个更平衡的树，以最少的层数来减少并行化调用的总次数。对于团内并行性，我们识别并并行化了三种主要的潜在表操作，包括潜在表边缘化、扩展和缩减。潜在表操作的关键步骤是找到原始表和更新表之间的索引映射。因此，这些操作的复杂性取决于潜在的表大小，其随着团（或分隔符）中的随机变量的数量而显著增加，426PPoPPJiang等人表1. Fast-BNI与其他实现的比较，以及Fast-BNI相对于每个比较实现的加速。BN顺序实现并行实现执行时间（秒）加速比执行时间（秒）加速比UnBBayes Fast-BNI-seq UnBBayesDir.小樱Elem Fast-BNI-par Dir.小樱Elem冰雹探测器28.34.07.13.03.24.02.51.21.31.6探路者319.268.94.640.523.627.811.13.62.12.5糖尿病90961694413.1301623113316558.65.44.15.9猪43714372911.7335310682380221.715.14.810.7木宁2305426431.21951934.71638241.78.13.96.8穆宁4258194341987.620364103482139830216.73.47.1变量的状态数我们开发了相应的内部团原语，并行化不同的潜在表条目的索引映射计算我们发现了仅使用两种并行粒度中的一种粒度来加速JT算法的一些缺点，如线程间的负载不平衡、高并行开销和依赖于结构的并行性能。为了弥补这些缺点，Fast-BNI利用了一种混合parallelism，该混合parallelism通过扁平化嵌套操作来紧密集成集团间和集团内parallelism。 在每一层的开始，对应于该层的所有潜在表条目被打包以构成并行任务之一。然后将任务分配给并行线程以并发地执行。总而言之，所提出的并行性具有三个主要优点，包括（i）工作负载平衡，(ii)较小的并行化开销和（iii）适应性，各种结构。3评价我们在一台Linux机器上进行了实验，这台机器配备了两个26核2GHz Intel Xeon Platinum 8167M CPU和768GB主内存。我们的算法在六个不同大小的真实世界BN1上进行了测试，其中最后四个被认为是大规模BN。我们从每个网络中随机生成了2,000个测试用例，每个测试用例都有20%的观察变量。表1显示了Fast-BNI的顺序和并行实现与现有实现的执行时间比较具体来说，我们比较了Fast-BNI的顺序版本（即，Fast-BNI-seq）与UnBBayes库2 [1]中的JT实现;我们还比较了Fast-BNI并行版本（即，Fast-BNI-par）与并行实现[3- 5 ]。实现[3]（由Direct，Dir. ）使用直接粗粒度并行;实现[4]（由Primitive，Prim. ）为JT提出了四个细粒度的节点级原语;实现[5]（由Element，Elem. ）利用细粒度的逐元素并行性。为了比较并行实现，我们将OpenMP线程的数量���从1变化到32，选择执行时间最短的一个1https：bnlearn.com/bnr电子邮件地址和/2UnBBayes： https://sourceforge.net/projects/unbbayes/。从表1的“加速”列可以看出，Fast-BNI的顺序实现可以比UnBBayes快1.2到13.1倍。 当比较并行实现时，Fast-BNI-par的运行速度比同行快1.2到15.2倍。 值得注意的是，Fast-BNI比大型网络上的现有实现更具优势。 对于一些小规模网络，Fast-BNI相对于其他并行实现的加速相对较小，因为它们需要较短的贝叶斯推理执行时间（例如，对于Hailfinder小于4秒），并且小规模网络的并行化开销占很大比例。另一个观察结果是，Fast-BNI总是在=32时达到最短的执行时间���。Munin4是一个非常大的BN，有超过1,000个节点和边。Munin4的实验是完成时间最长的任务。这个任务使用UnBBayes运行了近三天，使用现有的并行实现花费了3到6个小时，而使用拟议的Fast-BNI，执行时间显着减少到不到一个小时。致谢Ajmal Mian教授是澳大利亚政府资助的澳大利亚研究委员会未来奖学金奖（项目编号FT 210100268）的获得者。文泽毅为通讯作者。引用[1] 隆美尔·卡瓦略、KB·拉斯基、保罗·科斯塔、马塞洛·拉代拉、莱西奥·桑托斯和松本寿。2010年。UnBBayes：语义网中合理推理的不确定性建模 Semantic Web（2010），953- 978.[2] Jiantong Jiang，Zeyi Wen，and Ajmal Mian.2022年快速并行贝叶斯网络结构学习。国际并行与分布式处理研讨会（IPDPS）IEEE，617[3] 亚历山大·V·科兹洛夫和贾斯温德·辛格。一九九四年概率推理的并行Lauritzen-Spiegelhalter算法。1994年IEEE，320-329.[4] Yinglong Xia和Viktor K.Prasanna 2007年并行精确推理的节点级原语。SBAC-PAD（2007年），第221[5] 路征。2013年。基于GPU的并行联合树算法。博士D. 论文。卡内基梅隆大学。