Method and apparatus of instruction that merges and sorts smaller sorted vectors into larger sorted vector

Patent metadata

Field	Value
Publication number	US-10089075-B2
Application number	US-201213996972-A
Country	US
Kind code	B2
Filing date	Mar 30, 2012
Priority date	Mar 30, 2012
Publication date	Oct 2, 2018
Grant date	Oct 2, 2018

Abstract

A semiconductor chip is described that includes an instruction execution unit having a functional unit, said functional unit having minimum and maximum comparison circuitry followed by interleaving circuitry, said minimum and maximum comparison circuitry to respectively identify minimums and maximums of same positioned elements from two different sets of sorted elements, said interleaving circuitry to interleave said minimums and maximums to help form a third sorted set composed of elements from said different sets and being larger than each of said different sets.

First claim

What is claimed is:

1. A semiconductor chip, comprising:
decoder circuitry to decode a single instruction, the decoded single instruction to be executed by an instruction execution unit to perform minimum and maximum comparisons followed by interleaving;
the instruction execution unit having a functional unit to execute the decoded instruction, said functional unit having minimum and maximum comparison circuitry directly coupled to interleaving circuitry, said minimum and maximum comparison circuitry to respectively identify minimums and maximums of same positioned elements from two different sets of sorted elements, said interleaving circuitry to interleave said identified minimums and maximums to help form a third sorted set composed of elements from said different sets and being larger than each of said different sets.

2. The semiconductor chip of claim 1 wherein said execution unit comprises multiple stages of minimum and maximum comparison circuitry directly coupled to interleaving circuitry.

3. The semiconductor chip of claim 2 wherein said execution unit comprises a multiplexer to select an output from different ones of said stages as a function of the size of said sets.

4. The semiconductor chip of claim 2 wherein said size of said sets are variable across different instructions executed by said functional unit and include the following possible sizes: 4 elements, 8 elements and 16 elements.

5. The semiconductor chip of claim 2 wherein said size of said sets are specified in a respective immediate operand of said different instructions.

6. The semiconductor chip of claim 1 wherein said execution unit includes a ROM storing micro-code that controls a number of loops through said minimum and maximum comparison circuitry and interleaving circuitry that said execution unit executes as a function of said size of said sets.

7. The semiconductor chip of claim 2 wherein said size of said sets are specified in a respective immediate operand of said different instructions.

8. A method, comprising:
decoding a single instruction;
executing the decoded single instruction by:
i) producing a next set of minimums by flowing same positioned elements of two sets of elements into minimum comparison logic circuitry and producing a next set of maximums by flowing said same positioned elements of two sets of elements into maximum comparison logic circuitry;
ii) producing a set of interleaved elements by flowing said next set of minimums and said next set of maximums through interleaving circuitry, said set of interleaved elements corresponding to the next two sets of elements operated upon by any repetition of i) above;
repeating i) and ii) above as a function of the number of said elements in said two sets of elements.

9. The method of claim 8 wherein said repeating is effected by running flows through successive and different respective stages of minimum comparison logic circuitry, maximum comparison logic circuitry and interleaving circuitry.

10. The method of claim 9 wherein said method further comprises selecting respective interleaved elements produced by one of said stages and flowing said respective interleaved elements through multiplexer circuitry.

11. The method of claim 8 wherein said repeating is effected by looping flows through same minimum comparison circuitry, maximum comparison circuitry, and interleaving circuitry.

12. The method of claim 8 wherein determining the number of repetitions of i) and ii) above is accomplished with a look-up table implemented with ROM circuitry associated with said execution unit.

13. The method of claim 8 wherein said method further comprises running a received sorted set through pre-shuffling logic circuitry before a first instance of i) is performed.

14. A non-transitory machine readable medium containing program code that when executed by a computing system causes the computing system to perform a method, comprising:
decoding a single instruction identifying a first and a second unsorted set;
executing the decoding single instruction by combining and sorting elements of the identified first and second sorted sets to form a third sorted set.

15. The non-transitory machine readable medium of claim 14 wherein said instruction defines respective register locations for both said first and second unsorted sets.

Assignees

• Chhugani Jatin
• Satish Nadathur Rajagopalan
• Intel Corp

Inventors

• Chhugani Jatin
• Ck Kim Changkyu
• Satish Nadathur Rajagopalan

Classifications

• G06F9/3012

  Organisation of register space, e.g. banked or distributed register file · CPC title

• G06F9/3867

  using instruction pipelines · CPC title

• G06F9/3005

  to perform operations for flow control · CPC title

• G06F7/36 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