Genetic Algorithm to find optimal compiler flags

Yash Kothari — Thu, 21 May 2020 13:36:33 +0000

This post supports my entry into $ git remote 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. 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.

Using Genetic Algorithm

A large search space of about 2⁶⁰ 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 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.

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!

DEV Community: Yash Kothari