Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-07-12
2002-05-21
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C710S057000
Reexamination Certificate
active
06393514
ABSTRACT:
BACKGROUND
1. Field of Invention
This invention relates generally to content addressable memories and specifically to a full flag condition in a content addressable memory.
2. Description of Related Art
A content addressable memory (CAM) includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory cells in the CAM array constitute a CAM word. During compare operations, a comparand word is received at appropriate input terminals of the CAM and then compared to all the CAM words. For each CAM word that matches the comparand word, a corresponding match line signal is asserted to indicate a match condition. The matching CAM word is then read from the CAM.
FIG. 1
shows a portion of a CAM device
3
that includes a CAM array
1
and associated full flag logic
2
. Each row of the CAM array
1
includes an additional memory cell for storing a valid bit indicative of whether a valid word is presently stored in that row. Since the CAM array is initially undefined, all valid bits are initially de-asserted to indicate that there are no valid words stored in the array. In connection with each write operation in which valid data is written to a selected row of the CAM array
1
, the valid bit corresponding to the selected row is asserted, thereby indicating that valid data is stored in the selected row. Words stored in the CAM array
1
are invalidated by de-asserting corresponding valid bits. The valid bits are provided to the full flag logic
2
which, in response thereto, generates a full flag for the CAM array
1
. The full flag is asserted when all the valid bits are asserted, i.e., when all rows of the CAM array
1
contain valid data.
FIG. 2
is a timing diagram illustrating write operations to the last two available rows (i.e., those that don't contain valid data) of CAM array
1
, where the CAM array
1
has n rows. Each write instruction is latched into the CAM
3
on a rising edge of clock signal CLK and causes valid data to be subsequently written to a selected CAM row. The corresponding valid bit is then asserted.
Referring to
FIG. 2
, the n
th
write instruction latched at time t causes valid data to be written to the last available row of the CAM array
1
. In connection with this write operation, the valid bit corresponding to the last available row is asserted. Thereafter, all valid bits are logically combined by full flag logic
2
to assert, after some gate delay, the full flag FF at time t
2
. Thus, the full flag signal cannot be asserted to a logic high state until after the valid bit is resolved at the n
th
row of CAM array
1
. It is not desirable to have the full flag signal be asserted too close to the end of the n
th
clock cycle as this may not leave enough set-up time relative to CLK for a follow-on device that uses the full flag signal. If the full flag is not asserted until the last valid bit is asserted in response to the nth write, this may result in an undesirable need either to push out the clock timing to accommodate the full flag, or to have the follow-on device wait an extra clock cycle to latch the full flag. Either of these two results can degrade system performance for a system including CAM
3
.
Thus, it would be desirable to decrease the time delay between receiving the write instruction which causes valid data to be written to the last available CAM row and assertion of the full flag.
SUMMARY
In accordance with one embodiment of the present invention, an almost full flag is asserted when all but one of the rows of a CAM array contain valid data, as indicated by corresponding valid bits. Subsequent instructions are then monitored to detect an instruction which causes valid data to be written to the one available CAM row. The full flag is asserted when such an instruction is detected while the almost full flag is asserted. Thus, present embodiments do not need to use the last valid bit to generate the full flag, but rather can combine the almost full flag with information from subsequent instruction bits to generate the full flag. Accordingly, present embodiments do not need to wait until after the last valid bit is asserted to correctly determine the state of the full flag. As a result, present embodiments may assert the full flag sooner than prior art techniques allow.
REFERENCES:
patent: 5249271 (1993-09-01), Hopkinson et al.
patent: 5347648 (1994-09-01), Stamm et al.
patent: 5406279 (1995-04-01), Anderson et al.
patent: 5440715 (1995-08-01), Wyland
patent: 5440753 (1995-08-01), Hou et al.
patent: 5454094 (1995-09-01), Montove
patent: 5539882 (1996-07-01), Gopal et al.
patent: 5893931 (1999-04-01), Peng et al.
patent: 6076137 (2000-06-01), Asnaashari
patent: 6195277 (2001-02-01), Sywyk et al.
patent: 6249450 (2001-06-01), Tanaka et al.
Preliminary Data Sheet, GEC Plessey Semiconductors, Feb. 1997, pp. 1-15.
Khanna Sandeep
Nataraj Bindiganavale S.
Srinivasan Varadarajan
Kim Matthew
NetLogic Microsystems, Inc.
Paradice III William L
Vital Pierre M.
LandOfFree
Method of generating an almost full flag and a full flag in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of generating an almost full flag and a full flag in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of generating an almost full flag and a full flag in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2891591