# How does a TLB and data cache work?

I'm trying to study for an exam and I realized I'm confused about how the TLB and data cache work.

I understand that the TLB is essentially a cache of most recently used physical addresses. However, I was looking at a diagram in my textbook (shown below), and I don't understand what's going on in it. It suddenly splits up the physical address and uses it to index the cache, I guess. But why is it showing the cache and data separately? and why is the byte offset just left floating? I'm pretty sure the cache is supposed to store data as well. I don't think its sole purpose is to determine whether or not there's a hit or miss inside of it.

I apologize for my ignorance in advance, but the book barely covers TLB's (it's like a little more than a page) and it doesn't do a very good job at explaining the relationship between a TLB and cache.

• This question is too long. Can you extract a narrow, specific question out of this, and then edit your question to trim this down to just a single specific question? Part of asking a good question involves thinking carefully about what is the minimal essence of what you need to know and including only what is relevant and essential to that question. For instance, if you have a specific question about how TLBs work, instead of dumping all of this, how about trying to frame a single narrowly crafted question about a TLB? – D.W. Nov 25 '13 at 3:35
• All right, my intention was to show what I understand already about the subject, since most people on stack exchange don't like answering questions without the asker showing some effort (understandably). I guess I can't make everybody happy. Maybe I'll just edit it with my question in bold or something. – audiFanatic Nov 25 '13 at 4:34
• @D.W. is that better? – audiFanatic Nov 25 '13 at 4:39
• audiFanatic, you might have misinterpreted or misunderstood my comments and the "show some effort" mindset. My suggestion is that you identify a narrow question -- something like "how does a TLB work? I don't quite understand" -- and then re-focus solely on that question. Yes, you need to make a serious effort to answer that question, and you should show the effort you've done to answer that specific question, but effort on an unrelated subject is not relevant (e.g., the fact that you tried hard to make progress on a homework question which made you think of this question). – D.W. Nov 25 '13 at 5:51
• Let me help you understand the background behind this. We want to build up a high-quality archive of questions and answers that will be helpful to others (not just to you). The best thing you can do to help is to extract a specific, narrow, well-posed question, and focus your question on just that one question. A sprawling, open-ended, question that isn't very focused is less likely to be helpful to others who might stumble on it (and it's also harder for readers to get to the point and understand what the core of your question is, so you're less likely to get a good answer). – D.W. Nov 25 '13 at 5:53

I think I see your confusion. The TLB and the data cache are two separate mechanisms. They are both caches of a sort, but they cache different things:

• The TLB is a cache for the virtual address to physical address lookup. The page tables provide a way to map virtualaddress $\mapsto$ physicaladdress, by looking up the virtual address in the page tables. However, doing the lookup in the page tables is slow (it involves 2-3 memory loads). If the processor had to do this lookup every time any instruction accessed memory, this would cause a substantial slowdown.

Therefore, the TLB acts as a dedicated cache for this lookup. The TLB has a few TLB entries, where each TLB entry contains both a virtual address and its corresponding physical address.

The TLB lets the processor very quickly convert virtual addresses to physical addresses. If an instruction asks the processor to do some memory operation on a (virtual) address, the processor first checks to see whether the TLB contains an entry for that virtual address. If it does, then that's called a "cache hit" for the TLB lookup, and since the TLB entry also contains the translated physical address, the processor immediately knows what physical address to use. If it doesn't, that's a cache miss for the TLB lookup, and the processor has to laboriously do the virtual-to-physical conversion by walking the page table. (Once it finishes doing that conversion, it adds an entry to the TLB so that future conversions of that virtual address will happen much more quickly.)

• The data cache is a cache for the contents of memory. Main memory lets you specify a physical address and read the value at that physical address. However, main memory is slow. If we had to go to main memory every time we wanted to do any memory operation, our processor would be very slow.

Therefore, the data cache acts as a dedicated cache for memory reads. The data cache has some cache entries, where each cache entry contains a physical address and the value of memory at that address.

The data cache lets the processor very quickly read from memory. When the processor wants to read memory at some (physical) address, it first checks the data cache to see whether it contains a cache entry for that address. If it does, this is known as a "cache hit" (in the data cache), and the processor can immediately use the data value stored in that cache entry, without needing to contact main memory. If it doesn't, then this is a "cache miss" (for the data cache), and the processor needs to go to main memory. (After the processor receives the value at that address from main memory, it adds a cache entry to the data cache so that attempts to read that same address will hit in the data cache.)

They are both caches, but they serve a different purpose. The processor uses both for each memory operation: it first uses the TLB to convert from virtual address to physical address, then it checks the data cache to speed up the process of reading the value stored in memory at that address.

For more details, you can read the Wikipedia article on TLBs. If you do a search, there is a lot of other information available on TLBs and data caches. I suggest searching for "TLB" and for "L1 cache" or "L2 cache" (the latter 2 are kinds of data caches).

(For future reference: we expect you to do some research on your question before asking here, and to check standard Internet sources. If the answer can be found in Wikipedia, you haven't done enough research on your own. You might have had better luck if you'd checked Internet sources for information on how TLBs before asking here. See also How much research effort is expected of Stack Overflow users?. So, take the opportunity to use this as a lesson for how you can improve your own research skills -- something that will be valuable to you throughout your career.)

• Thank you! That cleared up mostly everything. I did spend a lot of time researching this (several days), I just couldn't find a clear, concise piece of information that tied it all together (plus my confusion probably didn't help my search). As an analogy, I felt like I was in a pharmacy looking for a cure to some undiagnosed ailment; using only symptoms as a guide. – audiFanatic Nov 25 '13 at 14:19
• With that said, I have one more question. If they are caches, why is the book separating the data and tag portions of the cache (hell, the data portion is even taller than the tag and valid bit portion)? It makes it seem like the cache serves no other than to check tags (as though it doesn't store data). Is that data block in the bottom-right corner of the picture part of the cache or is that part of main memory or what? – audiFanatic Nov 25 '13 at 14:22
• (1) The "tag" is the part of the address that is being translated. I simplified a little: rather than the TLB translating a single virtual address to a single physical address, it translates an entire page granularity's worth. If the page is 4096 bytes long, then the virtual-to-physical lookup only looks at the upper 20 bits of the virtual address; if virtual address $V$ translates to physical address $P$ (and they are page-aligned), then $V+1$ translates to $P+1$, $V+2$ to $P+2$, ..., $V+4095$ to $P+4095$. – D.W. Nov 25 '13 at 18:25
• (2) The data cache is the whole bottom part of the picture (bottom left block + bottom right block). Conceptually, the $i$th entry of the data cache consists of $i$th row of the bottom left block plus the $i$th row of the bottom right block. I don't know why this diagram shows them as separated; conceptually, you could treat them as grouped together if you like. – D.W. Nov 25 '13 at 18:26
• Ok, great. Thanks. I guess it was the separation that was confusing me the most. – audiFanatic Nov 27 '13 at 0:46