Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1998-12-23
2002-07-09
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S122000, C711S205000, C711S206000
Reexamination Certificate
active
06418521
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of electronic data processing systems, and more particularly to virtual memory systems.
BACKGROUND OF THE INVENTION
Many computer systems today use virtual memory systems to manage and allocate computer memory to various processes running within the computer system. Virtual memory systems, as known in the art, allow each process running on the system to operate as if it has control of the full range of addresses provided by the machine, without having to be concerned whether or not there is physical memory at the particular address or not. The operating system then takes care of mapping the virtual address space for each process to the actual physical address space for the system. The mapping from a physical address to a virtual address is typically maintained through the use of page tables.
Over time, computer processors have become faster, and systems have been developed in which multiple processors are used to execute the various computer programs running on a computer system. This has resulted in increased demands for memory performance, including performance of virtual memory systems. One important aspect of virtual memory system performance is insuring that “forward progress” can be made. Forward progress means that the CPU (Central Processing Unit) has access to the memory or other resources it needs to execute the current instruction without waiting.
One way in which the performance of virtual memory systems is improved is through the use of a translation lookaside buffer (TLB). A TLB is a relatively small section of memory on a processor which caches part of the system's virtual address to physical address translations. The translation can often be very large and complex and the data structures that comprise the translation set (often a page-table, where the memory described by a single translation is referred to as a page, or a memory page) can be too large to store efficiently on the processor. Instead, a few elements of the translation set are stored in the TLB which the processor can access extremely quickly. If a required translation for a particular virtual address is not present in the TLB, a “translation miss” occurs and the address translation is resolved using more general mechanisms implemented within hardware or the operating system running on the computer.
A typical computer system will use one of two mechanisms to maintain entries in a TLB. In the first mechanism, software instructions are executed which designate a particular entry in the TLB to modify. This mechanism allows the operating system software running on the computer to maintain the TLB.
In the second mechanism, hardware, such as the memory management unit of a computer system, controls the placement of entries in the TLB using a hardware replacement algorithm. This mechanism allows the TLB to serve as a cache of recently used address translations.
In addition, two types of TLBs have been used in previous computer systems. The first is referred to as a set-associative TLB. A set-associative TLB contains multiple entries used to contain cached virtual to physical address mappings. Each entry in the TLB is used to map a particular set of addresses. In other words, the mapping for a particular address will always be contained, if at all, in a specific set of TLB entries. While set-associative TLBs are generally faster than other types of TLBs, they have the disadvantage that it is difficult to support multiple memory page sizes without maintaining multiple structures.
A second type of TLB is the fully-associative TLB. Previous systems have implemented what will be referred to as a non-hierarchical TLB, that is, a singlelevel TLB structure. In a fully-associative TLB, any entry in the TLB can be used to map any address, there is no predetermined entry used to hold a translation for a particular address. A fully-associative TLB has the advantage that it is relatively easy to support multiple memory page sizes. However, a disadvantage to the non-hierarchical fully-associative TLB is that it cannot guarantee forward progress in those architectures that provide for software control of entries in the TLB. This is because a software instruction could cause the most recently used entry to be replaced, and therefore no longer available to provide a virtual to physical mapping for an address that may be required in the next instruction cycle.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for the present invention.
SUMMARY OF THE INVENTION
In one embodiment of the invention, a fully-associative translation lookaside buffer structure for a computer system providing translation register support and translation cache support includes a first-level TLB
0
memory having a plurality of entries. The TLB
0
entries are modified by the translation register operations and the translation cache operations. The TLB
0
treats translation register operations as if they are translation cache operations.
Also included is a second-level TLB
1
memory operatively coupled to the first level TLB
0
memory. The second-level TLB
1
memory also has a plurality of entries that are modified by translation register operations and translation cache operations.
REFERENCES:
patent: 5412787 (1995-05-01), Forsyth et al.
patent: 5940872 (1999-08-01), Hammond et al.
patent: 5991848 (1999-11-01), Koh
Cheong Fu John Wai
Mathews Gregory S.
Mulla Dean A.
Sailer Stuart E.
Intel Corporation
Schwegman Lundberg Woessner & Kluth P.A.
Song Jasmine
Yoo Do Hyun
LandOfFree
Hierarchical fully-associative-translation lookaside buffer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical fully-associative-translation lookaside buffer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical fully-associative-translation lookaside buffer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2917440