JP2000181801A - Data substitution system - Google Patents

Abstract

PROBLEM TO BE SOLVED: To increase the use efficiency of a TLB or cache memory by newly providing a bit indicating that a specific entry has been accessed more times than specified and preferentially replacing data which have not been accessed more times than specified. SOLUTION: A register 113 holds V2 and the V2 bit corresponding to a hit entry is set to 1. A group-V2 bit generating circuit 119 ANDs the output of the register 113 by four bits at each time to generate four group-V2 bits. A group-V2 bit reflecting circuit 120 reflects the group-V2 bits on group LRU information from a group-V0 bit reflecting circuit 118. A substitute entry high- order 2-bit generating circuit 121 generates two substitute group high-order 2-bits from the output of the group-V2 bit reflecting circuit 120. A V2-bit reflecting circuit 133 reflects the V2 bits on LRU information from the V0-bit reflecting circuit 132 so that the V2 bits from a selector 131 updates the entry of 1.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multi-layered LRU (Least Read Only) which stores data in a translation index buffer (hereinafter referred to as TLB) or cache memory having a plurality of entries.
The present invention relates to a data replacement system that performs replacement under control of “Recently Used”.

[0002]

2. Description of the Related Art As a conventional data replacement system in a computer device, there is a system for performing data replacement of a TLB or a cache memory by multi-layer LRU control. In the multi-layer LRU control, when data is stored in the storage area of the main storage device, the oldest used data in the cache is sequentially replaced with the most recently used data.

[0003]

However, in such a conventional data replacement system, when an LRU operation of an upper layer (hereinafter, referred to as a group) is performed, even if at least one of the data in each group is accessed, the data is lost. Since the group is up-to-date and does not become a replacement target group, even if there is almost unused data in this group, the data will not be replaced and will not be replaced.
There has been a problem that the LB or the cache memory continues to remain and the use efficiency of the TLB or the cache memory is reduced.

[0004] The present invention solves the above-mentioned problem, and newly sets a bit indicating that a specific entry has been accessed more than a set number of times, and preferentially replaces data that has not been accessed more than the set number of times. As a result, T
An object of the present invention is to provide a data replacement system that can increase the use efficiency of the LB or the cache memory.

[0005]

To achieve the above object,
2. The data replacement system according to claim 1, further comprising means for storing information indicating the number of times of data access for each entry, and migrating the conversion index buffer or cache memory by reflecting the information when a replacement entry is generated. Sometimes, the data of the entry having the smaller number of accesses is preferentially replaced.

According to a second aspect of the present invention, there is provided a data replacement system comprising: a first register for setting a bit corresponding to a registered entry; a plurality of second registers for setting a bit corresponding to a bit entry; And a third register storing a group LRU information bit for determining which of the plurality of groups is the latest or the oldest, and dividing the bits of the bit entry into a plurality of sets. Take the logical sum for each pair,
A hit group generation circuit for generating a hit group;
A hit group reflection circuit for reflecting the hit group in the group LRU information from the third register;
A first group bit generation circuit that divides an output of the first register into a plurality of sets, performs an AND operation for each of the sets, and generates a first group bit; and a group from the third register. A first group bit reflection circuit for reflecting the first group bit in the LRU information; and an output of the second register, divided into a plurality of sets, and a logical product of each of these sets is taken to generate a second group bit. A second group bit generation circuit, a second group bit reflection circuit for reflecting a second group bit in group LRU information from the first group bit reflection circuit, and a replacement from an output of the second group bit reflection circuit A replacement entry high-order bit generation circuit for generating an entry high-order bit; It provided a plurality of fourth register for setting an output of the bit entries reflecting circuit in accordance with the hit group from No. and hit group generation circuit, first
Of the fourth register according to the hit group, and the second selector selects a bit of the hit entry corresponding to the hit group. Causing the fourth selector to select an output of each of the fourth registers in accordance with the replacement entry upper bits, causing the fourth selector to select a first group bit in accordance with the replacement entry upper bits, The second group bit corresponding to the replacement entry upper bits is selected, the first group bit is reflected in the LRU information from the third selector in the first bit reflection circuit, and the second group bit is reflected in the second bit reflection circuit. And the second group bit is reflected in the LRU information from the first group bit reflection circuit, and the second bit is reflected in the replacement entry lower bit generation circuit. To produce a substituted entries lower bits from the output of the bets reflecting circuit, together with the substituted entry high bits is obtained so as to form a substituted entry bits.

[0007]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described below with reference to the drawings. In this case, 16 entries of T
A case where a replacement entry is determined for an LB or a cache memory by using a two-layer LRU will be described.
The 16 entries are divided into 4 entries × 4, and entry 0
3 are called group 0, entries 4 to 7 are called group 1, entries 8 to 11 are called group 2, and entries 12 to 15 are called group 3. In FIG. 1, reference numeral 111 denotes a register serving as a first register.
15), the V0 bit corresponding to the replacement entry is reset to 0 when the mishit signal becomes 1, and the V0 bit corresponding to the registered entry is set to 1 when the registration instruction signal becomes 1.

