Versatile and Scalable Parallel Histogram Construction

Histograms are used in various fields to quickly profile the distribution of a large amount of data. However, it is chal-lenging to efficiently utilize abundant parallel resources in modern processors for histogram construction. To make matters worse, the most efficient implementation varies de-pending on input parameters (e.g., input distribution, num-ber of bins, and data type) or architecture parameters (e.g., cache capacity and SIMD width). This paper presents versatile histogram methods that achieve competitive performance across a wide range of input types and target architectures. Our open source implementations are highly optimized for various cases and are scalable for more threads and wider SIMD units. We also show that histogram construction can be significantly accelerated by IntelR © Xeon Phi TM coprocessors for common input data sets because of their compute power from many cores and in-structions for efficient vectorization, such as gather-scatter. For histograms with 256 fixed-width bins, a dual-socket 8-core IntelR © XeonR © E5-2690 achieves 13 billion bin updates per second (GUPS), while a 60-core IntelR © Xeon Phi TM 5110P coprocessor achieves 18 GUPS for a skewed input. For histograms with 256 variable-width bins, the Xeon pro-cessor achieves 4.7 GUPS, while the Xeon Phi coprocessor achieves 9.7 GUPS for a skewed input. For text histogram, or word count, the Xeon processor achieves 342.4 million words per seconds (MWPS). This is 4.12×, 3.46 × faster than phoenix and tbb. The Xeon phi processor achieves 401.4 MWPS, which is 1.17 × faster than the Xeon proces-sor. Since histogram construction captures essential char-acteristics of more general reduction-heavy operations, our approach can be extended to other settings