Cache mapping

Hi,

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

Tim Frink wrote:
> Hi,
> 
> 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.

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.)

> 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)

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.

> or will they go into another set (leaving the
> second line of the first set free)?

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.

HTH

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .