Merge sort accelerator

Patent metadata

Field	Value
Publication number	US-10809978-B2
Application number	US-201815995647-A
Country	US
Kind code	B2
Filing date	Jun 1, 2018
Priority date	Jun 2, 2017
Publication date	Oct 20, 2020
Grant date	Oct 20, 2020

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 system, comprising:
a memory:
a processor;
an accelerator coupled to the memory and the processor, the accelerator configured to:
access an input vector from a memory;
receive, from the processor, 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;
receive, from the processor, a sorting instruction that indicates a first sorting and a second sorting to be applied; and
generate a sorted output vector based on the sorting instruction and the pre-processing output vector;
receive, from the processor, an accumulator instruction that indicates whether to:
replace an 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
receive, from the processor, 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 system of claim 1 wherein the accelerator is further configured to provide a vector from a memory to the pre-processing stage as the input vector.

3. The system of claim 1 wherein the accelerator is further configured to:
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 system of claim 1 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.

5. The system of claim 1 wherein the first sorting swaps 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.

6. The system 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.

7. A method comprising:
receiving an input vector;
receiving 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;
generating the pre-processing output vector based on the pre-processing instruction and the input vector;
receiving a sorting instruction that indicates a first sorting and a second sorting to be applied;
generating a sorted output vector based on the sorting instruction and the pre-processing output vector;
receiving an accumulator instruction that indicates whether to:
replace an 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;

updating the accumulator vector based on the accumulator instruction and the sorted output vector;
receiving 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
generating the post-processing output vector based on the instruction and the accumulator vector.

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

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

10. The method of claim 7 wherein the sorting results in a fully sorted output vector.

11. The method of claim 7 , further comprising:
receiving an instruction that indicates elements of the post-processing output vector to be stored; and
storing the indicated elements of the post-processing output vector.

12. The method of claim 7 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.

13. The method of claim 7 wherein the first sorting indicates 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.

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

Assignees

• Texas Instruments Inc

Inventors

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

Classifications

• G06F7/16 Primary

  Combined merging and sorting · CPC title

• G06F9/30036

  Instructions to perform operations on packed data, e.g. vector, tile or matrix operations · CPC title

• G06F9/30021

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

• G06F7/24

  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/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