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. A sorting apparatus to sort data, comprising:
a first memory that: 1) stores data to be sorted; 2) receives a search command to sort the stored data; and 3) outputs a match address in response to the search command;
a second memory capable of being either read or write memory;
a third memory capable of being either read or write memory;
a controller that: i) stores the data to be sorted in the first memory and one of the second memory or third memory; ii) issues the search command; and iii) controls whether each of the second memory and the third memory is read or write memory;
one of the second memory or third memory, in a read mode, having a copy of the data to be sorted, and the memory in read mode providing match data in response to the match address from the first memory; and
one of the second memory or third memory, in a write mode, storing the match data from the memory in read mode.
2. The sorting apparatus as claimed in claim 1 wherein the controller further causes the sorted data to be written back to the first memory from the one of the second memory or third memory in write mode to allow issuance of an additional search command on the sorted data.
3. The sorting apparatus as claimed in claim 1 wherein the search command is a masked M-bit search.
4. The sorting apparatus as claimed in claim 1 wherein the first memory is Content Addressable Memory (CAM).
5. The sorting apparatus as claimed in claim 1 wherein the controller controls the match address of the first memory and selects whether each of the second and third memory is in read or write mode using multiplexers.
6. The sorting apparatus as claimed in claim 1 wherein the second memory and third memory alternate between write and read memory on successive sort cycles.
7. The sorting apparatus as claimed in claim 1 wherein the second and third memories are random access memories.
8. The sorting apparatus as claimed in claim 1 wherein the sorted data is in ascending or descending order.
9. A method for sorting data, comprising:
storing data in a first memory;
storing a copy of the data to be sorted in a second memory;
identifying the second memory as read memory and a third memory as write memory, the second and third memories being capable of being either read or write memories;
receiving a search command, in the first memory, for sorting the data;
in response to the search command, outputting a match address to the second memory;
sending match data corresponding to each match address for the second memory to the third memory; and
storing the match data in the third memory.
10. The method as claimed in claim 9 further comprising:
writing the sorted data back to the first memory from the third memory to provide additional searching of the sorted data.
11. The method as claimed in claim 9 wherein the search command is a masked M-bit search.
12. The method as claimed in claim 9 wherein the first memory is a Content Addressable Memory (CAM).
13. The method as claimed in claim 9 further comprising:
selecting whether each of the second and third memory is in read or write mode using multiplexers.
14. The method as claimed in claim 9 further comprising:
alternating the second memory and the third memory between write and read memory on successive sort cycles.
15. The method as claimed in claim 9 wherein the second and third memories are random access memories.
16. The method as claimed in claim 9 wherein the sorted data is in ascending or descending order.