Sorting method and apparatus using a CAM
AssigneeMosaid Technologies Incorporated
InventorMourad Abdat
Life of this patent
Estimating the term…
Abstract
Method and apparatus for using a Content Addressable Memory for sorting a plurality of data items is presented. The data items to be sorted are stored in the Content Addressable Memory. A plurality of bit-by-bit burst searches are performed on the contents of the Content Addressable Memory with all other bits in the search key masked. The number of burst searches is proportional to the total number of bits in the data items to be sorted. The search is deterministic dependent on the number of bits in each data item on which a sort is performed and on the number of data items to be sorted.
Claims18
An apparatus for sorting data, comprising:
- a Content Addressable Memory storing data to be sorted, the Content Addressable Memory receiving a series of search commands and, in response to each of the search commands, outputting a match address corresponding to each match result;
- a first memory for storing a copy of the data stored in the Content Addressable Memory, the first memory providing match data corresponding to each match address for each of the search commands;
- a second memory for sequentially storing the match data for each of the search commands so that sorted data is stored in the second memory, the sorted data being written back to the Content Addressable Memory from the second memory such that a further sorting can be performed on the sorted data, if necessary;
- and
- a controller for controlling the sorting apparatus.
A method of sorting data stored in a Content Addressable Memory, the method comprising the steps of:
- duplicating the data of the Content Addressable Memory to a first memory;
- issuing a series of search commands to the Content Addressable Memory for outputting a match address corresponding to each match result in response to each of the series of the search commands;
- reading out from the first memory match data corresponding to each match address for each of the search commands;
- and
- writing the match data to a second memory sequentially for the series of the search commands to generate sorted data.
A sorting apparatus comprising:
- a first memory for storing data to be sorted, the first memory being capable of receiving a series of search commands and, in response to each of the search commands, outputting a match address for each match result;
- a second memory for storing a copy of the data stored in the first memory, the second memory providing match data corresponding to each match address for each of the search commands;
- a third memory for sequentially storing the match data for the series of the search commands to generate sorted data, the sorted data being written back to the first memory from the third memory such that a further sorting can be performed on the sorted data, if necessary;
- and
- a controller for controlling the sorting apparatus.
A method of sorting data, the method comprising the steps of:
- storing data to be sorted to a first memory, the first memory being a searchable memory;
- duplicating the data stored in the first memory to a second memory;
- issuing a series of search commands to the first memory such that a match address for each match result is output for each of the search commands;
- reading out from the second memory match data corresponding to each match address output from the first memory for each of the search commands;
- and
- sequentially writing the match data from the first memory to a third memory for the series of the search commands to generate sorted data.
Dependencies are inferred from the claim text.