Merge sort accelerator

Patent metadata

Field	Value
Publication number	US-2018349096-A1
Application number	US-201815995647-A
Country	US
Kind code	A1
Filing date	Jun 1, 2018
Priority date	Jun 2, 2017
Publication date	Dec 6, 2018
Grant date	—

Abstract

A merge sort accelerator (MSA) includes a pre-processing stage configured to receive an input vector and generate a pre-processing output vector based on a pre-processing instruction and the input vector. The MSA also includes a merge sort network having multiple sorting stages configured to be selectively enabled. The merge sort network is configured to receive the pre-processing output vector and generate a sorted output vector based on a sorting instruction and the pre-processing output vector. The MSA includes an accumulator stage configured to receive the sorted output vector and update an accumulator vector based on the accumulator instruction and the sorted output vector. The MSA also includes a post-processing stage configured to receive the accumulator vector and generate a post-processing output vector based on a post-processing instruction and the accumulator vector.

First claim

What is claimed is:

1 . A merge sort accelerator, comprising:
a pre-processing stage configured to:
receive an input vector;
receive a pre-processing instruction that indicates, for each element of a pre-processing output vector, a mapping from an element of the input vector to the pre-processing output vector; and
generate the pre-processing output vector based on the pre-processing instruction and the input vector;
a merge sort network comprising multiple sorting stages configured to be selectively enabled, the merge sort network configured to:
receive the pre-processing output vector;
receive a sorting instruction that indicates which, if any, sorting stages are enabled and, for those sorting stages that are enabled, a type of sorting to be applied to the pre-processing output vector; and
generate a sorted output vector based on the sorting instruction and the pre-processing output vector;
an accumulator stage comprising an accumulator vector, the accumulator stage configured to:
receive the sorted output vector;
receive an accumulator instruction that indicates whether to:
replace the accumulator vector with the sorted output vector; or
compare the sorted output vector with the accumulator vector and replace the accumulator vector with a result of the comparison; and

update the accumulator vector based on the accumulator instruction and the sorted output vector; and
a post-processing stage configured to:
receive the accumulator vector;
receive a post-processing instruction that indicates a selection of elements of the accumulator vector and a position in a post-processing output vector for each of the selected elements; and
generate the post-processing output vector based on the instruction and the accumulator vector.

2 . The merge sort accelerator of claim 1 further comprising a load stage configured to provide a vector from a memory to the pre-processing stage as the input vector.

3 . The merge sort accelerator of claim 1 further comprising a store stage configured to:
receive the post-processing output vector;
receive an instruction that indicates elements of the post-processing output vector to be stored; and
store the indicated elements of the post-processing output vector.

4 . The merge sort accelerator of claim 1 wherein the input vector is associated with the pre-processing output vector, the sorted output vector, the accumulator vector, and the post-processing output vector that result from a flow of the input vector through the stages of the merge sort accelerator, the merge sort accelerator further comprising an instruction control stage configured to:
receive pre-processing, sorting, accumulator, and post-processing instructions corresponding to the input vector;
apply a delay to the pre-processing instruction such that the pre-processing instruction is provided to the pre-processing stage when the input vector is received by the pre-processing stage;
apply a delay to the sorting instruction such that the sorting instruction is provided to the merge sort network when the pre-processing output vector associated with the input vector is received by the merge sort network;
apply a delay to the accumulator instruction such that the accumulator instruction is provided to the accumulator stage when the sorted output vector associated with the input vector is received by the accumulator stage; and
apply a delay to the post-processing instruction such that the post-processing instruction is provided to the post-processing stage when the accumulator vector associated with the input vector is received by the post-processing stage.

5 . The merge sort accelerator of claim 1 wherein the pre-processing stage is configured to sequentially read elements of the input vector, and wherein the pre-processing instruction specifies for each element of the pre-processing output vector whether that element of the pre-processing output vector is a previous element of the input vector, a current element of the input vector, a next element of the input vector, or a special value.

6 . The merge sort accelerator of claim 1 wherein the sorting instruction that indicates the type of sorting to be applied to the pre-processing output vector indicates whether to swap elements of the pre-processing output vector based on a comparison of those elements of the pre-processing output vector or based on a comparison of associated elements of a previous pre-processing vector, the merge sort network being further configured to generate the sorted output vector by swapping one or more elements of the pre-processing output vector based on the sorting instruction.

7 . The merge sort accelerator of claim 1 wherein the post-processing instruction further indicates one or more positions in the post-processing output vector for insertion of a special value.

8 . A method for accelerating mathematical operations, the method comprising:
pre-processing an input vector comprising multiple analysis groups to expand each of the analysis groups to a number of elements equal to a power of 2, resulting in a pre-processing output vector; sorting at least a portion of the pre-processing output vector, resulting in a sorted output vector; sorting corresponding elements of two or more sorted output vectors, resulting in an accumulator vector; and selecting elements of the accumulator vector and generating a post-processing output vector comprising the selected elements.

9 . The method of claim 8 further comprising loading a vector from a memory to be pre-processed as the input vector.

10 . The method of claim 8 further comprising storing only selected elements of the post-processing output vector.

11 . The method of claim 8 further comprises sorting in stages the pre-processing output vector, resulting in a fully sorted output vector.

12 . The method of claim 8 wherein sorting at least a portion of the pre-processing output vector comprises sorting each of the expanded analysis groups, resulting in a local maximum or a local minimum for each expanded analysis group.

13 . The method of claim 12 wherein sorting corresponding elements of the sorted output vectors further comprises sorting corresponding local maximums or corresponding local minimums, resulting in a two-dimensional local maximum or a two-dimensional local minimum for corresponding elements of each expanded analysis group.

14 . The method of claim 13 further comprising selecting the two-dimensional local maximums or two-dimensional local minimums and generating the post-processing output vector including those selected two-dimensional local maximums or two-dimensional local minimums.

15 . The method of claim 14 further comprising inserting a special value at one or more positions in the post-processing output vector prior to storing the post-processing output vector.

16 . A merge sort accelerator, comprising:
a pre-processing stage configured to pre-process an input vector comprising multiple analysis groups to expand each of the analysis groups to a number of elements equal to a power of 2, resulting in a pre-processing output vector; a merge sort network configured to sort at least a portion of the pre-processing output vector, resulting in a sorted output vector; an accumulator stage configured to sort corresponding elements of two or more sorted output vectors, resulting in an accumulator vector; and a post-processing stage configured to select elements of the accumulator vector and generate a post-processing output vector comprising the selected elements.

17 . The

Assignees

• Texas Instruments Inc

Inventors

• Redfern Arthur John
• Bhardwaj Asheesh
• Lahlou Tarek Aziz
• Leven William Franklin

Classifications

• G06F9/30021

  Compare instructions, e.g. Greater-Than, Equal-To, MINMAX · CPC title

• G06F9/30032

  Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE · CPC title

• G06F9/3877

  using a secondary processor, e.g. coprocessor (peripheral processor G06F13/12) · CPC title

• G06F7/36 Primary

  Combined merging and sorting · CPC title

• G06F7/32

  Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence {merging methods in general}(G06F7/36 takes precedence) · CPC title