Designing approximate adder circuits using reinforcement learning

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.

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.