Parallel Computation for n-ary Cartesian Product on Modern Microprocessors
Hu Chen, Fei Teng, Yu Wang · 2019
As an efficient method of representing huge sets, n-ary Cartesian product is widely used in many applications nowadays. In such applications, each element in the set of Cartesian product needs to be generated and evaluated. Therefore, the performance of generating all elements in the set of Cartesian product becomes a key factor. In this paper, we propose a SIMD-friendly algorithm to accelerate the computation of n-ary Cartesian product on CPUs. Based on it, we further introduce a CPU-GPU collaborative method for n-ary Cartesian product on GPU. In addition, we discuss the software architecture and dynamic schedule algorithm for multiple GPUs in one server. Experiments show that our approaches for n-ary Cartesian product can achieve a throughput of 113M per second on a single Corei7 core and almost 80G per second on a server with eight GTX 1080 GPUs. These high-performance implementations can meet the requirements of many applications.