cuPC: CUDA-Based Parallel PC Algorithm for Causal Structure Learning on GPU
cuPC: CUDA-Based Parallel PC Algorithm for Causal Structure Learning on GPU
复制标题
DOI：
10.1109/tpds.2019.2939126
复制
发表时间：
2018-12
影响因子：
5.3
通讯作者：
Behrooz Zarebavani;Foad Jafarinejad;Matin Hashemi;Saber Salehkaleybar
中科院分区：
文献类型：
--
作者：
Behrooz Zarebavani;Foad Jafarinejad;Matin Hashemi;Saber Salehkaleybar
经验科学许多领域的主要目标是从观察数据中发现一组变量之间的因果关系。 PC 算法是通过执行大量条件独立性测试来学习底层因果结构的有前途的解决方案之一。在本文中，我们提出了一种新颖的基于 GPU 的并行算法，称为 cuPC，用于执行与顺序无关的 PC 版本。所提出的解决方案有两个变体：cuPC-E 和 cuPC-S，它们以两种不同的方式并行化 PC 以实现多元正态分布。实验结果表明了所提出的算法在变量数量、样本数量和不同图密度方面的可扩展性。例如，在最具挑战性的数据集之一中，运行时间从 11 个小时以上减少到约 4 秒。平均而言，与 CPU 上的串行实现相比，cuPC-E 和 cuPC-S 分别实现了 500 倍和 1300 倍的加速。
The main goal in many fields in the empirical sciences is to discover causal relationships among a set of variables from observational data. PC algorithm is one of the promising solutions to learn underlying causal structure by performing a number of conditional independence tests. In this paper, we propose a novel GPU-based parallel algorithm, called cuPC, to execute an order-independent version of PC. The proposed solution has two variants, cuPC-E and cuPC-S, which parallelize PC in two different ways for multivariate normal distribution. Experimental results show the scalability of the proposed algorithms with respect to the number of variables, the number of samples, and different graph densities. For instance, in one of the most challenging datasets, the runtime is reduced from more than 11 hours to about 4 seconds. On average, cuPC-E and cuPC-S achieve 500X and 1300X speedup, respectively, compared to serial implementation on CPU.