Timing execution of compare instructions in a synchronous content addressable memory

• US 6,678,786 B2
• Filed: 12/11/2002
• Issued: 01/13/2004
• Est. Priority Date: 10/30/1997
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Nataraj, Bindiganavale S., Khanna, Sandeep, Srinivasan, Varadarajan
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US10/318,251
• Publication Number:
  US 20030131188A1
• Time in Patent Office: 398 Days
• Field of Search: 365/49, 365/226, 380/5, 380/9, 711/108
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: G11C 15/04 using semiconductor elements

Abstract

A content address memory (CAM) device. The CAM device is a synchronous device that may perform all of the following operations all in one clock cycle: (1) receive comparand data from a comparand bus; (2) receive an instruction from an instruction bus instructing the CAM device to compare the comparand data with a first group of CAM cells in a CAM array; (3) perform the comparison of the comparand data with the first group of CAM cells; (4) generate a match address for a location in the CAM array that stores data matching the comparand data; (5) access data stored in a second group of the CAM cells in the CAM array, wherein the second group of CAM cells may store data associated with the matched location; and (6) output to an output bus the match address, the data stored in the second group of CAM cells, and/or status information corresponding to the matched address or the second group of CAM cells. The status information may include a match flag, multiple match flag, full flag, skip bit, empty bit, or a device identification for the CAM device.

Claims

1. A synchronous content addressable memory (CAM) device comprising:

a CAM array having a plurality of first CAM cells and a second CAM cell;

a comparand storage element coupled to the CAM array and configured to receive comparand data;

an instruction decoder coupled to the CAM array and configured to receive a compare instruction, wherein the instruction instructs the CAM device to compare the comparand data with the plurality of first CAM cells;

a sensing circuit coupled to the CAM array and configured to sense data from the second CAM cell, wherein the second CAM cell corresponds to one of the plurality of first CAM cells storing data matching the comparand data;

an output port coupled to the sensing circuit;

a clock input coupled to the instruction decoder and configured to receive a clock signal; and

timing means, responsive to the clock signal and the compare instruction, for timing execution of the compare instruction and causing the sensed data to be output from the output port.

2. The synchronous CAM device of claim 1, wherein the compare instruction is executed in less than three clock cycles of the clock signal.

3. The synchronous CAM device of claim 1, wherein the compare instruction is executed in one clock cycle of the clock signal.

4. The synchronous CAM device of claim 1, further comprising a priority encoder coupled to the CAM array and configured to determine a match address for the one of the plurality of first CAM cells storing data matching the comparand data, wherein the match address is provided to the output port in response to the compare instruction.

5. The synchronous CAM device of claim 4, further comprising:

an address selector circuit coupled to the priority encoder and configured to receive the match address; and

an address decoder circuit coupled to the address selector circuit and the CAM array, the address decoder circuit configured to decode the match address and select the second CAM cell.

6. The synchronous CAM device of claim 1, wherein the sensing circuit is further configured to sense validity information from a third CAM cell in the CAM array, wherein the validity information corresponds to the one of the plurality of first CAM cells storing data matching the comparand data, wherein the validity data is provided to the output port in response to the compare instruction.

7. The synchronous CAM device of claim 6, wherein the validity information comprises a skip bit.

8. The synchronous CAM device of claim 5, wherein the validity information comprises an empty bit.

9. The synchronous CAM device of claim 1, wherein the timing means comprises a timing generator.

10. The synchronous CAM device of claim 9, wherein the timing generator comprises:

a pulse generator; and

at least one delay element coupled to the pulse generator.

11. The synchronous CAM device of claim 10, wherein the timing generator comprises:

a clock generator; and

at least one latch coupled to the pulse generator.

12. The synchronous CAM device of claim 9, wherein the timing means further comprises a clock buffer coupled to the timing generator and coupled to the clock input to receive the clock signal.

13. The synchronous CAM device of claim 12, wherein the clock buffer is operable to generate first and second clock signals, and wherein the timing generator is operable to selectively couple the first clock signal to the comparand storage element and the second clock signal to the sensing circuit.

14. The synchronous CAM device of claim 13, wherein the clock buffer is operable to generate a third clock signal, and wherein the timing generator is operable to selectively couple the third clock signal to the output circuit.

15. A synchronous content addressable memory (CAM) device comprising:

a CAM array having a plurality of CAM locations each comprising at least one CAM cell;

a comparand storage element coupled to the CAM array and configured to receive comparand data;

an instruction decoder coupled to the CAM array and configured to receive a compare instruction, wherein the instruction instructs the CAM device to compare the comparand data with the plurality of CAM locations; and

a priority encoder coupled to the CAM array and configured to determine a match address for a location in the CAM array storing data matching the comparand data;

an output port coupled to the priority encoder;

a clock input coupled to the instruction decoder and configured to receive a clock signal; and

timing means, responsive to the clock signal and the compare instruction, for timing execution of the compare instruction and causing the match address to be output from the output port.

16. The synchronous CAM device of claim 15, wherein the compare instruction is executed in less than three clock cycles of the clock signal.

17. The synchronous CAM device of claim 15, wherein the compare instruction is executed in one clock cycle of the clock signal.

18. The synchronous CAM device of claim 15, wherein the timing means comprises a timing generator.

19. The synchronous CAM device of claim 18, wherein the timing generator comprises:

a pulse generator; and

at least one delay element coupled to the pulse generator.

20. The synchronous CAM device of claim 18, wherein the timing generator comprises:

a clock generator; and

at least one latch coupled to the pulse generator.

21. The synchronous CAM device of claim 19, wherein the timing means further comprises a clock buffer coupled to the timing generator and coupled to the clock input to receive the clock signal.

22. The synchronous CAM device of claim 21, wherein the clock buffer is operable to generate first and second clock signals, and wherein the timing generator is operable to selectively couple the first clock signal to the comparand storage element and the second clock signal to the priority encoder.

23. The synchronous CAM device of claim 22, wherein the clock buffer is operable to generate a third clock signal, and wherein the timing generator is operable to selectively couple the third clock signal to the output circuit.