Grammatical Evolution of Complex Digital Circuits in SystemVerilog

Abstract

The evolution of complex circuits remains a challenge for the Evolvable Hardware field in spite much effort. There are two major issues: the amount of testing required and the low evolvability of representation structures to handle complex circuitry, at least partially due to the destructive effects of genetic operators. A 64-bit $\times$ 64-bit add-shift multiplier circuit modelled at register-transfer level in SystemVerilog would require approximately 33,200 gates when synthesized using Yosys Open SYnthesis Suite tool. This enormous gate count makes evolving such a circuit at the gate-level difficult. We use Grammatical Evolution (GE) and SystemVerilog, a hardware description language (HDL), to evolve fully functional parameterized Adder, Multiplier, Selective Parity and Up-Down Counter circuits at a more abstract level other than gate level-register transfer level. Parameterized modules have the additional benefit of not requiring a re-run of evolutionary experiments if multiple instances with different input sizes are required. For example, a 64-bit $\times$ 64-bit and 128-bit $\times$ 128-bit multipliers etc., can be instantiated from a fully evolved functional and parameterized N-bit $\times$ N-bit multiplier. The Adder (6.4 $\times$ ), Multiplier (10.7 $\times$ ) and Selective Parity (6.7 $\times$ ) circuits are substantially larger than the current state of the art for evolutionary approaches. We are able to scale so dramatically because of the use of a HDL, which permits us to operate at a register-transfer level. Furthermore, we adopt a well known technique for reducing testing from digital circuit design known as corner case testing. Skilled circuit designers rely on this to avoid time-consuming exhaustive testing. We demonstrate a simple way to identify and use corner cases for evolutionary testing and show that it enables the generation of massively complex circuits. All circuits were successfully evolved without resorting to the use of any standard decomposition methods, due to our ability to use programming constructs and operators available in SystemVerilog.

Keywords: Combinational circuits; Corner case testing; Evolutionary design of conventional circuits; Evolvable hardware; Grammatical evolution; Hardware description language (HDL); Register transfer level (RTL); Sequential circuits; SystemVerilog; Verilog.