A Skew-Insensitive Hashing Sync and Construction Scheme for Many-Core Coprocessors

摘要

Many-core coprocessors have been widely used in current high-performance computing area due to their highly parallel computing capabilities and superior energy efficiencies. Hash tables are one of the most used and most important data structures in many data-intensive applications, especially in main-memory database systems. Since the operation of building hash tables is a write-intensive activity, the biggest challenge for this work in a high-concurrency environment is multithread synchronization, especially when workloads are highly skewed. In order to overcome this problem, we propose an efficient parallel hash table construction scheme, including SIMD-aware data structure and a novel hashing synchronous processing algorithm named Pipelined Hashing Sync (PHS). The PHS is performed in two phases: in the first phase, the hash values are partitioned into batches of similar size. While in the second phase, threads process the tuples assigned to them in parallel, and a token-ring scheme is used to avoid multiple threads to concurrently process tuples from the same batch. The experimental results show that the proposed approach has similar performance for uniform datasets compared to the lock-based and CAS-based hashing algorithms. However, for high-skewed datasets, the performance is enhanced by an order of magnitude. This indicates that our approach has a better resilience for skewed workloads.