Reference numerals 112 and 113 denote second registers. Of these, the register 112 holds V1 (0-15). When the mishit signal becomes 1, the V1 bit corresponding to the replacement entry is reset to 0. If the hit signal is 1 and the V0 bit corresponding to the hit entry is 1, the V1 bit corresponding to the hit entry is set to 1, while
The register 113 holds V2 (0-15), resets the V2 bit corresponding to the replacement entry to 0 when the mishit signal becomes 1, and if the hit signal is 1 and the V1 bit corresponding to the hit entry is 1, The V2 bit corresponding to the hit entry is set to 1. Reference numeral 114 denotes a register serving as a third register.
Is a group LRU information 6 bits (a, b, b) that can determine whether any of the four groups is newest or oldest.
c, d, e, f), and when the hit signal becomes 1, the output of the hit group reflection circuit 116 is set.

In this embodiment, the 6 bits (a, b, c, d, e, f) of the group LRU information are 1
If xx11x, group 0 is the oldest group, 01xx
If x1, group 1 is the oldest group; if x01x0x, group 2 is the oldest group; if xx00x0, group 3 is the oldest group; if 0xx00x, group 0 is the latest. If the group is 10 ××× 0, the group 1 indicates the latest group. If the group is × 10 × 1 ×, the group 2 indicates the latest group. (× indicates that either 0 or 1 may be used)

Reference numeral 115 denotes a hit group generation circuit which converts 16 bits of a hit entry into bits 0 to 3
Bits 4 to 7, bits 8 to 11, and bits 12 to 15
A logical sum operation (OR) is performed bit by bit to generate 4 bits of a hit group. 116 is a hit group reflection circuit,
This reflects the hit group in the group LRU information from the register 114 so that the hit group from the hit group generation circuit 115 is updated.

The specific hit group reflection logic is as follows. The output from the hit group generation circuit 115 is HT (0-3), the output from the register 114 is a, b, c, d, e, f, and the output from the hit group reflection circuit 116 is a1, b1, c1, Assuming that d1, e1, and f1, a1 = a.HT (0) '+ HT (1) b1 = b.HT (1)' + HT (2) c1 = c.HT (2) '+ HT (3) d1 = d HT (0) '+ HT (3) e1 = e.HT (0)' + HT (2) f1 = f.HT (1) '+ HT (3)

Reference numeral 117 denotes a group V0 bit generation circuit as a first group bit generation circuit, which outputs the output of the register 1 to V0 (0-3) and V0 (4-
7), V0 (8-11), and V0 (12-15) are ANDed in units of 4 bits to generate 4 bits of group V0 bits. Reference numeral 118 denotes a group V0 bit reflection circuit serving as a first group bit reflection circuit. The group V0 bit reflection circuit includes a group VRU bit from the register 114 so that the group whose group V0 bit is 0 from the group V0 bit generation circuit 117 becomes the oldest. Reflect the V0 bit. When there are a plurality of groups in which the group V0 bit is 0, V L is added to the group LRU information from the register 114 so that the group with the smallest number is the oldest.
Reflect 0 bit. Group V0 bits are all 1
In this case, the output of the register 114 is output as it is.

The specific group V0 bit reflection logic is as follows. The output from the group V0 bit generation circuit 117 is GV0 (0-3), the output from the register 114 is a, b, c, d, e, f, and the output from the group V0 bit reflection circuit 118 is a2, b2, c2. d2, e2, f
Assuming that 2, a2 = a · GV0 (1) + GV0 (0) ′ b2 = b · GV0 (2) + GV0 (1) ′ c2 = c · GV0 (3) + GV0 (2) ′ d2 = d · GV0 (3) ) + GV0 (0) ′ e2 = e · GV0 (2) + GV0 (0) ′ f2 = f · GV0 (3) + GV0 (1) ′

Reference numeral 119 denotes a group V2 bit generation circuit as a second group bit generation circuit, which outputs the output of the register 113 to V2 (0-3) and V2 (4-
7), a logical product operation (AND) of 4 bits of V2 (8-11) and V2 (12-15) is performed to generate 4 bits of group V2 bits. Reference numeral 120 denotes a group V2 bit reflection circuit as a second group bit reflection circuit, which is a group V2 bit reflection circuit from the group V2 bit generation circuit 119.
Group V so that the group with the bit 1 is the latest
The group V2 bits are reflected in the group LRU information from the 0-bit reflection circuit 118. When there are a plurality of groups in which the group V2 bit is 1, the group LRU information is updated so that the group having the highest number among them is updated. When the group V2 bits are all 0,
The output of the group V0 bit reflection circuit 118 is output as it is.

The specific group V2 bit reflection logic is as follows. The output from the group V2 bit generation circuit 119 is GV2 (0-3), and the output from the group V0 bit reflection circuit 118 is a2, b2, c2, d2, e.
2, f2, the output from the group V2 bit reflection circuit 120 is a3, b3, c3, d3, e3, f3. A3 = a2 · GV2 (0) ′ + GV2 (1) b3 = b2 · GV2 (1) ′ + GV2 (2) c3 = c2 · GV2 (2) ′ + GV2 (3) d3 = d2 · GV2 (0) ′ + GV2 (3) e3 = e2 · GV2 (0) ′ + GV2 (2) f3 = f2 · GV2 (1) ) ′ + GV2 (3).

