The influence of several hash functions on the distribution of a shared address space onto p distributed memory modules is compared by simulations. Both synthetic workloads and address traces of applications are investigated. It turns out that on all workloads linear hash functions, although proven to be asymptotically worse, perform better than theoretically optimal polynomials of degree O(log p). The latter are also worse than hash functions that use boolean matrices. The performance measurements are done by an expected worst case analysis. Thus linear hash functions provide an efficient and easy to implement way to emulate shared memory.

International Conference on Parallel Architectures and Languages Europe - PARLE
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Engelmann, C, & Keller, J. (1993). Simulation-based comparison of hash functions for emulated shared memory. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence (pp. 1–11).