Cache mapping


I've a question on how blocks are mapped from memory to a set-associative cache.

Let's say, the instructions in memory are all 32 bits long, the I-cache (16kByte) is 2-way set-associative and the each cache line is 256 bits wide (so each line can hold 8 instructions).

How will the instructions be mapped into the sets? Let's say the first

8 instructions from memory are mapped into the first line of the first set. Will the next 8 instructions (assume they are allocated contiguously in memory) be placed in the second line of the first set (and thus completely fill this set) or will the go into another set (leaving the second line of the first set free)?

Regards, Tim

Reply to
Tim Frink
Loading thread data ...

OK, but the lines in a set are not really ordered for mapping purposes, so you can't talk about "mapping into the first line of the first set", just about "mapping into the first set". The cache will itself dynamically choose which line to use (in the first set) when these instructions are loaded into the cache.

(The only ordering that can apply to lines in the same set is access order -- often important for the replacement policy -- or some kind of architectural order when the cache lets you lock or flush particular lines of a set. But these orders have nothing to do with the mapping.)

Definitely not, that would work against the "spatial locality" principle; you don't want neighbouring instructions to compete for the same set in the cache.

Yes, the next 8 instructions will go into another set, as I understand the mapping for conventional caches. The mapping from address to set number simply takes a slice of the address bits, discarding least-significant bits according to the line size, and then taking a number of bits that corresponds to the number of sets.

There are some proposals for caches that use "hashed" mapping, which might be less regular, but I don't know details of those.


Niklas Holsti
Tidorum Ltd
 Click to see the full signature
Reply to
Niklas Holsti

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.