Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2003-01-06
2004-10-26
Anderson, Matthew D. (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S159000
Reexamination Certificate
active
06810473
ABSTRACT:
BACKGROUND OF INVENTION
As shown in
FIG. 1
, a typical computer (
24
) includes a processor (
26
), memory (
28
), a storage device (
30
), and numerous other elements and functionalities found in computers. The computer (
24
) may also include input means, such as a keyboard (
32
) and a mouse (
34
), and output means, such as a monitor (
36
). Those skilled in the art will appreciate that these input and output means may take other forms.
The processor (
26
) may contain internal memory (not shown), also called cache memory, in addition to the memory (
28
) that is external to the processor (
26
). The cache memory may provide a faster access time to load or store information compared to the memory (
28
). However, the cache memory typically holds less information than the memory (
28
).
FIG. 2
shows a block diagram of a typical memory system (
200
). In
FIG. 2
, a typical cache memory (
210
) and a typical main memory (
220
) are shown. The cache memory (
210
) may be internal to a processor (not shown), whereas the main memory (
220
) may be external to the processor. The cache memory (
210
) may have fewer address locations than the main memory (
220
). Consequently, the cache memory (
210
) may contain less information than the main memory (
220
).
A typical programming technique is to maintain virtual address locations. Virtual address locations improve the file size and speed of execution of a program. Furthermore, a programmer may be relieved of the task of managing a large address space. The virtual address locations may reference locations in the cache (
210
). In turn, the cache may maintain information that is a copy of a physical address in main memory (
220
). When a memory access occurs, the virtual address may be converted to a physical address. Page tables (not shown) record the translation of a virtual address to a physical address.
Page tables are typically large, and thus they are stored in the main memory (
220
). A small portion of the page tables may also be stored in the cache (
210
). Accordingly, a virtual memory access may take twice as long as a direct physical memory access because a first memory access to the main memory (
220
) and/or the cache (
210
) is needed to obtain the physical address translated from the virtual address and a second memory access to the main memory (
220
) and/or the cache (
210
) is needed to obtain the information.
One remedy is to remember recent address translations. The principle of temporal and spatial locality states that programs tend to reuse data and instructions (i.e., information) that a program has recently used. The principle of temporal locality states that recently accessed information is likely to be accessed in the near future. The principle of spatial locality states that information whose memory addresses are near one another tends to be referenced close together in time.
Accordingly, virtual memory accesses have locality. By keeping address translations in a special buffer, a memory access rarely requires an access to the main memory (
220
) and/or the cache (
210
) to translate a virtual address. A translation look-aside buffer, or TLB, is used to maintain a list of recent virtual address translations.
A fully associative translation look-aside buffer may allow a new entry to be added at any location. A fully associative translation look-aside buffer may, however, replace a least accessed entry. The least accessed entry may occur at any location in the in the fully associative translation look-aside buffer. A least accessed replacement algorithm follows the principle of locality.
In
FIG. 2
, a fully associative translation look-aside buffer (
230
) includes a comparison circuit (
240
), registers (
245
), and buffers (
250
). The buffers (
250
) maintain address translations from previous memory accesses. The registers (
245
) may maintain information about which entries in the buffers (
250
) are used or are available to add additional address translation entries. The comparison circuit (
240
) compares a virtual address used in a memory access to virtual addresses stored in the buffers (
250
). The comparison circuit (
240
) determines whether the virtual address has recently been translated. If the virtual address is in the buffers (
250
), a physical address, corresponding to the virtual address used in a memory access, is output from the fully associative translation look-aside buffer (
230
).
The fully associative translation look-aside buffer (
230
) may be required to add an additional address translation entry when all entries in the fully associative translation look-aside buffer (
230
) are occupied with previous address translation entries. The comparison circuit (
240
) may determine which address translation entry should be replaced based on a state of the registers (
245
).
Increasing a size of the fully associative translation look-aside buffer (
230
) increases a number of address translation entries that may be maintained thereby also increasing memory system performance. However, increasing the number of address translation entries in the fully associative translation look-aside buffer (
230
) may entail a large hardware design effort.
SUMMARY OF INVENTION
According to one aspect of the present invention, a method for address translation entry replacement comprising determining whether there is an invalid address translation entry in a first translation look-aside buffer; if there is an invalid address translation entry in the first translation look-aside buffer, replacing the invalid address translation entry in the first translation look-aside buffer; if there is no invalid address translation entry in the first translation look-aside buffer, determining if there is an invalid address translation entry in a second translation look-aside buffer; and if there is an invalid address translation entry in the second translation look-aside buffer, replacing the invalid address translation entry in the second translation look-aside buffer.
According to one aspect of the present invention, an apparatus comprising a first translation look-aside buffer where the first translation look-aside buffer comprises a first plurality of invalid registers associated with each of a first plurality of address translation entries; a second translation look-aside buffer where the second translation look-aside buffer comprises a second plurality of invalid registers associated with each of a second plurality of address translation entries; a first comparison circuit where the first comparison circuit is arranged to determine whether there is an invalid bit in the first plurality of invalid registers; and a second comparison circuit where the second comparison circuit is arranged to determine whether there is an invalid bit in the second plurality of invalid registers.
According to one aspect of the present invention, an apparatus comprising means for determining whether there is an invalid address translation entry in a first translation look-aside buffer; means for replacing an invalid address translation entry in the first translation look-aside buffer if there is an invalid address translation entry in the first translation look-aside buffer; means for determining whether there is an invalid address translation entry in a second translation look-aside buffer if there is no invalid address translation entry in the first translation look-aside buffer; and means for replacing an invalid address translation entry in the second translation look-aside buffer if there is an invalid address translation entry in the second translation look-aside buffer and there is no invalid address translation entry in the first translation look-aside buffer.
Other aspects and advantages of the invention will be apparent from the following description and the appended claims.
REFERENCES:
patent: 5497480 (1996-03-01), Hayes et al.
patent: 2002/0065993 (2002-05-01), Chauvel
Anderson Matthew D.
Osha & May L.L.P.
Sun Microsystems Inc.
LandOfFree
Replacement algorithm for a replicated fully associative... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Replacement algorithm for a replicated fully associative..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Replacement algorithm for a replicated fully associative... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3328692