Sorting method and apparatus using a CAM
View Patent ↗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.
1. An apparatus for sorting data, comprising:
a first Content Addressable Memory storing data to be sorted, the first 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 first 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 first 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 apparatus.
2. The apparatus as claimed in claim 1 , wherein the search command includes a bit search command with certain bits masked.
3. The apparatus as claimed in claim 1 , wherein the roles of the first memory and the second memory are configured to be swapped when the further sorting is performed on the sorted data.
4. The apparatus as claimed in claim 1 , wherein the second memory includes a second Content Addressable Memory.
5. The apparatus as claimed in claim 4 , wherein, when the further sorting is performed, the series of the search commands are issued to the second Content Addressable Memory and the first Content Addressable Memory serves as the second memory.
6. The apparatus as claimed in claim 1 , further comprising a third memory for storing a sorting boundary generated when a progressive sorting is performed.
7. A method of sorting data stored in a first Content Addressable Memory, the method comprising the steps of:
duplicating the data of the first Content Addressable Memory to a first memory;
issuing a series of search commands to the first 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.
8. The method as claimed in claim 7 , wherein the search command includes a bit search command with certain bits masked.
9. The method as claimed in claim 7 , further comprising the step of copying the sorted data to the first Content Addressable Memory from the second memory such that a further sorting can be performed on the sorted data.
10. The method as claimed in claim 9 , wherein the second memory includes a second Content Addressable Memory.
11. The method as claimed in claim 10 , wherein, when the further sorting is performed, the series of the search commands are issued to the second Content Addressable Memory and the first Content Addressable Memory serves as the second memory.
12. 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.
13. The apparatus as claimed in claim 12 , wherein the search command includes a bit search command with certain bits masked.
14. The apparatus as claimed in claim 12 , wherein the first memory includes a Content Addressable Memory.
15. 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 second memory to a third memory for the series of the search commands to generate sorted data.
16. The method as claimed in claim 15 , wherein the search command includes a bit search command with certain bits masked.
17. The method as claimed in claim 15 , further comprising the step of copying the sorted data to the first memory from the third memory such that a further sorting can be performed on the sorted data.
18. The method as claimed in claim 15 , wherein the first memory includes a Content Addressable Memory.