Further, reference numeral 121 denotes a replacement entry high-order 2 bit generation circuit as a replacement entry high-order bit generation circuit, which generates a replacement group, that is, a replacement entry high-order 2 bits from the output of the group V2 bit reflection circuit 120. The replacement entry upper two bits generation logic is as follows. If the output from the group V2 bit reflection circuit 120 is a3, b3, c3, d3, e3, and f3, and the upper two bits of the replacement entry are R (0-1), R (0) = b3'.c3.e3 '+ c3 '・ D3' ・ f
3 ′ R (1) = a3 ′ · b3 · f3 + c3 ′ · d3 ′ · f
3 '.

Reference numeral 122 denotes a register constituting a fourth register.
3 are stored, and when the hit signal is 1 and the hit group from the hit group generation circuit 115 is 1000, the output of the hit entry reflection circuit 128 is set. Reference numeral 123 denotes a register constituting a fourth register. This register 123 stores LRU information for the entries 4 to 7 in the group 1. When the hit signal is 1 and the hit group from the hit group generation circuit 115 is 0100, The output of the hit entry reflection circuit 128 is set.

Reference numeral 124 denotes a register which constitutes a fourth register. This register 124 stores LRU information for the entries 8 to 11 in the group 2 and has a hit signal of 1 and a hit group from the hit group generating circuit 115. Hit entry reflection circuit 12 when
8 output is set. Reference numeral 125 denotes a register that constitutes a fourth register. This register 125 stores LRU information for the entries 12 to 15 in the group 3, and when the hit signal is 1 and the hit group from the hit group generation circuit 115 is 0001. The output of the hit entry reflection circuit 128 is set.

Reference numeral 126 denotes a selector as a first selector. The selector 126 is a register 12 if the hit group from the hit group generation circuit 115 is 1000, a register 13 if the hit group is 0100, a register 14 if the hit group is 0010, and For example, the output of the register 125 is selected. 127 is a selector as a second selector, and this selector 127 is a hit group generation circuit 11
If the hit group from 5 is 1000, bits 0 to 3 of the 16 bits of the hit entry, if 0100, bits 4 to 7,0010, bits 8 to 11, 0001
Then, bits 12 to 15 are selected. A hit entry reflecting circuit 128 reflects the hit entry in the LRU information from the selector 126 so that the hit entry from the selector 127 is updated.

The specific hit entry reflection logic is as follows. The output from the selector 127 is set to HE (0-
3), output from the selector 126 is a4, b4, c4,
Assuming that d4, e4, f4 and the output of the hit entry reflection circuit 128 are a5, b5, c5, d5, e5, f5, a5 = a4.HE (0) '+ HE (1) b5 = b4.HE (1)' + HE (2) c5 = c4 · HE (2) ′ + HE (3) d5 = d4 · HE (0) ′ + HE (3) e5 = e4 · HE (0) ′ + HE (2) f5 = f4 · HE (1) ) ′ + HE (3).

Reference numeral 129 denotes a selector as a third selector. The selector 129 is a register 122 if the upper two bits of the replacement entry from the replacement entry upper two bits generation circuit 121 are 00, and a register 12 if the upper two bits are 01.
Register 124 for 3 and 10, register 1 for 11
Select the output from 25. Reference numeral 130 denotes a selector as a fourth selector. The selector 130 is the upper two bits of the replacement entry from the replacement entry upper two bits generation circuit 121.
If the bit is 00, V0 (0-3); if the bit is 01, V0
(4-7) If it is 10, V0 (8-11) is selected, and if it is 11, V0 (12-15) is selected. Reference numeral 131 denotes a selector serving as a fifth selector. This selector 131 is V2 (0-3) if the upper two bits of the replacement entry from the replacement entry upper two bits generation circuit 121 are 00, and V if it is 01.
If 2 (4-7) and 10, V2 (8-11) is selected; if 11, V2 (12-15) is selected.

Reference numeral 132 denotes a V0 bit reflection circuit as a first bit reflection circuit, which reflects the V0 bit in the LRU information from the selector 129 so as to make the entry with the V0 bit of 0 from the selector 130 the oldest. Let it. When there are a plurality of entries having the V0 bit of 0, the VRU bit is reflected in the LRU information from the selector 129 so that the entry with the smallest number is the oldest. When all the V0 bits are 1, the output of the selector 129 is output as it is.

The specific V0 bit reflection logic is as follows. The output from the selector 130 is connected to VS0 (0-
3), output from the selector 129 is a6, b6, c6,
Assuming that the outputs of the d6, e6, f6 and V0 bit reflection circuits 132 are a7, b7, c7, d7, e7, f7, a7 = a6ａVS0 (1) + VS0 (0) ′ b7 = b6 ・ VS0 (2) + VS0 (1) ′ c7 = c6 · VS0 (3) + VS0 (2) ′ d7 = d6 · VS0 (3) + VS0 (0) ′ e7 = e6 · VS0 (2) + VS0 (0) ′ f7 = f6 · VS0 (3) ) + VS0 (1) ′.

Reference numeral 133 denotes a V2 bit reflection circuit serving as a second bit reflection circuit. The V2 bit reflection circuit 133 adds the V2 bit to the LRU information from the V0 bit reflection circuit 132 so that the entry having the V2 bit of 1 from the selector 131 is updated. To reflect. When there are a plurality of entries having the V2 bit of 1, the LRU information from the V0 bit reflection circuit 132 includes the V2 bit so that the entry having the highest number among them is updated.
Reflect the bits. When all V2 bits are 0,
The output of the V0 bit reflection circuit 132 is output as it is.

