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.
Conclusion:
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:
Direct-Mapped-Cache
4-Way-Set-Associative
Cache
2-Way-Set-Associative
Cache
Keywords:
What is a cache memory
How does a cache memory work
What is Cache Miss
What is Cache Hit
What is 'tag'.