# Evolving Multi-Output Digital Circuits Using Multi-Genome Grammatical Evolution
## 3 Proposed Approach: Multi-Genome GE
### Grammar Design  
In MG-GE, each genome is mapped to its output expression or subprogram to model and predict its corresponding output variable. MG-GE requires a single grammar, just like standard GE. However, custom grammar rules have been introduced and must be adhered to. There are two main custom rules: _output rule_ and _output variable rule_. These rules are illustrated by a sample grammar in Figure 3. These custom rules allow for grammar rules to be annotated with required details which are parsed and used by the mapper, wrapper, selection, initialisation and genetic operators. An _output rule_ (or _target rule_) is a rule that codes a solution to one of the output variables in a multi-output problem. To define an output rule, the rule's name must be preceded by \(tr\) followed by an output group number. During the mapping process, whenever such a rule is encountered, a sub-mapping process is spawned. For example, in Figure 3, there are four output rules: \(\langle\)tr1-output-1\(\rangle\), \(\langle\)tr1-output-2\(\rangle\), \(\langle\)tr1-output-3\(\rangle\) and \(\langle\)tr1-output-4\(\rangle\). Also, in Figure 3, there are two groups of output variables: 1 and 2. In other words, there should be an output variable rule for each output group number as illustrated in Figure 3.  
The purpose of the group numbers is to facilitate modelling dependencies between output variables while avoiding cyclic dependencies, which is very key for the evolution of combinational circuit designs. Recall in Section 3.2, we stated there might exist dependencies between outputs in some multi-output problems; hence, the group number allows outputs (represented by the output variable names as productions of output variable rules) to be grouped to allow evolution to evolve the potential dependencies which may exist between outputs belonging to the same group. For example, in combinational circuit problems, there may exist dependencies between outputs, but we need to ensure there exist no cyclic dependencies between these outputs. Failing to do so will result in circuit synthesis tools synthesising memory elements to store past/present output values, which render such a sequential circuit. Illustrated in Listing 1 is an example of a program with an existing cyclic dependency. Assuming the program in Listing 1 is a combinational circuit design in SystemVerilog, both outputs depend on each other, which will cause memory elements to be synthesised by circuit synthesis tools rendering the circuit a sequential circuit instead of a combinational circuit. The cyclic dependency checker in Algorithm 3 is used to ensure that during the initialisation and mapping processes, such cyclic dependencies do not occur. An output variable rule is defined by preceding the outputs group name by \(tv\) followed by the output group number (e.g., \(\langle\)tv1-outputs\(\rangle\) and \(\langle\)tv2-outputs\(\rangle\)). Essentially, an output  
Figure 3: MG-GE Sample Grammar. Figure 2: A Multi-genome representation for an multi-output problem with three output variables. variable rule's productions are output variables (e.g., output_1 and output_2) as shown in Figure 3. Also, note that the exact order in which output rules are defined for each corresponding output variable must be followed when defining an output variable rule as observed in Figure 3. For implementation purposes, extra attributes (corresponding output rule) are used to differentiate these outputs (e.g., output_1 and output_2), which are terminals from other terminals in the grammar during initialisation and mapping processes. An output variable rule is how evolution evolves dependencies that may potentially exist between outputs. During the initialisation and mapping process of each output rule (in other words, when an output variable is being modelled), the cyclic dependency checker algorithm ensures only choices of output variables that do not cause cyclic dependency can be chosen whenever an output variable rule non-terminal is encountered.