Implementing a genetic algorithm in OpenROAD for improved resynthesis

A while back we described a new resynthesis strategy proposed by Antmicro in the OpenROAD ASIC design toolchain, based on simulated annealing. With this approach, we were able to significantly improve the process of fixing paths in the design that don’t satisfy the timing constraints of logic gates.

To optimize local resynthesis in OpenROAD even further, in a recent customer project we introduced an alternative strategy based on a genetic algorithm. It serves the same purpose as simulated annealing, but is more complex and therefore can potentially yield better results.

With both simulated annealing and a genetic algorithm-based approach implemented, OpenROAD users are now able to choose the strategy that best suits their needs. In this article we describe the new resynthesis strategy and show how it compares to simulated annealing.

Resynthesis with a genetic algorithm

The genetic algorithm in OpenROAD involves the following steps:

1. initialization
2. for n iterations:
   • crossover
   • mutation
   • selection

Initialization is the generation of n random solutions. Each solution (an individual) in the initial population is defined as a sequence of ABC operations to be performed for optimizing slack (i.e. the difference between how much time a given path takes and the clock period). We’ll refer to the elements of such a sequence as “genes”.

Crossover involves creating new solutions based on existing ones. Two random individuals (parents) are picked from the population to create a new one: using half of the genes of the first parent and the other half from the second one.

During mutation, a random individual from the population is picked to create a new, similar one by adding, removing or swapping genes with a given mutation probability.

The resulting solutions are selected for further optimization based on their fitness values, which in this case are their worst slacks. A deterministic tournament selection with replacement method is used for this purpose.

Using the genetic algorithm-based strategy in OpenROAD

The genetic algorithm implementation in OpenROAD includes the following customizable parameters:

• population size
• mutation probability
• crossover probability
• tournament size
• tournament probability

For a detailed list of options, refer to the OpenROAD documentation.

To test the genetic resynthesis strategy in OpenROAD, first follow the installation instructions. When you run openroad, it launches an interactive shell. Load the design:

read_liberty asap7.lib
read_lef asap7.lef
read_verilog aes_asap7.v
link_design aes
read_sdc aes_asap7.sdc

Then, run genetic resynthesis with default values:

resynth_genetic

report_checks

This will generate a design timing report containing information about the slack. And, like with simulated annealing, this process can be easily integrated with the OpenROAD flow.

Simulated annealing and genetic resynthesis: choosing the right approach

To illustrate how the genetic algorithm compares to the previously introduced simulated annealing strategy, we prepared a benchmark for a floorplan run of 3 designs from OpenROAD-flow-scripts:

• asap7/aes
• asap7/uart
• asap7/ethmac_lvt

resynth_genetic 
  -seed 66 
  -initial_ops 10 
  -iters 10  
  -population_size 50 
  -mutation_probability 0.70  
  -crossover_probability 0.50 
  -tournament_size 3 
  -tournament_probability 0.7

The results were compared against the baseline (ORFS master) and the simulated annealing strategy with the following parameters, tailored to AES:

resynth_annealing 
  -seed 66 
  -iters 100 
  -initial_ops 10 
  -temp 1e-11 
  -revert_after 10

Results

The experiments show noticeable improvements in terms of reduced power consumption for both simulated annealing and genetic algorithms. When it comes to timing results, we noticed that there are designs (such as AES) for which the genetic algorithm finds better solutions than simulated annealing. Keep in mind that the genetic algorithm’s parameters play an important role in yielding satisfactory results; values tailored to the AES design do not bring the same advantage to other designs or may even worsen the results (as in the case of ethmac_vlt).

Our recommendation is to stick with the annealing strategy for multi-design flows where adjusting parameters for every single design is not feasible, and to use the genetic strategy for specific designs that can benefit from experimental efforts in fine-tuning the parameters, which entails extending the overall computation time.

More efficient ASIC design with OpenROAD

Antmicro can help you take full advantage of the OpenROAD toolchain, whether you want to introduce new features or improve existing ones. We support our customers during architectural exploration and prototyping, providing them with developer productivity tools, coverage analysis and comprehensive testing workflows.

If you would like to learn more about Antmicro’s engineering services around OpenROAD and other ASIC design solutions, reach out to us at contact@antmicro.com.