Instruction and logic for boyer-moore search of text strings

Patent metadata

Field	Value
Publication number	US-9268567-B2
Application number	US-201213632075-A
Country	US
Kind code	B2
Filing date	Sep 30, 2012
Priority date	Sep 30, 2012
Publication date	Feb 23, 2016
Grant date	Feb 23, 2016

Abstract

Instructions and logic provide extended vector suffix comparisons for Boyer-Moore searches. Some embodiments, responsive to an instruction specifying: a pattern source operand and a target source operand, compare each of m data elements of the pattern operand with each data element of the target operand. A first and second equal ordered aggregation operation are performed from the comparisons according to the m data elements of the pattern source operand. A result of the first and second aggregation operations indicating whether or not a possible match exists between the m data elements of the pattern source operand and d data element positions relative to data elements of the target source operand is stored. Ordering of the data elements of the pattern and the target operands may be reversed for the second aggregation operation, and d may be a sum of m−1 and the quantity of target operand elements in some embodiments.

First claim

What is claimed is:

1. A processor comprising:
a vector register comprising a first plurality of m data fields to store values of m data elements;
a decode stage to decode a first instruction specifying: a pattern source operand specifying the vector register, an immediate operand, and a target source operand; and
an execution unit, responsive to the decoded first instruction, to:
compare each data element of the pattern source operand with each data element of the target source operand;
perform a first equal ordered aggregation operation from the comparisons according to the m data elements of the pattern source operand;
perform a second equal ordered aggregation operation from the comparisons according to the m data elements of the pattern source operand; and
store a result of the first and second aggregation operations indicating whether or not a match exists between the m data elements of the pattern source operand and d data element positions relative to data elements of the target source operand.

2. The processor of claim 1 , the result of the first and second aggregation operations is an index indicating the least significant element position of a possible suffix match to the m data elements of the pattern source operand relative to the data elements of the target source operand.

3. The processor of claim 1 , the result of the first and second aggregation operations is a mask indicating any element position of a possible suffix match to the m data elements of the pattern source operand relative to the data elements of the target source operand.

4. The processor of claim 1 , wherein d is greater than m.

5. The processor of claim 1 , wherein d is greater than a quantity of data elements of the target source operand.

6. The processor of claim 1 , wherein d is equal to a sum of m−1 and the quantity of data elements of the target source operand.

7. The processor of claim 1 , wherein d is equal to 2m.

8. The processor of claim 1 , wherein for the second equal ordered aggregation operation, ordering of the data elements of both the pattern source operand and the target source operand are reversed.

9. A non-transitory machine-readable medium to record functional descriptive material including a first executable instruction, which if executed by a machine causes the machine to:
compare each of m data elements of a pattern source operand with each data element of a target source operand;
perform a first equal ordered aggregation operation from the comparisons according to the m data elements of the pattern source operand;
perform a second equal ordered aggregation operation from the comparisons according to the m data elements of the pattern source operand; and
store a result of the first and second aggregation operations indicating whether or not a possible match exists between the m data elements of the pattern source operand and d data element positions relative to data elements of the target source operand.

10. The non-transitory machine-readable medium of claim 9 , wherein for the second equal ordered aggregation operation, an ordering of the data elements of both the pattern source operand and the target source operand are reversed.

11. The non-transitory machine-readable medium of claim 10 , wherein d is equal to a sum of m−1 and the quantity of data elements of the target source operand.

12. The non-transitory machine-readable medium of claim 9 , wherein d is greater than a quantity of data elements of the target source operand.

13. The non-transitory machine-readable medium of claim 9 , wherein the result of the first and second aggregation operations is a mask indicating any element position of a possible suffix match with the m data elements of the pattern source operand relative to the data elements of the target source operand.

14. The non-transitory machine-readable medium of claim 9 , wherein the result of the first and second aggregation operations is an index indicating the least significant element position of a possible suffix match with the m data elements of the pattern source operand relative to the data elements of the target source operand.

15. A processing system comprising:
a memory; and
a first plurality of processors, each of the first plurality of processors comprising:
a vector register comprising a first plurality of m data fields to store values of m data elements;
a decode stage to decode a first instruction specifying: a pattern source operand specifying the vector register, an immediate operand, and a target source operand; and
an execution unit, responsive to the decoded first instruction, to:
compare each data element of the pattern source operand with each data element of the target source operand;
perform a first equal ordered aggregation operation from the comparisons according to the m data elements of the pattern source operand;
perform a second equal ordered aggregation operation from the comparisons according to the m data elements of the pattern source operand; and
store a result of the first and second aggregation operations indicating whether or not a match exists between the m data elements of the pattern source operand and d data element positions relative to data elements of the target source operand.

16. The processing system of claim 15 , wherein d is equal to a sum of m−1 and the quantity of data elements of the target source operand.

17. The processing system of claim 16 , wherein for the second equal ordered aggregation operation, an ordering of the data elements of both the pattern source operand and the target source operand are reversed.

18. The processing system of claim 17 , wherein the first instruction is decoded to produce one or more micro-operations to reverse the ordering of data elements of both the pattern source operand and the target source operand, and a plurality of micro-operations to perform packed comparisons of strings with equal ordered aggregation.

19. The processing system of claim 18 , wherein the result of the first and second aggregation operations is an index indicating the least significant element position of a possible suffix match with the m data elements of the pattern source operand relative to the data elements of the target source operand.

20. The processing system of claim 18 , wherein the result of the first and second aggregation operations is a mask indicating any element position of a possible suffix match with the m data elements of the pattern source operand relative to the data elements of the target source operand.

21. A computer-implemented method comprising:
comparing each of m data elements of a pattern source operand with each data element of a target source operand;
performing a first equal ordered aggregation operation from the comparisons according to the m data elements of the pattern source operand;
performing a second equal ordered aggregation operation from the comparisons according to the m data elements of the pattern source operand; and
storing a result of the first and second aggregation operations indicating whether or not a possible match exists between the m data elements of the pattern source operand and d data element positions relative to data elements of the target source operand.

22. The computer-implemented method of claim 21 , wherein an ordering of the data elements of both the pattern source operand and the target source operand are reversed for the second equal ordered aggregation operation.

23. The computer-

Assignees

• Intel Corp

Inventors

• Kuo Shih J

Classifications

• G06F9/30185

  according to one or more bits in the instruction, e.g. prefix, sub-opcode · CPC title

• G06F9/30021 Primary

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

• G06F9/3016 Primary

  Decoding the operand specifier, e.g. specifier format · CPC title

• G06F9/30036 Primary

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

• G06F9/30038

  using a mask · CPC title