The specific V2 bit reflection logic is as follows. The output from the selector 131 is connected to VS2 (0-
3) output from the V0 bit reflection circuit 132 to a7, b
7, c7, d7, e7, f7, V2 bit reflection circuit 13
Assuming that the output of 3 is a8, b8, c8, d8, e8, f8, a8 = a7.VS2 (0) '+ VS2 (1) b8 = b7.VS2 (1)' + VS2 (2) c8 = c7.VS2 ( 2) '+ VS2 (3) d8 = d7.VS2 (0)' + VS2 (3) e8 = e7.VS2 (0) '+ VS2 (2) f8 = f7.VS2 (1)' + VS2 (3)

Further, reference numeral 134 denotes a replacement entry lower-order 2 bit generation circuit as a replacement entry lower-order bit generation circuit, which generates the replacement entry upper-order 2 bits from the output of the V2 bit reflection circuit 133.

The specific logic for generating the lower 2 bits of the replacement entry is as follows. The output from the V2 bit reflection circuit 133 is a8, b8, c8, d8, e8, f8, and the output from the replacement entry lower 2 bit generation circuit 134 is R (2-
Assuming 3), R (2) = b8'.c8.e8 '+ c8'.d8'.f
8 ′ R (3) = a8 ′ · b8 · f8 + c8 ′ · d8 ′ · f
8 '.

Next, the operation will be described. Data is registered in the TLB in the order of entries 0 to 15, and after the first access to all entries is completed, the value of each register is as follows. V0 (0-15) = 1111111111111111 V1 (0-15) = 11111111111111111 V2 (0-15) = 00000000000000000 Group LRU information = 111111 (Replacement group = Group 0) LRU information in Group 0 = 111111 (Replacement entry = Entry 0) LRU information in group 1 = 111111 (substitution entry = entry 4) LRU information in group 2 = 111111 (substitution entry = entry 8) LRU information in group 3 = 111111 (substitution entry = entry 12) (→ substitution entry = 0)

The operation of setting the V2 bit and updating the LRU when entry 0 is accessed in this state will be described below. First, in the V2 bit set operation, when an entry 0 is accessed, the hit signal becomes 1 and the bit 0 of the hit entry becomes 1. Register 112 is
When the hit signal is 1 and the bit 0 of the hit entry is 1,
Since V1 (0) = 1, 1 is set to V2 (0). On the other hand, in the LRU update operation, the hit group 1
Logical OR of 4 bits of 6 bits 100000000000000000 to generate a hit group 1000,
The hit group reflection circuit 116 reflects the hit group 1000 from the hit group generation circuit 115 on the group LRU information 111111 from the register 114, and outputs 011001. When the hit signal becomes 1, the register 114 reads the hit group reflection circuit 116.
Output 011001 is set. At this time, the replacement group is group 1.

On the other hand, as for the lower two bits, the selector 126 outputs the output 1000 of the hit group generation circuit 115.
Output 111111 of the register 122 is selected, and the selector 127 outputs 1000 of the hit entry bits 0 to 3 from the output 1000 of the hit group generation circuit 115.
Select The hit entry reflection circuit 128 reflects the hit entry 1000 from the selector 127 on the LRU information 111111 from the selector 126,
1001 is output. The register 122 has a hit signal of 1 and an output of the hit group generation circuit 115 of 1000.
Therefore, the output 0110 of the hit entry reflection circuit 128
Set 01. At this time, the replacement entry is entry 4.

As described above, the value of each register after accessing the entry 0 is as follows. V0 (0-15) = 1111111111111111 V1 (0-15) = 11111111111111111 V2 (0-15) = 100000000000000000 Group LRU information = 0101001 (Replacement group = Group 1) LRU information in Group 0 = 01101001 (Replacement entry = Entry 1) LRU information in group 1 = 111111 (replacement entry = entry 4) LRU information in group 2 = 111111 (replacement entry = entry 8) LRU information in group 3 = 111111 (replacement entry = entry 12) Thus, 2 for entry 0 After the second access, the group and the LRU information in the group are updated, and V2 (0) is set to 1.

From this state, entries 4 → 5 → 6 → 7 → 8
If there is a second or subsequent access to each entry in the order of → 9 → 10 → 11 → 12 → 13 → 14 → 15 → 0, the value of each register is as follows. V0 (0-15) = 1111111111111111 V1 (0-15) = 11111111111111111 V2 (0-15) = 1000111111111111 TLB replacement entry = 4 Group LRU information = 0101001 (Replacement group = Group1) LRU information in Group0 = 01101001 (Replacement) Entry = entry 1) LRU information in group 1 = 111111 (replacement entry = entry 4) LRU information in group 2 = 111111 (replacement entry = entry 8) LRU information in group 3 = 111111 (replacement entry = entry 12) (→ replacement Entry = entry 4) In this state, a replacement entry generation operation when a TLB mishit occurs will be described below.

