Sorting method and apparatus using a CAM
View Patent ↗Method and apparatus 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 comprising:
Content Addressable Memory which stores entries to be sorted;
first memory which stores a copy of the contents of the Content Addressable Memory; and
second memory which stores ordered entries read from the first memory using match addresses output in response to a burst search command issued to the Content Addressable Memory, the ordered entries stored in the second memory being written back to the Content Addressable Memory to allow further sorting of the entries.
2. The apparatus as claimed in claim 1 wherein the burst search command performs a masked M-bit search.
3. The apparatus as claimed in claim 2 wherein M=1 and a one bit sort of the entries is performed by issuing a masked one bit burst search for the bit set to ‘1’ and another masked one bit burst search for the bit set to ‘0’.
4. The apparatus as claimed in claim 2 wherein the number of M-bit burst searches to sort a list with precision P is (P/M)*2M.
5. The apparatus as claimed in claim 2 wherein M=1 and the average number of Content Addressable Memory cycles to sort N entries of precision P is (3/2*P*N).
6. The apparatus as claimed in claim 5 wherein the number of one bit masked burst searches is proportional to P.
7. The apparatus as claimed in claim 1 wherein the first and second memory are random access memory.
8. The apparatus as claimed in claim 7 wherein one of the random access memories is assigned as read memory and the other random access memory is assigned as write memory and the assignment of read and write memory alternates on successive sort cycles.
9. The apparatus as claimed in claim 1 wherein a progressive sort is performed by issuing a first burst search for a most significant bit to the Content Addressable Memory.
10. The apparatus as claimed in claim 1 wherein a non-progressive sort is performed by issuing a first burst search for a least significant bit to the Content Addressable Memory.
11. The apparatus as claimed in claim 1 wherein the ordered entries are in ascending order.
12. The apparatus as claimed in claim 1 wherein the ordered entries are in descending order.
13. A method for performing a sort comprising, in successive sort cycles, the steps of:
duplicating entries to be sorted in Content Addressable Memory to a first random access memory;
issuing a burst search command to Content Addressable Memory;
using match addresses output from Content Addressable Memory in response to the issued burst search command, wherein,
the entries corresponding to the match addresses are copied from the first random access memory to a second random access memory; and,
copying entries stored in the second random access memory to Content Addressable Memory to allow further sorting of the entries.
14. The method as claimed in claim 13 wherein one of the first or second random access memories is assigned as read memory and the other random access memory is assigned as write memory and the assignment of read and write memory alternates on successive sort cycles.
15. The method as claimed in claim 13 wherein the burst search command performs a masked M-bit search.
16. The method as claimed in claim 15 wherein a one bit sort of the entries is performed by issuing a masked one bit search for the bit set to ‘1’ and another masked bit search for the bit set to ‘0’.
17. The method as claimed in claim 16 wherein the average number of cycles to sort N entries of precision P is (3/2*P*N).
18. The method as claimed in claim 17 wherein the number of one bit masked burst searches is proportional to P.
19. The method as claimed in claim 13 wherein a progressive sort is performed by issuing a first masked one bit burst search for a most significant bit to the Content Addressable Memory.
20. The method as claimed in claim 13 wherein a non-progressive sort is performed by issuing a first masked one bit burst search for a least significant bit in the Content Addressable Memory.
21. The method as claimed in claim 13 wherein the ordered entries are in ascending order.
22. The method as claimed in claim 13 wherein the ordered entries are in descending order.