Back to results
US 10,242,124 B2Granted
Content addressable memory and semiconductor device
AssigneeRenesas Electronics Corporation
InventorTsutomu Makino
Life of this patent
Estimating the term…
Abstract
In a memory, multiple pieces of entry data sorted in ascending or descending order are stored associated with addresses. With whole addresses for storing the multiple pieces of entry data as an initial search area, the search circuit repeatedly performs a search operation for comparing entry data stored in a central address of the search area with the search data, outputting the address as a search result in the case of a match, and narrowing the search area for the next search based on a magnitude comparison result in the case of a mismatch.
Claims10
A content addressable memory comprising:
- a memory which stores a plurality of pieces of entry data sorted in ascending or descending order, each of the plurality of pieces of entry data stored in association with an address among a plurality of addresses;
- a search circuit configured to search for a particular address in the memory, among the plurality of addresses, which stores entry data that matches search data, wherein, with entirety of addresses arranged in an order associated with plurality of pieces of entry data being considered as an initial search area, the search circuit repeatedly performs a search operation to compare the search data with entry data stored in a central address, which is an address located at a center of the order in which the entirely of the addresses is arranged in the initial search area with the search data, output the central address as a search result in the case of a match, and narrow the initial search area based on a magnitude comparison result in the case of a mismatch;
- wherein the memory has first to Nth memories (N is a natural number greater than 1) each having power-of-two words ranging from one word to 2 to the (N−1)th power, each word being associated with the central address of the initial search area, and
- wherein a first memory, among the first to the Nth memories, is a one word memory, and a second memory, among the first to the Nth memories, is a two word memory.
1 more element
A content addressable memory which can store (2 to the Nth power) pieces of entry data (N is a natural number greater than 1) and searches for entry data that matches input search data, the content addressable memory comprising:
- first to Nth memories each having power-of-two words ranging from one word to 2 to the (N−1)th power;
- an (N+1)th memory of one word;
- and
- first to (N+1)th comparison circuits provided corresponding to the first to (N+1)th memories,
- wherein the first comparison circuit reads entry data from the first memory, performs a match/magnitude comparison with a search data, and outputs a first comparison result to the second comparison circuit, the first comparison result including a magnitude information in case of a mismatch,
- wherein the second comparison circuit reads entry data stored in an address of the second memory calculated based on the magnitude information in the first comparison result input from the first comparison circuit, performs a match/magnitude comparison with the search data, and outputs a second comparison result to the third comparison circuit, the second comparison result including a magnitude information in case of a mismatch,
- wherein the third or the third to Nth comparison circuits determine an address for reading entry data to be compared, based on an address for storing entry data compared by a comparison circuit in a preceding stage and a magnitude information in the second comparison result input from the second comparison circuit or a magnitude information in a preceding comparison result input from the preceding stage, read entry data from a corresponding memory, perform a match/magnitude comparison with the search data, and output a current comparison result to a comparison circuit in a subsequent stage, the current comparison result including a magnitude information in case of a mismatch,
- wherein the (N+1)th comparison circuit performs a comparison as to whether or not the search data matches entry data stored in the (N+1)th memory, and if there exists entry data that matches the search data, based on a number of a memory that stores the matched entry data and an address in the memory that stores the matched entry data, the (N+1)th comparison circuit calculates and outputs what number entry data matches the search data in a state where the (2 to the Nth power) pieces of entry data are sorted, and
- wherein a first memory, among the first to the Nth memories, is a one word memory, and a second memory, among the first to the Nth memories, is a two word memory.
6 more elements
Dependencies are inferred from the claim text.