Next, the replacement entry generating operation will be described. First, with regard to the upper two bits, the group V0 bit generation circuit 117 sets bits 0 (0-15) of the register 1 to V0 (0-15).
, 3, 4-7, 8-11 and 12-15 are ANDed to generate a group V0 bit 1111. The group V0 bit reflection circuit 118 reflects 1111 from the group V0 bit generation circuit 117 on the group LRU information 010001 from the register 4 and
01 is output.

On the other hand, group V2 bit generation circuit 119
Now, bits 0 to 0 of V2 (0-15) of the register 113
3, 4 to 7, 8 to 11, and 12 to 15
ND is performed to generate group V2 bit 0111. Therefore, the group V2 bit reflection circuit 120 reflects the output 0111 from the group V2 bit generation circuit 119 on the group LRU information 011001 from the group V0 bit reflection circuit 118 and outputs 111111.
The replacement entry upper 2-bit generation circuit 121 is group V
When receiving 111111 from the 2-bit reflection circuit 120, it generates a replacement group, that is, the upper two bits of the replacement entry, and outputs 00.

On the other hand, for the lower 2 bits, the selector 129 outputs the output 0110 from the register 122 by the output 00 from the replacement entry upper 2 bits generation circuit 121.
Select 01. Therefore, the selector 130 receives V from the replacement entry high-order 2 bit generation circuit 121 to generate V
0 (0-3) = 1111 is selected. The selector 131 selects V2 (0-3) = 1000 based on 00 from the replacement entry upper 2-bit generation circuit 121. Also, V
The 0-bit reflection circuit 132 outputs V0 from the selector 130.
(0-3) = 11111 is reflected in the LRU information 011001 from the selector 129, and 011001 is output.
Further, the V2 bit reflection circuit 133 reflects V2 (0-3) = 1000 from the selector 131 on the LRU information 011001 from the V0 bit reflection circuit 132, and 011.
001 is output.

As a result, the replacement entry lower 2 bit generation circuit 134 outputs the LRU from the V2 bit reflection circuit 133.
From the information 011001, lower 2 bits 01 of the replacement entry
Is generated and output. As described above, the replacement entry 4 bits become 0001 and the replacement entry becomes entry 1. Note that the conventional multi-layer L without reflecting the V2 bit is used.
In the RU method, the replacement entry 4 bits is 0100,
The replacement entry is entry 4.

It should be noted that, in the above description, 2
A new V2 bit is set to indicate that the
Although the data that has not been accessed more than once is preferentially replaced to improve the efficiency of the TLB or the cache memory, V3 to n bits indicating that the data has been accessed more than 3 to n times are shown. Is newly established, and 3 to n
Even if data not accessed more than once is replaced preferentially, or data other than data accessed more than a certain number of times by the counter is replaced preferentially, instead of the V bit, the efficiency of the TLB or cache memory is similarly increased. Can be achieved.

[0038]

As described above, according to the present invention, there is provided means for storing information indicating the number of times of data access for each entry, and the information is reflected at the time of generation of the replacement entry, thereby providing the conversion index buffer or the cache. In the case of a memory mishit, the data of the entry with a small number of accesses is preferentially replaced. Therefore, even if data with a high access frequency exists in the group, data with a low access frequency in the group is not replaced. It is possible to avoid remaining without being replaced, and as a result, it is possible to obtain the effect of increasing the use efficiency of the TLB or the cache memory.

[Brief description of the drawings]

FIG. 1 is a circuit diagram showing a data replacement system according to an embodiment of the present invention.

[Explanation of symbols]

