Searching small entities in a wide CAM
AssigneeMosaid Technologies Incorporated
InventorLawrence King
Life of this patent
Estimating the term…
Abstract
A plurality of entities are stored in a single addressable location in a Content Addressable Memory (CAM). A column in a CAM entry is selected for storing an entity based on the property of the entity to distribute the entities among the columns to maximize memory utilization. A match for a search key stored in one of the plurality of columns can be found in a single search operation.
Claims14
A method of searching a Content Addressable Memory for entities which are smaller than Content Addressable Memory entries comprising:
- storing entities in respective columns of the Content Addressable Memory;
- selecting a column to be searched based on a property of an entity search key wherein the column is selected based on a result of a hash function performed on less than all bits in the entity search key;
- and
- applying the entity search key to the selected column to search for a match.
A method of searching a Content Addressable Memory for entities which are smaller than Content Addressable Memory entries comprising:
- storing entities in respective columns of the Content Addressable Memory;
- selecting a column to be searched based on a property of an entity search key;
- and
- applying the entity search key to the selected column to search for a match by shifting the entity search key to bit locations in a Content Addressable Memory search key corresponding to the selected column and performing a masked search masking nonselected columns.
An apparatus for searching a Content Addressable Memory for entities which are smaller than Content Addressable Memory entries comprising:
- categorization function logic which selects a column of the Content Addressable Memory to be searched based on a result of a hash function performed on less than all of bits in the entity search key, the Content Addressable Memory storing entities in respective columns;
- and
- bit shift logic which applies the entity search key to the selected column to search for a match.
An apparatus for searching a Content Addressable Memory for entities which are smaller than Content Addressable Memory entries comprising:
- categorization function logic which selects a column of the Content Addressable Memory to be searched based on a property of an entity search key, the Content Addressable Memory storing entities in respective columns;
- and
- bit shift logic which applies the entity search key to the selected column to search for a match by shifting the entity search key to bit locations in a Content Addressable Memory search key corresponding to the selected column and performing a masked search masking nonselected columns.
Dependencies are inferred from the claim text.