cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on
  GPU
  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 500 X and 1300 X speedup, respectively,
compared to serial implementation on CPU. The source code of cuPC is available
online [1].
