Implementing specialized floating point instructions on an integer pipeline for accelerating dynamic programming algorithms
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.
1 . 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, on an integer pipeline, at least one of a first floating point fused addition and comparison instruction, a first floating point three-operand comparison instruction, or a first floating point two-operand comparison instruction that indicates a first source operand associated with a first destination operand to determine a first result, wherein execution of the at least one of a first floating point fused addition and comparison instruction, a first floating point three-operand comparison instruction, or a first floating point two-operand comparison instruction includes a comparison performed on multiple source operands including the first source operand; and
during a second iteration of the loop, executing, on the integer pipeline, at least one of a second floating point fused addition and comparison instruction, a second floating point three-operand comparison instruction, or a second floating point 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.
2 . The computer-implemented method of claim 1 , wherein the at least one of the first floating point fused addition and comparison instruction, the first floating point three-operand comparison instruction, or the first floating point two-operand comparison instruction comprises at least one of a two-way single instruction, multiple data (SIMD) instruction or a four-way SIMD instruction.
3 . The computer-implemented method of claim 1 , wherein the first floating point fused addition and comparison instruction computes a minimum or maximum of a first floating point value included in a third source operand and a sum of a second floating point value included in a fourth source operand and a third floating point value included in a fifth source operand.
4 . The computer-implemented method of claim 1 , wherein the first floating point three-operand comparison instruction computes a minimum or maximum of a first element of a third source operand, a second element of a fourth source operand, a third element of a fifth source operand, and zero.
5 . The computer-implemented method of claim 1 , wherein the first floating point two-operand comparison instruction indicates that a first element of the first destination operand is equal to a first element of the first source operand.
6 . The computer-implemented method of claim 1 , further comprising, prior to the second iteration of the loop, storing the first result in an array of results associated with a plurality of sub-problems.
7 . The computer-implemented method of claim 1 , wherein the dynamic programming algorithm comprises a Needleman-Wunsch algorithm, a local sequence alignment algorithm, a multi-sequence alignment algorithm, a partial order alignment algorithm, or a genome mapping algorithm.
8 . The computer-implemented method of claim 1 , wherein the dynamic programming algorithm comprises a Floyd-Warshall algorithm, a tensor contraction optimization algorithm, a median sorting network, or an algorithm associated with a fifth generation of wireless technology.
9 . The computer-implemented method of claim 1 , wherein executing the at least one of the first floating point fused addition and comparison instruction, the first floating point three-operand comparison instruction, or the first floating point two-operand comparison instruction comprises causing an integer pipeline of a parallel processor to execute a first operation on at least two floating point values.
10 . The computer-implemented method of claim 1 , wherein executing the at least one of the first floating point fused addition and comparison instruction, the first floating point three-operand comparison instruction, or the first floating point two-operand comparison instruction comprises causing a floating point pipeline of a parallel processor to execute an addition operation on two integer values.
11 . 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 steps of:
during a first iteration of a loop of a dynamic programming algorithm, executing, on an integer pipeline, at least one of a first floating point fused addition and comparison instruction, a first floating point three-operand comparison instruction, or a first floating point two-operand comparison instruction that indicates a first source operand associated with a first destination operand to determine a first result, wherein execution of the at least one of a first floating point fused addition and comparison instruction, a first floating point three-operand comparison instruction, or a first floating point two-operand comparison instruction includes a comparison performed on multiple source operands including the first source operand; and
during a second iteration of the loop, executing, on the integer pipeline, at least one of a second floating point fused addition and comparison instruction, a second floating point 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.
12 . The one or more non-transitory computer readable media of claim 11 , wherein the at least one of the first floating point fused addition and comparison instruction, the first floating point three-operand comparison instruction, or the first floating point two-operand comparison instruction comprises at least one of a two-way single instruction, multiple data (SIMD) instruction or a four-way SIMD instruction.
13 . The one or more non-transitory computer readable media of claim 11 , wherein the first floating point fused addition and comparison instruction computes a minimum or maximum of a first element of a third source operand and a sum of a first element of a fourth source operand and a first element of a fifth source operand.
14 . The one or more non-transitory computer readable media of claim 11 , wherein the first floating point three-operand comparison instruction computes a minimum or maximum of a first floating point value included in a third source operand, a second floating point value included in a fourth source operand, and a third floating point value included in a fifth source operand.
15 . The one or more non-transitory computer readable media of claim 11 , wherein the first floating point two-operand comparison instruction indicates that a first floating point value included in the first destination operand is equal to a second floating point value included in the first source operand.
16 . The one or more non-transitory computer readable media of claim 11 , further comprising, prior to the second iteration of the loop, storing the first result in an array of results associated with a plurality of sub-problems.
17 . The one or more non-transitory computer readable media of claim 11 , wherein the dynamic programming algorithm comprises a Needleman-Wunsch algorithm, a local sequence alignment algorithm, a multi-sequence alignment algorithm, a partial order alignment algorithm, or a genome mapping algorithm.
18 . The one or more non-transitory computer readable media of claim 11 , wherein the dynamic programming algorithm comprises a Floyd-Warshall algorithm, a tensor contraction optimization algorithm, a median sorting network, or an algorithm associated with a fifth generation of wireless technology.
19 . The one or more non-transitory computer readable media of claim 11 , wherein executing the at least one of the first floating point fused addition and comparison instruction, the first floating point three-operand comparison instruction, or the first floating point two-operand comparison instruction comprises causing an integer pipeline of a parallel processor to execute a first operation on at least two floating point values.
20 . A system comprising:
one or more memories storing instructions; and
one or more processors coupled to the one or more memories that, when executing the instructions:
during a first iteration of a loop of a dynamic programming algorithm, executes, on an integer pipeline included in the one or more processors, at least one of a first floating point fused addition and comparison instruction, a first floating point three-operand comparison instruction, or a first floating point two-operand comparison instruction that indicates a first source operand associated with a first destination operand to determine a first result, wherein execution of the at least one of a first floating point fused addition and comparison instruction, a first floating point three-operand comparison instruction, or a first floating point two-operand comparison instruction includes a comparison performed on multiple source operands including the first source operand; and
during a second iteration of the loop, execues, on the integer pipeline, at least one of a second floating point fused addition and comparison instruction, a second floating point 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.