patternMajor
Tag, index and offset of associative cache
Viewed 0 times
tagoffsetcacheandindexassociative
Problem
My main issue of a homework problem is trying to figure out the different parts of the chart. I have a 3 way set associative cache with 2 word blocks, total size of 24 words. I am given $3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253$ to try to map.
What I have so far and where I am stuck:
My main problem is trying to figure out how to find the index and offset of associative (3-way set) cache. Since I have 3 sets, is it: $3 \bmod 3 = 0$, so $0$ is the index? $180 \bmod 3 = 0$ index as well? And would it looks like the following:
$$
\begin{array}{|c|c|c|c|c|c|c|c|} \hline
\text{Block} & \text{Ix} & \text{Hit/Miss} &
\text{Set 0} & \text{Set 0} &
\text{Set 1} & \text{Set 1} &
\text{Set 2} & \text{Set 2} \\\hline
3 & 0 & \text{miss} & \mathit{mem}[3] \\
180 & 0 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] \\
43 & 1 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] \\
2 & 2 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] && \mathit{mem}[2] \\
191 & 2 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] && \mathit{mem}[2] & \mathit{mem}[191] \\\hline
\end{array}
$$
etc...
Somehow I feel like this is all wrong, because of some sample problems I have seen. But in class, this is how I remember it being explained. Helping me understand the fundamentals of this problem would be so helpful and I appreciate all the help I can get. Sorry if it doesn't seem like I have put a lot of work into this, but I am familiar with only directly mapped cache and the sample problems I have seen aren't very explanatory.
What I have so far and where I am stuck:
My main problem is trying to figure out how to find the index and offset of associative (3-way set) cache. Since I have 3 sets, is it: $3 \bmod 3 = 0$, so $0$ is the index? $180 \bmod 3 = 0$ index as well? And would it looks like the following:
$$
\begin{array}{|c|c|c|c|c|c|c|c|} \hline
\text{Block} & \text{Ix} & \text{Hit/Miss} &
\text{Set 0} & \text{Set 0} &
\text{Set 1} & \text{Set 1} &
\text{Set 2} & \text{Set 2} \\\hline
3 & 0 & \text{miss} & \mathit{mem}[3] \\
180 & 0 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] \\
43 & 1 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] \\
2 & 2 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] && \mathit{mem}[2] \\
191 & 2 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] && \mathit{mem}[2] & \mathit{mem}[191] \\\hline
\end{array}
$$
etc...
Somehow I feel like this is all wrong, because of some sample problems I have seen. But in class, this is how I remember it being explained. Helping me understand the fundamentals of this problem would be so helpful and I appreciate all the help I can get. Sorry if it doesn't seem like I have put a lot of work into this, but I am familiar with only directly mapped cache and the sample problems I have seen aren't very explanatory.
Solution
Before getting to your question, let's recall what set-associativity means, and how one can figure out how to split the address into tag, index and offset. If you prefer to learn by examples, jump to after the fold.
Cache
A cache is just a faster, yet smaller, memory.
It might take a long time to access data in the main memory, but it is very fast to access the cache. So we better save data in our small and fast cache rather than in our big and slow main memory.
However, the cache is small, so it cannot hold the entire data of the main memory.
Instead, it will hold some part of the data stored in the main memory.
Which part of the data?
We don’t know in advance - this would depend on the actual usage of the data (i.e., it depends on the software we run).
In general we would like to be able to put in the cache any part of the main memory,
and we would need to figure out where to put each memory-address in the cache, and how to identify which memory-address lies in each cache-cell. The index and tag bits will do just that (see below for a better explanation). But before we get there, let’s make things a bit more complex: we stop discussing addresses of the main memory and start discussing memory blocks.
Blocks and offsets
Many times, when we access the memory, we access consecutive addresses. That is, many times if we access address 0, then shortly after we will access address 1 (and 2, and 3....). So maybe when we first access address 0, and put it in the cache, it will be smart to bring along addresses 1 and 2 and 3 [...] and put them in the cache as well.
This "chunk" of information that we bring into the cache is called a block. The cache always hold blocks of consecutive memory addresses. It is possible that each block in the cache contains the data of only 1 memory-address. It is possible that a block contains the data of 2 (consecutive) addresses. Maybe it contains 128 consecutive addresses... Each cache has its own parameters.
Since the cache "knows" only blocks rather than specific addresses, we need a way to distinguish different addresses within a specific block. For this we have offset bits.
If a block contains $x$ addresses of the memory, then any $x$ consecutive addresses constitute a single block.
Given a specific address in the memory, we can look at its bits representation: the MSB will be the "block number" and the LSB would be the offset inside the block. That is, to get the block number out of a specific address we can simply ignore the last $\log_2 x$ bits (LSB), and the rest will indicate the number of the block associated with these $x$ addresses. The lower $\log_2 x$ bits are called offset bits and they are used to tell the cache which address within the block we wish to access.
Set Associativity
Now to the more interesting part of caching. Where does each block go within the cache? This seems like a stupid question: why don't any block go anywhere in the cache. The answer is that if any block can be anywhere, then it may be very difficult to locate that block when we need it -- we will have to search through the entire cache for that block, and this search may be slow/expensive.
The solution is that the cache is split into “sets”. Each memory block is assigned to one specific set. This assignment never changes.
Whenever you access that memory block: if it is in the cache it will be in that assigned set; if it is not in that assigned set, it is not in the cache and you need to bring it from the memory.
Example: let's say the cache have a place for only 2 blocks (Place A, and Place B), and the memory contains 10 blocks (block0 to block9). We can decide that in the first “set” (Place A) we put only even blocks, and in the second set (Place B) only odd blocks. Now if we access block 5 (say), then we only need to check the second set (Place B), because it can only be there. This may save us HALF the search time (or half the cost of searching a block).
In the above example, each “set” could hold only one block, but in general, each set can hold $n$ blocks at the same time: this kind of cache is called $n$-associative.
In other words, an $n$-associative cache is split into sets, where each set holds $n$ memory blocks. This allows us to determine the amount of different sets: it is the size of the cache (in blocks) divided by $n$.
Let’s have two examples:
-
1-associative: each set can hold only one block. As always, each address is assigned to a unique set (this assignment better be balanced, or all the addresses will compete on the same place in the cache). Such a setting is called direct mapping
-
fully-associative: here each set is of the size of the entire cache. That is, if the cache is of size $t$ blocks, a fully associative cache is in fact a $t$-associative cache. How many sets are there? one! and all the blocks are assigned to this single set. Therefore, each blocks can be saved “anywhere” at the cache, because all the cells of the cache belong to the
Cache
A cache is just a faster, yet smaller, memory.
It might take a long time to access data in the main memory, but it is very fast to access the cache. So we better save data in our small and fast cache rather than in our big and slow main memory.
However, the cache is small, so it cannot hold the entire data of the main memory.
Instead, it will hold some part of the data stored in the main memory.
Which part of the data?
We don’t know in advance - this would depend on the actual usage of the data (i.e., it depends on the software we run).
In general we would like to be able to put in the cache any part of the main memory,
and we would need to figure out where to put each memory-address in the cache, and how to identify which memory-address lies in each cache-cell. The index and tag bits will do just that (see below for a better explanation). But before we get there, let’s make things a bit more complex: we stop discussing addresses of the main memory and start discussing memory blocks.
Blocks and offsets
Many times, when we access the memory, we access consecutive addresses. That is, many times if we access address 0, then shortly after we will access address 1 (and 2, and 3....). So maybe when we first access address 0, and put it in the cache, it will be smart to bring along addresses 1 and 2 and 3 [...] and put them in the cache as well.
This "chunk" of information that we bring into the cache is called a block. The cache always hold blocks of consecutive memory addresses. It is possible that each block in the cache contains the data of only 1 memory-address. It is possible that a block contains the data of 2 (consecutive) addresses. Maybe it contains 128 consecutive addresses... Each cache has its own parameters.
Since the cache "knows" only blocks rather than specific addresses, we need a way to distinguish different addresses within a specific block. For this we have offset bits.
If a block contains $x$ addresses of the memory, then any $x$ consecutive addresses constitute a single block.
Given a specific address in the memory, we can look at its bits representation: the MSB will be the "block number" and the LSB would be the offset inside the block. That is, to get the block number out of a specific address we can simply ignore the last $\log_2 x$ bits (LSB), and the rest will indicate the number of the block associated with these $x$ addresses. The lower $\log_2 x$ bits are called offset bits and they are used to tell the cache which address within the block we wish to access.
Set Associativity
Now to the more interesting part of caching. Where does each block go within the cache? This seems like a stupid question: why don't any block go anywhere in the cache. The answer is that if any block can be anywhere, then it may be very difficult to locate that block when we need it -- we will have to search through the entire cache for that block, and this search may be slow/expensive.
The solution is that the cache is split into “sets”. Each memory block is assigned to one specific set. This assignment never changes.
Whenever you access that memory block: if it is in the cache it will be in that assigned set; if it is not in that assigned set, it is not in the cache and you need to bring it from the memory.
Example: let's say the cache have a place for only 2 blocks (Place A, and Place B), and the memory contains 10 blocks (block0 to block9). We can decide that in the first “set” (Place A) we put only even blocks, and in the second set (Place B) only odd blocks. Now if we access block 5 (say), then we only need to check the second set (Place B), because it can only be there. This may save us HALF the search time (or half the cost of searching a block).
In the above example, each “set” could hold only one block, but in general, each set can hold $n$ blocks at the same time: this kind of cache is called $n$-associative.
In other words, an $n$-associative cache is split into sets, where each set holds $n$ memory blocks. This allows us to determine the amount of different sets: it is the size of the cache (in blocks) divided by $n$.
Let’s have two examples:
-
1-associative: each set can hold only one block. As always, each address is assigned to a unique set (this assignment better be balanced, or all the addresses will compete on the same place in the cache). Such a setting is called direct mapping
-
fully-associative: here each set is of the size of the entire cache. That is, if the cache is of size $t$ blocks, a fully associative cache is in fact a $t$-associative cache. How many sets are there? one! and all the blocks are assigned to this single set. Therefore, each blocks can be saved “anywhere” at the cache, because all the cells of the cache belong to the
Code Snippets
Block Add Index Hit/Miss Set 0 Set 0 Set 0 Set 1 Set 1 Set 1 Set 2 Set 2 Set 2 Set 3 Set 3 Set 3
3 =00000011 01 miss mem[00000]
180 =10110100 10 miss mem[00000] mem[10110]
43 =00101011 01 miss mem[00000] mem[00101] mem[10110]
2 =00000010 01 hit mem[00000] mem[00101] mem[10110]Context
StackExchange Computer Science Q#33818, answer score: 22
Revisions (0)
No revisions yet.