Design validation of RTL circuits using evolutionary swarm intelligence

In this paper, we present BEACON, a Branch-oriented Evolutionary Ant Colony OptimizatioN method which is a bio-inspired meta-heuristic for design validation and functional test generation. BEACON combines an evolutionary search technique with Ant Colony Optimization (ACO) for improved search capability. BEACON first cross-compiles the Verilog circuit source to a C++ base for fast simulation. Then, it profiles the code, keeping track of each branch and the number of times it has been visited in a database. Branch coverage provides a very useful metric for exploring the design, especially visiting the most critical states, including corner states, in the design. At 100% branch coverage, we can conclude that every control state described in the RTL has been visited. Thus, during execution, BEACON trims highly visited branches from the search and focuses the search on rarely occurring branches and paths. This approach gives a significant performance boost while maintaining a high level of coverage. Experimental results show that BEACON is able to achieve very high branch coverages with a fraction of computational cost. In addition, previous hard-to-reach corner states in the ITC99 benchmarks have now been reached by BEACON. New states can also be discovered from the RTL descriptions. For many circuits, one to two orders of magnitude speedups over existing methods have been achieved.