Hierarchical in-memory sort engine
A local sorting module includes a set of storage elements storing binary vectors configured in a one-dimensional (1D) or two-dimensional (2D) array structure and separated by respective comparators configured to conditionally compare and sort the binary vectors. The comparators may perform a sort using a compare-and-flip or a compare-and-swap operation. Local sorting modules may be coupled with a global sorting module for enabling a tournament sort algorithm to output values stored in storage elements one at a time until all data is outputted in a predetermined sorting order.
1. A hardware implemented method for sorting a plurality of data words, comprising:
loading, by a processor, first and second data words into first and second data storage elements; and
comparing, by a comparator, the first data word to the second data word, the comparator comprising:
a first priority decoder for comparing a first data word stored in the first data storage element with the second data word stored in the second data storage element, the first priority decoder comprising a first AND gate generating a first output based on receiving both a first bit of the first data word and an output of a first XOR gate, the first XOR gate receiving both the first bit of the first data word and a first bit of the second data word, and a first OR gate generating a second output based on receiving the first output, and a grounded input;
a second priority decoder, comprising a second AND gate generating a third output based on receiving a second bit of the first data word, an inverted value of the second output, and an output of a second XOR gate, the second XOR gate receiving the second bit of the first data word and a second bit of the second data word;
wherein for each bit in the first data word, the first storage element comprises a first storage device receiving an input from a multiplexer (MUX), the MUX comprising:
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 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; and
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.