XOR-based hash functions

Hans Vandierendonck, K. De Bosschere

Research output: Contribution to journalArticle

46 Citations (Scopus)

Abstract

Bank conflicts can severely reduce the bandwidth of an interleaved multibank memory and conflict misses increase the miss rate of a cache or a predictor. Both occurrences are manifestations of the same problem: Objects which should be mapped to different indices are accidentally mapped to the same index. Suitable chosen hash functions can avoid conflicts in each of these situations by mapping the most frequently occurring patterns conflict-free. A particularly interesting class of hash functions are the XOR-based hash functions, which compute each set index bit as the exclusive-or of a subset of the address bits. When implementing an XOR-based hash function, it is extremely important to understand what patterns are mapped conflict-free and how a hash function can be constructed to map the most frequently occurring patterns without conflicts. Hereto, this paper presents two ways to reason about hash functions: by their null space and by their column space. The null space helps to quickly determine whether a pattern is mapped conflict-free. The column space is more useful for other purposes, e. g., to reduce the fan-in of the XOR-gates without introducing conflicts or to evaluate interbank dispersion in skewed-associative caches. Examples illustrate how these ideas can be applied to construct conflict-free hash functions.
Original languageEnglish
Pages (from-to)800-812
Number of pages13
JournalIEEE Transactions on Computers
Volume54
Issue number7
Publication statusPublished - Jul 2005

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'XOR-based hash functions'. Together they form a unique fingerprint.

  • Cite this

    Vandierendonck, H., & De Bosschere, K. (2005). XOR-based hash functions. IEEE Transactions on Computers, 54(7), 800-812.