111 register (first register) 112, 113 register (second register) 114 register (third register) 115 hit group generation circuit 116 hit group reflection circuit 117 group V0 bit generation circuit (first group bit generation circuit) 118 Group V0 bit reflection circuit (first group bit reflection circuit) 119 Group V2 bit reflection circuit (second group bit reflection circuit) 120 Group V2 bit reflection circuit (second group bit reflection circuit) 121 Replacement entry upper 2-bit generation circuit (Replacement entry high-order bit generation circuit) 122, 123, 124, 125 Register (fourth register) 126 Selector (first selector) 127 Selector (second selector) 128 Hit entry reflection circuit 129 Selector (first 130 selector (fourth selector) 131 selector (fifth selector) 132 V0 bit reflection circuit (first bit reflection circuit) 133 V2 bit reflection circuit (second bit reflection circuit) 134 replacement entry lower 2 Bit generation circuit (replacement entry lower bit generation circuit)

────────────────────────────────────────────────── ───

[Procedure amendment]

[Submission date] November 8, 1999 (1999.11.
8)

[Procedure amendment 1]

[Document name to be amended] Statement

[Correction target item name] Claims

[Correction method] Change

[Correction contents]

[Claims]

1. A translation lookaside buffer having a plurality entries
Or the data in the cache memory is under multi-layer LRU control
In in data replacement system for replacing a first register for setting the bit corresponding to the entry when the data is registered in the entry, a second register for setting the number of accesses information for each entry, a plurality of entries LRU that determines which is the newest or oldest of a plurality of groups obtained by grouping
A third register that stores information bits, a hit group generation circuit that divides the bits of the hit entry into a plurality of sets, performs an OR operation on each of these sets, and generates a hit group; and a third register. and the hit group reflecting circuit the hit group are reflected in the group LRU information from, divides the output of said first register into a plurality of sets, taking the logical product of each of these in each set, the first group the valid bit a first group enable bit generating circuit for generating a first group enable bit <br/> preparative reflecting circuit for reflecting the first <br/> group effective bit group LRU information from said third register, dividing the output of said second register into a plurality of sets, taking the logical product of each of these in each set, the second group valid bit raw to generate a second group valid bit A circuit, a group from the first group enable bit reflects circuit L
Second to reflect the second group valid bit in the RU information
Storing a group enable bit reflects circuit, a substituted entry high bit generating circuit for generating a replacement entry upper bits from the output of the group the effective bit reflects circuit of the second, the LRU information to entries in the group, respectively, the hit signal and A plurality of fourth registers for setting the output of the hit entry reflection circuit according to the hit group from the hit group generation circuit; and a first selector for selecting any of the fourth registers according to the hit group. the second selector for selecting hits entry corresponding to a hit group, the second selector to the LRU information from said first selector
Hit entry that reflects the hit entry from the Kuta
A reflection circuit, a third selector for selecting an output of the fourth register according to the replacement entry upper bit, and a first register according to the replacement entry upper bit.
A fourth selector for selecting an output of the second register, and a second register corresponding to the upper bit of the replacement entry.
A fifth selector for selecting the output of the third selector, and the fourth selector for the LRU information from the third selector.
A first effective bit reflection circuit for reflecting an output from the first valid bit reflection circuit, and the LRU information from the first valid bit reflection circuit .
A second valid bit reflecting circuit for reflecting an output from the selector No. 5, and a replacement for generating a replacement entry lower bit from the output of the second valid bit reflecting circuit and forming a replacement entry bit together with the replacement entry upper bit. A data replacement system comprising an entry lower bit generation circuit.

[Procedure amendment 2]

[Document name to be amended] Statement

[Correction target item name] 0001

[Correction method] Change

[Correction contents]

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multi-layered LRU (Least Read Only) which stores data in a translation index buffer (hereinafter referred to as TLB) or cache memory having a plurality of entries.
Recent l y Used: relates to a data replacement system for replacing the original least recently used) control.

[Procedure amendment 3]

[Document name to be amended] Statement

[Correction target item name] 0005

[Correction method] Change

[Correction contents]

[0005]

To achieve the above object,
Such data replacement system to a first aspect of the invention, entry
When data is registered in the entry, the bit corresponding to the entry
The first register to set the
A second register for setting access count information;
One of the multiple groups that group the entries
Group LRU information bit to determine if
A third register storing the hit entry,
Divide the bits into multiple sets and perform a logical OR on each of these sets.
Hit group generation times to generate hit groups
Route and group LRU information from the third register
Hit group reflection times to reflect the hit group
And the output of the first register are divided into a plurality of sets.
The logical product of each of these sets is taken and the first group is effective.
A first group valid bit generation circuit for generating bits;
The first LRU information from the third register
The first group valid bit that reflects the group valid bit
And the output of the second register is divided into a plurality of sets.
Then, the logical product of each pair is taken and the second group is obtained.
Second group valid bit generation for generating a group valid bit
A circuit from the first group valid bit reflection circuit.
Reflect the second group valid bit in the loop LRU information
A second group valid bit reflection circuit for causing
From the output of the loop valid bit reflection circuit
Replacement entry high-order bit generation circuit for generating the
LRU information for each entry in the group
From the hit signal and hit group generation circuit
Hit entry reflection circuit according to the hit group of
A plurality of fourth registers for setting the force;
Select one of the fourth registers according to the loop
A first selector, and a hit corresponding to the hit group.
A second selector for selecting a security entry, and the first selector
The LRU information from the second selector to the LRU information from the second selector.
A hit entry reflection circuit for reflecting the entry
The fourth register according to the upper bit of the replacement entry
A third selector for selecting the output of the
Select the output of the first register according to the upper bits
And a fourth selector that performs
A fifth selector for selecting the output of the second register according to
And the LRU information from the third selector.
The first valid bit reflecting the output from the selector 4
A reflection circuit and an LRU from the first valid bit reflection circuit.
A second reflecting the output from the fifth selector in the information;
Effective bit reflection circuit and the second effective bit reflection circuit
Generates the lower bits of the replacement entry from the output of
Form replacement entry bits with entry high-order bits
And a replacement entry lower bit generation circuit.
Features.

[Procedure amendment 4]

[Document name to be amended] Statement

[Correction target item name] 0006

[Correction method] Deleted

[Procedure amendment 5]

[Document name to be amended] Statement

[Correction target item name] 0008

[Correction method] Change

[Correction contents]

[0008] In addition, register 112 V1 (0-15)
And when the mishit signal becomes 1, the V1 bit corresponding to the replacement entry is reset to 0, and the hit signal becomes 1
And if the V0 bit corresponding to the hit entry is 1,
To set the V1 bit corresponding to the hit entry to 1
You. Reference numeral 113 denotes a second register. The register 113 holds V2 (0-15). When the mishit signal becomes 1, the V2 bit corresponding to the replacement entry is reset to 0. If the V1 bit corresponding to the hit entry is 1, the V corresponding to the hit entry is
Set two bits to one. Reference numeral 114 denotes a register serving as a third register. This register 114 has 6 bits of group LRU information (a, b, c, d, and d) for determining which of the four groups is the latest or the oldest.
e, f) are stored, and when the hit signal becomes 1, the output of the hit group reflection circuit 116 is set.

