Design of new XOR-based hash functions for cache memories

✍ Scribed by Sung-Jin Cho; Un-Sook Choi; Yoon-Hee Hwang; Han-Doo Kim

• Book ID: 104008081
• Publisher: Elsevier Science
• Year: 2008
• Tongue: English
• Weight: 536 KB
• Volume: 55
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/j.camwa.2007.07.008

✦ Synopsis

A hash function H is a computationally efficient function that maps bitstrings of arbitrary length to bitstrings of fixed length, called hash values. Hash functions have a variety of general computational uses. They are used in processors to augment the bandwidth of an interleaved multibank memory or to enhance the utilization of a prediction table or a cache. In this paper, we design new XOR-based hash functions, which compute each set index bit as XOR of a subset of the bits in the address by using the concepts of rank and null space. These are conflict-free hash functions which are of different types according to whether m is even or odd. To apply the constructed hash functions to the skewed-associative cache, we show that the degree of interbank dispersion between two hash functions is maximal.