A NEW HASHING ALGORITHM FOR PARALLEL PROCESSORS
Onstantinos V. Papadopoulos · International Journal of Parallel Emergent and Distributed Systems · 1994
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, represent 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 = O (logn) expected parallel steps and W - O(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 Performance data collected from an implementation of our algorithms on the Connection Machine CM-2 and CRAY Y-MP show that it is faster than sorting by up to a factor of four on both machines. These data show that the total time required by the algorithm is more closely related to the amount of work performed, rather than the parallel step count. Our results indicate that work efficiency is an important consideration when trying to achieve high performance on parallel machines.