Design and evaluation of parallel hashing over large-scale data

Cheng, L.; Kotoulas, S.; Ward, T.; Theodoropoulos, G.

Abstract

High-performance analytical data processing systems often run on servers with large amounts of memory. A common data structure used in such environment is the hash tables. This paper focuses on investigating efficient parallel hash algorithms for processing large-scale data. Currently, hash tables on distributed architectures are accessed one key at a time by local or remote threads while shared-memory approaches focus on accessing a single table with multiple threads. A relatively straightforward “bulk-operation” approach seems to have been neglected by researchers. In this work, using such a method, we propose a high-level parallel hashing framework, Structured Parallel Hashing, targeting efficiently processing massive data on distributed memory. We present a theoretical analysis of the proposed method and describe the design of our hashing implementations. The evaluation reveals a very interesting result - the proposed straightforward method can vastly outperform distributed hashing methods and can even offer performance comparable with approaches based on shared memory supercomputers which use specialized hardware predicates. Moreover, we characterize the performance of our hash implementations through extensive experiments, thereby allowing system developers to make a more informed choice for their high-performance applications.

Citation

Cheng, L., Kotoulas, S., Ward, T., & Theodoropoulos, G. (2014, December). Design and evaluation of parallel hashing over large-scale data. Presented at 2014 21st International Conference on High Performance Computing (HiPC), Velha Goa, India

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2014 21st International Conference on High Performance Computing (HiPC)
• Start Date: Dec 17, 2014
• End Date: Dec 20, 2014
• Publication Date: Dec 20, 2014
• Deposit Date: Apr 21, 2016
• Publicly Available Date: Apr 28, 2016
• Pages: 1-10
• Series ISSN: 1094-7256
• Book Title: 2014 21st International Conference on High Performance Computing (HiPC 2014) : Velha Goa, India, 17 - 20 December 2014.
• DOI: https://doi.org/10.1109/hipc.2014.7116909
• Public URL: https://durham-repository.worktribe.com/output/1150468
• Additional Information: Date of Conference: 17-20 December 2014