Plausability-driven fault detection in result logic and condition codes for fast exact substring match

Patent metadata

Field	Value
Publication number	US-11042371-B2
Application number	US-201916567398-A
Country	US
Kind code	B2
Filing date	Sep 11, 2019
Priority date	Sep 11, 2019
Publication date	Jun 22, 2021
Grant date	Jun 22, 2021

Abstract

A method for detecting faults in substring search operations includes providing, using a processor unit including 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. A vector element is an n-bit element for encoding a character. 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 indicates characters of the target string that partially match the reference string. Fault detection in the substring search operations is performed by utilizing the resulting bit vector.

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 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 utilizing the resulting bit vector.

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 based on the resulting bit vector and generating a condition code indicating a type of a detected match based on the resulting bit vector.

3. The method of claim 2 , wherein performing the fault detection further comprises comparing the resulting bit vector with a first row of the M×M matrix and indicating an error if the resulting bit vector is different from a subset of the first row of the M×M matrix.

4. The method of claim 2 , further comprising generating a zero detect vector having a value indicative of a terminating element of the target string and comparing the resulting bit vector with the zero detect vector, wherein performing the fault detection further comprises indicating an error if the bit position within the resulting bit vector of the bit indicating a match is higher than the bit position within the zero detect vector of the bit indicating the terminating element of the target string.

5. The method of claim 2 , further comprising determining a matchable region within the target string and comparing the resulting bit vector with the matchable region and wherein performing the fault detection further comprises indicating an error if the condition code indicates a full match and all bits of the matchable region within the target string are set to 0.

6. The method of claim 2 , wherein performing the fault detection further comprises indicating an error if the resulting bit vector is misaligned with a vector element.

7. The method of claim 6 , wherein misalignment is detected if at least one byte different from a first byte of the vector element of the resulting bit vector is set to 1.

8. The method of claim 2 , further comprising generating a zero detect vector having a value indicative of a terminating element of the target string, comparing the condition code with the generated index, and comparing the condition code with the zero detect vector, and wherein performing the fault detection further comprises indicating an error (a) if the condition code indicates that (1) no full string match has been detected, (2) no partial match has been detected and (3) no terminating elements have been detected or (b) if (1) the generated index indicates the first match or (2) the zero detect vector has a bit value set to 1 indicating the terminating element of the target string.

9. The method of claim 8 , wherein performing the fault detection further comprises indicating an error (a) if the condition code indicates that no full string match has been detected and no partial match has been detected and indicating that the terminating element has been detected or (b) if the generated index indicates the first match or the zero detect vector has all bits set to 0 indicating no terminating element of the target string has been detected.

10. The method of claim 8 , further comprising determining a match type based on the resulting bit vector, comparing the condition code with the generated index, and comparing the condition code with the determined match type, and wherein performing the fault detection further comprises indicating an error if (a) the condition code indicates that a full string match has been detected or (b) if (1) the generated index indicates that no match has been detected or (2) the resulting bit vector indicates that a partial match has been detected.

11. The method of claim 10 , wherein performing the fault detection further comprises indicating an error if (a) the condition code indicates that a partial match has been detected and no full string match has been detected or (b) if (1) the generated index indicates that no match has been detected or (2) the resulting bit vector indicates that a full match has been detected.

12. 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 of the plurality of vector registers storing the reference string and elements of a second register of the plurality of vector registers storing a target string;
a result generating logic for generating a resulting bit vector, 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
a fault detection logic for performing fault detection in the substring search operations by utilizing the resulting bit vector.

13. The processor unit of claim 12 , 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 based on the resulting bit vector and generating a condition code indicating a type of a detected match based on the resulting bit vector.

14. The processor unit of claim 13 , wherein performing the fault detection further comprises comparing the resulting bit vector with a first row of the M×M matrix and indicating an error if the resulting bit vector is different from a subset of the first row of the M×M matrix.

15. The processor unit of claim 13 , further comprising a zero detect logic for generating a zero detect vector having a value indicative of a terminating element of the target string, wherein performing the fault detection further comprises indicating an error if the bit position within the resulting bit vector of the bit indicating a match is higher than the bit position within the zero detect vector of the bit indicating the terminating element of the target string.

16. The processor unit of claim 13 , wherein the fault detection logic determines a matchable region within the target string and compares the resulting bit vector with the matchable region and wherein performing the fault detection further comprises indicating an error if the condition code indicates a full match and all bits of the matchable region within the target string are set to 0.

17. The processor unit of claim 13 , wherein performing the fault detection further comprises indicating an error if the resulting bit vector is misaligned with a vector element.

18. The processor unit of claim 17 , wherein misalignment is detected if at least one byte different from a first byte of the vector element of the resulting bit vector is set to 1.

19. The processor unit of claim 13 , further comprising a

Assignees

• IBM

Inventors

• Figuli Razvan Peter
• Payer Stefan
• Lichtenau Cedric
• Schelm Kerstin Claudia

Classifications

• G06F9/30038

  using a mask · CPC title

• G06F9/30036 Primary

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

• G06F9/30018 Primary

  Bit or string instructions · CPC title

• G06F9/30021

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

• G06F9/30098

  Register arrangements · CPC title