Work Efficient Hashing on Parallel and Vector Computers
Abstract
Hashing techniques have long been used to efficiently store and locate data indexed by key. Recently, parallel hashing algorithms have been developed that allow table insertion of many keys in a few parallel steps. The analyses of these algorithms have focused on the expected number of steps required, ignoring the issue of work complexity. As a result, these algorithms have not been work efficient. In this paper, we present a parallel hashing algorithm that is shown to be work efficient because it performs no more work than its serial counterpart. An analysis of its behavior shows that it performs S = 0(logn) expected parallel steps and W = 0(n) expected work. Many parallel algorithms can make use of hashing as a core step. Procedures such as histogramming, set difference, keyed reduction and dictionary lookup can be formulated using a general hash routine. Thus, parallel hashing is an important fundamental parallel operation. The above applications may also be implemented using sorting as the core step. While the use of parallel hashing has been generally accepted in the folklore of parallel computing, a dearth of literature about the expected performance of such algorithms has led many to favor the use of sorting. This paper sheds light on the performance that may be achieved using parallel hashing algorithms and should lend credibility to their use.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 18, 1992
- Accession Number
- ADA256355
Entities
People
- Randal Bryant
- Thomas J. Sheffler
Organizations
- Carnegie Mellon University