Efficient SIMD and MIMD parallelization of hash-based aggregation by conflict mitigation
Peng Ming Jiang, Gagan Agrawal · 2017
As the rate of data generation is growing exponentially each year, data aggregation has become one of the most common and expensive operations for data analysis. Previous efforts to accelerate data aggregation have been mainly focused on multi-core CPUs, improving single-core cache performance and/or reducing multi-core data synchronization overheads. In this paper, we aim at utilizing both SIMD and MIMD of a modern processor with a more recent (and wide lane) SIMD instruction set. We find that a straightforward method for vectorization of hash table often cannot deliver good performance, because wider SIMD vector increases data conflicts among the lanes (especially with skewed data). To address this problem, we design a variant of basic bucket hashing and a bucketized aggregation procedure that can utilize both SIMD and MIMD parallelism efficiently. Our approach first adds distinct offsets to input rows on different SIMD lanes, which reduces the possibility of different lanes accessing identical slot in the hash table. An efficient bucketized aggregation procedure is invoked to save space when the hash table is saturated, or to calculate the final results after all input rows have been inserted into the hash table. For parallelization across cores, we adopt separate hash tables and optimize with parallel reduction and a hybrid approach. We evaluate our methods with input datasets of different distributions. On a single core of Intel Xeon Phi, we obtain 1.6x to 2.9x speedup (over serial code) using our SIMD approach, and outperform a straightforward SIMD implementation by up to 7x. Over multiple cores, our approach has a near-linear scalability.