Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2000-08-31
2004-03-30
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
Reexamination Certificate
active
06715057
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a processor that includes a large range of page sizes stored in main memory. More particularly, the invention relates to a computer system with a multi-level page table and translation lookaside buffer (“TLB”) that efficiently maps virtual page addresses to physical page addresses for a memory system containing variable sized pages. Still more particularly, the present invention relates to a system that eliminates one level of the page table to efficiently map addresses of large pages in the memory system.
2. Background of the Invention
Almost all computer systems include a processor and a main memory. The main memory functions as the physical working memory of the computer system, where data is stored that has been or will be used by the processor and other system components. In computer systems that implement “virtual memory,” software programs executing on the computer system reference main memory through the use of virtual addresses. A memory management unit (“MMU”) translates each virtual address specified by a software program instruction to a physical address that is passed to the main memory in order to retrieve the requested data. The use of virtual memory permits the size of programs to greatly exceed the size of the physical main memory and provides flexibility in the placement of programs in the main memory.
Implementing a virtual memory system requires establishing a correspondence between virtual address space and physical address space in the main memory. The most common technique by which to have virtual address space correspond with physical address space is by using a paging system. A paging system involves separately dividing virtual address space and its corresponding physical address space into contiguous blocks called pages. Each page has a virtual page number (“VPN”) address in virtual address space that corresponds to the physical page number (“PPN”) address of the page in physical address space.
For each access to main memory, a virtual page number address in virtual address space is translated into the corresponding physical page number address in physical address space and a page offset within the physical page is appended to the physical page number address. Thus, the virtual address subdivided into a Virtual Page Number Address:Page Offset is translated into a physical address consisting of Physical Page Number Address:Page Offset. The physical address is then used to access main memory. Translation of the virtual page number address into its corresponding physical page number address occurs through the use of page tables stored in physical main memory.
In order to reduce the total number of page table main memory accesses required per virtual-to-physical address translation, one or more translation-lookaside buffers are often provided in the MMU. TLB accesses reduce the overall average time required to perform the steps of a virtual-to-physical address translation. A TLB is a cache-like memory, typically implemented in Static Random Access Memory (“SRAM”) and/or Content Addressable Memory (“CAM”), that holds virtual page number address to physical page number address translations that have recently been fetched from the page table in physical main memory.
Access to a TLB entry holding an output physical page number address corresponding to an input virtual page number address obviates the need for and is typically many orders of magnitude faster than access to the page table in main memory.
If the TLB does not contain the requested translation (i.e., a TLB “miss” occurs) then the MMU initiates a search of page tables stored in main memory for the requested virtual page number address. TLB miss handler software executing on the MMU then loads the physical page number address referenced by the virtual page number address into the TLB, where it may be available for subsequent fast access should translation for the same input virtual page number address be required at some future point.
Modem day computer systems implement large virtual address spaces requiring many virtual address bits. A simple page table array with one entry for each possible input virtual page number address, as commonly used in the prior art, is not a feasible solution for implementing the page table because of the slow translation times for such large input addresses and the enormous size of the page table array. To keep page tables required for address translation to a reasonable size and reduce translation times, some virtual to physical address translation schemes implement address translation in multiple stages. In a typical implementation, each stage of the virtual-to-physical address translation requires one or more accesses to the page table that is held in physical main memory. Each stage of the translation requires accessing a different level of the page table using a subfield of bits from the virtual address. Thus, for a virtual memory system that incorporates three stage address translation, the page table may be broken up into three levels with the virtual page number address field from the virtual address being divided into three subfields of bits. One advantage of multistage address translation is the reduction of the amount of main memory needed to store the page tables. The reduction of main memory needed to store the page tables comes from the ability to sparsely populate the page tables and the ability to page out parts of the page table.
The final stage of address translation implemented by the bottom level of the page table (e.g., three level system this would be the third level) prior to generating the physical page number address may be virtually mapped to provide quick access to the page table entries on a TLB miss. Prior to walking each level of the page table to generate the physical page number address, a page table lookup of the virtually mapped bottom level page table entry would occur. The virtually mapped page table lookup to the TLB may also result in a miss, thus resulting in a double translation lookaside buffer miss (virtual page number address TLB miss and virtually mapped final level of the page table TLB miss). Such double TLB misses are slow since a complete walk of the page table structure is then required. Thus, for the three level page table example, a double translation lookaside buffer miss would result in the physical page number address being generated by sequential multiple accesses to each of the three levels of the page table.
One solution to reduce translation lookaside buffer misses is to use larger page sizes so that the same physical main memory can be described by many fewer virtual page number addresses. TLB misses for a system with large page sizes are much less likely. For example, if the small page sizes are such that physical main memory can be mapped into a total of 16 pages while the TLB can only hold eight virtual-to-physical page translations, on the average a random TLB access will miss 50% of the time. Alternatively, if the virtual memory system is implemented with large page sizes such that physical main memory can be mapped into a total of eight pages while the TLB can hold eight virtual-to-physical page translations, an access to the TLB will never miss. However, large page sizes also result in more expensive and complex hardware to access the page offset within the physical page and increase unused fields within the pages (due to internal fragmentation). For this reason, high-performance processors generally allow any of a plurality of page sizes to be selected for different purposes.
High performance processors implementing a virtual memory system that allow multiple page sizes regardless of the page size use the same strategy for all page sizes to translate the virtual page number address into the physical page number address. In such systems, accesses to large size pages using the same translation mapping as small size pages may resul
Kessler Richard E.
Samberg Eileen J.
Wiedemeier Jeffrey G.
Choi Woo H.
Hewlett--Packard Development Company, L.P.
Kim Matthew
LandOfFree
Efficient translation lookaside buffer miss processing in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient translation lookaside buffer miss processing in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient translation lookaside buffer miss processing in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3244533