US 12,141,582 B2 · Implementing specialized instructions for accelerating dynamic programming algorithms

Abstract

Various techniques for accelerating dynamic programming algorithms are provided. For example, a fused addition and comparison instruction, a three-operand comparison instruction, and a two-operand comparison instruction are used to accelerate a Needleman-Wunsch algorithm that determines an optimized global alignment of subsequences over two entire sequences. In another example, the fused addition and comparison instruction is used in an innermost loop of a Floyd-Warshall algorithm to reduce the number of instructions required to determine shortest paths between pairs of vertices in a graph. In another example, a two-way single instruction multiple data (SIMD) floating point variant of the three-operand comparison instruction is used to reduce the number of instructions required to determine the median of an array of floating point values.

Claims20

Dependent claims

A computer-implemented method for executing dynamic programming algorithms on parallel processors, the method comprising:

during a first iteration of a loop of a dynamic programming algorithm, executing at least one of a first fused addition and comparison instruction, a first three-operand comparison instruction, or a first two-operand comparison instruction that indicates a first source operand associated with a first destination operand to determine a first result, wherein the comparison is performed on multiple source operands including the first source operand;
and
during a second iteration of the loop, executing at least one of a second fused addition and comparison instruction, a second three-operand comparison instruction, or a second two-operand comparison instruction that indicates a second source operand associated with a second destination operand to determine a second result based on the first result, wherein the comparison is performed on multiple source operands including the second source operand.

One or more non-transitory computer readable media including instructions that, when executed by one or more processors, cause the one or more processors to execute dynamic programming algorithms by performing the steps of:

during a first iteration of a loop of a dynamic programming algorithm, executing at least one of a first fused addition and comparison instruction, a first three-operand comparison instruction, or a first two-operand comparison instruction that indicates a first source operand associated with a first destination operand to determine a first result, wherein the comparison is performed on multiple source operands including the first source operand;
and
during a second iteration of the loop, executing at least one of a second fused addition and comparison instruction, a second three-operand comparison instruction, or a second two-operand comparison instruction that indicates a second source operand associated with a second destination operand to determine a second result based on the first result, wherein the comparison is performed on multiple source operands including the second source operand.

Dependencies are inferred from the claim text.

Implementing specialized instructions for accelerating dynamic programming algorithms

Life of this patent

Implementing specialized instructions for accelerating dynamic programming algorithms

Life of this patent

Abstract

Claims20