Patent Publication Number: US-9424308-B2

Title: Hierarchical in-memory sort engine

Description:
FIELD OF THE INVENTION 
     The present disclosure generally relates to computer implemented sorting techniques and tools, and more particularly to hardware-implemented sort engines. 
     BACKGROUND 
     Sorting and searching data have several applications in the database and analytics domains. Sorting operations involve reordering data in a particular order, and a conditional search operation may involve retrieving a particular entry from the sorted data. Responding to queries to the database, ranking these responses based on their relevance or other metrics, and determining the most frequently accessed entries are some of the operations that may depend on such sorting and conditional searching. These operations usually involve processing large amounts of data. 
     Data is conventionally fetched from a storage device, such as memory or caches, to a general purpose computation module (usually a processor), which carries out the sort and search operations. One algorithm used for sorting is the Batcher&#39;s Odd-Event Sort. Existing software and hardware implementations of this sort algorithm have several limitations and drawbacks, including, for example, large overhead, slow speed, and high cost. 
     Batcher&#39;s Odd-Event Sort may be implemented, for an array of n elements X 1  to Xn, as follows. An odd-even pair may be defined as a first element having an odd subscript, and a next element having an even subscript. In a first step of the sort operation, every element with an odd subscript, i.e., X 1 , X 3 , . . . , is compared with its respective successor element having an even subscript, i.e., X 2 , X 4 , . . . . For any given comparison, in the case of an ascending sort operation, if the odd element is greater than the even element, the two elements are swapped. This operation is performed for every odd-even pair in the array. In a second step, every element with an even subscript is compared with its successor element with an odd subscript, and their values are swapped if the element with the even subscript is larger. This operation is performed for every even-odd pair in the array. The operations of the first and second steps are repeated, alternately, until the entire array is sorted. 
     BRIEF SUMMARY 
     According to at least one embodiment, an in-memory sort engine that performs sort operations, including Batcher&#39;s Odd-Even Sort while increasing speed and reducing overhead and cost, and provides for custom programming, may be provided. 
     Accordingly, one embodiment of the present disclosure includes a sorting module including a two-dimensional (2D) local sorting module. The 2D local sorting module may include a first data storage element, a second data storage element adjacent to the first data storage element along a first axis, whereby the first and second data storage elements are operatively connected via a first comparator, a third data storage element adjacent to the second data storage element along a second axis, where the second axis is substantially perpendicular to the first axis, whereby the second and third data storage elements are operatively connected via a second comparator, a fourth data storage element adjacent to the third data storage element along the first axis, and adjacent to the first data storage along the second axis, whereby the third and fourth data storage elements are operatively connected via a third comparator, and the first and fourth data storage elements are operatively connected via a fourth comparator. 
     The first, second, third, and fourth comparators may be configured to logically compare data stored in adjacent ones of the first, second, third, and fourth data storage elements according to a sorting order indicated by a processor. The embodiment may also include a completion detector configured to detect outputs of the first, second, third and fourth comparators to determine a completion of sorting operations. 
     A further embodiment of the disclosure may include a hardware-implemented local sorting module. The local sorting module may include first and second data storage elements operatively connected to a first comparator for comparing first and second data words stored in the first and second data storage elements, where for each bit in the first data word, the first storage element includes a first storage device receiving an input from a multiplexer (MUX). The MUX may include the following elements: a first MUX input corresponding to a first bit of the first data word; a second MUX input corresponding to a first bit of an external input data word; a third MUX input corresponding to a first output generated by a first XOR gate receiving both a second output of a first AND gate and the first bit of the first data word, the first AND gate receiving both a third output of the first comparator and a fourth output of a second XOR gate, the second XOR gate receiving both the first bit of the first data word and a first bit of the second data word stored in the second data storage element. The MUX may also include a plurality of control signals for selecting the first, second, or third MUX input, wherein at least one of the plurality of control signals corresponds to the third output. 
     A further embodiment of the disclosure may include a hardware implemented method for sorting a group of data words. The method may load, using a processor, first and second sets of data words in the group of data words into first and second two-dimensional (2D) local sorting modules. The method may locally sort the first set of data words using the first 2D local sorting module, and may further locally sort the second set of data words using the second 2D local sorting module. The method may globally sort the locally sorted first set of data words and the locally sorted second set of data words using a global sorting module. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         FIG. 1  depicts an exemplary one-dimensional local sorting module, according to an embodiment of the present disclosure. 
         FIG. 2A  depicts an exemplary circuit-level implementation of the one-dimensional local sorting module of  FIG. 1 , using a compare-and-flip technique, according to an embodiment of the present disclosure. 
         FIG. 2B  depicts an exemplary priority decoder component of the one-dimensional local sorting module of  FIGS. 1-2A , according to an embodiment of the present disclosure. 
         FIG. 3  depicts an exemplary circuit-level implementation of the one-dimensional local sorting module of  FIG. 1 , using a compare-and-swap technique, according to an embodiment of the present disclosure. 
         FIG. 4  depicts an exemplary two-dimensional local sorting module, according to an embodiment of the present disclosure. 
         FIG. 5  depicts an exemplary sorting module having a hierarchical sorting structure, according to an embodiment of the present disclosure. 
         FIG. 6  depicts an exemplary implementation of the global sorting module of  FIG. 5 , using a pipeline sort technique, according to an embodiment of the present disclosure. 
         FIG. 7A  depicts an exemplary implementation of the sorting modules of  FIGS. 1-6  as an on-chip module, according to an exemplary embodiment of the present disclosure. 
         FIG. 7B  depicts an exemplary implementation of the sorting modules of  FIGS. 1-6  as an off-chip accelerator, according to an exemplary embodiment of the present disclosure. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  depicts an exemplary one-dimensional (1D) local sorting module  100 , according to an embodiment of the present disclosure. The local sorting module  100  may be used to sort data values (also referred to as data words) that it receives as input. The local sorting module  100  may be an integrated circuit (IC) on board a computer processing chip (processor), or may be an off-chip circuit operatively connected to the processor. Additional details on the placement of the local sorting module  100  within a computer&#39;s and/or a processor&#39;s architecture are discussed in greater detail below in connection with  FIGS. 7A-B . 
     The local sorting module  100  may receive input data  150 , for sorting, from an input source. The input source may include, for example, the processor, a programming circuit within or connected to the processor, caches, memory, other internal or external data sources within the memory hierarchy of the computer system within which the processor is integrated, or a combination thereof. The local sorting module  100  may store the received input data  150  in storage elements  102 A-C. Each storage element  102 A-C may include, for example, a latch-based memory structure, such as a flip-flop, that stores the input data  150 . Other memory structures may be used as well. The local sorting module  100  may have additional storage elements (not shown) that may store additional input data  150 . The number of instances of data inputs  150  need not equal the number of storage elements  102  that are available in the local sorting module  100 . According to one embodiment, each storage element  102 A-C may store a data value having a size of a 32-bit word. 
     The local sorting module  100  may also include one or more comparators  104 A-B, each separating a pair of adjacent storage elements  102 A-C. Each additional storage element  102  may be separated from an adjacent storage element by an additional comparator  104 . According to one embodiment, each comparator  104 A-B may be a digital binary comparator configured to perform a sort operation between data values stored in a pair of adjacent storage elements  102 . The comparators  104  may perform bitwise conditional comparison and sort (“compare-sort”) operations using, for example, a compare-and-flip or a compare-and-swap operation (“flip/swap”), based on contents of the pair of adjacent storage elements  102 . For example, the comparator  104 A may compare and flip/swap the data in one storage element  102 A with the data in another storage element  102 B, according to a comparison order (ascending or descending) as determined by the processor and/or the program circuitry. Similarly, the comparator  104 B may compare and flip/swap the data in the storage element  102 B with the data in the storage element  102 C. 
     The compare-sort operations of the comparators  104  may be used to perform odd-even sort operations. Data values stored in pairs of adjacent storage elements  102  may be compared by their corresponding intermediary comparator  104 . For example, in one clock cycle, the comparator  104 A may compare, and sort if necessary, the data values stored in the storage elements  102 A and  102 B; this may be considered a comparison between an odd/even pair of storage elements  102 . In a following cycle, the comparator  104 B may compare, and sort if necessary, the data values of the storage elements  102 B and  102 C; this may be considered a comparison between an even/odd pair. Through successive cycles, therefore, the local sorting module may perform the Batcher&#39;s Odd-Even Sort, until the data in all the storage elements  102  are sorted. 
     According to an aspect of the disclosure, the comparators  104  may perform a sort operation using a compare-and-flip technique. In one example, the comparator  104 A may determine that the value stored in the storage element  102 A (the “first value”) is larger than the value in the storage element  102 B (the “second value”). In order to sort these two values in ascending order, the comparator  104 A stores the second value in the storage element  102 A, and the first value in the storage element  102 B, by selectively flipping non-matching bits of each storage element  102 A-B as necessary, whilst leaving other bits (i.e., the matching bits) unchanged. Additional details of this technique are discussed in greater detail in connection with  FIGS. 2A-B , below. Amongst other benefits, the compare-and-flip technique may lead to power efficiencies by changing only bits that require such change. 
     According to a further aspect of the present disclosure, the comparators  104  may perform a sort using a compare-and-swap technique. In one example, the comparator  104 A may determine that the value stored in the storage element  102 A (the “first value”) is larger than the value in the storage element  102 B (the “second value”). In order to sort these two values in ascending order, the comparator  104 A stores the second value in the storage element  102 A, and the first value in the storage element  102 B, by swapping the two values. Additional details of this technique are discussed in greater detail in connection with  FIG. 3 , below. 
     The order of sorting by the comparators  104 A-B may be determined, in one embodiment, directly or indirectly, via one or more input ports to the comparators  104 A-C. For example, a program may require a set of data to be sorted in ascending order, or in descending order. The program may direct the processor to cause the comparators  104 A-B to swap the contents of the storage elements  102 A-C in either a predetermined ascending or a predetermined descending order. In another embodiment, the order in which the sort is performed may be preconfigured into the internal circuitry of the comparators  104 A-B. 
     According to an aspect of the present disclosure, an output of each comparator  104 A-B may be fed to a completion detector  154  ( FIG. 1 ), which detects when no sort operations have been performed after a set of comparisons, indicating that the data in the storage elements is properly sorted, and that no additional comparisons are necessary. The completion detector may include, for example, a NOR gate  155  that receives inputs corresponding to outputs of the comparators  104 . As will be discussed below in connection with  FIGS. 2A-B , a logic HIGH (hereinafter, “HIGH”) output of a comparator  104  indicates that the data values stored by the corresponding storage elements  102 , whose values the comparator  104  compares, are out of order and should be sorted. Conversely, a logic LOW (hereinafter, “LOW”) output indicates that the data values stored in the corresponding storage elements  102  are in order. Therefore, in a given comparison cycle, if the data values in all storage elements  102  are sorted, the outputs of all comparators  104  are LOW. Since these outputs are fed as inputs to the NOR gate  155 , the output of the NOR gate  155  is HIGH under these logic conditions. A HIGH or LOW output from the NOR gate  155  corresponds, in the disclosed embodiment, to an output of the completion detector  154 . A HIGH output indicates that sorting operations of the local sorting module  100  are complete. Conversely, a LOW output indicates that sorting operations of the local sorting module  100  are incomplete. 
     According to an embodiment of the disclosure, the local sorting module  100  may operatively be connected to one or more clocks (not shown in  FIG. 1 ) that synchronize its operations, such that each comparator  104 A-B may perform one comparison per clock cycle. The total sorting cycle may depend on the particular implementation of the disclosed embodiment; however, at most, n clock cycles may be required for sorting n data values stored in n data storage elements  104 . 
     As discussed below in connection with  FIGS. 5-6 , the local sorting module  100  depicted in  FIG. 1  may be operatively connected to one or more additional local sorting modules  100  to perform parallel sorting operations, and/or to facilitate a hierarchical sorting operation. 
       FIG. 2A  depicts an exemplary circuit-level implementation of the 1D local sorting module  100  of  FIG. 1 , using a compare-and-flip technique, according to an embodiment of the present disclosure. Like elements in  FIGS. 1 and 2A  are labeled with like reference characters. The local sorting module  100  depicted in  FIG. 2A  performs an ascending sort, and includes the storage elements  102 A-C, each of which can store up to a 32-bit word, and further includes the comparators  104 A-B. It shall be understood by a person of ordinary skill in the art that the disclosed circuitry may also be used to perform a descending sort, and may further be modified to compare and sort data words of other sizes, without departing from the spirit and scope of the present disclosure. 
     In the depicted embodiment, the comparators  104 A-B may be 32-bit static comparators configured to perform compare-and-flip operations between their respective adjacent storage elements  102  (for example, storage element  102 A and  102 B, or storage elements  102 B and  102 C). Accordingly, each data value stored in a storage element  102  may be a 32-bit word consisting of 32 bits numbered b 0 -b 31 , wherein b 0  and b 31  are the 32-bit word&#39;s Most Significant Bit (MSB) and the Least Significant Bit (LSB), respectively. Given a binary vector such as (0101 . . . 0101), the leftmost bit is the MSB ( 0 ) and the rightmost bit is the LSB ( 1 ). It shall be apparent to a person of ordinary skill in the art that bit-words of other sizes and other bit position conventions may be used without departing from the spirit and scope of the present disclosure. 
     With continued reference to  FIG. 2A , the storage element  102 B is depicted at a different level of detail than the storage elements  102 A and  102 C, although these storage elements may, but need not, be identical. The internal circuitry of the storage element  102 B is depicted only with respect to its k th  bit, while the storage elements  102 A and  102 C are depicted more generally, including their respective 32 bits b 0 -b k -b 31  in block form. It shall be understood by a person of ordinary skill in the art, however, that the storage elements  102 A-C may, but need not, be identical or similar to one another. For example, the storage element  102 A may be a first storage element in the local sorting module  100 , and may be connected only to the comparator  104 A, whereas the storage element  102 B may be an intermediary storage element and may be connected to two comparators  104 A and  104 B (it may also be connected to additional comparators, in some embodiments, as discussed with respect to  FIGS. 4-6 ). 
     Each bit of a given 32 bit-word stored in a given storage element  102 A-C may be set in a corresponding storage device or storage structure, such as a flip-flop  235 , using a corresponding multiplexer (MUX)  236 , whose data inputs and control inputs determine the value that is fed into and stored by the storage structure. Each flip-flop  235  may be set using a clock signal  233  fed into the flip-flop  235 . According to one aspect of the disclosed embodiment, the local sorting module  100  may set a given flip-flop, for example, the flip-flop  235  of the storage element  102 B, using a corresponding MUX  236  having the following exemplary Inputs  1 - 7 :
         Input  1 : A feedback input corresponding to a Q k  value, stored in and outputted by the flip-flop  235 , where Q k  corresponds to the k th  bit of the data value stored in the storage element  102 B. Input  1  may be coupled to the flip-flop  235  through the MUX  236  when all MUX selection signals S 0 , and S 1 , and EIC, are 0. Other embodiments of the present disclosure may be implemented without use of Input  1 , whereby the data value (i.e., the bit) Q k  stored in the flip-flop  235  is maintained, without being set again, by disabling a corresponding clock input  233  to the flip-flop  235 .   Input  2 : The output of an XOR gate  230 A from the comparator  104 A. This output may be used, for example, during an odd-even comparison execution cycle, to control whether b k  of the storage element  102 B should be flipped based on a comparison with b k  of the storage element  102 A. Input  2  may be coupled to the flip-flop  235  through the MUX  236  when the MUX selection signal S 0  is 1, S 1  is 0, and EIC is 0.   Input  3 : An External Input (EI)  270 , corresponding to a bit of an external data value to be stored in the flip-flop  235 . This may be, for example, a bit from the input data  150  ( FIG. 1 ). Input  3  may be coupled to the flip-flop  235  through the MUX  236  when an external input control signal (EIC)  260  to the MUX  236  is 1, while S 0  and S 1  are 0.   Input  4 : The output of an XOR gate  230 B from the comparator  104 B. This output may be used, for example, during an even-odd comparison execution cycle, to control whether b k  of the storage element  102 B should be flipped based on a comparison with b k  of the storage element  102 C. Input  4  may be coupled to the flip-flop  235  through the MUX  236  when the MUX selection signal S 1  is 1, while S 0  and EIC are 0.   Input  5 : An External Input Control (EIC)  260 . This control allows the local sorting module  100  to store data into the flip-flops  235 . When this control signal is 1, EI  270  is selected as the input so that the corresponding data bit is inputted to the flip-flop  235  and stored. When EIC  260  is 0, EI  270  is not selected. When EIC  260  is 0, S 0  and S 1  may be 0.   Inputs  6  &amp;  7 : Signal inputs S 0    251 A and S 1    251 B correspond to outputs  250 A and  250 B of the comparators  104 A and  104 B, respectively. These signals are used, in the depicted embodiment, to enable ascending sort operations using the MUX  236 , and are enabled only when EIC  260  is LOW (in other embodiments, they may be used to enable descending sort operations). Additional details of the source of these outputs and signals and the effects they have on the circuitry of the local sorting module  100  are described in greater detail, below, in connection with  FIG. 2B .       

     It should be noted that S 1  and S 0  are labeled as such for ease of reference, and to more clearly define operations of the local sorting module  100  and its components. However, it shall be apparent to a person of ordinary skill in the art that these control signals may correspond to outputs of comparators  104  (e.g., the comparator  104 A and the comparator  104 B). 
     Initially, each bit stored in the storage element  102 B may be set based on a corresponding EI  270  bit value (Input  3  to the MUX  236 ) by setting EIC  260 =1, S 0 =0, S 1 =0. The result of the MUX  236  in this instance is fed to the flip-flop  235 , which stores the corresponding value (data from EI  270 ). As part of the local sorting module&#39;s  100  further operations during other cycles, the MUX  236  and the control signals may be used to select other inputs from the module&#39;s  100  internal circuitry to carry out a sort operation, where necessary. 
     With continued reference to  FIG. 2A , for a given pair of adjacent storage elements  102  undergoing a comparison in a cycle, such as the storage elements  102 A and  102 B, the local sorting module  100  determines whether their respective data values should be sorted (i.e., reordered, according to a predetermined sorting order). Where this is the case, the local sorting module  100  may perform a bit-by-bit comparison of the two data values stored in the pair using the comparator  104 A, and may flip bits that do not match. 
     For example, each comparator  104 A-B may include 32 successive XOR gates  220  (for example, the XOR gates  220 A in the comparator  104 A, and the XOR gates  220 B in the comparator  104 B), each of which receives, as inputs, k th  bits (b k ) of the two storage elements  102 A-B whose data values the comparator is to compare, where k is in the range {0-31}. The output of each XOR gate  220 A/B may be fed to other components of the circuitry of the local storage module  100 , as described below, to further facilitate sorting operations. For example, this may include a priority decoder  241 A/B component(s) of respective comparators  104 A/B, described in greater detail in connection with  FIG. 2B , below. This additional circuitry of the comparators  104 A-B enables the local sorting module  100  to determine which of the two values under comparison is larger, and whether a sorting operation (using, for example, a flip technique) should be performed based on the two data values. 
     Where a comparator  104 , for example, the comparator  104 A, has determined that two values do not require sorting (i.e., reordering), based on results of the priority decoder(s)  241 A (this result may correspond to the output  250 A of the comparator  104 A), then all MUX selection signals EIC, S 0 , and S 1  may be set to 0. This results in transferring the Q k  output back to the flip-flop  235 , keeping the data bit stored therein the same. Other techniques for maintaining the value stored in the flip-flop  235  are possible (for example, the clock  233  input to the flip-flop  235  may be disabled). 
     Where a comparator  104 , for example, the comparator  104 A, has determined that two values should be sorted (i.e., reordered) based on results of the priority decoder(s)  241 A (this result may correspond to the output  250 A of the comparator  104 A), it may compare the b k  bit of the storage element  102 A to the b k  bit of the storage element  102 B, for all k values {0-31}, and flip bits that do not match. Initially, each such b k  is stored in a flip-flop  235  of the corresponding storage element  102 A/B that feeds into the XOR gate  220 A. The result of the XOR gate  220 A is fed into an AND gate  240 A, along with the result  250 A of the comparator  104 A. The result of the AND gate  240 A, as well as Q k  (the b k  value of the storage element  102 B), are fed into an XOR gate  230 A. The output of the XOR gate  230 A is inputted to the MUX  236  in the storage element  102 B. The output  250 A of the comparator  104 A may additionally be inputted to a MUX (not shown) of the storage element  102 A as a corresponding control signal S 1  (not shown) within the storage element  102 A. 
     Similarly, during a separate cycle, the comparator  104 B may compare the b k  bit of the storage element  102 B to the b k  bit of the storage element  102 C, wherein the XOR gate  220 B receives as inputs respective b k  bits of the two storage elements  102 B and  102 C. The result of the XOR gate  220 B and the result  250 B of the comparator  104 B are fed into the AND gate  240 B. The result of the AND gate  240 B and Q k  are fed into an XOR gate  230 B, whose output is fed into the MUX  236 . The output of the XOR gate  220 B is also fed into the priority decoder(s)  241 B. The output  250 B of the comparator  104 B is additionally fed into the MUX  236  as a control signal, e.g., S 1    251 B. The output  250 B may also be fed into a MUX (not shown) of the storage element  102 C as a corresponding control signal S 0  (not shown). 
     As discussed above and as illustrated in  FIG. 2A , the storage element  102 B may be an intermediary storage element, i.e., neither the first nor the last storage element  102  of the local sorting module  100 . However, first and last storage elements  102  (e.g., the storage elements  102 A and  102 C) may have similar internal circuitry, except that they may (but need not) be connected to only one comparator. For example, a MUX of a b k  bit of the storage element  102 A may have fewer inputs than that of the storage element  102 B (it may, for example, have only inputs  1 ,  3 , and  4 , and control signals EIC and S 0 , where S 0  corresponds to the output  250 A of the comparator  104 A). Similarly, a MUX of a b k  bit of the storage element  102 C may have fewer inputs than that of the storage element  102 B (it may, for example, have only inputs  1 ,  2 , and  3 , and control signals EIC and S 0 , where S 0  corresponds to the output  250 B of the comparator  104 B). 
     As an illustrative example, let V A ={a binary vector stored in the storage element  102 A}, V B ={a binary vector stored in the storage element  102 B}; Q kA ={b k  bit in V A }; and Q kB ={b k  bit in V B }, where k is in the range {0-31}. The comparator  104 A may compare V A  and V B  during an odd-even comparison cycle, and reorder them if necessary, to sort them in ascending order. Prior to a comparison operation, a given Q kA/B  value may be stored in the flip-flop  235  of its respective storage element  102 A/B. In one comparison cycle, Q kA  and Q kB  are fed into the XOR gate  220 A. There are three comparison scenarios to consider: V A =V B , V A &gt;V B , and V A &lt;V B . 
     In the first scenario, where V A =V B , the output of the priority decoder(s)  220 A, and a corresponding comparator  104 A output  250 A, are LOW, indicating that V A  and V B  are equal and should not be reordered (the manner in which these outputs are determined are discussed below in connection with  FIG. 2B ). The AND gate  240 A takes, as a first input, the output  250 A of the comparator  104 A. Since the output  250 A is LOW, the output of the AND gate  240 A is LOW, regardless of a second input to the AND gate  240 A (i.e., where the output  250 A is LOW, the b k  bits of the storage elements  102 A and  102 B cannot cause a sort operation). This ensures that the value of Q kB  remains the same, since the output  250 A is LOW and is fed into the MUX  236  as the control S 0    251 A. The MUX  236  may be configured such that when S 0    251 A is LOW (other MUX  236  selection signals EIC and S 1  also are 0), it selects Input  1  corresponding to Q kB . Alternatively, to retain the flip-flop  235  data bit, the clock input  233  to the flip-flop  235  may be disabled where a reordering is not required (e.g., where VA=VB, or where all MUX selection signals EIC, S 0 , and S 1  are LOW). 
     In the second scenario, where V A &gt;V B , the output of the priority decoder(s)  220 A, and a corresponding comparator  104 A output  250 A, are HIGH. Therefore, the comparator  104 A sorts the two binary vectors by flipping their respective non-matching bits. This is accomplished using, in part, the XOR gate  220 A, whose output is LOW if the Q kA =Q kB . If the output is LOW, it causes the output to the AND gate  240 A to be LOW. This ensures that the output of the XOR gate  230 A is HIGH only if Q kB  is (1). Since S 0    251 A is set to 1 (in this example) based on the output value  250 A of the comparator  104 A, it is HIGH where V A &gt;V B , and the MUX  236  may be configured to select Input  2  corresponding to the output of the XOR gate  230 A. Therefore, the output of the XOR gate  230 A will correspond, under these logic conditions, to the value of Q kB , which is selected as an input to the MUX  236  and fed back to the flip-flop  235 . Accordingly, where V A &gt;V B  and Q kA =Q kB , no bits are flipped. 
     However, if V A &gt;V B , but Q kA &gt;Q kB , the output of the XOR gate  220 A, as well as the output  250 A of the comparator  104 A, will be HIGH. This causes the output of the AND gate  240 A to be HIGH. This, in turn, causes the output of the XOR gate  230 A to be HIGH (since Q kB , by definition, is 0 under these logic conditions). Since S 0    251 A and Input  2  (the latter corresponds to the output of the XOR gate  230 A) are both HIGH, the MUX  236  flips the value stored in the flip-flop  235 . 
     Similarly, if V A &gt;V B , but Q kA &lt;Q kB , the output of the XOR gate  220 A, as well as the output  250 A of the comparator  104 A, will be HIGH. This causes the output of the AND gate  240 A to be HIGH. Since Q kB  is 0 (because it is, in this instance, less than Q kA ), and the output of the AND gate  240  is HIGH, the output of the XOR gate  230 A is HIGH. Since S 0    251 A is set to HIGH, the MUX  236  selects Input  2  (the output of the XOR gate  230 A). Therefore, this has the effect of retaining the value of Q kB  in the flip-flop  236 . 
     In the third scenario, where V A &lt;V B , the result of the priority decoder(s)  241 A and a corresponding comparator  104 A output  250 A are LOW. Accordingly, no sorting is performed. This result is ensured since S 0    251 A is set to LOW (S 1  and EIC  260  also are LOW), causing the MUX  236  to select Input  1  corresponding to Q kB , such that no bit is flipped for any value of k. 
       FIG. 2B  depicts an exemplary priority decoder(s)  241  component of the 1D local sorting module  100  of  FIGS. 1-2A , according to an embodiment of the present disclosure. Like elements in  FIGS. 1-2B  are labeled using like reference characters. The priority decoders  241  may be implemented as components of the comparators  104  of the local sorting module  100 , and may be used to determine whether data values stored in adjacent storage elements  102  should be sorted (i.e., reordered). Each comparator  104  may have a corresponding set of priority decoders  241 . For example, the comparator  104 A may have 32 priority decoders  241 A, such as Priority Decoders  1 - 31  (only Priority Decoders  1 ,  2  and  31  are shown), one for processing each of 32 bit pairs from the adjacent storage elements  102 A and  102 B. 
     For example, in the comparator  104 A (the comparator  104 A compares data values stored in storage elements  102 A and  102 B), the result of the operations of the priority decoders  241 A is outputted as the comparator output  250 A. As discussed in connection with  FIG. 2A , above, this output  250 A is fed into respective MUXs  236  of the storage elements  102 A and  102 B as a control signal, which may be an S 0  control signal (not shown) in the case of the storage element  102 A, or S 1    251 B, in the case of storage element  102 B. 
     Generally, given exemplary first and second binary vectors (0110) and (0101), comparing the MSB of each vector (0 in both cases) alone does not allow a determination of which vector is larger, since both bits are equal in this example. Therefore, in such a case, the priority decoders  241 A check successive bits of the first vector against corresponding bits of the second vector (pairs of MSB, MSB- 1 , MSB- 2  . . . LSB) until one of the priority decoders  241 A detects a pair of unequal bits. When a priority decoder  241 A detects a pair of unequal bits, a sort operation (i.e., reordering) may be triggered, depending on which vector value is larger, and which sorting order the local sorting module  100  is instructed to carry out. 
     Accordingly, comparison operations of the priority decoders  241 A of the comparator  104 A may begin with a comparison of the MSB of corresponding 32-bit values in the storage elements  102 A and  102 B using an XOR gate  220 A, as described above with respect to  FIG. 2A . The output of the XOR gate  220 A is fed into a corresponding priority decoder  241 A (e.g., Priority Decoder  1 ). If the two bits are different, the output of the XOR gate  220 A will be HIGH, indicating that a reordering may be required to perform a sort operation, depending on a final output  250 A value of the comparator  104 A. A HIGH state of a given XOR  220 A output enables a corresponding priority decoder  241 A. Accordingly, the output of the XOR gate  220 A is fed into an AND gate  222 A followed by an OR gate  224 A, whose output will also be HIGH when a reordering operation is required. This has the effect of determining whether a sort operation (reordering the contents of the storage elements  102 A and  102 B) should be carried out. 
     More specifically, assuming that a sort is to be performed in ascending order, a reordering operation (whether by swapping or flipping bits) may be required if the bit from the storage element  102 A is 1, and the bit from the storage element  102 B is 0. Where this is the case, the output of the XOR gate  220 A is HIGH, which enables the AND gate  222 A. The AND gate  222 A detects this inequality (since b 0 =1, it means that the MSB b 0  of the storage element  102 A is larger than that of the storage element  102 B). Accordingly, the AND gate  222 A output will be HIGH. This, in turn, is detected by the OR gate  224 A whose output also will be HIGH. A HIGH output of an OR gate  224 A causes the final output  250 A of the comparator  104 A to be HIGH, because it will cause an output of a subsequent OR gate  224 A to be HIGH. The output of the last OR gate  224 A corresponds to the output of the priority decoder  104 A. If the output of any OR gate  224 A is HIGH, no additional bit comparisons are required. Subsequent priority decoders  241 A are disable by the HIGH state of the OR gate  224 A output from a previous priority decoder  241 A, which is inverted and inputted to an AND gate  222 A in a next priority decoder  241 A. 
     Where a given pair of MSB bits under comparison (from the storage elements  102 A and  102 B) are different, and b 0  of the storage element  102 A is 0 and b 0  of the storage element  102 B is 1, the AND gate  222 A and OR gate  224 A outputs are LOW, even though the XOR gate  220 A output is HIGH. Therefore the corresponding priority decoder  241 A (for example, the Priority Decoder  1 ) does not generate a HIGH output, and does not cause the output  250 A of the comparator  104 A to be HIGH. This allows a subsequent priority decoder  241 A to compare the next MSB pair. 
     If the bits in an MSB pair under comparison are equal, the XOR gate  220 A output is LOW. This causes outputs of the AND gate  222 A and the OR gate  224 A to be LOW, which enables the priority decoder  241 A to begin to operate and perform a comparison of the next MSB pair. Accordingly, in the case of an ascending sort, the output  250 A of the comparator  104 A will be HIGH only if the data value stored in the storage element  102 A is larger than that of the storage element  102 B. 
     The AND gate  222 A has an additional input corresponding to an inverted output of the OR gate  224 A. This structure ensures that if the output of the OR gate  224 A is HIGH (indicating that a sort is required), subsequent priority decoders  241 A need not be activated. The output of the OR gate  224 A is fed into subsequent comparators  241 A until the last comparator  241 A outputs the value as the output  250 A of the comparator  104 A. 
     According to an aspect of the disclosure, a program may set a sorting order (ascending or descending) by setting an input value of a series of programmability components (not shown) operatively connected to each of the priority decoders  241 A. For example, in the case of the storage elements  102 A and  102 B under comparison by the comparator  104 A, each programmability component may include an XOR gate having inputs of a b k  bit from the storage element  102 A and a control input set by the program. The output of the programmability component is fed into the AND gate  222 A of the corresponding priority decoder. When the control input is 0, for example, the programmability component may be configured to cause the comparator  104 A to perform either an ascending sort or a descending sort, while a control input value of 1 may cause the comparator  104 A to perform an opposite sort, i.e., descending or ascending sort. 
     Referring now to  FIGS. 1-2B , certain names have been used to facilitate ease of reference to groups of functional elements of the local sorting module  100 . For example, the logic gates  220 A,  230 A, and  240 A have been referenced as belonging to the comparator  104 A. It shall be understood by a person of ordinary skill in the art, however, that these components may be grouped together with, for example, the storage element  102 B and/or the storage element  102 A, without departing from the spirit or scope of the disclosed invention. 
       FIG. 3  depicts an exemplary circuit-level implementation of the 1D local sorting module  100  of  FIG. 1 , using a compare-and-swap technique, according to an embodiment of the present disclosure. Like elements in  FIGS. 1 and 3  are labeled using like reference characters. The local sorting module  100  in  FIG. 3  includes the storage elements  102 A-B, the comparator  104 A, the clock  233 , and the completion detector  154 . It may include additional storage elements and comparators. 
     According to one embodiment, the comparator  104 A includes a comparison unit  302 . The comparison unit  302  may include, for example, a set of priority decoders (not shown in  FIG. 3 ), such as the priority decoders  241 A described in connection with  FIG. 2B , above. The comparison unit  302  receives the bits stored in the storage elements  102 A and  102 B, and determines if they should be reordered according to a predetermined sorting order. Based on the comparison, the comparison unit  302  generates an output C and its complement, C′. The comparison unit  302  may set C and C′ to HIGH where a sort operation is required, and otherwise to LOW. 
     For each bit-pair from the storage elements  102 A and  102 B, the comparator  104 A includes two multiplexers, MUX  336 A and  336 B. For clarity,  FIG. 3  depicts only one pair of multiplexers and their corresponding connections to other components of the local sorting module  100 , including the storage element  102 A and  102 B, and the comparison unit  302 . Both the MUX  336 A and the MUX  336 B may have at least two inputs: one being a bit stored in the storage element  102 A, the other being the bit from the storage element  102 B. The MUX  336 A and the MUX  336 B each have at least one control signal input corresponding to C and C′ respectively. 
     If the value of C and C′ are LOW, no sort operation is performed. The MUX  336 A selects the bit from the storage element  102 A and provides that value as an output that is fed back to the storage element  102 A. Similarly, the MUX  336 B selects the bit from the storage element  102 B and provides that bit as an output that is fed back to the storage element  102 B. This has the effect of leaving the bits stored in each of the storage elements  102 A-B unchanged. Alternatively, the bits stored in the storage elements  102 A-B may be maintained by disabling the clock  233  input to the storage elements  102 A-B if C/C′ are LOW. 
     Conversely, if the values of C and C′ are HIGH, a swap operation is performed whereby the MUX  336 A selects the bit from the storage element  102 B and provides that bit as an output that is fed to the storage element  102 A for storage. Similarly, the MUX  336 B selects the bit from the storage element  102 A and provides that bit as an output that is fed to the storage element  102 B for storage. This has the effect of swapping the bits stored in each of the storage elements  102 A-B during a sort operation. The data storage elements  102 A and  102 B fetch the MUX  336 A and  336 B outputs, respectively based on the clock  233  signal, or after the muxing operation has been completed. 
     According to aspect of the disclosure, the comparison unit  302  also includes an output to the completion detector  154 , which may be, in one embodiment, the same signal C′ (or C) or a modified form thereof, that signals whether a swap operation is to be performed. For example, if C/C′ is HIGH, a swap is to be performed, and the completion detector determines that the sort operation of the local sorting module  100  is incomplete. If the value of C/C′ is LOW, however, the completion detector may determine that the sort operation may complete, depending on outputs of other comparators. 
       FIG. 4  depicts an exemplary two-dimensional (2D) local sorting module  400 , according to an embodiment of the present disclosure. Aspects of the local sorting module  400  may be similar to aspects of the local sorting module  100  of  FIGS. 1-3 . Like elements in  FIGS. 1-4  are labeled using like reference characters. The local sorting module  400  may be an on-chip or off-chip integrated circuit (IC), and may include a 2D array of storage elements  102 A-I, and comparators  104 A-L. In another embodiment, the local sorting module  400  may have four storage elements  102  and four comparators  104  arranged in a grid structure, wherein each storage element is substantially adjacent to at least two of the other storage elements, along an x-axis and a y-axis substantially perpendicular to the x-axis, respectively, and wherein each pair of adjacent storage elements includes one comparator situated between the two storage elements. 
     Each storage element  102 A-I may be positioned substantially adjacent to one to four other storage elements, separated from each of them by an intermediary comparator  104 . Each intermediary comparator  104  may be configured to perform bitwise compare-and-sort operations with respect to its adjoining storage elements  102 . For example, the comparator  104 A may have inputs of bits from the storage element  102 A-B, and may have output of bits to each of these two storage elements, such that it may sort their respective data values according to a predetermined sorting order. For clarity, additional circuitry of the storage elements  102 A-I, and the comparators  104 A-L, are omitted. It will be understood by a person of ordinary skill in the art that each of these components may have additional inputs and outputs without departing from or limiting the scope of the present disclosure. These additional inputs may include, for example: data inputs, control signals, clock signals, comparator logic signals, etc. Furthermore, the array of storage elements  102 A-I and comparators  104 A-L may be expanded to include additional storage elements and comparators, wherein each additional storage element may be adjacent to up to four additional storage elements, and separated from each of them by a comparator. 
     According to an aspect of the disclosure, the storage elements  102  and the comparators  104  may be as described above in connection with  FIGS. 1-3 . Furthermore, connections between these components across rows and columns of the local sorting module  400  may be as described in connection with  FIGS. 1-3 . For example, the storage elements  102 A-C and comparators  104 A-B may be configured similarly to the storage elements and comparators of the local sorting module  400 . 
     The control signals (not shown) of the comparators  104 A-L may be used by a program circuitry and/or other components of a processor to determine whether to perform a sort operation in an ascending or descending order, and whether to perform a sort in a column-wise or row-wise order. For example, a program may set the control signals to perform a partial sort across rows/columns of the local sort module  400 , such that a sort is performed first in a row-wise order, for each row, and thereafter, column-wise for each column. To accomplish this, in one embodiment, the program circuitry (not shown) may enable the comparators  104 C-E and  104 H-J, by activating respective control signal inputs of these comparators, to enable column-wise sorting. For row-wise sorting, the program circuitry may activate respective control signal inputs of comparators  104 A,  104 F,  104 K, and  104 B,  104 G,  104 L. 
     In one example, the local sorting module  400  may perform a partial sort using the row/column technique. The data values stored in the storage elements  102 A-C may first be sorted row-wise. Data values stored in other rows also may be sorted. Thereafter, the data values stored in the storage elements  102 A,  102 D, and  102 G may be sorted column-wise. Data values stored in other columns also may be sorted. In one embodiment of the present disclosure, this sorting technique may sort batches of database entries according to different sorting criteria for difference sub-sequences. 
     In another example, the local sorting module  400  may perform a complete sort, as follows. Given a 2D array of N rows and M columns, the sort may be implemented by selectively swapping values of storage elements  102  in the following manner. Assuming X i,j  corresponds to a storage element  102  in the i th  row and j th  column, the comparators  104  may be programmed/activated using the program circuitry (not shown) so as to enable the following swap operations:
         Swap (X i−1,j , X i,j ) if X i−1,j &gt;X i,j , where i=2 . . . N and j is odd (this performs an ascending swap);   Swap (X i−1,j , X i,j ) if X i−1,j &lt;X i,j , where i=2 . . . N and j is even (this performs a descending swap);   Swap (X N,j , X N,j+1 ) if X N,j &gt;X i,j , where j&lt;N is odd; and   Swap (X N,j , X N,j+1 ) if X N,j &lt;X i,j , where j&lt;N is even;       

       FIG. 5  depicts an exemplary sorting module  500  having a hierarchical sorting structure, according to an embodiment of the present disclosure. Like elements in  FIGS. 1-5  are labeled using like reference characters. The sorting module  500  may include two or more local sorting modules  501 A-C and a global sorting module  502 . This hierarchical sorting structure enables relatively faster sorting operations while minimizing silicon overhead. Each of the local sorting modules  501 A-C may be a 1D local sorting module  100  or a 2D local sorting module  400 , as described in connection with  FIGS. 1-4 . Although the sorting module  500  is depicted as having three local sorting modules  501 A-C, the sorting module  500  may have a number of local sorting modules in the range of {2-n}. A sort operation may be performed using, in part, all or a subset of the local sorting modules  501 A-C of the sorting module  500 . 
     The local sorting modules  501 A-C may receive data inputs  150 A-C, respectively. The data inputs  150 A-C may be, for example, binary arrays or vectors, represented in  FIG. 5  using decimal numerals. The local sorting modules  501 A-C may receive the data inputs  150 A-C from one or more sources, and may sort them in parallel, as described above in connection with  FIGS. 1-4 , preferably using an even/odd sorting algorithm. However, other sorting approaches may be used, if desired. Each local sorting module  501 A-C may generate a sorted list  152 A-C based on the input data  150 A-C, and generate a corresponding output block  503 A-C. Output blocks  503 A-C may be provided as an input to the global sort module  502  for further sorting operations. 
       FIG. 6  depicts an exemplary embodiment of the global sorting module  502  of  FIG. 5 , based on a pipeline sort implementation. Like elements in  FIGS. 1-6  are labeled using like reference characters. The global sorting begins after all local sorting has been completed, which can be detected by the global sorting module  502  through communication with the completion detector  154  ( FIG. 1 ). The global sorting module  502  receives k sorted memory blocks  603  (“sorted blocks  603 ”). The sorted blocks  603  may be, for example, the same as, or generated based on, the sorted blocks  503 A-C generated in the sorting module  500  ( FIG. 5 ) by successive local sorting modules  501 A-C. In the depicted embodiment, contents of each sorted block  603  are organized as having their minimum value M as the right-most entry of the corresponding memory block, followed by M′, and so forth. Each M value may be, for example, a binary vector. It shall be apparent to a person of ordinary skill in the art that the sorted blocks  603  may be sorted in a different order, without departing from the spirit or scope of the present disclosure. 
     The global sorting module  502  may include a series of buffers  604 A-D, whose number may depend, in one embodiment, on the number of elements in each sorted block  602 . Each buffer  605  may include a series of storage elements, and may temporarily store elements of the sorted blocks  603 , to facilitate compare-and-sort operations during a tournament sort. The tournament determines a winner output corresponding to a smallest value (or largest value, depending on the sort order), based on results of the final set of comparators  604 D. Assuming 2 k  tournament sorts, k stages of buffers  605  may be used to make this determination. This results in significantly faster sorting compared to existing techniques. For example, for sorting 1024 values, only 10 cycles (log 2  1024=10) are required. 
     The global sorting module  502  may also include a series of comparator sets  605 A-D. Each of these comparator sets may, but need not, include comparators  104  as described in connection with  FIGS. 1-5 , above, and each comparator may be configured to compare two data elements and sort/reorder their contents where necessary. The number of the comparator sets  605  may depend, in one embodiment, on the number of buffers  604 . Each pair of buffers  604  may be separated by a comparator set  605 . Additionally, the sorted blocks  602  and the first buffer  604 A may be separated by a comparator set  605 A. 
     Using the circuitry described above, the sorting module  502  may perform a global sort. According to an exemplary embodiment, performing the global sort may be accomplished as follows. As stated above, the global sorting may begin once all local sorting has been completed. 
     Initially, the data in the buffers  604 A-D may be set to an initialization value by default; for example, all ones (“INF”), or all zeroes. The smallest element (M i ) from each sorted block  602  may be compared with the value stored in a corresponding storage element in the first buffer  604 A using a corresponding comparator in the comparator set  605 A. In the first operational pass of the circuitry, each smallest sorted block  602  element M i  is compared to the (INF) value stored in the buffer  604 A, in which case the comparison may necessitate a swap. For each sorted block  602 , this has the effect of entering (INF) into the right-most element of that sorted block  602 . This results in a completion detector being reset, which causes the compare operation between consecutive elements in the sorted block  602  to resume, such that the INF value is moved to a left-most position in the array, and M′ is moved to the M position. Since (INF) is greater than all other elements in each of the sorted blocks  602 , each block is shifted to the right. For example, in the case of the first sorted block  602 , M 1  is swapped with (INF) stored in a first storage element of the buffer  604 A via a first comparator in the comparator set  605 A. Subsequently, the first sorted block  604 A is restored such that M 1 ′ moves into the M 1  position for comparison during a subsequent cycle. Alternatively, the sorted blocks  603  may operate as simple shift registers to provide the input to a first tournament stage of buffer  605 A. A shift resister may shift a given bit to the right only when the bit is moved to the next stage as a tournament winner. 
     Neighboring elements within the first buffer  604 A are compared using the comparators in the comparator set  605 B, and in each comparison, the smaller element is swapped with the corresponding element in buffer  604 C. This process continues with respect to other buffers  604  using additional comparator sets  605  until the overall smallest element is obtained as the output after k cycles. Consequently, the global sorting module  502  outputs one element per cycle, which is the overall minimum element within all sorted blocks  602 . 
     As each minimum element is outputted by the global sorting module  502 , another element is swapped from the corresponding sorted block  602 , which originally contains the outputted minimum element, into the first buffer  604 A. 
     The above process is repeated until all elements of the sorted blocks  602  are evaluated and outputted by the global sorting module  502 , in order. 
     Since data in the first buffer  604 A may be written from the sorted blocks  602  while simultaneously being read out and swapped with contents of the second buffer  604 B, master and slave buffering stages may be implemented. Techniques for implementing master and slave buffer are well known to persons of ordinary skill in the art. 
     Implementing the global sorting techniques described above may require additional storage elements than may otherwise be used in a given system architecture. To minimize a potential increase in silicon overhead, selecting local and global sort module lengths may take the following into consideration. Using relatively more storage elements for local sorting may require more sorting time with less silicon area. Using relatively more storage elements for global sorting may shorten sorting time, but may increase silicon overhead. Therefore, it may be desirable to implement the above described hierarchical sorting, whereby performing local sorts first, followed by global sorts, may provide an optimal approach in terms of performance and silicon overhead. 
       FIG. 7A  depicts an exemplary implementation of the sorting modules of  FIGS. 1-6  as an on-chip module, according to an exemplary embodiment of the present disclosure. A computer processor  1100  may include on-board circuitry including one or more sorting modules  1101   1 - n . Each of the sorting modules  1101  may be, for example, a local sorting module, global sorting module, or a combination thereof, as described above in connection with  FIGS. 1-6 . The sorting modules  1101  may be interconnected with one another and with the processor  1100  using, for example, an on-chip bus  1102 . Data may be written onto each sorting module  1101  using, for example, a direct memory access (DMA) interface. Data may be fetched via DMA from on-chip memories onto the sorting module  1101 . 
       FIG. 7B  depicts an exemplary implementation of the sorting modules of  FIGS. 1-6  as an off-chip accelerator, according to an exemplary embodiment of the present disclosure. The processor  1100  may communicate with one or more sorting modules  1104 , which may be a local sorting module, global sorting module, and/or a combination thereof, operatively connected to the processor  1100  via an off-chip bus  1105 . The sorting module  1104  may also be implemented as part of main memory. Data may be written into the sorting module  1104  via DMA through the off-chip bus  1105 . Upon completion of sort operations, an interrupt may be issued to the processor  1100  to cause sorted data to be retrieved from the sorting module  1104  through a DMA operation.