Static information storage and retrieval – Systems using particular element – Flip-flop
Reexamination Certificate
2001-12-21
2002-12-10
Lam, David (Department: 2818)
Static information storage and retrieval
Systems using particular element
Flip-flop
C365S049130, C365S189050, C365S189090
Reexamination Certificate
active
06493255
ABSTRACT:
PRIORITY TO FOREIGN APPLICATIONS
This application claims priority to Japanese Patent Application No. P2000-206861.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a semiconductor integrated circuit device and an information processing device using the semiconductor integrated circuit device, and more particularly, to an insulated-gate type semiconductor integrated circuit device having an associative memory function and an addition function, and an information processing device using the semiconductor integrated circuit device.
2. Description of the Background
A conventional technique related to an associative memory is disclosed in Neil Waste, Kamran Eshraghian: “Principles of CMOS VLSI Design—A System Perspective”, Addison Wesley (June 1988), Page 351 (hereinbelow referred to as a “document 1”).
A conventional technique related to circuitry for high-speed A+B=K judgment processing is disclosed in “Evaluation of A+B=K Conditions Without Carry Propagation”, IEEE Trans. on Computers, Vol. 41, No. 11, pp. 1484-1487, November 1992 (hereinbelow referred to as a “document 2”).
A conventional technique related to circuitry for high-speed addition and address decoding is disclosed in “Address Addition and Decoding without Carry Propagation”, IEICE Trans. (The Journal of the Institute of Electronics, Information and Communication Engineers), Inf. & Syst., Vol. E08-D, No. 1, pp. 98-100, January 1997 (hereinbelow referred to as a “document 3”).
A conventional technique related to high-speed integrated adder and TLB (Translate Lookaside Buffer) circuit is disclosed in Japanese Published Unexamined Patent Application No. Hei 8-212789 (hereinbelow referred to as a “document 4”).
The document 1 discloses that 1-bit memory portion of content-addressable memory (CAM) having a comparison function can be constructed with 2 P-channel MOS transistors and 7 N-channel MOS transistors. Note that the herein throughout P-channel MOS transistor will be abbreviated to PMOS, and N-channel MOS transistor, NMOS.
Further, the document 1 discloses supplying !DATA (! indicates logical invert, and DATA means comparison data given from the outside) to a BIT terminal of a memory cell and DATA to a !BIT terminal, and, if a mismatch in the comparison of those lines occurs, pulling down a MATCH line, i.e. a “hit line”, to a low level. Further, plural bit comparison processing using this memory cell, i.e., processing to judge whether n-bit data inputted corresponds with n-bit data stored in the memory, is well known in the art. To perform plural bit comparison, the MATCH line is shared among plural bits.
Further, it is known that a TLB (Translation Lookaside Buffer, i.e., a memory for logical/physical address translation) computer can be constructed by accessing a RAM based on the result on a CAM hit line.
The document 2 discloses that in the case of judgment of equation A+B=K (where K is a fixed value signal, and A and B are input signals) in plural bits, carry propagation time is conventionally required in an adder. However, the carry. propagation can be omitted in the adder by arrangement of logic circuits.
The document 3 discloses that in the case of address decoding on a word line of memory based on the result of addition between a first value and a second value, address decoding processing can be started without carry propagation time by using a circuit called FAC (Fast-Adder-Comparator). Note that, for this purpose, the algorithm in the document 2 is used.
The document 4 discloses that in case of searching a TLB with the result of addition between a first value and a second value, it is judged at a high speed whether or not the result of addition between the first and second values corresponds with a comparison value, by using the FAC. The high-speed processing is attained by reducing a part of carry propagation time in the adder. Note that, for this purpose, the algorithm in the document 2 is used.
The operation to search an associative memory with a value obtained by addition as search data is an example of processing that may be performed in a MOS integrated circuit device. As a typical example, many computers perform processing to search an associative memory, such as a TLB, with a value obtained by adding two data values as an address.
If the technique disclosed in the document 4 is used in a case wherein the address obtained by addition is provided to the associative memory, it is determined whether the value corresponds with a value of comparison object, i.e., a memory value.
One difficulty that arises when the technique of document 4 is used in such a comparison application is that the number of transistors is large and the logic scale of the TLB circuit is large. For example, in a circuit in the document 4 at page 16 and
FIG. 9
, 1 inverter, 1 two-input AND gate, 1 two-input OR gate and 2 EOR gates are required per 1-bit memory cell of memory requiring association, i.e., per tag memory. In a general CMOS circuit, 1 inverter requires 2 transistors; 1 AND gate, 6 transistors; 1 OR gate, 6 transistors; and 1 EOR gate, 10 transistors. As a result, a total of 34 transistors are required per 1-bit memory cell. This is referred to as result 1.
In addition to the result 1, assuming that the memory bit length requiring 1-entry association is n, an n-input AND gate is required. As the n-input AND gate requires (2n+2) transistors for reasons apparent to those skilled in the art, about 2 transistors are required per 1-bit memory cell. This is referred to as result 2. As the result 1 and the result 2 are added to the 34 transistors, 36 transistors per 1-bit memory cell must be prepared, in addition to the memory circuit transistors.
It is known that a simple memory cell, without search function, can be constructed with 6 transistors, where the memory is a CMOS type SRAM (Static Random Access Memory). The number of transistors for the memory cell, where the technique disclosed in the document 4 is employed, is seven times the number of transistors in this simple SRAM. In the case of LSI, this greatly increases the LSI chip area.
A second difficulty is that n signal lines are required for signals to be inputted into the n-input AND gate, and, thus, a wire channel area for at least (n/2) signal lines is necessary in each of two entry directions of the memory. In the case of LSI, these wire channels also greatly increase the LSI chip area.
A third difficulty is that if a carry signal from a lower bit exists in a bit number of a tag portion in the associative memory, a RAM access word line through which an output from the associative memory is made to the RAM cannot be determined before the result of carry processing is obtained. Accordingly, high speed operation is limited.
As an example of a carry from a lower bit, in a case wherein A[
31
:
0
] is added to B[
31
:
0
], and it is determined whether a bit [
31
:
12
] resultant from the addition is equal to [
31
:
12
] in the associative memory, and a bit
11
:
0
is a lower bit, and a carry to a higher bit from this lower bit may result from the addition between A[
11
:
0
] and B[
11
:
0
].
A temporary added result A[
31
:
12
]+B[
31
:
12
], wherein attention is paid only to the bit
31
:
12
, may be incremented (+1 to the bit
12
in this case) by the carry from the lower bit. In the document 4, as the output from the associative memory depends on the result of any carry from the lower bit, a RAM access word line through which the output from the associative memory is made to the RAM cannot be determined before the result of processing on the carry from lower bit is obtained. For this reason, the operation cannot be performed at a high speed.
Therefore, the need exists for a semiconductor integrated circuit device wherein, in a case of searching a TLB with the result of addition between a first value and a second value, it is determined at a high speed whether or not the result of ad
Nishii Osamu
Tonomura Motonobu
Tsunoda Takanobu
LandOfFree
Semiconductor integrated circuit device and information... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Semiconductor integrated circuit device and information..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Semiconductor integrated circuit device and information... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2994432