System and method for TLB buddy entry self-timing

Details System and method for TLB buddy entry self-timing System and method for TLB buddy entry self-timing

2000-02-21

2003-03-25

Gossage, Glenn (Department: 2187)

Electrical computers and digital processing systems: memory

Address formation

Address mapping

C711S108000, C365S049130, C365S210130

Reexamination Certificate

active

06539466

ABSTRACT:

TECHNICAL FIELD
This invention relates in general to accessing memory of a computer system, and in particular to a method and system that provide a translation look-aside buffer (TLB) implementing a self-timed evaluation of whether a virtual address for a memory access request is found within the TLB, which reduces the latency involved in accessing the memory to satisfy the memory access request.
BACKGROUND
Computer systems may employ a multi-level hierarchy of memory, with relatively fast, expensive but limited-capacity memory at the highest level of the hierarchy and proceeding to relatively slower, lower cost but higher-capacity memory at the lowest level of the hierarchy. The hierarchy may include a relatively small, fast memory called a cache, either physically integrated within a processor or mounted physically close to the processor for speed. The computer system may employ separate instruction caches (“I-caches”) and data caches (“D-caches”). In addition, the computer system may use multiple levels of caches. The use of a cache is generally transparent to a computer program at the instruction level and can thus be added to a computer architecture without changing the instruction set or requiring modification to existing programs.
Cache structures implemented for processors typically include a translation look-aside buffer (TLB), which is generally a large content addressable memory (CAM) structure. Generally, when an instruction being executed by the processor
19
(as shown in
FIG. 2A
) requests access to memory (e.g., to read from or write to an address), the cache's TLB receives a virtual address for such memory access request and translates the virtual address to a physical address. That is, the TLB translates a received virtual address to a physical address of the cache memory (e.g., random access memory (RAM)) to be accessed to satisfy the memory access request. More specifically, a TLB typically comprises multiple entries of addresses, and when the TLB receives a virtual address it compares the virtual address with its entries to determine if a match is made for the cache. If the TLB determines that a match is made for one of its entries, indicating that the requested address is contained in the cache, a WORD line is activated or fired (e.g., transitions from a low voltage value to a high voltage value) causing the appropriate physical address to be accessed in the cache memory (e.g., in the RAM memory). That is, if a match is made for a received virtual address within the TLB, then the TLB outputs the appropriate physical address and the WORD line is fired causing such physical address to be accessed in the cache data arrays (e.g., RAM memory) to satisfy the memory access request.
Therefore, the cache TLB is necessarily in the critical path (the path required for completing an instruction) for a memory access request. The TLB is a fundamental part of all microprocessors in that an access of the cache cannot begin for a memory access request until the physical address is obtained for such memory access request from the TLB. Therefore, it is very critical that a TLB executes as fast as possible. That is, because the TLB necessarily affects the speed at which an instruction can be satisfied, it is desirable to have the TLB implemented in a manner such that instructions requiring to access the cache can be satisfied in a timely manner (i.e., quickly). However, prior art TLB implementations result in an undesirably long time in evaluating whether a match exists for a received virtual address within the TLB. As a result, prior art TLB implementations consume an undesirably long time before firing the WORD line to access the appropriate physical address in the cache memory when a match occurs within the TLB. Therefore, prior art implementations require an undesirably long time to satisfy a memory access request.
Turning to
FIG. 1
, an example of a TLB CAM
10
of the prior art is shown. As shown, TLB CAM
10
comprises circuitry
12
, which is the circuitry for a single bit of the TLB CAM
10
. Such circuitry of a TLB CAM
10
is well-known in the art, and therefore will not be described in great detail herein. In the exemplary TLB CAM
10
of
FIG. 1
, such a TLB CAM comprises 128 entries with each entry having 52 bits. Thus, circuitry
12
would be duplicated 51 times to provide a 52-bit entry, and such a 52-bit entry would be duplicated 127 times to provide a 128 entry TLB. Because such a TLB CAM is commonly implemented as an array having 128 rows of entries and 52 columns, the TLB entries may be referred to herein as rows. It should be understood that in various implementations TLB CAM
10
may have any number of entries (rows) with each entry having any number of bits (columns). TLB CAM
10
may receive a 52-bit virtual address for a memory access request, and compare the virtual address with its entries to determine whether a match is achieved in the TLB CAM for the received virtual address. As further shown in
FIG. 1
, TLB CAM
10
comprises a MATCH line through each bit circuitry
12
of an entry. TLB CAM
10
comprises a separate MATCH line (not shown) for each of the 128 entries, and each MATCH line indicates whether a match is made for its corresponding entry and a received virtual address.
Generally, each bit of an entry has a field effect transistor (FET) that is used to indicate whether it matches a corresponding bit of a received virtual address. For example, bit circuitry
12
of
FIG. 1
includes an N-channel field effect transfer (NFET)
26
that is coupled to the MATCH line for that entry. NFET
26
is implemented such that if the bit circuitry
12
of this entry fails to match the corresponding bit of a received virtual address, then the NFET
26
pulls the MATCH line for this entry low. That is, the MATCH line is initially at a high voltage level, and if all the bits of the entry match a received virtual address, then the MATCH line remains at a high voltage level to indicate that the corresponding entry matches the virtual address (i.e., that a “hit” is achieved for the virtual address in the corresponding entry). However, if one or more bits fail to match the received virtual address, then such mismatching bit(s) pull the MATCH line low, thereby indicating that a hit was not achieved for the virtual address in the corresponding entry. Because every bit of the TLB CAM
10
includes such an NFET
26
, a very small NFET
26
is typically utilized to reduce the amount of surface area and cost required for implementing the TLB CAM
10
. Therefore, each NFET
26
of the TLB's bits is typically capable of discharging the MATCH line at a relatively slow rate. That is, each NFET
26
is typically a small NFET that requires a relatively long time to discharge a MATCH line because of the parasitic capacitance on the MATCH line presented by the other cells coupled to such MATCH line. Although, if many bits of an entry all fail to match the virtual address, thereby causing many of such NFETs
26
to join in pulling down the MATCH line, such an entry is capable of discharging the MATCH line more quickly than an entry in which only a few bits fail to match the virtual address.
It should be recognized that it is desirable to determine the MATCH line value for each entry as soon as possible so as to allow the cache memory to be accessed to satisfy a memory access request in a timely manner. Therefore, it is desirable to evaluate the value of the MATCH lines for a TLB as soon as possible to decrease the time required to satisfy a memory access request. However, care must be taken to prevent the MATCH lines from being accessed prematurely (i.e., before an entry has completed pulling the MATCH line low for a mismatch) to avoid an erroneous access of a physical address in the cache memory. For example, suppose a match is achieved for a virtual address in a first entry of the TLB, and suppose a second entry of the TLB does not match the virtual address. If the MATCH lines are evaluated before the MATCH line for the second entry has had sufficient opport

Affiliated with

Also associated with

Rating

System and method for TLB buddy entry self-timing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for TLB buddy entry self-timing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for TLB buddy entry self-timing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3064853