Translation lookaside buffer flush filter

Details Translation lookaside buffer flush filter Translation lookaside buffer flush filter

2000-06-15

2003-01-21

Ellis, Kevin L. (Department: 2185)

Electrical computers and digital processing systems: memory

Address formation

Address mapping

C711S135000

Reexamination Certificate

active

06510508

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to processors, and more particularly, to a translation lookaside buffer used for storing address translations.
2. Description of the Relevant Art
Computer systems using memory management may have the need to translate virtual addresses into physical addresses in order to perform a memory access. Typical computer programs are written to address a memory model, and thus issue virtual memory addresses when performing a memory access. A virtual memory address must then be translated into a physical memory address in order to access the information required by the program. Various mechanisms exist in different computer architectures for performing virtual-to-physical address translations.
One problem with performing address translations is latency. In addition to the time required to access the information from memory, a number of clock cycles may be used to perform the address translation. This latency penalty may become severe or unacceptable in programs that perform frequent memory accesses. One common method of reducing the latency penalty from translating addresses is to use a translation lookaside buffer (TLB). A TLB is a small memory located within a processor, and is used to store virtual-to-physical address translations. A typical TLB may store both the virtual and physical addresses for the most recent address translations. When a program attempts a memory access, it may issue a virtual address. The TLB may then be searched for the issued virtual address. If found, a physical address corresponding to the issued virtual address may then be used to access main memory. Typically, translations are provided on a page basis (e.g. 4 kilobytes, 2 megabytes, 4 megabytes, etc.) and the TLB may store the page portion of the virtual address and page portion of the corresponding physical address.
Despite the advantages provided by a TLB, problems still exist. One such problem occurs on a context switch. In many processors employing a TLB, a context switch results in the removal of all translations stored in the TLB. This is known as a TLB flush. The TLB is flushed because one or more of the address translations corresponding to the context switched out of may be modified, and thus the translations cached in the TLB may no longer be the correct translations. Unfortunately, as the new process runs following the context switch, each memory access requires an address translation, and the TLB must be reloaded. The address translations and reloading of the TLB may result in large latency penalties. These latency penalties may be exacerbated by programs or operating systems that require frequent context switches.
The address translations stored in a TLB are supported by underlying data structures stored in memory. For example, computers that employ paging may store data structures in a page table. Such data structures may include the translations which are loaded into the TLB. While these data structures may be altered for a context which was switched out via a context switch, frequently these data structures are not altered. Despite the fact that the data structures are not altered in all instances, a typical processor may still perform a flush of the TLB. A TLB flush under such circumstances may not be necessary, and may result in large latency penalties as described above.
SUMMARY OF THE INVENTION
The problems outlined above may in large part be solved by a translation lookaside buffer (TLB) flush filter as described herein. In one embodiment, a processor includes a TLB for storing recent address translations. A TLB flush filter monitors blocks of memory from which address translations have been loaded and cached in the TLB. The TLB flush filter is configured to determine if any of the underlying address translations in memory have changed. If no changes have occurred, the TLB flush filter may then prevent a flush of the TLB on a context switch. If changes have occurred to the underlying address translations, the TLB flush filter may then allow a flush of the TLB following a context switch.
In one embodiment, the TLB flush filter uses a region table to track blocks of memory from which address translations have been cached in the TLB. The TLB flush filter may monitor for modifications to the underlying address translations in various blocks of memory (typically page tables or directories). A first context switch may result in a TLB flush, and may then activate the TLB flush filter. TLB flushes may be blocked by the TLB flush filter on subsequent context switches if no changes to the underlying address translations in memory are detected in the region table.
The method of operating the TLB flush filter also includes tracking context switches. In one embodiment, this may be performed by tagging the values of a base address register. The base address register may be configured to store the base address of a page table associated with a particular context. The tag and the actual value of the register may be stored as entries in the region table, and may correspond to specific memory regions. The tag may be stored along with the other data in a TLB entry to associate the translation in that entry with a context. In this way, translations for many contexts may reside in the TLB at the same time. Only translations with context tags that match the current context tag would be available to the current context.
The region table used in one embodiment is implemented with a content addressable memory (CAM) and a random access memory (RAM). The CAM may be used to store information regarding the memory structures from which address translations are loaded into the TLB. Such information may include page directory information and page table information. The RAM may be used to store values of the base address register and its associated tag. A counter may also be used to track the number of base address entries. When the counter overflows, the TLB flush filter may then be deactivated, and the region table cleared. A region counter may also be used to record the number of entries stored in the CAM. An overflow of this counter may also cause the TLB flush filter to be deactivated and the region table cleared. Following the deactivation of the TLB flush filter, a context switch may result in a TLB flush. The TLB flush filter may then be activated once again.
Thus, in various embodiments, the TLB flush filter may prevent unnecessary flushes to a TLB. Since unnecessary flushes to a TLB may be prevented, a new context may be able to use previously cached address translations when none of the underlying address translations have changed. In many cases, this may eliminate the need to repeat the process of translating a virtual address to a physical address and caching it into the TLB. Thus, the latency for a large number of memory accesses may be significantly reduced, and may thereby allow for a significant increase in processor performance.


REFERENCES:
patent: 4053948 (1977-10-01), Hogan et al.
patent: 4669043 (1987-05-01), Kaplinsky
patent: 4700291 (1987-10-01), Saito
patent: 5060137 (1991-10-01), Bryg et al.
patent: 5428757 (1995-06-01), Sutton
patent: 5623619 (1997-04-01), Witt
patent: 5671444 (1997-09-01), Akkary et al.
patent: 5680572 (1997-10-01), Akkary et al.
patent: 5751996 (1998-05-01), Glew et al.
patent: 5752274 (1998-05-01), Garibay, Jr. et al.
patent: 5761691 (1998-06-01), Witt
patent: 5895501 (1999-04-01), Smith
patent: 5924125 (1999-07-01), Arya
patent: 6021481 (2000-02-01), Eickemeyer et al.
patent: 6216214 (2001-04-01), Bryg et al.
patent: 44 16 658 (1994-05-01), None
patent: 93302453 (1993-03-01), None
patent: 2 210 479 (1989-06-01), None
Pentium Pro Family Developer's Manual, vol. 3: Operating System Writer's Manual, Intel, 1996, pp. 11-13 thru 11-26.
Patterson et al., Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers, 1990, pp. 437-438.
Alpha 21164 Microprocessor Hardware Reference Manual, Dec. 1998, Compaq Computer Corporation, Ch. 1, p. 4; Ch. 2, pp. 7, 8, 10-13; Ch. 5, p. 7,

Affiliated with

Also associated with

Rating

Translation lookaside buffer flush filter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Translation lookaside buffer flush filter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Translation lookaside buffer flush filter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3007376