Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-12-06
2003-07-08
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S147000, C711S154000, C711S170000, C365S049130
Reexamination Certificate
active
06591331
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to content addressable memory (CAM) devices.
BACKGROUND
A content addressable memory (CAM) device is a storage device that can be instructed to compare a specific pattern of comparand data with data stored in its associative CAM array. The entire CAM array, or segments thereof, is searched in parallel for a match with the comparand data. If a match exists, the CAM device indicates the match by asserting a match flag. Multiple matches may also be indicated by asserting a multiple match flag. The CAM device typically includes a priority encoder to translate the highest priority matching location into a match address or CAM index.
When the CAM array is segmented into many CAM array blocks, the priority encoder may also be distributed or segmented such that each block has its own encoder. The outputs of the encoders can then be combined to generate the address of the highest priority matching location. This approach, however, may use a significant amount of die area in an integrated circuit to implement the distributed priority encoder. Other approaches have suggested a hierarchical priority encoding scheme that includes a main priority encoder and a subblock priority encoder. The subblock priority encoder monitors the match signals from the individual blocks and sequentially enables each block to provide its match results to the main priority encoder. This approach may require a significant amount of time to reach the block having the highest priority matching entry.
SUMMARY OF THE INVENTION
A method and apparatus for determining the address of a highest priority matching entry in a segmented content addressable memory device is disclosed. For one embodiment, a segmented CAM device is disclosed that includes m CAM array blocks each having n rows of CAM cells coupled to one of n corresponding match lines. The CAM array blocks have a predetermined priority based on their addresses such that the first CAM array block has the highest priority addresses and the mth CAM array block has the lowest priority addresses. Comparand data is provided for comparison with entries in each of the CAM array blocks. Each row of CAM cells in each block has arrow enable logic circuit. A main priority encoder is coupled to the row enable logic circuits of the mth CAM array block. Each CAM array block also has an associated match flag circuit to determine a match flag signal for the block. A block priority encoder encodes the match flag signals into a block address of the highest priority matching location. The block address is provided to a decoder that decodes the block address. The decoded block address enables one of the groups of row enable logic circuits associated with the CAM array block having the highest priority matching location to provide its match results to the main priority encoder. The main priority encoder determines the subblock address of the matching entry in that CAM array block. The block address and the subblock address form the address of the highest priority matching entry or location in the entire CAM array.
Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.
REFERENCES:
patent: 4890260 (1989-12-01), Chuang et al.
patent: 4928260 (1990-05-01), Chuang et al.
patent: 5123105 (1992-06-01), Wyland et al.
patent: 5319589 (1994-06-01), Yamagata et al.
patent: 5394353 (1995-02-01), Nusinov et al.
patent: 5511222 (1996-04-01), Shiba et al.
patent: 5555397 (1996-09-01), Sasama et al.
patent: 5568485 (1996-10-01), Chaisemartin
patent: 5602545 (1997-02-01), Ishii et al.
patent: 5619446 (1997-04-01), Yoneda et al.
patent: 5726942 (1998-03-01), Yoneda et al.
patent: 5818786 (1998-10-01), Yoneda
patent: 5949734 (1999-09-01), Matano
patent: 5973950 (1999-10-01), Shindo
patent: 5978246 (1999-11-01), Shindo
patent: 6069573 (2000-05-01), ClarkI et al.
patent: 05189979 (1993-07-01), None
patent: WO9854725 (1998-12-01), None
Tamaru, Keikichi. “The Trend of Functional Memory Development,”IEICE Trans. Electron.,vol. E76-C, No. 11 (Nov. 1993), pp. 1545-1554.
Blakely , Sokoloff, Taylor & Zafman LLP
Chace Christian P.
Netlogic Microsystems Inc.
Yoo Do Hyun
LandOfFree
Method and apparatus for determining the address of the... 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 and apparatus for determining the address of the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining the address of the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3040897