Hierarchical in-memory sort engine

Patent metadata

Field	Value
Publication number	US-9424308-B2
Application number	US-201615063315-A
Country	US
Kind code	B2
Filing date	Mar 7, 2016
Priority date	Jun 3, 2014
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

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.

First claim

What is claimed is:

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.

Assignees

• IBM

Inventors

• Buyuktosunoglu Alper
• Chellappa Srivatsan
• Kirihata Toshiaki
• Swaminathan Karthik V

Classifications

• G06F13/1626 Primary

  by reordering requests · CPC title

• G06F17/30312

  Physics · mapped topic

• G06F17/30424 Primary

  Physics · mapped topic

• G06F16/24578

  using ranking · CPC title

• G06F13/374

  using a self-select method with individual priority code comparator · CPC title