Back to results
US 2019/0171674 A1Published application
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.
Claims8
A content addressable memory comprising:
- a memory to which search data is inputted and which stores multiple pieces of entry data;
- and
- a search circuit for searching for an address in the memory which stores entry data that matches the search data,
- wherein, in the memory, the multiple pieces of entry data are sorted in ascending or descending order and can be stored associated with addresses, and
- wherein, 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 central address as a search result in the case of a match, and narrowing the search area based on a magnitude comparison result in the case of a mismatch,
- wherein a first content addressable memory has the same configuration as the content addressable memory,
- the content addressable memory further comprising:
- a second content addressable memory having the same number of entries as the first content addressable memory;
- a plurality of first content addressable memories;
- and
- a transfer circuit for reading multiple pieces of entry data from the second content addressable memory, sorting the multiple pieces of entry data in ascending or descending order, and transferring the sorted multiple pieces of entry data to the first content addressable memory.
8 more elements
A content addressable memory which can store (2 to the Nth power) pieces of entry data (N is a natural number) 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 the search data, and outputs a comparison result to the second comparison circuit,
- wherein the second comparison circuit reads entry data stored in an address of the second memory calculated based on the comparison result inputted from the first comparison circuit, performs a match/magnitude comparison with the search data, and outputs a comparison result to the third comparison circuit,
- wherein 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 comparison result inputted from the preceding stage, read entry data from a corresponding memory, perform a match/magnitude comparison with the search data, and output a comparison result to a comparison circuit in a subsequent stage,
- 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,
- wherein the first memory stores (2 to the (N−1)th power)th piece of entry data out of the (2 to the Nth power) pieces of entry data,
- wherein the (N+1)th memory stores (2 to the Nth power)th piece of entry data out of the (2 to the Nth power) pieces of entry data,
- wherein the ith memory (i is a natural number equal to or greater than 2 and less than N) stores entry data, other than entry data stored in the first to (i−1)th memories, out of (j×2 to the (N−i)th power)th entry data (j is all natural numbers less than 2 to the ith power),
- wherein if there exists entry data that matches the search data, (j×2 to the (N−i)th power−1) corresponding to the matched entry data is outputted, and
- wherein a first content addressable memory has the same configuration as the content addressable memory,
- the content addressable memory further comprising:
- a second content addressable memory having the same number of entries as the first content addressable memory;
- a plurality of first content addressable memories;
- and
- a transfer circuit for reading multiple pieces of entry data from the second content addressable memory, sorting the multiple pieces of entry data in ascending or descending order, and transferring the sorted multiple pieces of entry data to the first content addressable memory.
15 more elements
Dependencies are inferred from the claim text.