Cache Memory Tutorial - 3
-Aviral Mittal (avimit att yhaoo dat cam)
Connect @

Cache Memories - 3 : Organization of Cache Memories
In the previous Section(s), it was explained what is a cache memory, why a cache memory is needed, what is temporal and spatial locality.
This chapter is about structure and organization of cache memories.
So far it was established that a cache memory typically is a couple of normal SRAMs, controlled by a controller, i.e. the cache controller. This chapter elaborates further on the structure and organization of caches. The 2 SRAMs in a cache are:
1. TAG RAM : Stores TAG Address or simply TAG.
2. DATA RAM : Stores DATA.

In order to understand what is a TAG, first we need to understand how the address of the transaction issued to a cache memory is organized.
The address is organized as a concatination of what is called 'TAG ADDRESS or simply TAG, 'SET Address or simply SET' and 'OFFSET' Address or simply OFFSET

Hence an example 32 bit address that is issued by some processor and received by the cache-controller may appear like this

ADDRESS = {TAG[TAG_WIDTH-1:0],SET[SET_WIDTH-1:0],OFFSET[OFFSET_WIDTH-1:0]}, where TAG_WIDTH = 24, SET_WIDTH = 6, OFFSET_WIDTH = 5, in the following example

Note: 'SET' is also known as 'INDEX'.

To further understand the 'Tag', 'Set' and 'Offset', first we need to understand how cache memories are organized.
The following figure shows an example of the cache memory.
It can be seen that it has a 'Tag RAM' and a 'Data RAM'. The Data RAM contains blocks of data, with each block containing 16 words. The number of words in a block also determines what is called the block size. A block is also called a cache line. Hence in this example a cache line (or a cache block) has 16 words.
The Data RAM contains 32 cache lines or 32 cache blocks. Hence the size of Data Ram = 16 x 32 = 512 Bytes. This is also the size of the cache memory. Hence in this example, the size of the cache memory is 512 Bytes, or 0.5 KB.  The Offset will identify 1 byte with in a cache line. And since there are 16 bytes in this cache line example, the offset will be 4 bits. (2^4 = 16)
There are 32 cache lines in the memory. The 'SET' identifies the cache line. Hence the number of bits for SET will be 5. (2^5 = 32).
In the following figure, the SET is pointing to 25th TAG location and also pointing to 25th Cache line location, while the OFFSET is pointing to the 8th byte in 16 byte cache line.

The following figure shows the address as a concatination of 'TAG' , 'SET' and 'OFFSET'.

What is TAG?
TAG is that left over bits of the address, after taking out 'SET' and 'OFFSET', which is stored in TAG memory at the address identified by 'SET'. Now when a new access is issued to this cache memory then the cache controller, takes the 'TAG' portion of the input address, and compares it to the contents of the TAG RAM location identified by the SET  bits. If there is a match, the transaction is said to be a 'Cache Hit'. If the TAG portion of the input address does not match with what is stored in the TAG RAM @address = 'SET', then its a Cache Miss. Hence the TAG is that portion of the address which determines the Cache Hit or a Cache Miss.
In the above example, the address received as input by the cache controller will compare its TAG with the TAG bits stored at the 25th location (@ SET address = 24). And if the TAG bits of input address matches with what is stored at the 25th location (@ SET address = 24), the cache line at 25th location will be accessed.

As mentioned earlier a cache memory contains multiple cache lines. The number of cache lines in cache memory of course depends upon the size of the cache memory and also on the size of 1 single cache line in bytes.

Example 1 : Cache Size (Cs) = 64 KB, Cache line size (Cls) = 16 Bytes, Calculate the number of cache lines (Cl)

Cache line size (Cl) = Cache Size in Bytes/Number of Bytes in 1 Cache line

Cl = Cs/Cls
Cl = 64K/16 = 4K
Hence in this example the number of Cache lines (Cl) = 4K.

Example 2: Cache Size (Cs) = 256 KB, Cache line size (Cls) = 32 Bytes, Calculate the number of cache lines (Cl)
Cl  = Cs/Cls
Cl = 256K/32 = 8K.

As seen previously, to identify a cache line in cache memory, an address is required which is called 'SET' address. In Example 1 above, the number of bits for SET address will be equal to Log2(Cl) i.e. Log2(4K) = 12, similarly in example 2, the number of bits for SET address will be Log2(8K) = 13.

So far we have learned how to identify a cache line in a cache memory and how to identify a byte in a cache line. That is, if we have to read 1 byte from a cache memory, we need 'SET' address to identify the location of cache line and offset address to identify the byte location in the identified cache line.
Hence to build a cache memory we need a RAM which will be organized as each address identifying a cache line. An array of Cl x Cls, where Cl is the number of cache lines, and Cls is cache line size in bytes.

Direct Mapped Cache:
Important Note: In the above example, it can be observed, that a cache-line corresponding to a TAG address has a fixed location in DATA RAM. A 'SET' address simply identifies a single Cache line. This arrangement is called Direct-Mapped Cache Memory. Hence in a direct mapped cache memory a Cache line has a fixed location in the DATA RAM and this location is what the 'SET' address points to. In Next chapter we will learn how the 'SET' Address may identify a 'set' of cache line locations and a 'set' of TAG locations instead of a single cache line location and a single TAG location.

Following figure explains the Direct-Mapped Operation:
Memory size = 0.5 KB
Cache line size = 32 bytes.
Offset address Width = Log2(cache line size) = Log2(320 = 5
Number of lines =  Memory size/cache line size = 0.5KB/32 = 16.
'SET' address width = Log2(number of lines) = Log2(16) = 4
TAG Address width = Total address width-SET width-OFFSET width. = 16-4-5 = 7.

Learned the organization of Cache memory into TAG RAM and DATA RAM. Learned what is TAG Address, SET Address and OFFSET address. Learned what is Direct-Mapped Cache.
In General a Cache memory is just 2 RAMS(TAG RAM + DATA RAM) + Controller.

<= Spatial Locality Temporal Locality                            Next => 'Associativity' in Cache memories

Cache Organizations:
4-Way-Set-Associative Cache
2-Way-Set-Associative Cache

What is a cache memory
How does a cache memory work
What is Cache Miss
What is Cache Hit
What is 'tag'.