[Procedure amendment 6]

[Document name to be amended] Statement

[Correction target item name] 0012

[Correction method] Change

[Correction contents]

Reference numeral 117 denotes a group V0 bit generation circuit as a first group V bit generation circuit (first group valid bit generation circuit) , which is a register 1
Are output as V0 (0-3), V0 (4-7), V0 (8-
11) and V0 (12-15) are ANDed by 4 bits,
Generate 4 bits of group V0 bits. Reference numeral 118 denotes a first group V bit reflection circuit (first group valid bit).
Group reflection circuit) .
This reflects the group V0 bit in the group LRU information from the register 114 so that the group whose group V0 bit from the group V0 bit generation circuit 117 is the oldest. When there are a plurality of groups in which the group V0 bit is 0, the group LR from the register 114 is set so that the group with the smallest number is the oldest.
The V0 bit is reflected in the U information in the group. When all the group V0 bits are 1, the output of the register 114 is output as it is.

[Procedure amendment 7]

[Document name to be amended] Statement

[Correction target item name] 0014

[Correction method] Change

[Correction contents]

Reference numeral 119 denotes a group V2 bit generation circuit as a second group V bit generation circuit (second group effective bit generation circuit) , which outputs the output of the register 113 to V2 (0-3) and V2 (4- 7), V2 (8-1)
1), AND operation (AND) is performed on each of 4 bits of V2 (12-15) to generate 4 bits of group V2 bits. Reference numeral 120 denotes a second group V bit reflection circuit (second group
A group V2 bit reflection circuit as a loop effective bit reflection circuit) , which is a group V2 bit generation circuit 11
The group V2 bit is reflected in the group LRU information from the group V0 bit reflection circuit 118 so that the group whose group V2 bit from 9 is 1 is the latest.
When there are a plurality of groups in which the group V2 bit is 1, the group LRU information is updated so that the group having the highest number among them is updated. When all the group V2 bits are 0, the group V0 bit reflection circuit 1
18 is output as it is.

[Procedure amendment 8]

[Document name to be amended] Statement

[Correction target item name] 0019

[Correction method] Change

[Correction contents]

Reference numeral 126 denotes a selector serving as a first selector. The selector 126 is a register 122 if the hit group from the hit group generation circuit 115 is 1000, a register 123 if the hit group is 0100, a register 124 if the hit group is 0010, and a register 124 if the hit group is 0010. For example, the output of the register 125 is selected. Reference numeral 127 denotes a selector as a second selector. This selector 127 is bits 0 to 3 of 16 bits of the hit entry if the hit group from the hit group generation circuit 115 is 1000, bits 4 to 7 if the hit group is 0100, and bits 4 to 7 if 0010. Bits 8-11,00
If 01, bits 12 to 15 are selected. 128 in front Symbol <br/> hit entry reflecting circuit, which is to reflect the hit entry in LRU information from the selector 126 to the latest hits entry from the selector 127.

[Procedure amendment 9]

[Document name to be amended] Statement

[Correction target item name] 0022

[Correction method] Change

[Correction contents]

Further, 132 is a first V bit reflection circuit.
This is a V0 bit reflection circuit as a (first effective bit reflection circuit) , which is the LR from the selector 129 so that the entry whose V0 bit from the selector 130 is 0 becomes the oldest.
The V0 bit is reflected in the U information. When there are a plurality of entries in which the V0 bit is 0, the LR from the selector 129 is set so that the entry with the smallest number is made the oldest.
The V0 bit is reflected in the U information. When all the V0 bits are 1, the output of the selector 129 is output as it is.

[Procedure amendment 10]

[Document name to be amended] Statement

[Correction target item name] 0024

[Correction method] Change

[Correction contents]

Reference numeral 133 denotes a second V bit reflection circuit.
A V2 bit reflection circuit as a (second effective bit reflection circuit) , which is a V0 bit reflection circuit 132 such that the entry with the V2 bit from the selector 131 is the latest one.
The V2 bit is reflected in the LRU information from. When there are a plurality of entries having the V2 bit of 1, the V2 bit is reflected in the LRU information from the V0 bit reflection circuit 132 so that the entry having the largest number among them is updated. When all V2 bits are 0, the output of the V0 bit reflection circuit 132 is output as it is.

[Procedure amendment 11]

[Document name to be amended] Statement

[Correction target item name] Explanation of sign

[Correction method] Change

[Correction contents]

