Method and apparatus for high speed streaming sorter

Patent metadata

Field	Value
Publication number	US-10101965-B1
Application number	US-201514925006-A
Country	US
Kind code	B1
Filing date	Oct 28, 2015
Priority date	Oct 28, 2015
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

Sorting algorithms are generally used at different steps in data processing. In many situations, the efficiency of the sorting algorithm used determines the throughput/execution speed of the application. Methods for implementing high speed sorting in hardware are often based on Batcher's Odd/Even sort or Bitonic sort algorithms. These algorithms are computation intensive and involve high number of logic gates to implement and high power consumption. The higher the number of logic gates, the more silicon area may be required and may lead to higher cost. Insertion sort is a sorting algorithm that is relatively simpler and may require fewer logic gates to implement. However, throughput achieved using Insertion sort algorithm is much lower than the throughput achieved using high speed sorting algorithms. A method and apparatus enable an efficient hardware design capable of simultaneously sorting multiple data inputs for high throughput at reduced complexity.

First claim

The invention claimed is:

1. A method for sorting, by circuitry, N data elements into M most significant data elements in sorted order, wherein M<N, the method comprising:
controlling, by a processing device, inputting L data elements of the N data elements at a same time into at least one sorting unit of a cascade of S sorting units, in which the L input data elements are sorted by a first comparator circuit of the circuitry only among the L input data elements before the inputting, in which the sorting units are arranged in the cascade in order of priority, in which each of the sorting units includes B registers for storing M/S data elements in sorted order and in order in relation to data elements respectively in the B registers of a neighbor sorting unit in the cascade, in which the S sorting units store a current set of most significant data elements of data elements previously input thus far, and in which S*B=M, B≥L and L≥1;
controlling, by the processing device, for each sorting unit of the cascade, sorting (i) each comparison data element determined to be inserted in the sorting based on a comparison by a second comparison circuit of the circuitry of each of the L input data elements with a most significant value of the B registers of the sorting unit and (ii) by a third comparison circuit of the circuitry the data elements respectively of the B registers of the sorting unit, to obtain a sorted array of data elements in order of significance; and
controlling, by the processing device, at a given sorting unit of the cascade,
storing, into the B registers in sorted order, data elements determined from
(i) when no shift data elements is output from a preceding neighbor sorting unit in the cascade, the B most significant values of the sorted array of data elements for the given sorting unit determined by a fourth comparison circuit of the circuitry, and
(ii) when SH shift data elements is output from the preceding neighbor sorting unit in the cascade, the SH shift data elements and a subset of the data elements of the sorted array determined by a fifth comparison circuit of the circuitry in accordance with the value of SH, in which 1≤SH≤B, and

outputting, as SHN shift-next data elements in order, SHN data elements from the sorted array of data elements more or less significant than the most or least significant data element of the sorted array stored in the B registers by the storing, in which 1≤SHN≤B.

2. The method of claim 1 ,
wherein, when the SH shift data elements is output from the preceding neighbor sorting unit in the cascade,
the SH shift data elements is stored into the B registers of the given sorting unit in sequence starting from a least or most significant register of the B registers, and
B-SH data elements from the sorted array, starting from the SH+1 data element of the sorted array, is stored in the B registers in sequence starting from the register of the B registers neighboring the register of the B registers in which the least or most significant of the shift data elements is stored.

3. The method of claim 1 ,
wherein each of the S sorting units includes a load-shift control block and a value selector block as a part of the processing device, and is associated with an Internal Parallel Sorter (IPS) which is a part of the processing device,
wherein, in each of the S sorting units,
the load-shift control block controls the comparison of each of the L data elements with the most significant value of the B registers,
when at least one comparison data element is determined from the comparison, the IPS generates the sorted array including each comparison data element determined from the comparison and the data elements of the B registers in the order of significance, and
the value selector block selects B data elements for storing into the B registers in sorted order based on a number of data elements input into one or more sorting units of the cascade having one of higher and lower priority.

4. The method of claim 3 , wherein, in the given sorting unit, the sorted array is generated by the IPS using Batcher's Odd/Even sorting algorithm when L is less than a predetermined value.

5. The method of claim 3 , wherein, in the given sorting unit when L is less than B, an input of the IPS that is unused is set to a maximum value to be discarded when the value selector block is selecting B data elements for storing into the B registers.

6. The method of claim 1 , wherein, in each of the S sorting units, each comparison data element determined based on the comparison is less than a maximum value or greater than a minimum value of the B registers for the sorting unit.

7. The method of claim 1 , wherein, in the given sorting unit, when the SH shift data elements is output from the preceding neighboring sorting unit, the subset of the data elements of the sorted array does not include the SH data elements of the sorted array starting in sequence from a first or last data element of the sorted array.

8. The method of claim 1 , wherein the inputting of the L input data elements is into each sorting unit of the cascade at the same time.

9. An apparatus for sorting N data elements into M most significant data elements in sorted order, wherein M<N, the apparatus comprising:
circuitry configured to control:
inputting L data elements of the N data elements at a same time into at least one sorting unit of a cascade of S sorting units of the circuitry, in which the L input data elements are sorted by a first comparator circuit of the circuitry only among the L input data elements before the inputting, in which the sorting units are arranged in the cascade in order of priority, in which each of the sorting units includes B registers for storing M/S data elements in sorted order and in order in relation to data elements respectively in the B registers of a neighbor sorting unit in the cascade, in which the S sorting units store a current set of most significant data elements of data elements previously input thus far, and in which S*B=M, B≥L and L≥1;
for each sorting unit of the cascade, sorting (i) each comparison data element determined to be inserted in the sorting based on a comparison by a second comparison circuit of the circuitry of each of the L input data elements with a most significant value of the B registers of the sorting unit and (ii) by a third comparison circuit of the circuitry the data elements respectively of the B registers of the sorting unit, to obtain a sorted array of data elements in order of significance; and
at a given sorting unit of the cascade,
storing, into the B registers in sorted order, data elements determined from
(i) when no shift data elements is output from a preceding neighbor sorting unit in the cascade, the B most significant values of the sorted array of data elements for the given sorting unit determined by a fourth comparison circuit of the circuitry, and
(ii) when SH shift data elements is output from the preceding neighbor sorting unit in the cascade, the SH shift data elements and a subset of the data elements of the sorted array determined by a fifth comparison circuit of the circuitry in accordance with the value of SH, in which 1≤SH≤B, and

outputting, as SHN shift-next data elements in order, SHN data elements from the sorted array of data elements more or less significant than the most or least significant data element of the sorted array stored in the B registers by the storing, in which 1≤SHN≤B.

10. The apparatus of claim 9 ,
wherein, when the SH shift data elements is output from the preceding neighbor sorting unit in the cascade,
the SH shift data elements is stored into the B registers of the given sorting unit in sequence starting from a l

Assignees

• Mbit Wireless Inc

Inventors

• Bhat Raghavendra H
• Patel Bhaskar

Classifications

• G06F2207/22

  Indexing scheme relating to groups G06F7/22 - G06F7/36 · CPC title

• G06F5/01

  for shifting, e.g. justifying, scaling, normalising {(digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00)} · CPC title

• G06F7/24 Primary

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title

• G06F7/22 Primary

  Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc · CPC title

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title