Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-11-17
2002-12-17
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S122000
Reexamination Certificate
active
06496903
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a cash memory device containing a cash memory of 2 way set associative method, and more particularly to a cash memory device having a function for replacing ways by means of an LRU (Least Recently Used) algorithm and the like.
BACKGROUND OF THE INVENTION
With progress of computers, more speeding up in access is demanded. In response to such demand, a system provided with a cash memory device composed of cash memories thereby to intend speeding up in accessing of data increases. However, there is still a need for a cash memory device having a faster processing speed in these days where processing speed of computer increases dramatically.
In computer system, a cash memory and a cash memory device provided with a cash control section capable of high-speed reading/writing has been heretofore been used for eliminating differences in speed between a CPU and a main memory. In such a cash memory device, data transmission between the CPU and a cash memory (main memory) is carried out in line unit.
As a method for allowing data on a main memory to correspond to a line in a cash memory, there is a set associative method wherein the main memory and the cash memory are divided into a plurality of sets (a set of lines: called by the name of “way”), and a certain data on the main memory shall be disposed on only a line contained in each way which has been previously determined. For example, if there are two ways, it is called by the name of “2 way set associative method”.
Such cash memory holds a part of the data stored in the main memory, it is, for instance, memory of the above-mentioned 2 way set associative method. The cash memory is composed of tag RAM (Random Access Memory) retaining an address representing storage positions of data and data RAM retaining the above described data.
In each of two ways in tag RAM, a bit LRU which is used in determination of an old way is maintained in accordance with LRU algorithm. In LRU algorithm, a way which has not been referred to for the longest period of time in two ways is the one corresponding to the above described old way. Bits LRU retained in two ways, respectively, are used for determining a fact which way is an old way in the two ways.
Furthermore, in either a case where a cash hit which means that data to be read exists in cash memory arises, or a case where replacement which means that the data and addresses in cash memory should be updated arises, a cash control section accesses two ways, respectively, to update an old way, whereby bits LRU retained in the respective ways are updated. As a result, the old way shifts from an either way where cash hit (replacement) arose to the other way.
Meanwhile, as mentioned above, when bits LRU are updated as a result of arising of cash hit or replacement in a conventional cash memory device, a cash control section must access to two ways, respectively. More specifically, in case of updating bits LRU, two times of access are required in such that first, the cash control section accesses to either of two ways, and then, it accesses to the other way. Accordingly, there has been such a problem that a processing speed becomes slow by an amount of period of time required for accessing operations of two times in a conventional cash memory device.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a cash memory device by which a processing speed can be elevated.
In order to achieve the above described object, the invention described in a first aspect of the invention relates to a cash memory device utilizing an algorithm wherein replacement is conducted with respect to an old way retaining data which has not been accessed for the longest period of time, characterized in that the cash memory device is composed of a cash memory (corresponding to a primary cash memory
11
in the first embodiment which will be mentioned hereinafter) containing two ways each retaining bits taking a value
0
or
1
together with data and an address, respectively; an old way determining means (corresponding to a primary old way determining circuit
13
in the first embodiment which will be mentioned hereinafter) for determining which way of the two ways is the above described old way on the basis of patterns of two bits retained in the above described two ways; and a control means (corresponding to a primary cash control circuit
14
in the first embodiment which will be mentioned hereinafter) for inverting only the bits retained in a way which has been accessed in the two ways in the case when the present way which has been accessed is the above described old way, while maintaining values of the bits retained in the present way in the case when the way which has been accessed is not the above described old way.
According to the present invention, in the old way determining means, an old way is determined from two ways on the basis of patterns of two bits in 2-bit composition (combinations of “0” and “1”). Thus, when either of two ways is accessed, the control means determines whether or not the way which has been accessed is an old way on the basis of a result of determination by the old way determining means, and when the accessed way is an old way, only the bits retained in this accessed way are inverted. Accordingly, bits in the other way which has not been accessed are not inverted. Namely, in this case, the control means accesses one time to only either way of these two ways.
On one hand, when the way which has been accessed is not the above described old way, the control means maintains values of bits retained in this way. Namely, in this case, the control means accesses to neither of these two ways nor the other.
As described above, according to the invention as described in the first aspect of the invention, it is arranged in such that when an old way is accessed, only the bits retained in the old way in two bits which have been retained respectively in two ways are inverted, so that it is sufficient for only one time access in case of updating bits, whereby a processing speed can be elevated in comparison with two times access in the prior art.
Furthermore, a second aspect of the invention relates to the cash memory device as described in the first aspect of the invention, characterized in that when a way which was cash-hit or replaced is the above described old way, the aforesaid control means inverts only the bits retained in the aforesaid way which was cash-hit or replaced, while when the aforesaid way which was cash-hit or replaced is not the above described old way, values of the bits retained in the present way are maintained.
According to the present invention, an old way is determined from two ways on the basis of patterns of two bits in 2-bit composition (combinations of “0” and “1”) in the old way determining means. Then, when either of two ways is cash-hit or replaced, the control means determines whether or not the way which was cash-hit or replaced is an old way on the basis of a result of determination by the old way determining means, and when the aforesaid way is an old way, only the bits retained in the aforesaid way are inverted. Accordingly, bits retained in the other way are not inverted. Namely, in this case, the control means accesses to only either of two ways one time.
On the other hand, when the way which was accessed is not the aforesaid old way, the control means maintains values of bits retained in the way which was accessed. Namely, in this case, the control means does not accesses to both the ways of these two ways.
As described above, according to the second aspect of the invention, it is arranged in such that when an old way is cash-hit or replaced, only the bits retained in the old way in two bits which have been retained respectively in two ways are inverted. Accordingly, it is sufficient for only one time access in case of updating bits, whereby a processing speed can be elevated in comparison with two times access in the prior art.
Moreover, a third aspect of the invention relates to a cash memory devic
Kato Shinya
Nonaka Takumi
Terunuma Takashi
Moazzami Nasser
Staas & Halsey , LLP
Yoo Do Hyun
LandOfFree
Cache memory device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cache memory device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache memory device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2925851