Memory and power efficient mechanism for fast table lookup
View Patent ↗A method of implementing classification CAM functionality using primarily RAM cells is disclosed. The method offers significantly more table entries in a given area, or significantly less area for a given table size than conventional ternary CAMs. The method is much more power-efficient, cheaper, and offers a greater range of features than conventional CAMs.
1. A method for operating a content-addressable memory having a specification memory loaded with at least a first group having first entries, the method comprising the steps of:
selecting a number of bit positions for said first entries as distinguishing bit positions;
configuring an entry selector circuit with first values of said first entries, said first values located at said distinguishing bit positions;
receiving an input;
selecting a matching entry from said plurality of entries that has first values that match said input at said distinguishing bit positions;
outputting an indicator corresponding to a location of said matching entry in said entry selector circuit.
2. The method of claim 1 , wherein no more than one of said first entries can match any given input.
3. The method of claim 1 , wherein said first values from said first entries at said distinguishing bit positions are sufficient to uniquely identify a first entry in said first group from remaining entries in said first group.
4. The method of claim 1 wherein the specification memory comprises at least one of RAM cells, DRAM cells, or SRAM cells.
5. The method of claim 1 , wherein the entry selector circuit comprises at least one of binary CAM cells or ternary CAM cells.
6. The method of claim 1 , wherein selecting a matching entry is performed by a multi-stage circuit.
7. The method of claim 1 , further comprising the steps of:
selecting a second matching entry from a plurality of second entries from a second group;
assigning a priority value to each of said first and second matching entries; and
outputting one of said first and second matching entries having a higher priority value.
8. A content-addressable memory comprising:
an input device adapted to receiving an input;
a specification memory adapted to store at least a first group having first entries;
a supervisory processor adapted to select a number of bit positions for said first entries as distinguishing bit positions;
an entry selector circuit adapted to select a matching entry from said first entries that has first values that match said input at said distinguishing bit positions; and
an output device adapted to output an indicator corresponding to a location of said matching entry in said entry selector circuit.
9. The content-addressable memory of claim 8 , wherein no more than one of said first entries can match any given input.
10. The content-addressable memory of claim 8 , wherein said first values at said distinguishing bit positions are sufficient to uniquely identify a first entry in said first group from remaining entries in said first group.
11. The content-addressable memory of claim 8 wherein said specification memory comprises at least one of RAM cells, DRAM cells, or SRAM cells.
12. The content-addressable memory of claim 8 , wherein said entry selector circuit comprises at least one of binary CAM cells or ternary CAM cells.
13. The content-addressable memory of claim 8 , wherein said entry selector circuit comprises a multi-stage circuit.
14. The content-addressable memory of claim 8 , wherein said entry selector circuit is further adapted to selecting a second matching entry from a plurality of second entries from a second group, the content-addressable memory further comprising:
a priority circuit adapted to:
assign a priority value to each of said first and second matching entries; and
output one of said first and second matching entries having a higher priority value.
15. A system for operating a content-addressable memory comprising:
storage means for storing at least a first group having first entries,
selecting means for selecting a number of bit positions from said plurality of entries as distinguishing bit positions;
entry selector configuring means for configuring an entry selector circuit with first values of said first entries, said first values located at said distinguishing bit positions;
input receiving means for receiving an input;
matching means for selecting a matching entry from said first entries that has first values that match said input at said distinguishing bit positions;
outputting means for outputting an indicator corresponding to a location of said matching entry in said entry selector circuit.
16. The system of claim 15 , wherein no more than one of said first entries can match any given input.
17. The system of claim 15 , wherein said first values at said distinguishing bit positions are sufficient to uniquely identify a first entry in said first group from remaining entries in said first group.
18. The system of claim 15 wherein said storage means comprises at least one of RAM cells, DRAM cells, or SRAM cells.
19. The system of claim 15 , wherein said matching means comprises at least one of binary CAM cells or ternary CAM cells.
20. The system of claim 15 , wherein said matching means comprises multi-stage matching means.
21. The system of claim 15 , wherein said matching means further selects a second matching entry from a plurality of second entries from a second group, the system further comprising:
prioritizing means for assigning a priority value to each of said first and second matching entries and outputting one of said first and second matching entries having a higher priority value.