Plausibility-driven fault detection in string termination logic for fast exact substring match

Patent metadata

Field	Value
Publication number	US-10996951-B2
Application number	US-201916567356-A
Country	US
Kind code	B2
Filing date	Sep 11, 2019
Priority date	Sep 11, 2019
Publication date	May 4, 2021
Grant date	May 4, 2021

Abstract

A method for detecting faults in substring search operations using a processor unit including vector registers of M vector elements each. A non-limiting example of the method includes providing an M×M matrix of comparators for characterwise comparison of the elements of a reference string and a target string. A first zero detect vector having value indicative of terminating element of the target string and a second zero detect vector having a value indicative of terminating element of the reference string are generated. A resulting bit vector is generated using comparison performed by the M×M matrix. The resulting bit vector indicates characters of the target string that fully match the reference string and indicate characters of the target string that partially match the reference string. Fault detection in the substring search operations is performed by comparing the generated zero detect vectors with operands.

First claim

What is claimed is:

1. A method for detecting faults in substring search operations, the method comprising:
providing, using a processor unit comprising vector registers of M vector elements each, an M×M matrix of comparators for characterwise comparison of the elements of a reference string stored in a first one of the vector registers and a target string stored in a second one of the vector registers, wherein a vector element is an n bit element for encoding a character;
generating a first zero detect vector having a value indicative of a terminating element of the target string and a second zero detect vector having a value indicative of a terminating element of the reference string;
generating a resulting bit vector using comparison performed by the M×M matrix, the resulting bit vector indicating characters of the target string that fully match the reference string and indicating characters of the target string that partially match the reference string; and
performing fault detection in the substring search operations by comparing at least one generated zero detect vector with at least one operand.

2. The method of claim 1 , wherein generating the resulting bit vector further comprises generating an index of the resulting bit vector for identifying a first match of the reference string within the target string and generating a condition code indicating a type of a detected match.

3. The method of claim 1 , wherein the first zero detect vector includes bits corresponding to elements of the target string preceding the terminating element of the target string set to 0 and remaining bits of the first zero detect vector set to 1 and wherein the second zero detect vector includes bits corresponding to elements of the reference string preceding the terminating element of the reference string set to 0 and remaining bits of the second zero detect vector set to 1.

4. The method of claim 3 , wherein performing the fault detection further comprises indicating an error if an explicit length of the target string is zero and the first zero detect vector includes at least one bit set to 0 or if an explicit length of the reference string is zero and the second zero detect vector includes at least one bit set to 0.

5. The method of claim 3 , wherein performing the fault detection further comprises indicating an error if the target string is not terminated by the terminating element and the first zero detect vector includes at least one bit set to 1 or if the reference string is not terminated by the terminating element and the second zero detect vector includes at least one bit set to 1.

6. The method of claim 3 , wherein performing the fault detection further comprises indicating an error if the first zero detect vector or the second zero detect vector is misaligned with a vector element.

7. The method of claim 6 , wherein misalignment is detected if bits of the first zero detect vector associated to bytes of an encoded character element of the target string differ from each other or if bits of the second zero detect vector associated to bytes of an encoded character element of the reference string differ from each other.

8. A processor unit for detecting faults in substring search operations, the processor unit comprising:
a plurality of vector registers of M vector elements each, wherein a vector element is an n-bit element for encoding a character;
an M×M matrix of comparators for characterwise comparison of elements of a first register storing the reference string and elements of a second register of the registers storing a target string, wherein the M×M matrix is configured to generate a bit vector indicating at least one of characters of the target string that fully match the reference string and characters of the target string that partially match the reference string;
a first zero detect logic for generating a zero detect vector having value indicative of a terminating element of the target string;
a second zero detect logic for generating a zero detect vector having value indicative of a terminating element of the reference string;
a result generating logic for generating using the resulting bit vector an indication of a substring of the target string that matches a part of the reference string, wherein the indication is of the beginning of the substring and the length of the substring; and
a fault detection logic for performing fault detection in the substring search operations by comparing at least one generated zero detect vector with at least one operand.

9. The processor unit of claim 8 , wherein the result generating logic generates an index of the resulting bit vector for identifying a first match of the reference string within the target string and generating a condition code indicating a type of a detected match.

10. The processor unit of claim 8 , wherein the first zero detect vector includes bits corresponding to elements of the target string preceding the terminating element of the target string set to 0 and remaining bits of the first zero detect vector set to 1 and wherein the second zero detect vector includes bits corresponding to elements of the reference string preceding the terminating element of the reference string set to 0 and remaining bits of the second zero detect vector set to 1.

11. The processor unit of claim 10 , wherein the fault detection logic indicates an error if an explicit length of the target string is zero and the first zero detect vector includes at least one bit set to 0 or if an explicit length of the reference string is zero and the second zero detect vector includes at least one bit set to 0.

12. The processor unit of claim 10 , wherein the fault detection logic indicates an error if the target string is not terminated by the terminating element and the zero detect vector includes at least one bit set to 1 or if the reference string is not terminated by the terminating element and the second zero detect vector includes at least one bit set to 1.

13. The processor unit of claim 10 , further comprising a misalignment detection logic for detecting misalignment between the first zero detect vector and a vector element and for detecting misalignment between the second zero detect vector and a vector element.

14. The processor unit of claim 13 , wherein misalignment is detected if bits of the first zero detect vector associated to bytes of an encoded character element of the target string differ from each other or if bits of the second zero detect vector associated to bytes of an encoded character element of the reference string differ from each other.

15. A computer-program product for detecting faults in sub string search operations, the computer-program product comprising a non-transitory computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:
providing, using a processing unit comprising vector registers of M vector elements each, an M×M matrix of comparators for characterwise comparison of the elements of a reference string stored in a first one of the vector registers and a target string stored in a second one of the vector registers, wherein a vector element is an n-bit element for encoding a character;
generating a first zero detect vector having a value indicative of a terminating element of the target string and a second zero detect vector having a value indicative of a terminating element of the reference string;
generating a resulting bit vector using comparison performed by the M×M matrix, the resulting bit vector indicating characters of the targe

Assignees

• IBM

Inventors

• Figuli Razvan Peter
• Payer Stefan
• Leber Petra
• Lichtenau Cedric

Classifications

• G06F9/30038

  using a mask · CPC title

• G06F9/30036

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

• G06F9/30018

  Bit or string instructions · CPC title

• G06F9/30021 Primary

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

• G06F9/30098

  Register arrangements · CPC title