[Explanation of Signs] 111 register (first register) 112 register 113 register (second register) 114 register (third register) 115 hit group generation circuit 116 hit group reflection circuit 117 group V0 bit generation circuit (first Group existence
Effective bit generation circuit) 118 Group V0 bit reflection circuit (with first group )
Effective bit reflection circuit) 119 Group V2 bit generation circuit (with second group )
Effective bit generation circuit) 120 group V2 bit reflection circuit (with 2nd group )
Effective bit reflection circuit) 121 replacement entry high-order 2 bit generation circuit (replacement entry high-order bit generation circuit) 122, 123, 124, 125 register (fourth register) 126 selector (first selector) 127 selector (second selector) 128 hit entry reflection circuit 129 selector (third selector) 130 selector (fourth selector) 131 selector (fifth selector) 132 V0 bit reflection circuit (first effective bit reflection circuit) 133 V2 bit reflection circuit ( (The second valid bit reflection circuit) 134 Replacement entry lower 2 bit generation circuit (Replacement entry lower bit generation circuit) ───────────────────────────

[Procedure amendment]

[Submission date] January 21, 2000 (2000.1.2
1)

[Procedure amendment 1]

[Document name to be amended] Statement

[Correction target item name] Claims

[Correction method] Change

[Correction contents]

[Claims]

[Procedure amendment 2]

[Document name to be amended] Statement

[Correction target item name] 0005

[Correction method] Change

[Correction contents]

[0005]

To achieve the above object,
The data replacement system according to claim 1, wherein when data is registered in an entry, a first register that sets a bit corresponding to the entry, and a second register that sets access count information for each entry. A third register storing a group LRU information bit for determining which of a plurality of groups obtained by grouping a plurality of entries is latest or oldest, and a hit entry.
A hit group generation circuit that divides the bit of the hit entry, which is the information indicating , into a plurality of sets, performs an OR operation on each of these sets, and generates a hit group, and stores the hit in the group LRU information from the third register. A first group for generating a first group valid bit by dividing a plurality of sets of the output of the first register and a hit group reflection circuit for reflecting the group, and taking a logical product of each of the sets.
A group valid bit generating circuit, a first group valid bit reflecting circuit for reflecting the first group valid bit in the group LRU information from the third register, and an output of the second register divided into a plurality of sets. A second group valid bit generating circuit that generates a second group valid bit by taking a logical product of each of the sets; and a second group valid bit in the group LRU information from the first group valid bit reflecting circuit. , A replacement entry high-order bit generation circuit that generates a replacement entry high-order bit from the output of the second group valid bit reflection circuit, and LRU information for entries in the group. Hit entry according to the hit signal and the hit group from the hit group generation circuit. A plurality of fourth register for setting the output of the reflection circuit, a first selector for selecting one of the fourth register in response to the hit group,
A second selector for selecting a plurality of bits according to the hit group from the hit entries;
And the hit entry reflecting circuit for reflecting the output from the second selector to the LRU information from the selector, and a third selector for selecting the output of the fourth register in accordance with the replacement entry high bits, the second Register 1
Of the outputs, a plurality corresponding to the upper bits of the replacement entry
A fourth selector for selecting a bit of the second register;
A fifth selector for selecting a plurality of bits according to the higher-order bit of the replacement entry from the output of the
A first effective bit reflection circuit for reflecting the output from the fourth selector on the LRU information from the selector, and reflecting the output from the fifth selector on the LRU information from the first valid bit reflection circuit. A second valid bit reflecting circuit for generating a replacement entry lower bit from an output of the second valid bit reflecting circuit and forming a replacement entry bit together with the replacement entry upper bit. It is characterized by having.

Claims (2)

[Claims] 1. A data replacement system for replacing data in a conversion index buffer or a cache memory having a plurality of entries under multi-layer LRU control, means for storing information indicating the number of data accesses for each entry; Means for preferentially replacing the data of the entry with a small number of accesses when the conversion index buffer or cache memory has a mishit by reflecting the data when the replacement entry is generated. 2. A first register for setting a bit corresponding to a registered entry, a plurality of second registers for setting a bit corresponding to a bit entry, and a plurality of groups in which the plurality of entries are grouped. Group LRU to determine which is newest or oldest
A third register storing information bits; a bit group of the bit entry divided into a plurality of sets; a logical sum of each of these sets; a hit group generating circuit for generating a hit group; And a hit group reflection circuit for reflecting the hit group in the group LRU information from the first group. The output of the first register is divided into a plurality of sets, and the logical product of each of these sets is taken to determine the first group bit. A first group bit generation circuit for generating, a first group bit reflection circuit for reflecting the first group bit in the group LRU information from the third register, and an output of the second register divided into a plurality of sets, A second group bit generating circuit that generates a second group bit by taking a logical product of each of the sets; Group LRU from the movies circuit
A second group bit reflecting circuit for reflecting a second group bit in information; a replacement entry upper bit generating circuit for generating a replacement entry higher bit from an output of the second group bit reflecting circuit; an entry in each of the groups A plurality of fourth registers respectively storing LRU information corresponding to the hit groups and setting an output of a bit entry reflection circuit according to a hit signal and a hit group from a hit group generation circuit; and the fourth register according to the hit group. A first selector for selecting any one of the following: a second selector for selecting a bit of a hit entry according to the hit group; and an output of each of the fourth registers according to the upper bit of the replacement entry. A third selector to be selected, and a first group corresponding to the upper bit of the replacement entry. A fourth selector for selecting the first group bit, a fifth selector for selecting a second group bit corresponding to the upper bit of the replacement entry, and reflecting the first group bit in the LRU information from the third selector. A first bit reflection circuit, a second bit reflection circuit for reflecting a second group bit in the LRU information from the first group bit reflection circuit, and a replacement entry lower than an output of the second bit reflection circuit A replacement entry lower bit generation circuit for generating bits and forming a replacement entry bit together with the replacement entry upper bit.