Genetic Algorithm to find optimal compiler flags
Tags: octograd2020, python, angular, devgrad2020
Published: 2020-05-21 13:36:33

*This post supports my entry into [$ git remote graduation](https://github.com/education/graduation).*

## Introduction

Compiler flags offer control over which optimizations should be enabled/disabled during the compilation of a program. A compiler like GCC offers *~60* flags related to different types of optimization, a list of these flags can be found [here](https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html). These flags can affect the execution time, binary file size, power consumption, etc.

This project focuses on finding optimal GCC flags for a given C program to improve its execution time and benchmark it using [MiBench](http://vhosts.eecs.umich.edu/mibench/Publications/MiBench.pdf).

## Using Genetic Algorithm

A large search space of about *2<sup>60</sup>* combination of flags makes it impossible to try all possibilities, an evolutionary algorithm starts with a random set of population and over generations of selection, cross-over and mutation tries to converge to a global optimal solution. Each member of the population has a DNA which is a binary string of 58 characters corresponding to the compiler flags.

Pseudo code: 
```
init_population()
calculate_fitness()
while generation < MAX_GENERATIONS:
    perform_selection()
    perform_mutation()
    calculate_fitness()
```

* Selection involves,
  * Elitism, maintaining the top *10%* of the population of current generation in the next generation
  * Crossover, selecting two parents and producing a child using one point cross over with *60%* probability.

* Mutation performs a bit-flip at a random position in the DNA of a member with *1%* probability.


## Results
To conclude the project we decided to simulate the process of genetic algorithm over various generations by storing population data for each generation and plotting the fitness graph on a web browser. Here, is an example of one such plot,

![Fitness vs Generation graph](https://dev-to-uploads.s3.amazonaws.com/i/pmqxr4qxaci9ir9tkjje.png)

Fitness is calculated as, *1 / execution time*

## Tech stack

The core algorithm was implemented using *Python* and the front-end simulation was implemented using Angular. The data for each generation is stored in a JSON file. 

One of the most important task was to calculate the execution time, I used the `timeit` and `subprocess` module to accomplish this.

```
        stmt = 'subprocess.run({}, stderr=subprocess.STDOUT,\
        stdout=subprocess.DEVNULL, check=True)'.format(cmd_list)
        return timeit.timeit(stmt=stmt,
                             setup='import subprocess',
                             number=iterations) / iterations
```

I also learnt about how Angular updated in the DOM by evaluating expressions repeatedly, for my use case I needed more control over when the DOM gets updated and came across `ChangeDetectorRef` which does exactly that. 

## Link to Code
Code is available on [github](https://github.com/soumyas98/Compiler).

## Conclusion

This project provided me with various opportunities to learn more about compilers, optimization, reading research papers, and trying out new things which were just out of my comfort zone. The next steps that I have in mind is to run it on a larger population and generation size, using different crossover and mutation rates.

Thanks for reading!