Browse Prior Art Database

Emulating Multi-Way Set-Associativity Through an Address Mapping Scheme Disclosure Number: IPCOM000014799D
Original Publication Date: 2001-Jun-14
Included in the Prior Art Database: 2003-Jun-20
Document File: 2 page(s) / 41K

Publishing Venue




This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 58% of the total text.

Page 1 of 2

Emulating Multi-Way Set-Associativity Through an Address Mapping Scheme


A 2-way set-associative cache of size N/2 has about the same miss
rate as a direct-mapped cache of size N (Hennessy and Patterson:
Computer Architecture, A Quantitative Approach). However, a 2-way
set associative cache involves more complex logic and a larger
hit time compared to a direct-mapped cache.

The technique described herein seeks to achieve a similar miss
rate reduction as a 2-way or multi-way set-associative cache
compared to a direct-mapped cache, at a much smaller increase in
complexity and hit time. Reduction of the cache miss rate results
in a smaller number of memory accesses experiencing the
relatively large miss penalty of an access to main memory and can
substantially improve overall computer performance.


The problem of reducing the hit rate of a cache can be regarded
as a " distribution problem": the addresses that relate to the
instructions/data which are used by a program within a certain
time frame, have to be distributed as well as possible over the
cache indices that relate to the memory locations available
within the cache for storing cache lines.

In a direct-mapped cache, this distribution is realized by a
fixed mapping of addresses on cache indices: the cache index is
simply the least significant part of the address.

In contrast to this conventional fixed mapping of addresses on
indices, the technique described herein involves the following

(1) A m...