Rapid character substring searching

Patent metadata

Field	Value
Publication number	US-10169451-B1
Application number	US-201815957984-A
Country	US
Kind code	B1
Filing date	Apr 20, 2018
Priority date	Apr 20, 2018
Publication date	Jan 1, 2019
Grant date	Jan 1, 2019

Abstract

A processor unit can be used to rapidly search a string of characters. The processor unit can include vector registers each having M vector elements, each vector element having n bits of data for containing an encoded character. An M×M matrix of comparators within the processor unit can be used to compare elements of a first register storing a reference string and elements of a second register storing a target string. A logic gate is associated with each diagonal of the matrix of comparators, and is configured to combine the results of comparators along the diagonal, resulting in a bit vector indicating characters of the target string that fully match the reference string and characters that partially match the reference string. Correction logic within the processor unit can suppress indications of a partial match or of a full match in the bit vector.

First claim

What is claimed is:

1. A processor unit for searching, within a target character string, for a reference character string of length “L,” the processor unit comprising a plurality of vector registers each including a number “M” of n-bit vector elements, each vector element of the M n-bit vector elements configured to contain a binary-encoded character, the processor unit further comprising:
an M×M matrix of comparators configured to perform a character-by-character comparison of characters of a reference string stored in a first register of the plurality of vector registers with characters of a target string stored in a second register of the plurality of vector registers;
a plurality of logic gates, each logic gate of the plurality of logic gates associated with a respective diagonal of the matrix of comparators, each logic gate of the plurality of logic gates configured to combine the results of comparators located along the respective diagonal of the matrix of comparators, the plurality of logic gates configured to produce a bit vector indicating at least one item selected from the group consisting of: characters of the target string that fully match characters of the reference string and characters of the target string that partially match characters of the reference string; and
correction logic configured to suppress an indication of at least one item selected from the group consisting of: a partial match in the resulting bit vector and a full match in the resulting bit vector.

2. The processor unit of claim 1 , wherein the plurality of logic gates includes an AND gate chain configured to perform a logical AND operation between outputs of comparators located along a diagonal of the matrix of comparators.

3. The processor unit of claim 2 , wherein the AND gate chain includes an AND gate connected to outputs of each adjacent pair of comparators of the diagonal of the matrix of comparators.

4. The processor unit of claim 1 , the correction logic including a register configured to store the resulting bit vector, the register including a correction mask and logic for performing a logical AND operation between corresponding elements of the resulting bit vector and of the correction mask.

5. The processor unit of claim 1 , the plurality of logic gates further including:
zero-detect logic configured to identify empty n-bit vector elements of the first register and to generate a zero bit vector including logical values indicating the identified empty n-bit vector elements and indicating the non-empty n-bit vector elements; and
a logic circuit for performing a logical OR operation between each bit value of the zero bit vector and the output of a corresponding comparator, wherein the corresponding comparator output results from the comparison of an n-bit vector element stored in the first register to an n-bit vector element stored in the second register.

6. The processor unit of claim 5 , the logic circuit for performing logical OR operation including a plurality of OR gates, wherein each OR gate of the plurality of OR gates is connected between an AND gate and a respective comparator.

7. The processor unit of claim 1 , wherein the correction logic includes:
a NOR logic circuit configured to identify empty elements of the first register and further configured to generate a zero bit vector having values indicating of positions of the identified empty elements and non-empty elements;
a shift unit configured to shift the zero bit vector and reverse the order of bits in the shifted zero bit vector, the shifting and reversing of the order of bits producing a correction mask having the last L−1 bits set to zero; and
a combination logic configured to combine the correction mask with the resulting bit vector for the suppression.

8. The processor unit of claim 1 , wherein the resulting bit vector includes a first bit value located in a first bit position that indicates a beginning of a substring of the target string that fully matches the reference string and a second bit value at a second bit position that indicates the beginning of a substring of the target string that matches a portion of the reference string.

9. The processor unit of claim 1 , wherein the correction logic is configured to maintain an indication of the characters of the target string that fully match characters of the reference string in the bit vector.

10. The processor unit of claim 1 , wherein the comparators are equality comparators.

11. A method for searching within a target character string of length “L,” using a processor unit comprising a plurality of vector registers each including a number “M” of n-bit vector elements, each vector element of the M n-bit vector elements configured to contain a binary-encoded character, the method comprising:
loading a reference string into a first register of the plurality of vector registers;
loading a target string into a second register of the plurality of vector registers;
performing, using an M×M matrix of comparators, a character-by-character comparison of characters of the reference string with characters of the target string;
combining, with a plurality of logic gates, each logic gate of the plurality of logic gates associated a respective diagonal of the matrix of comparators, the results of comparators located along the respective diagonal of the matrix of comparators, the combining producing a bit vector indicating at least one item selected from the group consisting of: characters of the target string that fully match characters of the reference string and characters of the target string that partially match characters of the reference string; and
suppressing, with a correction logic, an indication of at least one item selected from the group consisting of: a partial match in the resulting bit vector and a full match in the resulting bit vector.

12. The method of claim 11 , wherein the suppressing includes performing a bitwise operation on the resulting bit vector.

13. The method of claim 12 , further comprising:
creating a correction mask having rightmost L−1 bits set to a logical “0”; and
performing a logical AND operation between the resulting bit vector and the correction mask for use in performing the suppression.

14. The method of claim 11 , further comprising:
identifying empty elements of the first register and, in response to the identifying, generating a zero bit vector including values that indicate identified empty elements and non-empty elements; and
using the zero bit vector to disregard comparisons involving the empty elements.

15. The method of claim 11 , wherein bits of the resulting bit vector are ordered so that a first bit includes the results of comparators along a main diagonal of the matrix, and so that subsequent bits include the results of comparators located along respective subsequent diagonals adjacent to the main diagonal.

16. A computer program product for searching, within a target character string, for a reference character string of length “L,” using at least one processor unit comprising a plurality of vector registers each including a number “M” of n-bit vector elements, each vector element of the M n-bit vector elements configured to contain a binary-encoded character, the computer program product comprising at least one non-transitory computer-readable storage medium having program instructions embodied therewith, the program instructions executable by the at least one processor unit to cause the at least one processor unit to perform a method comprising:
loading a reference string into a first register of the plurality of vector registers;

Assignees

• IBM

Inventors

• Payer Stefan
• Figuli Razvan Peter
• Lichtenau Cedric
• Klein Michael

Classifications

• G06F40/126

  Character encoding · CPC title

• G06F16/90344

  by using string matching techniques · CPC title

• H03K19/20

  characterised by logic function, e.g. AND, OR, NOR, NOT circuits (H03K19/003 - H03K19/01 take precedence) · CPC title

• G06F16/3347 Primary

  using vector based model · CPC title

• H03K19/17704 Primary

  the logic functions being realised by the interconnection of rows and columns · CPC title