Data Parallel Hashing using Pablo and Scatter/Gather - Introductory Example

Notes and Resources

• This is a good introduction to the problem of data parallel hashing with parallel bitstreams.

• Bit-space hashing. For some lengths, it may be useful to consider bit-space hashing. For example, consider identifiers of length 5 and suppose that we want to calculate hash values for a 32-byte hash table (5 bits). Each of the basis bit streams will have 5 bits of information for this identifier. With masking and shifting we can apply variable bit rotations to some of the streams. Bitwise logic to combine the results can then produce 5-bit hash values. This work can be done fully in parallel if there are several instances within a block of 256 positions.

• Bit gathers. We can use the pext instruction to do bit-based gathers. For example, we can gather 5 bits of data from each of the basis bit streams for each length 5 identifier. Then we have a set of compressed basis streams with 51 instances in each 256 bits of stream data. Hash calculations could then be performed using bitwise logic and shifting for all 51 instances in parallel.

• It may be possible to generate perfect hashes dynamically.
• Parallelized cuckoo hashing could be used.

• Conversion of marker bits to position indexes in parallel could proceed as follows.
  • Input streams are partitioned into, say, groups of 16 positions at a time.
  • We first calculate the position of the first nonzero bit in each group 16 using a parallel count-forward-zeroes technique.
    • Parallel count-forward-zeroes can be implemented by determined the mask of positions which are zero and have no preceding 1 bit in the group. This is (x^(x-1))&x.
    • Parallel popcount can then be applied.
  • We thus get up to N/16 parallel position calculations happening.
  • If a field has no one bits, we mask it from subsequent work.
  • We apply the gather and the work on the gathered data.
• We then remove the bits for which we have calculated data and repeat the process until no bits remain.