APPARATUS FOR OPTIMIZED MICROCODE INSTRUCTIONS FOR DYNAMIC PROGRAMMING BASED ON IDEMPOTENT SEMIRING OPERATIONS
In one embodiments, a method is provided. The method includes determining whether a set of algorithmic operations can be represented using an algebraic formulation. The method also includes generating a sequence of idempotent semiring operations based on the set of algorithmic operations in response to determining that the set of algorithmic operations can be represented using the algebraic formulation. The sequence of idempotent semiring operations are part of an algebraic idempotent semiring, represent the algebraic formulation, and comprise one or more of an associative, commutative pick operation that forms an abelian monoid and an associative tally operation that forms a monoid and distributes over the pick operation. The method also includes generating a sequence of microcode instructions based on the sequence of idempotent semiring operations, wherein the sequence of microcode instructions carries out the sequence of idempotent semiring operations.
1 . An apparatus, comprising:
a memory configured to store a sequence of microcode instructions, wherein:
a subset of the sequence of microcode instructions are based on a set of idempotent semiring operations;
the set of idempotent semiring operations are part of an algebraic idempotent semiring; and
the set of idempotent semiring operations represent an algebraic formulation representing a set of algorithmic operations;
a hardware processing device operatively coupled to the memory and comprising a set of processing units configured to:
receive the sequence of microcode instructions, wherein:
the sequence of microcode instructions carries out the set of idempotent semiring operations; and
the set of processing units are configured for parallelized operations based on one or more of the algebraic formulation and the set of idempotent semiring operations;
and
execute the sequence of microcode instructions in the set of processing units.
2 . The apparatus of claim 1 , wherein the sequence of microcode instructions are executed in parallel in the set of processing units.
3 . The apparatus of claim 1 , wherein the hardware processing device is further configured to:
receive an indication that a second set of idempotent semiring operations should be used, wherein:
the second set of idempotent semiring operations represent a second algebraic formulation; and
the second set of idempotent semiring operations are part of a second algebraic idempotent semiring;
receive a second sequence of microcode instructions, wherein the second sequence of microcode instructions are generated based on the second set of idempotent semiring operations; and
execute the second sequence of microcode instructions, wherein the set of processing units are further configured for operations based on one or more of the second algebraic formulation and the second set of idempotent semiring operations.
4 . The apparatus of claim 1 , wherein:
each of the set of idempotent semiring operations comprises one or more of an associative, commutative pick operation that forms an abelian monoid and an associative tally operation that forms a monoid and distributes over the pick operation;
the associate commutative pick operation selects a value from a first plurality of values; and
the associative tally operation generates a generalized product of a second plurality of values.
5 . The apparatus of claim 1 , wherein the hardware processing device comprises a systolic array and wherein the set of processing units comprises a set of data processing units.
6 . The apparatus of claim 1 , wherein the hardware processing device comprises a single instruction multiple thread (SIMT) architecture.
7 . The apparatus of claim 1 , wherein the hardware processing device comprises a single instruction multiple data (SIMD) architecture.
8 . The apparatus of claim 1 , wherein the hardware processing device comprises a multiple instruction multiple data (MIMD) architecture.
9 . The apparatus of claim 1 , wherein each processing unit of the set of processing units provides a partial result to a respective next processing unit.
10 . The apparatus of claim 8 , wherein each processing unit of the set of processing units comprises a memory configured to store an operand.
11 . The apparatus of claim 1 , wherein the set of algorithmic operations comprise operations for determining a solution for a dynamic programming problem.
12 . The apparatus of claim 11 , wherein the set of algorithmic operations comprise operations for determining a solution for aligning nucleotide sequences.
13 . The apparatus of claim 11 , wherein the set of algorithmic operations comprise operations for determining a solution for a maximum likelihood decoder.
14 . The apparatus of claim 1 , wherein the algebraic idempotent semiring comprises one or more of: a tropical semiring, a k-tropical semiring, a Lukasiewicz semiring, a t-norm semiring, a Viterbi semiring, a matrix semiring, and a Boolean semiring.
15 . A method, comprising:
obtaining a sequence of microcode instructions, wherein:
a subset of the sequence of microcode instructions are based on a set of idempotent semiring operations;
the set of idempotent semiring operations are part of an algebraic idempotent semiring;
the set of idempotent semiring operations comprise one or more of an associative, commutative pick operation that forms an abelian monoid and an associative tally operation that forms a monoid and distributes over the pick operation;
the set of idempotent semiring operations represent an algebraic formulation representing a set of algorithmic operations; and
the sequence of microcode instructions carries out the set of idempotent semiring operations; and
executing the sequence of microcode instructions in a set of processing units of a hardware processing device, wherein the set of processing units are configured for parallelized operations based on one or more of the algebraic formulation and the set of idempotent semiring operations.
16 . The method of claim 15 , further comprising:
receiving an indication that a second set of idempotent semiring operations should be used, wherein:
the second set of idempotent semiring operations represent a second algebraic formulation; and
the second set of idempotent semiring operations are part of a second algebraic idempotent semiring;
obtaining a second sequence of microcode instructions, wherein the second sequence of microcode instructions are generated based on the second set of idempotent semiring operations; and
executing the second sequence of microcode instructions, wherein the set of processing units are further configured for operations based on one or more of the second algebraic formulation and the second set of idempotent semiring operations.
17 . The method of claim 15 , wherein:
each of the set of semiring operations comprises one or more of an associative, commutative pick operation that forms an abelian monoid and an associative tally operation that forms a monoid and distributes over the pick operation;
the associate commutative pick operation selects a value for a first plurality of values; and
the associative tally operation generates a generalized product of a second plurality of values.
18 . The method of claim 15 , wherein the hardware processing device comprises a systolic array and wherein the set of processing units comprises a set of data processing units.
19 . The method of claim 15 , wherein each processing unit of the set of processing units provides a partial result to a respective next processing unit.
20 . The method of claim 19 , wherein each processing unit of the set of processing units comprises a memory configured to store an operand.