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:
 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 apply retention logic to an input value and a retained value, 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 retention logic is configured to retain at the sorting element one of the input value and the retained value, and wherein the retention logic 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 sequence of sorting elements is configured to output the sequence of values as sorted based on the retention logic.   
     
     
         2 . The device of  claim 1 , wherein the retention logic 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 retention logic 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 retention logic 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 retention logic is programmable. 
     
     
         6 . The device of  claim 1 , wherein a terminal sorting element of the sequence of sorting elements comprises terminal retention logic configured to retain at the terminal sorting element one of the input value and the retained value, and wherein the terminal retention logic is configured to discard the other of the input value and the retained value. 
     
     
         7 . The device of  claim 1 , further comprising a sequence of processing elements, each processing element including a processor and memory, wherein each processing element includes a single sorting element of the sequence of sorting elements. 
     
     
         8 . The device of  claim 1 , further comprising a sequence of processing elements, each processing element including a processor and memory, wherein each processing element includes a subsequence of sorting elements of the sequence of sorting elements. 
     
     
         9 . The device of  claim 1 , further comprising a controller configured to control the sequence of sorting elements to simultaneously apply the retention logic. 
     
     
         10 . A device comprising:
 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 apply retention logic to an input value and a retained value, 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 retention logic is configured to retain at the sorting element one of the input value and the retained value, and wherein the retention logic 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 based on the retention logic.   
     
     
         11 . The device of  claim 10 , wherein the retention logic 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.   
     
     
         12 . The device of  claim 10 , wherein the retention logic 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.   
     
     
         13 . The device of  claim 10 , wherein the retention logic 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.   
     
     
         14 . The device of  claim 10 , wherein the retention logic is programmable. 
     
     
         15 . The device of  claim 10 , wherein a terminal sorting element of the logically parallel sequence of sorting elements comprises terminal retention logic configured to retain at the terminal sorting element one of the input value and the retained value, and wherein the terminal retention logic is configured to discard the other of the input value and the retained value. 
     
     
         16 . The device of  claim 10 , further comprising a sequence of processing elements, each processing element including a processor and memory, wherein each processing element includes a single sorting element of the logically parallel sequence of sorting elements. 
     
     
         17 . The device of  claim 10 , further comprising a sequence of processing elements, each processing element including a processor and memory, wherein each processing element includes a subsequence of sorting elements of the logically parallel sequence of sorting elements. 
     
     
         18 . The device of  claim 10 , further comprising a controller configured to control the sequence of sorting elements to simultaneously apply the retention logic.