Computational memory for sorting multiple data streams in parallel

Abstract

A processing device having a sequence of sorting elements arranged in an array. Each of the sorting elements stores a previously retained value therein and receives an input value from a previous sorting element. Each sorting element applies retention logic to select one of the input value or the retained value to be passed to the next sorting element in the array. The value that is passed to the next sorting element can either be set to be the larger, or the smaller, of the input value and the previously retained value, as desired. Rows of processing elements in the array operate in parallel such that large data streams are sorted in parallel (with the data values moving down from one row of processing elements to the next row such that the largest, or the smallest, data values accumulating in the final row of processing elements).

What is claimed is: 
     
       1. A device comprising:
 an array of processing elements configured for single-instruction, multiple data (SIMD) operation, wherein each processing element includes logic and memory configured as a subsequence of sorting elements, such that the array of processing elements provide a sequence of sorting elements configured to receive a sequence of values to sort; 
 each sorting element of the sequence of sorting elements configured to compare an input value and a retained value simultaneously with each other element comparing respective input values and respective retained values, wherein the input value is received at the sorting element from a previous sorting element in the sequence of sorting elements or from an input to the sequence of sorting elements, and wherein the retained value is stored at the sorting element; 
 wherein the sorting element is configured to retain at the sorting element one of the input value and the retained value, and wherein the sorting element is configured to pass the other of the input value and the retained value to a next sorting element in the sequence of sorting elements; 
 wherein the array of processing elements is configured to output the sequence of values as sorted. 
 
     
     
       2. The device of  claim 1 , wherein the sorting element is configured to:
 numerically compare the input value to the retained value; 
 retain a greater of the input value and the retained value; and 
 pass a lesser of the input value and the retained value to the next sorting element. 
 
     
     
       3. The device of  claim 1 , wherein the sorting element is configured to:
 numerically compare the input value to the retained value; 
 retain a lesser of the input value and the retained value; and 
 pass a greater of the input value and the retained value to the next sorting element. 
 
     
     
       4. The device of  claim 1 , wherein the sorting element is configured to:
 numerically compare the input value to the retained value, and if the input value is equal to the retained value; then pass either the input value or the retained value to the next sorting element. 
 
     
     
       5. The device of  claim 1 , wherein the sorting element is programmable. 
     
     
       6. The device of  claim 1 , wherein a terminal sorting element of the sequence of sorting elements is configured to retain at the terminal sorting element one of the input value and the retained value, and wherein the terminal sorting element is configured to discard the other of the input value and the retained value. 
     
     
       7. The device of  claim 1 , further comprising a controller configured to control the array of processing elements to simultaneously operate the sequence of sorting elements. 
     
     
       8. A device comprising:
 an array of processing elements configured for single-instruction, multiple data (SIMD) operation, wherein each processing element includes logic and memory configured as a sorting element of an array of sorting elements including logically parallel sequences of sorting elements, each sequence of sorting elements configured to receive a sequence of values to sort; 
 each sorting element of each sequence of sorting elements configured to compare an input value and a retained value simultaneously with each other element comparing respective input values and respective retained values, wherein the input value is received at the sorting element from a previous sorting element in the sequence of sorting elements or from an input to the sequence of sorting elements, and wherein the retained value is stored at the sorting element; 
 wherein the sorting element is configured to retain at the sorting element one of the input value and the retained value, and wherein the sorting element is configured to pass the other of the input value and the retained value to a next sorting element in the sequence of sorting elements; 
 wherein each sequence of sorting elements is configured to output the sequence of values as sorted. 
 
     
     
       9. The device of  claim 8 , wherein the sorting element is configured to:
 numerically compare the input value to the retained value; 
 retain a greater of the input value and the retained value; and 
 pass a lesser of the input value and the retained value to the next sorting element. 
 
     
     
       10. The device of  claim 8 , wherein the sorting element is configured to:
 numerically compare the input value to the retained value; 
 retain a lesser of the input value and the retained value; and 
 pass a greater of the input value and the retained value to the next sorting element. 
 
     
     
       11. The device of  claim 8 , wherein the sorting element is configured to:
 numerically compare the input value to the retained value, and if the input value is equal to the retained value; then 
 pass either the input value or the retained value to the next sorting element. 
 
     
     
       12. The device of  claim 8 , wherein the sorting element is programmable. 
     
     
       13. The device of  claim 8 , wherein a terminal sorting element of the logically parallel sequence of sorting elements is configured to retain at the terminal sorting element one of the input value and the retained value, and wherein the terminal sorting element is configured to discard the other of the input value and the retained value. 
     
     
       14. The device of  claim 8 , wherein each processing element includes a single sorting element of the logically parallel sequence of sorting elements. 
     
     
       15. The device of  claim 8 , wherein each processing element includes a subsequence of sorting elements of the logically parallel sequence of sorting elements. 
     
     
       16. The device of  claim 8 , further comprising a controller configured to control the array of processing elements to simultaneously operate the logically parallel sequences of sorting elements.