# Coverage Fulfillment Automation in Hardware Functional Verification Using Genetic Algorithms
## 3 Materials and Methods
### Operation of Genetic Algorithms  
Use of genetic algorithms is considered one of the best practices for speeding up functional coverage fulfillment [13]. Two key attributes of these algorithms are that they \"ensure global optimization and have a high degree of parallelism\" [14]. Using genetic algorithms, multiple stimulus sets are combined in a close-to-optimal way. If two stimuli sequences provide a good coverage value, it can be considered that a combination between them will be beneficial as well. Therefore, when combining these lists of stimuli in different ways, other datasets are generated which have the potential to improve the coverage fulfillment level. As genetic algorithms provide approximated solutions close to the optimal one, more than one set of stimuli can be obtained as potential results for a desired coverage. Genetic algorithms begin with the generation of a random population of stimuli. A population consists of individuals. Each individual contains a sequence of stimuli which will be further driven to the DUT using the verification components usually employed according to the UVM methodology (sequence, sequencer, and driver). In Figure 4, the representation of an individual which contains values 8 bits wide can be seen. These values are transmitted to the DUT input called the \"first operand\". In some implementations, multiple groups of individuals are generated for the same verification environment. Data from each group are transmitted through a specific interface signal to the DUT. There are two main operators which are used in most implementations of genetic algorithms in the industry, namely, crossover and mutation [28; 29]. Crossover operators combine two individuals by breaking them into two parts at a random position and switching their second part, as represented in Figure 5.  
The initial individuals are called parents, and the individuals resulting from combinations of parents are called children [30]. The crossover process is mathematically described for the first child using (1). The first child takes the genes of parent 1 until the breaking point and the genes of parent 2 found after the breaking point. For the second child, the complementary behavior can be easily deduced. \[child_{1}[i]=\left\{ \begin{array}{l}parent_{1}\ [i],\ if\ i\leq random\_number\\ parent_{2}[i],\ if\ i>random\_number\end{array} ,i\in[1,2]\right. \tag{1}\]  
where _random_number_ is a randomly generated value in the range of the number of bits/elements of the stimuli list. The _random_number_ represents the crossing point (the dashed line in Figure 5). In this way, if two parents obtained good performance in terms  
Figure 4: The representation of an individual containing 20 values of data items, each 8 bits wide. Figure 5: Crossover process representation. of functional coverage fulfillment, the children embedding the \"best part\" of each parent could give even better results. Furthermore, two parents who initially were not valuable in terms of coverage fulfillment could generate high-performing children by creating other combinations of input stimuli. If more breaking points are employed, the same parents can generate more than two children. The mutation operator is applied by changing a few of their values (randomly selected); in the current implementation, one or two values were altered inside the structure of children. This helps the algorithm to avoid local maxima, represented by high coverage values the population converges to which are not the best overall score. The effect of the mutation operator is represented in Figure 6.  
In Figure 6, the element with value 4 and index 8 was mutated. In this way, a fresh offspring appeared in the available population of individuals. Considering the information above, the number of children can exceed the number of parents. Therefore, after creating all of the desired children, a selection process is applied, as can be observed in (2).