Sorting method and apparatus using a CAM

• US 6,990,552 B2
• Filed: 10/31/2002
• Issued: 01/24/2006
• Est. Priority Date: 10/31/2002
• Status: Expired due to Term

• Current Assignee: MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management)
• Original Assignee: MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management)
• Inventors: Abdat, Mourad
• Primary Examiner(s): Kim, Hong
• Assistant Examiner(s): THOMAS, SHANE M
• Application Number:
  US10/286,743
• Publication Number:
  US 20040088476A1
• Time in Patent Office: 1,181 Days
• Field of Search: 711/108, 711/158, 711/165, 707/3, 707/7, 707/101, 365/49
• US Class Current: 711/108
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

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.

Claims

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.