Logic optimization

Algorithm

And-inverter graph

Boolean circuit

Statistics

Markov process

Sequential logic

Theoretical computer science

Operating system

Computer science

Markov decision process

Mathematics

Logic gate

Logic synthesis

Combinational logic

Heuristics

Logic synthesis for combinational circuits is to find the minimum equivalent representation for Boolean logic functions. A well-adopted logic synthesis paradigm represents the Boolean logic with standardized logic networks, such as and-inverter graphs (AIG), and performs logic minimization operations over the graph iteratively. Although the research for different logic representation and operations is fruitful, the sequence of using the operations are often determined by heuristics. We propose a Markov decision process (MDP) formulation of the logic synthesis problem and a reinforcement learning (RL) algorithm incorporating with graph convolutional network to explore the solution search space. The experimental results show that the proposed method outperforms the well-known logic synthesis heuristics with the same sequence length and action space.

Exploring Logic Optimizations with Reinforcement Learning and Graph Convolutional Network