Extensions of Cartesian Genetic Programming for Optimization of Complex Combinational Circuits

Extensions of Cartesian Genetic Programming for Optimization of Complex Combinational Circuits

Paper in proceedings outside WoS and Scopus

Evolution and optimization of digital circuits using standard Cartesian Genetic Programming (CGP) is not scalable mainly because the evaluation time grows exponentially with increasing number of circuit inputs. We propose to combine two extensions of CGP to improve post-synthesis optimization capabilities of CGP. Firstly, we replace the standard fitness function by an equivalence checking algorithm which significantly reduces the fitness evaluation time for complex circuits. Secondly, we propose to modify the selection strategy of CGP to increase the number of functionally correct solutions that can be created using a mutation operator. Proposed extensions of CGP are evaluated using the LGSynth93 benchmark circuits. Experimental results show that extended CGP can significantly reduce the number of gates (area reduced by 24% on average) in benchmark circuits for the cost of runtime in comparison to conventional methods such as SIS and ABC.

Evolution and optimization of digital circuits using standard Cartesian Genetic Programming (CGP) is not scalable mainly because the evaluation time grows exponentially with increasing number of circuit inputs. We propose to combine two extensions of CGP to improve post-synthesis optimization capabilities of CGP. Firstly, we replace the standard fitness function by an equivalence checking algorithm which significantly reduces the fitness evaluation time for complex circuits. Secondly, we propose to modify the selection strategy of CGP to increase the number of functionally correct solutions that can be created using a mutation operator. Proposed extensions of CGP are evaluated using the LGSynth93 benchmark circuits. Experimental results show that extended CGP can significantly reduce the number of gates (area reduced by 24% on average) in benchmark circuits for the cost of runtime in comparison to conventional methods such as SIS and ABC.

logic optimization, genetic programming, digital circuit

logic optimization, genetic programming, digital circuit

VAŠÍČEK, Z.; SEKANINA, L.

04.06.2011

University of California San Diego

San Diego

Proc. of the 20th International Workshop on Logic and Synthesis

55

61

7

http://hdl.handle.net/