Content addressable memory addressable by redundant form input

Details Content addressable memory addressable by redundant form input Content addressable memory addressable by redundant form input

1998-08-13

2002-01-22

Nguyen, Hiep T. (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C365S049130

Reexamination Certificate

active

06341327

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a content addressable memory suitable for use with redundant form input signals.
It is a goal of memory systems to fulfill requests for stored data with as little delay as possible. Often, the requesting agent cannot achieve forward progress without the requested information. This principle holds true for content addressable memories (“CAMs”).
However, increasingly, arithmetic operations are included as part of a memory operation. That is, a request for data defines one or more arithmetic operations whose result is to be applied to a memory as an address. Any time spent completing an arithmetic operation is delay introduced to a memory request that includes the arithmetic operation. Thus, it becomes a goal of memory systems to reduce the time required to perform any arithmetic operations included in a memory request.
FIG. 1
illustrates a traditional adder circuit. There, an addition performed on two multi-bit values X (X=X
0−
X
3
) and Y (Y=Y
0−
Y
3
) generates a multi-bit sum S (S=S
0−
S
3
) and a carry out C
out
. The traditional adder includes an internal carry chain wherein a carry from a first bit position i may affect the value of the sum at a second bit position i+1. Carries must propagate through the entire length of the adder before true results may be obtained therefrom. The internal carry chain causes the traditional adder to be slow. There is a need in the art for a memory system that improves the processing speed of memory requests that require mathematical preprocessing operations.
Redundant form adders are known to be faster than traditional adders. Shown in
FIG. 2
, a redundant form adder omits the internal carry chain that characterizes the traditional adder. Instead, for each bit position i of inputs X, Y and Z, the redundant form adder generates a multi-bit sum Ŝ
i
. The output Ŝ (Ŝ=Ŝ
0−
Ŝ
n
) is said to be in “redundant form” because two bits are used per bit position rather than a single bit to represent a sum result that may be more efficiently represented by only a single bit. To reduce the redundant form result Ŝ to non-redundant form, the two bits of each “bit position” Ŝ
i
may be input to a traditional adder, such as the adder of FIG.
1
.
The redundant form adder provides significant processing advantages over traditional adder, particularly where a number of additions are performed in sequence. For a plural number of sequential adds, the traditional adder must complete the carry chain of each add before it may begin a subsequent add. However, redundant form processing permits quick additions to be performed. A carry chain may be omitted until a redundant form sum is obtained from the final addition. When the redundant form sum is obtained, it may be converted to non-redundant form by use of only a single carry chain.
No known memory system retrieves data based on redundant form input data.
Content addressable memories are known per se. A block diagram of a known CAM
100
is shown in FIG.
3
. The CAM
100
includes a plurality of registers
110
each of which stores data. When input data is applied to the CAM
100
, it generates an output identifying which registers, if any, store data having the same value as the input data. Typically, the CAM
110
generates an output signal having a one-bit flag per register position in the CAM. For example, the flag may be enabled if the register stores data that is equal to the input signal and disabled otherwise.
The CAM
100
contains match logic
120
associated with each register
110
. The match logic
120
performs a bit-by-bit comparison of the input data and the data stored in the register
110
. As shown in
FIG. 4
, it includes selection switches
130
-
160
, one provided for each bit position C
0
-C
3
of data in the register
110
. Each switch
130
-
160
is controlled by the value of the associated bit position in the register
110
. The output of each selection switch
130
-
160
is input to an AND gate
170
.
Typically, for each bit position D
i
in the input signal, the match logic generates its complement, Di# (not shown). D
i
and Di# are input to the switch associated with register it position i. The value of the data stored in the register at bit position i controls which of D
i
and Di# are output to the AND gate
170
from the switch.
The AND gate
170
generates a signal representing a logical AND of the values output from each of the selection switches
130
-
160
. The AND is a logical 1 only when the signal input to the CAM
100
has the same value as the data stored in the register
110
.
No known memory system operates on redundant form input data. Accordingly, there is a need in the art for a content addressable memory system that reduces latency of memory requests when those requests include arithmetic operations. Further, there is a need in the art for a content addressable memory that operates on redundant form input data.
SUMMARY OF THE INVENTION
Embodiments of the present invention provide a content addressable memory addressable by redundant form input data.


REFERENCES:
patent: 3527930 (1970-09-01), Cocke et al.
patent: 3917935 (1975-11-01), Lazecki
patent: 4337519 (1982-06-01), Nishimoto
patent: 4473887 (1984-09-01), Odaka
patent: 4534029 (1985-08-01), Singh et al.
patent: 4603397 (1986-07-01), Ohtsuki et al.
patent: 4636973 (1987-01-01), Cantwell
patent: 4952823 (1990-08-01), Guo
patent: 5245576 (1993-09-01), Foss et al.
patent: 5467318 (1995-11-01), Motomura
patent: 5583806 (1996-12-01), Widigen et al.
patent: 5625582 (1997-04-01), Timko
patent: 5659495 (1997-08-01), Briggs
patent: 5677883 (1997-10-01), Miwa
patent: 5754819 (1998-05-01), Lynch et al.
patent: 5893137 (1999-04-01), Parks et al.
patent: 5815420 (1999-09-01), Steiss
patent: 5953745 (1999-09-01), Lattimore et al.
patent: 6172933 (2001-01-01), Sager
patent: 0 210 752 (1987-02-01), None
patent: 2 063 166 (1981-06-01), None
patent: 2 077 190 (1981-12-01), None
“Evaluation of A+B=K Conditions Without Carry Propagation”, Jodi Cortadella and Jose M. Llaberia, IEEE Transaction on Computers, vol. 41, No. 11, Nov., 1991, pp 1-10.
“The Half-Adder Form and Early Branch Conditions Resolution,” David Lutz and D.N. Jayasimha, 1997, pp. 1-8.
“Early Zero Detection”, David R. Lutz and D.N. Jayasimha, 1997, pp. 1-6.
Lammers, David, “. . . While IBM Shows Path to GHz Processors,”Electronic Engineering Times, p. 4, Feb. 9, 1998.

Affiliated with

Also associated with

Rating

Content addressable memory addressable by redundant form input does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Content addressable memory addressable by redundant form input, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory addressable by redundant form input will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2860398