Obtaining search results for content addressable memory
7 Assignments
0 Petitions
Accused Products
Abstract
Content addressable memory (CAM) in which search results such as an address code and an array match signal can be obtained for multiple search widths. The CAM includes a CAM array that can provide match signals and suppress signals for memory locations. Match combining circuitry combines the match signals for memory locations to obtain combined match signals; the combination depends on an indicated search width, which can be one of a set of multiples of the memory location width. A priority encoder provides a priority signal indicating a combined match signal that has priority and is asserted; the priority encoder can therefore be smaller than would be necessary to prioritize all the match signals. An address encoder obtains most significant bits of an address code in response to the priority signal. Select circuitry responds to the priority signal by selecting match signals and suppress signals for the combined match signal with priority. The selected match signals are used to obtain least significant bits (LSBs) of the address code in accordance with the search width. The LSBs, selected suppress signals, and a PE match signal from the priority encoder are used to obtain an array match signal.
26 Citations
61 Claims
-
1-45. -45. (canceled)
-
46. A content addressable memory (CAM), comprising:
-
a CAM array that stores entries in P memory locations that each have a location width and that stores, for each memory location, a suppress value, the CAM array providing, for each memory location, a match signal indicating whether the location has a stored entry satisfying a match criterion and suppress signals based on locations'"'"' suppress values;
match combining circuitry that responds to the match signals and to a signal indicating a search width that is a multiple of the location width, the match combining circuitry providing P/Q combined match signals, each combined match signal indicating a combination of a group of Q match signals, the combination depending on the indicated search width; and
search results circuitry that responds to the combined match signals and to the suppress signals, providing an address code of a memory location, the memory location storing at least part of an entry of the indicated search width that satisfies the match criterion. - View Dependent Claims (47, 48)
-
-
49. A content addressable memory (CAM), comprising
a CAM array that stores entries in P memory locations that each have a location width, the CAM array providing, for each location, a match signal indicating whether the location has a stored entry satisfying a match criterion; -
match combining circuitry that responds to the match signals and to a signal indicating a search width that is a multiple of the location width, the match combining circuitry providing P/Q combined match signals, each combined match signal indicating a combination of a group of Q match signals, the combination depending on the indicated search width;
priority encoding circuitry that responds to the combined match signals, providing P/Q priority signals, each priority signal indicating, for a respective combined match signal, whether it has priority and is asserted, the priority encoder circuitry also providing a PE match signal indicating whether any of the combined match signals is asserted;
MSB address encoding circuitry that responds to the priority signals, providing log2(P/Q) most significant bits (MSBs) of a (log2P)-bit address code for the respective memory locations of a selected group of match signals; and
LSB circuitry that responds to a selected group of match signals and to the signal indicating the search width, the LSB circuitry providing log2Q least significant bits (LSBs) of the address code, the address code being a memory location of one of the selected group of match signals, the memory location storing at least part of an entry of an indicated search width that satisfies the match criterion. - View Dependent Claims (50, 51)
-
-
52. A content addressable memory (CAM), comprising
a CAM array that stores entries in P memory locations that each have a location width and that stores, for each memory location, a suppress value; - the CAM array providing, for each memory location, a match signal indicating whether the location has a stored entry satisfying a match criterion and suppress signals based on locations'"'"' suppress values;
priority encoding circuitry that responds to the combined match signals, providing P/Q priority signals, each priority signal indicating, for a respective combined match signal, whether it has priority and is asserted, the priority encoder circuitry also providing a PE match signal indicating whether any of the combined match signals is asserted; and
search results circuitry that responds to the priority signals and to the suppress signals, providing output search results. - View Dependent Claims (53, 54)
- the CAM array providing, for each memory location, a match signal indicating whether the location has a stored entry satisfying a match criterion and suppress signals based on locations'"'"' suppress values;
-
55. A content addressable memory (CAM), comprising:
-
a CAM array that stores entries in P memory locations that each have a location width and that stores, for each memory location, a suppress value, the CAM array providing, for each memory location, a match signal indicating whether the location has a stored entry satisfying a match criterion and suppress signals based on locations'"'"' suppress values;
match combining circuitry that responds to the match signals and to a signal indicating a search width that is a multiple of the location width, the match combining circuitry providing P/Q combined match signals, each combined match signal indicating a combination of a group of Q match signals, the combination depending on the indicated search width;
priority encoding circuitry that responds to the combined match signals, providing P/Q priority signals, each priority signal indicating, for a respective combined match signal, whether it has priority and is asserted;
the priority encoder circuitry also providing a PE match signal indicating whether any of the combined match signals is asserted;
match selecting circuitry that responds to the priority signals, selecting the respective group of Q match signals of the combined match signals that has priority and is asserted; and
suppress selecting circuitry that responds to the priority signals, selecting a group of Q suppress signals for the respective memory locations of the selected group of match signals. - View Dependent Claims (56, 57)
-
-
58. A router comprising:
-
input lines that receive data transmissions;
output lines that retransmit data transmissions received on the input lines; and
content addressable memory circuitry that provides information used to retransmit data transmissions on the output lines, the CAM circuitry comprising;
a CAM array that stores entries in P memory locations that each have a location width and that stores, for each memory location, a suppress value, the CAM array providing, for each memory location, a match signal indicating whether the location has a stored entry satisfying a match criterion and suppress signals based on locations'"'"' suppress values, match combining circuitry that responds to the match signals and to a signal indicating a search width that is a multiple of the location width, the match combining circuitry providing P/Q combined match signals, each combined match signal indicating a combination of a group of Q match signals, the combination depending on the indicated search width, and search results circuitry that responds to the combined match signals and to the suppress signals, providing an address code of a memory location, the memory location storing at least part of an entry of the indicated search width that satisfies the match criterion.
-
-
59. A router comprising:
-
input lines that receive data transmissions;
output lines that retransmit data transmissions received on the input lines; and
content addressable memory circuitry that provides information used to retransmit data transmissions on the output lines, the CAM circuitry comprising;
a CAM array that stores entries in P memory locations that each have a location width, the CAM array providing, for each location, a match signal indicating whether the location has a stored entry satisfying a match criterion, match combining circuitry that responds to the match signals and to a signal indicating a search width that is a multiple of the location width, the match combining circuitry providing P/Q combined match signals, each combined match signal indicating a combination of a group of Q match signals, the combination depending on the indicated search width, priority encoding circuitry that responds to the combined match signals, providing P/Q priority signals, each priority signal indicating, for a respective combined match signal, whether it has priority and is asserted;
the priority encoder circuitry also providing a PE match signal indicating whether any of the combined match signals is asserted,MSB address encoding circuitry that responds to the priority signals, providing log2(P/Q) most significant bits (MSBs) of a (log2P)-bit address code for the respective memory locations of a selected group of match signals, and LSB circuitry that responds to a selected group of match signals and to the signal indicating the search width;
the LSB circuitry providing log2Q least significant bits (LSBs) of the address code, the address code being a memory location of one of the selected group of match signals, the memory location storing at least part of an entry of an indicated search width that satisfies the match criterion.
-
-
60. A router comprising:
-
input lines that receive data transmissions;
output lines that retransmit data transmissions received on the input lines; and
content addressable memory circuitry that provides information used to retransmit data transmissions on the output lines, the CAM circuitry comprising;
a CAM array that stores entries in P memory locations that each have a location width and that stores, for each memory location, a suppress value, the CAM array providing, for each memory location, a match signal indicating whether the location has a stored entry satisfying a match criterion and suppress signals based on locations'"'"' suppress values, priority encoding circuitry that responds to the combined match signals, providing P/Q priority signals, each priority signal indicating, for a respective combined match signal, whether it has priority and is asserted, the priority encoder circuitry also providing a PE match signal indicating whether any of the combined match signals is asserted, and search results circuitry that responds to the priority signals and to the suppress signals, providing output search results.
-
-
61. A router comprising:
-
input lines that receive data transmissions;
output lines that retransmit data transmissions received on the input lines; and
content addressable memory circuitry that provides information used to retransmit data transmissions on the output lines, the CAM circuitry comprising;
a CAM array that stores entries in P memory locations that each have a location width and that stores, for each memory location, a suppress value, the CAM array providing, for each memory location, a match signal indicating whether the location has a stored entry satisfying a match criterion and suppress signals based on locations'"'"' suppress values, match combining circuitry that responds to the match signals and to a signal indicating a search width that is a multiple of the location width, the match combining circuitry providing P/Q combined match signals, each combined match signal indicating a combination of a group of Q match signals, the combination depending on the indicated search width;
priority encoding circuitry that responds to the combined match signals, providing P/Q priority signals, each priority signal indicating, for a respective combined match signal, whether it has priority and is asserted, the priority encoder circuitry also providing a PE match signal indicating whether any of the combined match signals is asserted, match selecting circuitry that responds to the priority signals, selecting the respective group of Q match signals of the combined match signals that has priority and is asserted; and
suppress selecting circuitry that responds to the priority signals, selecting a group of Q suppress signals for the respective memory locations of the selected group of match signals.
-
Specification