Dynamic variable page size translation of addresses

Details Dynamic variable page size translation of addresses Dynamic variable page size translation of addresses

2001-03-16

2003-04-15

Nguyen, Hiep T. (Department: 2187)

Electrical computers and digital processing systems: memory

Address formation

Address mapping

Reexamination Certificate

active

06549997

ABSTRACT:

BACKGROUND
1. Field of the Invention
The present invention relates to the field of electronic memories and, more particularly, to dynamic variable page size translation of addresses. More specifically, the invention relates to translation look-aside buffers (TLB's) used in variable page size translation of memory addresses. Accordingly, the general objects of the invention are to provide novel methods, apparatus, data structures, etc. of such character.
2. Background of the Invention
Most modem data processing equipment relies on virtual memory to help manage the flow of data. Operating systems using such virtual memory map the user's view of the memory (the virtual address) to the actual physical location of data in the memory (the physical address). These mappings are either stored in the main memory or cached in buffers in the system. These buffers are called translation look-aside buffers and contain the mapping information necessary to translate virtual addresses into physical addresses.
Generally, memories are broken into separate blocks called pages and for a variety of reasons, these pages can vary greatly in size. Therefore, typical processors support multiple page sizes. The page size determines the number of bits in the virtual address that need to be translated because the offset for a given page can be derived from certain bits in the virtual address. For example, in the case of a 4 Kbyte page size, the 12 least significant (in terms of magnitude) bits of the virtual address (VA[
12
:
0
]) need not be translated. In the case of a 4 Mbyte page size, the 22 least significant bits (VA[
21
:
0
]) are not translated.
Typical translation look-aside buffers store size-field data in a page table entry array and (with the use of some peripheral circuitry) use this information to determine how many of the virtual address bits need to be translated and how many of the virtual address bits can be bypassed. These conventional TLB's utilize external control logic to decode the size-field data read from the TLB and additional bypass multiplexers to select either the virtual address bits or the physical address bits, depending on the situation for a particular address. Because such circuitry is synchronous, the additional control logic and multiplexers add significant delay in the critical path of the address data. This delay represents an undesirable obstacle to the implementation of higher clock-speed processors. Given the constant drive to create faster and faster processors, limits such as these pose a significant impediment to the achievement of higher clock speeds demanded by the next generation of processors. Conventional TLB's of this nature are described in more detail immediately below.
FIG. 1
is a diagram of a conventional variable page size TLB
100
shown in combination with the requisite peripheral circuitry. TLB
100
and the peripheral circuitry of
FIG. 1
, collectively, receive a virtual address VA[
63
:
0
]
101
and translate that address into a translated physical address TPA[
40
:
0
]. In particular, TLB
100
includes a content addressable memory (CAM)
102
and a page table entry array (RAM)
104
. A representative page table entry
106
in RAM
104
stores a validity bit (“V”)
108
, size-field bits (“SZ[
1
:
0
]”)
110
, physical address bits (“PA[
40
:
13
]”)
112
and status bits (“STATUS[
8
:
0
]”)
114
. As with the entirety of TLB
100
, the function of the validity bit
108
and status bits
114
are well known in the art. Since these components, however, are less important to the operation of the invention, they need not be discussed in further detail herein. It will also be understood that the virtual addresses discussed herein have omitted various “content” bits which vary from system to system.
FIG. 1A
is a table showing typical encoded size-field data for the four different page sizes supported by TLB
100
of FIG.
1
. As shown in
FIG. 1A
, the size-field data consists of 2 bits, SZ[
1
:
0
], each different combination of these two bits representing a different page size. The data structure for the information stored in each page table entry is shown in
FIG. 1B
(see also page table entry
106
of FIG.
1
). Those of ordinary skill will recognize the structure and function of data structure
130
.
Referring back to
FIG. 1
, external size-field control logic
116
is coupled to the TLB
100
. Further, external multiplexers
118
,
120
, and
122
are coupled to TLB
100
, virtual address VA[
63
:
0
]
101
and size-field control logic
116
. Among other things it will be appreciated that TLB
100
includes a plurality of page table entries
106
′ which are substantially identical in function and structure to entry
106
. The operation of TLB
100
will now be illustrated in conjunction with the encoded size-field data shown in FIG.
1
A.
With joint reference to
FIGS. 1 and 1A
, CAM
102
receives VA[
63
:
0
]
101
, generates a CAM match signal
124
when the virtual address matches a virtual address tag in CAM
102
and sends match signal
124
to page table entry array
104
. In response to CAM match signal
124
, a corresponding page table entry of RAM
104
(taken to be entry
106
for purposes of illustration) is selected to output the stored physical address bits
112
. Note that virtual address bits VA[
12
:
0
] of the translated physical address PA [
40
:
0
] are never translated because virtual address bits VA[
12
:
0
] (corresponding to the minimum page size 8 Kbytes) can always be used as the translated physical address bits TPA[
12
:
0
]. Similarly, physical address bits [
40
:
22
] are not fed into multiplexers
118
,
120
and
122
but used directly as translated physical address bits TPA[
40
:
22
] (always translated), because these bits represent blocks of data larger than the maximum page size of 4 Mbytes.
Continuing the discussion above with respect to address bits which are not directly output, CAM match signal
124
identifies a page table entry which corresponds to the matched virtual address tag of CAM
102
and size-field control logic
116
receives the size-field data SZ[
1
:
0
] from that page table entry. The size-field control logic then decodes this data and generates select signals which control multiplexers
118
,
120
, and
122
. If SZ[
1
:
0
] is “11” (representing a 4 Mbyte page size), then size-field control logic
116
generates select signals to select the virtual address bits VA[
21
:
19
], VA[
18
:
16
], and VA[
15
:
13
] in multiplexers
118
,
120
, and
122
, respectively. This is because none of the physical address bits PA[
21
:
19
], PA[
18
:
16
] and PA[
15
:
13
] are necessary. If SZ[
1
:
0
] is “10” (representing a 512 Kbyte page size), then size-field control logic
116
generates select signals to select the physical address bits PA[
21
:
19
] in multiplexer
118
and virtual address bits VA[
18
:
16
] and VA[
15
:
13
] in the multiplexers
120
and
122
, respectively. This is because the physical address bits PA[
18
:
16
] and PA[
15
:
13
] are not necessary. If SZ[
1
:
0
] is “01” (representing a 64 Kbyte page size), then size-field control logic
116
generates select signals to select the physical address bits PA[
21
:
19
] and PA[
18
:
16
] in multiplexers
118
and
120
, respectively, and virtual address bits VA[
15
:
13
] in multiplexer
122
. This is because the physical address bits PA[
15
:
13
] are not necessary. Finally, if SZ[
1
:
0
] is “00” (representing a 8 Kbyte page size—the minimum page size), then size-field control logic
116
generates select signals to select the physical address bits PA[
21
:
19
], PA[
18
:
16
] and PA[
15
:
13
] in multiplexers
118

Affiliated with

Also associated with

Rating

Dynamic variable page size translation of addresses does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic variable page size translation of addresses, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic variable page size translation of addresses will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3094850