Hashing and rehashing in emulated shared memory
Jörg Keller · Data Archiving and Networked Services (DANS) · 1992
The PRAM model is widely used to formulate parallel algorithms because of its shared memory and its synchronous behaviour. The model however bears little resemblance to real parallel machines. This has led to various approaches to emulating PRAMs on processor networks. We briefly survey the principles behind these emulations and show why hashing is an important part of them. We discuss the commonly used types of hash functions and their theoretical properties and relate these to their behaviour in simulations. Both synthetic and application based traces are used as input data for these simulations. The simulation results suggest the use of linear functions with randomly chosen coefficients. These functions also have the advantage of short evaluation time and bijectivity. But no matter which type of hash function is chosen, it may be necessary to choose a new hash function on the fly. We present an algorithm to rehash linear functions in optimal time without using shade memory or mass storage systems during rehashing.