Designing approximate adder circuits using reinforcement learning
Methods, systems, and apparatus, including computer programs encoded on a computer storage medium for designing approximate adder circuits. In one aspect, a method includes: initializing a parallel prefix graph representing a parallel prefix circuit; and for each step in a sequence of steps: obtaining a current state of the parallel prefix graph; processing the current state using a neural network to generate a policy for adding or deleting nodes in the parallel prefix graph; adding or deleting a node in the parallel prefix graph while subject to one or more constraints; synthesizing the parallel prefix circuit having logic circuits corresponding to nodes in the parallel prefix graph; generating a respective value for each of multiple circuit-based metrics; determining a reward based on the values of the circuit-based metrics; and training the network parameters of the neural network on the reward using a reinforcement learning algorithm.
1 . A method performed by one or more computers for optimizing a parallel prefix circuit configured to process an input sequence to generate an output sequence comprising, at least approximately, a prefix computation of the input sequence, the method comprising:
initializing a parallel prefix graph representing the parallel prefix circuit, the parallel prefix graph comprising:
a respective input and corresponding output at each of a plurality of bit positions that are arranged from a least significant bit to a most significant bit; and
a plurality of nodes connecting the inputs to the outputs, each node representing a logic circuit that implements an associative operator of the prefix computation,
wherein for each bit position proceeding the least significant bit, the output at the bit position is connected to the input at the bit position and one or more preceding bit positions; and
for each step in a sequence of steps:
obtaining a current state of the parallel prefix graph;
processing the current state using a neural network, in accordance with a set of network parameters of the neural network, to determine a policy for adding or deleting nodes in the parallel prefix graph given the current state;
adding or deleting a node in the parallel prefix graph using the policy while subject to one or more constraints,
wherein the one or more constraints specify that, when the node is added or deleted, the output at each bit position proceeding a threshold bit position is connected to, at minimum, a threshold number of inputs;
synthesizing the parallel prefix circuit having logic circuits corresponding to nodes in the parallel prefix graph;
generating a respective value for each of a plurality of circuit-based metrics of the parallel prefix circuit when synthesized;
determining a reward for the step based on the values of the circuit-based metrics at the step; and
training the network parameters of the neural network on the reward for the step using a reinforcement learning algorithm.
2 . The method of claim 1 , wherein:
the threshold bit position is a first threshold bit position;
the threshold number of inputs is a first threshold number of inputs, and
the one or more constraints further specify that, when the node is added or deleted, the output at each bit position proceeding a second threshold bit position is connected to, at maximum, a second threshold number of inputs.
3 . The method of claim 2 , wherein the second threshold number of inputs is equal to a binary logarithm of a total number of inputs.
4 . The method of claim 3 , where the total number of inputs is equal to one of: eight, sixteen, thirty-two, or sixty-four.
5 . The method of claim 1 , wherein the parallel prefix graph is initialized as a Sklansky parallel prefix graph, an approximate Sklansky parallel prefix graph, a Kogge-Stone parallel prefix graph, or an approximate Kogge-Stone parallel prefix graph.
6 . The method of claim 1 , wherein the circuit-based metrics comprise, at least one of, a circuit area or a computation delay.
7 . The method of claim 6 , wherein the circuit-based metrics further comprise a power consumption.
8 . The method of claim 1 , wherein determining the reward for the step based on the values of the circuit-based metrics at the step comprises:
determining the reward for the step based on a difference between: (i) the values of the circuit-based metrics at the step, and (ii) values of the circuit-based metrics at a preceding step.
9 . The method of claim 1 , wherein the reinforcement learning algorithm is a Q-learning algorithm.
10 . The method of claim 9 , wherein processing the current state using the neural network, in accordance with the network parameters of the neural network, to determine the policy for adding or deleting nodes in the parallel prefix graph given the current state comprises:
processing the current state using the neural network, in accordance with the network parameters of the neural network, to generate a Q-value given the current state,
wherein the Q-value characterizes a cumulative measure of rewards that are predicted to be received at each proceeding step if nodes are added or deleted from the parallel prefix graph using the policy at each proceeding step; and
determining the policy by maximizing the Q-value.
11 . The method of claim 10 , wherein training the network parameters of the neural network on the reward for the step using the Q-learning algorithm comprises:
determining gradients of an objective function that depends on the Q-value and the reward at the step; and
updating the network parameters of the neural network using the gradients of the objective function.
12 . The method of claim 9 , wherein the Q-learning algorithm is a double Q-learning algorithm.
13 . The method of claim 12 , wherein the double Q-learning algorithm is a scalarized double Q-learning algorithm.
14 . The method of claim 1 , wherein the logic circuit comprises two AND logic gates and an OR logic gate.
15 . The method of claim 14 , wherein each input of the input sequence comprises: (i) a respective generate bit, and (ii) a corresponding propagate bit.
16 . The method of claim 15 , wherein each output of the output sequence comprises: (i) a respective approximate group generate bit, and (ii) a corresponding approximate group propagate bit.
17 . The method of claim 1 , wherein the neural network is a convolutional neural network.
18 . The method of claim 17 , wherein the convolutional neural network is in a residual network configuration.
19 . One or more non-transitory computer storage media storing instructions that, when executed by one or more computers, cause the one or more computers to perform operations of a method for optimizing a parallel prefix circuit configured to process an input sequence to generate an output sequence comprising, at least approximately, a prefix computation of the input sequence, the method comprising:
initializing a parallel prefix graph representing the parallel prefix circuit, the parallel prefix graph comprising:
a respective input and corresponding output at each of a plurality of bit positions that are arranged from a least significant bit to a most significant bit; and
a plurality of nodes connecting the inputs to the outputs, each node representing a logic circuit that implements an associative operator of the prefix computation,
wherein for each bit position proceeding the least significant bit, the output at the bit position is connected to the input at the bit position and one or more preceding bit positions; and
for each step in a sequence of steps:
obtaining a current state of the parallel prefix graph;
processing the current state using a neural network, in accordance with a set of network parameters of the neural network, to determine a policy for adding or deleting nodes in the parallel prefix graph given the current state;
adding or deleting a node in the parallel prefix graph using the policy while subject to one or more constraints,
wherein the one or more constraints specify that, when the node is added or deleted, the output at each bit position proceeding a threshold bit position is connected to, at minimum, a threshold number of inputs;
synthesizing the parallel prefix circuit having logic circuits corresponding to nodes in the parallel prefix graph;
generating a respective value for each of a plurality of circuit-based metrics of the parallel prefix circuit when synthesized;
determining a reward for the step based on the values of the circuit-based metrics at the step; and
training the network parameters of the neural network on the reward for the step using a reinforcement learning algorithm.
20 . A system comprising one or more computers and one or more storage devices communicatively coupled to the one or more computers, wherein the one or more storage devices store instructions that, when executed by the one or more computers, cause the one or more computers to perform operations of a method for optimizing a parallel prefix circuit configured to process an input sequence to generate an output sequence comprising, at least approximately, a prefix computation of the input sequence, the method comprising:
initializing a parallel prefix graph representing the parallel prefix circuit, the parallel prefix graph comprising:
a respective input and corresponding output at each of a plurality of bit positions that are arranged from a least significant bit to a most significant bit; and
a plurality of nodes connecting the inputs to the outputs, each node representing a logic circuit that implements an associative operator of the prefix computation,
wherein for each bit position, the output at the bit position is connected to the input at the bit position and one or more preceding bit positions; and
for each step in a sequence of steps:
obtaining a current state of the parallel prefix graph;
processing the current state using a neural network, in accordance with a set of network parameters of the neural network, to determine a policy for adding or deleting nodes in the parallel prefix graph given the current state;
adding or deleting a node in the parallel prefix graph using the policy while subject to one or more constraints,
wherein the one or more constraints specify that, when the node is added or deleted, the output at each bit position proceeding a threshold bit position is connected to, at minimum, a threshold number of inputs;
synthesizing the parallel prefix circuit having logic circuits corresponding to nodes in the parallel prefix graph;
generating a respective value for each of a plurality of circuit-based metrics of the parallel prefix circuit when synthesized;
determining a reward for the step based on the values of the circuit-based metrics at the step; and
training the network parameters of the neural network on the reward for the step using a reinforcement learning algorithm.