Instruction for Determining Histograms

• US 20140189320A1
• Filed: 12/28/2012
• Published: 07/03/2014
• Est. Priority Date: 12/28/2012
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: KUO, Shih Shigjong
• Granted Patent: US 9,804,839 B2
• Time in Patent Office: Days
• US Class Current: 712/222
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30038 using a mask
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields

Abstract

A processor is described having a functional unit of an instruction execution pipeline. The functional unit has comparison bank circuitry and adder circuitry. The comparison bank circuitry is to compare one or more elements of a first input vector against an element of a second input vector. The adder circuitry is coupled to the comparison bank circuitry to add the number of elements of the second input vector that match a value of the first input vector on an element by element basis of the first input vector.

Claims

1. A processor, comprising:

a functional unit of an instruction execution pipeline having;

comparison bank circuitry to compare one or more elements of a first input vector against an element of a second input vector;

adder circuitry coupled to said comparison bank circuitry to add the number of elements of said second input vector that match a value of said first input vector on an element by element basis of said first input vector.

2. The processor of claim 1 wherein said functional unit contains a ROM to contain micro-code that control a loop through said comparison bank and adder circuitry for each element of said second input vector.

3. The processor of claim 1 wherein said functional unit further comprises:

second comparison bank circuitry to compare said one or more elements of said first input vector against another element of a second input vector, said second comparison bank coupled to said adder circuitry.

4. The processor of claim 1 further comprising a data path from said comparison circuitry that bypasses said adder circuitry.

5. The processor of claim 4 wherein said functional unit is to execute a first instruction for determining a histogram and a second instruction to determine if certain characters are found in a character string.

6. The processor of claim 1 wherein said functional unit is to execute an instruction whose instruction format includes an immediate operand that specifies a type of comparison to be performed.

7. The processor of claim 6 wherein said type of comparison includes any of:

equal range;

equal any.

8. The processor of claim 7 wherein said functional unit is to execute a first instruction for determining a histogram and a second instruction to determine if certain characters are found in a character string, said instruction having an instruction format to specify if said equal range or equal any comparisons are to be performed for said first and second instructions.

9. The processor of claim 1 wherein said functional unit contains wiring to fan-out said element of said first vector to multiple comparison circuits of said comparison circuitry to perform multiple comparisons of said single element against said elements of said second input vector in a same cycle.

10. The processor of claim 9 wherein said functional unit contains wiring to fan-in multiple respective values from said multiple comparison circuits to said adder circuitry to produce a scalar summation value for said element of said first input vector against said elements of said second input vector.

11. A method, comprising:

determining a histogram or portion thereof through execution of a single instruction in an instruction execution pipeline, said executing of said single instruction including;

comparing elements of a first input vector against an element of a second input vector;

adding the number of elements of said second input vector that match a value of said first input vector on an element by element basis of said first input vector.

12. The method of claim 11 further comprising performing micro-controlled loops through comparison circuitry designed to perform said comparing and adder circuitry designed to perform said adding for each of multiple elements of said second input vector.

13. The method of claim 11 further comprising performing the following simultaneously with said comparing:

comparing said elements of said first input vector against another element of a second input vector.

14. The method of claim 11 further comprising executing a second instruction with said functional unit that compares elements of another first input vector against an element of another second input vector but does not add the number of elements of said another second input vector that match a value of said another first input vector on an element by element basis of said another first input vector.

15. The method of claim 14 wherein both said first and second instruction perform a comparison operation selected from a group of comparison operations that include:

equal range;

equal any.

16. A machine readable medium containing program code that when processed by a processor causes the processor to perform a method, comprising:

determining a first portion of a histogram, said portion being final counts for a portion of said histogram'"'"'s bins, said determining including executing a series of instructions, each instruction comparing and summing thereover a different set of said histogram'"'"'s population against said portion of said histogram'"'"'s bins until said final counts are reached.

17. The machine readable medium of claim 16 wherein an immediately following one of said instructions accepts as an input the resultant counts of an immediately preceding one of said instructions.

18. The machine readable medium of claim 16 wherein said series of instructions are interleaved with vector addition instructions.

19. The machine readable medium of claim 16 wherein said comparisons are a equal range comparison.

20. The machine readable medium of claim 16 wherein said comparisons are an equal any comparison.