The Translation Look-aside Buffer (TLB) is a part of most Memory Management Units (MMUs), used to increase address translation speed. It caches recently used portions of the page table, used to map virtual page numbers to physical memory locations.
Purpose
Because the page table is stored in main memory, an un-cached paged RAM system will take twice as long for each access: one clock for the page table entry, and one for the actual data. This would become a major performance hit, especially when modern CPUs outpace their main memory by an order of magnitude.
As with most such problems, the solution is to cache the information required most often: the page table entry. Since the page table is being cached, certain elements of its metadata also need to be duplicated in the TLB. These include the dirty bit, which is set when the page is modified, and the reference bit, used to track page usage for the page replacement algorithm.
Operation
On every memory access, the memory controller looks for the virtual page number in the TLB. If it is found (a TLB hit), the reference bit is set (as is the dirty bit, if the access is a write), and the physical page number is used to determine the physical address; then, the actual memory access is made.
However, if the virtual page number is not in the TLB (a TLB miss), the situation becomes slightly more complicated. The memory controller cannot assume that this is only a TLB miss, and the page accessed is in physical memory somewhere, because there is the possibility that a page fault has occurred.
Therefore, the page table is checked for the accessed page. If the page is in physical memory, the entry is loaded into the TLB, and the access is retried as if a hit ocurred. If the page is not in memory, a page fault exception must be generated, as normal.
Interestingly, handling a TLB miss can be done equally well in software or hardware. In fact, in superscalar processors, handling misses in software can even be an advantage, allowing instructions unaffected by the memory access to continue executing, instead of waiting for the TLB hardware to finish. However, due to the relatively small size of the buffer, TLB misses are far more likely to occur than page faults, and so the software algorithm cannot afford to be as inefficient as the one used for page replacement can.
Performance Implications
In a protected memory system, a context switch implies the use of a new page table. Clearly then, the old page table must have the dirty and reference bits synchronised with the TLB, which must then be flushed of all entries. The TLB must then be slowly filled as pages are accessed, according to the operation outlined above. This can be a fairly expensive operation, and when rapid context switching occurs it can severely impact performance.
Implementation
Typical parameters for a Translation Look-aside Buffer are:
- Size: 32 to 8192 page table entries (each around 4 to 8 bytes in size)
- Access time: less than one clock cycle
- Miss penalty: 10 to 30 cycles
- Miss rate: 0.01% to 1%
- Associativity: 2-way to fully associative
References:
Computer Organization & Design, Patterson and Hennessy, Morgan Kaufman