How does lookup the L1 and L2 cache?

Recently I was reading some material on cpu cache. I am wondering how does the cpu lookup the L1 and L2 cache and in what format is the data in the cpu cache stored?

I think a linear scan of the cache would be inefficient, are there any b开发者_开发技巧etter solutions?

Thanks.

It uses index bits and tags extracted from the address it is looking up.

Say you are accessing some 32 bit address ADDR

ADDR will have bits: 31--------------------------0, [------tag|index|offset]

Then depending on the size of your cache: Let's say you have a 32K, Direct Mapped cache with 32bytes per block.

Offset bits are used to find the data within each line because 8bytes is a minimum data size to be brought into the cache (well you always get the full 32bytes, but within the 32bytes you will have your data.)

This accounts for a cache with 1024 lines or sets, again each line with 32bytes. In order to index the 1024 sets you need 10bits. Thus the 10 bits from your address are used as an index into the cache. The offset bits are used to see where inside that line your data is , and the tag bits are used to match the address that you are looking up since two or more addresses will map into the same line of the cache. Makes sense?

I do not know your answer, but I can recommend a good book that might lead you to one - The Essentials Of Computer Organization and Architecture