Translation lookaside buffer: Difference between revisions
No edit summary |
edit |
||
Line 6: | Line 6: | ||
A TLB has a fixed number of slots that contain [[page table]] entries, which map virtual addresses to [[physical address]]es. The [[virtual memory]] is the space seen from a process. This space is segmented in pages of a prefixed size. The [[page table]] (generally loaded in memory) holds trace of where the virtual pages are loaded in the physical memory. The TLB is a cache of the [[page table]], that is only a subset of its content are stored. |
A TLB has a fixed number of slots that contain [[page table]] entries, which map virtual addresses to [[physical address]]es. The [[virtual memory]] is the space seen from a process. This space is segmented in pages of a prefixed size. The [[page table]] (generally loaded in memory) holds trace of where the virtual pages are loaded in the physical memory. The TLB is a cache of the [[page table]], that is only a subset of its content are stored. |
||
The TLB references physical memory addresses in its table. It may reside between the CPU and the [[CPU cache]], between the CPU cache and [[primary storage]] memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches |
The TLB references physical memory addresses in its table. It may reside between the CPU and the [[CPU cache]], between the CPU cache and [[primary storage]] memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an ASID. Caches that don't have ASIDs must be flushed every [[context switch]] in a [[multiprocessing]] environment. |
||
In a [[Harvard architecture]] or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each of access types. |
In a [[Harvard architecture]] or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each of access types. |
||
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a [[virtual memory]] system having 4 KiB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the [[CPU cache#Address translation|address translation]] section in the cache article for more details about virtual addressing as it pertains to caches and TLBs. |
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a [[virtual memory]] system having 4 KiB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the [[CPU cache#Address translation|address translation]] section in the cache article for more details about virtual addressing as it pertains to caches and TLBs. |
||
== Implications for performance == |
|||
The CPU has to go off-chip for a: |
|||
*instruction cache miss |
|||
*data cache miss |
|||
*TLB miss |
|||
The third case is (the simplest case) where the desired information actually ''is'' on-chip, but the information for virtual-to-physical translation is not available. These are all about equally slow, so a program 'thrashing' the TLB will run just as poorly as one thrashing the data cache. That is why a well functioning TLB is important. |
|||
==Software TLB and hardware TLB== |
==Software TLB and hardware TLB== |
Revision as of 00:25, 29 June 2010
A translation lookaside buffer (TLB) is a CPU cache that memory management hardware uses to improve virtual address translation speed. It was the first cache introduced in processors.[citation needed] All current desktop and server processors (such as x86) use a TLB.
The TLB is typically implemented as content-addressable memory (CAM). The CAM search key is the virtual address and the search result is a physical address. If the requested address is present in the TLB, the CAM search yields a match quickly and the retrieved physical address can be used to access memory. This is called a TLB hit. If the requested address is not in the TLB, it is a miss and the translation proceeds by looking up the page table in a process called a page walk. The page walk is an expensive process, as it involves reading the contents of multiple memory locations and using them to compute the physical address. After the physical address is determined by the page walk, the virtual address to physical address mapping is entered into the TLB.
Overview
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) holds trace of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table, that is only a subset of its content are stored.
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an ASID. Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each of access types.
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KiB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.
Implications for performance
The CPU has to go off-chip for a:
- instruction cache miss
- data cache miss
- TLB miss
The third case is (the simplest case) where the desired information actually is on-chip, but the information for virtual-to-physical translation is not available. These are all about equally slow, so a program 'thrashing' the TLB will run just as poorly as one thrashing the data cache. That is why a well functioning TLB is important.
Software TLB and hardware TLB
A software TLB or a software loaded TLB, is a TLB that relies on the operating system to load entries from the pagetable. Instruction sets of CPUs that implement TLB have instructions that allow loading entries into any slot in the TLB. The format of the TLB entry is defined as a part of the ISA[1]. SPARC and MIPS provide examples of designs that implement a software loaded TLB.
A hardware loaded TLB (or hardware walked TLB), like on x86, is designed to load entries from the pagetable invisibly to the operating system. Filling the TLB with address translations is under the control of dedicated hardware. In fact, if the TLB were removed from the CPU (not that it is a good idea), the programs would exhibit no difference, except that the time for executing them would increase. Moreover, since it is invisible to the OS and the ISA, the format of the TLB entries can be defined as needed and this definition can change from CPU to CPU without causing loss of compatibility for the programs. Processors with a hardware TLB may still require TLB flushing instructions, such as ARM processors, whilst other processor may implicitly flush the TLB on certain operations, such as x86.
The Itanium architecture provides an option of using either software or hardware managed TLBs[2].
Miss
Two schemes for handling TLB misses are commonly found in modern architectures:
- With hardware TLB management, the CPU itself walks the page tables (using the CR3 register on x86 for instance) to see if there is a valid page table entry for the specified virtual address. If an entry exists, it is brought into the TLB and the TLB access is retried: this time the access will hit, and the program can proceed normally. If the CPU finds no valid entry for the virtual address in the page tables, it raises a page fault exception, which the operating system must handle. Handling page faults usually involves bringing the requested data into physical memory, setting up a page table entry to map the faulting virtual address to the correct physical address, and resuming the program (see Page fault for more details.)
- With software-managed TLBs, a TLB miss generates a "TLB miss" exception, and the operating system must walk the page tables and perform the translation in software. The operating system then loads the translation into the TLB and restarts the program from the instruction that caused the TLB miss. As with hardware TLB management, if the OS finds no valid translation in the page tables, a page fault has occurred, and the OS must handle it accordingly. This is how TLB misses are handled on MIPS CPUs for instance[3].
Typical TLB
- Size: 8 - 4,096 entries
- Hit time: 0.5 - 1 clock cycle
- Miss penalty: 10 - 30 clock cycles
- Miss rate: 0.01 - 1%
Computer Organization And Design. Burlington, MA 01803, USA: Morgan Kaufmann Publishers. 2007. p. 523. ISBN 978-0-12-370606-5. {{cite book}}
: More than one of |pages=
and |page=
specified (help); Unknown parameter |coauthors=
ignored (|author=
suggested) (help)CS1 maint: location (link)
If a TLB hit takes 1 clock cycle, a miss takes 30 clock cycles, and the miss rate is 1%, the effective memory cycle rate is an average of
(1.30 clock cycles per memory access).
Context switch
On a context switch, some TLB entries can become invalid, since for example the previously running process had access to a page, but the process to run does not. The simplest strategy to deal with this is to completely flush the TLB. Newer CPUs have more efficient strategies; for example in the Alpha 21264, each TLB entry is tagged with an "address space number" (ASN), and only TLB entries with an ASN matching the current task are considered valid. Another example in the Intel Pentium Pro, the page global enable (PGE) flag in the register CR4 and the global (G) flag of a page-directory or page-table entry can be used to prevent frequently used pages from being automatically invalidated in the TLBs on a task switch or a load of register CR3.
While selective flushing of the TLB is an option in software managed TLBs, till now the only option in some hardware TLBs (e.g., x86) has been the complete flushing of the TLB on a context switch. Other hardware TLBs (e.g., ARM) allow the flushing of individual entries from the TLB indexed by virtual address.
Virtualization and x86 TLB
With the advent of virtualization for server consolidation, a lot of effort has gone into making the x86 architecture easier to virtualize and to ensure better performance of virtual machines on x86 hardware[4][5]. In a long list of such changes to the x86 architecture, the TLB is the latest.
Normally, the entries in the x86 TLBs are not associated with any address space. Hence, every time there is a change in address space, such as a context switch, the entire TLB has to be flushed. Maintaining a tag which associates each TLB entry with an address space in software and comparing this tag during TLB lookup and TLB flush is very expensive, especially since the x86 TLB is designed to operate with very low latency and completely in hardware. In 2008, both Intel (Nehalem)[6] and AMD (SVM)[7] have introduced tags as part of the TLB entry and dedicated hardware which checks the tag during lookup. Even though these are not fully exploited, it is envisioned that in the future, these tags will identify the address space to which every TLB entry belongs. Thus a context switch will not result in the flushing of the TLB - but just changing the tag of the current address space to the tag of the address space of the new task.
References
- ^ J. Smith and R. Nair. Virtual Machines: Versatile Platforms for Systems and Processes (The Morgan Kaufmann Series in Computer Architecture and Design). Morgan Kaufmann Publishers Inc., 2005.
- ^ Virtual Memory in the IA-64 Kernel > Translation Lookaside Buffer
- ^ Welsh, Matt. "MIPS r2000/r3000 Architecture". Retrieved 16 November 2008.
If no matching TLB entry is found, a TLB miss exception occurs
- ^ D. Abramson, J. Jackson, S. Muthrasanallur, G. Neiger, G. Regnier, R. Sankaran, I. Schoinas, R. Uhlig, B. Vembu, and J. Wiegert. Intel Virtualization Technology for Directed I/O. Intel Technology Journal, 10(03):179–192.
- ^ Advanced Micro Devices. AMD Secure Virtual Machine Architecture Reference Manual. Advanced Micro Devices, 2008.
- ^ G. Neiger, A. Santoni, F. Leung, D. Rodgers, and R. Uhlig. Intel Virtualization Technology: Hardware Support for Efficient Processor Virtualization. Intel Technology Journal, 10(3).
- ^ Advanced Micro Devices. AMD Secure Virtual Machine Architecture Reference Manual. Advanced Micro Devices, 2008.