Slashdot Mirror

← Back to Stories (view on slashdot.org)

Genetic Algorithms and Compiler Optimizations

Posted by michael on from the when-it-absolutely-positively-has-to-run-overnight dept.

mfago writes "Scott Robert Ladd has written an enlightening article and accompanying software package that utilizes genetic algorithms to optimize the optimization flags fed to a compiler. Those who have tried to squeeze the last drop of performance from a code know that it can be very difficult to determine the set of optimization flags beyond -O3 (with gcc for example) that yields the best performance. Lots of background links included in the article."

6 of 222 comments (clear)

  1. I did for this for my Ph.D. defense by Anonymous Coward · · Score: 4, Interesting

    It turns out that hand tuning will ALWAYS get you the best optimizations, but human nature dictates that a certain portion of optimizations will never be found. Genetic algorithms will find some of these optimizations in a reasonable time, but not all. So the bottom line is, no code can ever be 100% optimized, unless it is compiled for weeks.

  2. cool application for GA by millette · · Score: 4, Interesting

    This is a very neat application of genetic algoriths! Haven't seen something so interesting since this Tron cycle game.

  3. Skepticism by wdavies · · Score: 5, Interesting

    It actually seems like a good idea.Some problems I can imagine are optimization flags may have non speed related side-effects?

    However, this seems like a great candidate for GA's - a fitness function (ie speed of execution), and a nice binary vector of atributes (flags).

    Interesting that the gains aren't that great it would seem to sugges that the flags don't do much :) or maybe the base-line is already close to optimal, and so it isnt a hard problem?

    But Kudos nevertheless. No expert in the GA field, so its possible someones tackled this before, but if they haven't, extra Kudos.

    Winton

  4. Why use a GA? by eclarkso · · Score: 4, Interesting
    In general, the literature suggests that GAs tend to be a kind of 'jack of all trades, master of none' type approach. See, e.g., Russell & Norvig's AI: A Modern Approach textbook.

    As such, is there any justification for using a GA to do this rather than, say, simulated annealing? I'd would be interested to see a comparison of the two approaches. Especially in light of papers like this one.

  5. Re:Beware the simple, elegant solution. by mfago · · Score: 4, Interesting

    anyways think about the overkill of developing such an elegant solution for such a minor problem. i mean those few percentages of performance enhancement...

    I'm sure some people would love a few percent improvement in their SPEC results...

    Personally, I have an algorithm that I'm running hundreds of millions of times as part of a larger calculation for my PhD research. I'd love a "few percent" improvement simply by changing the compiler flags.

    Acovea is curently a research tool in its own right, and not quite ready for application to general problems. Some issues that require modest effort to resolve:

    1) Code currently is pentium3/4 centric
    2) Optimizes flags for gcc 3.4 or intel's compiler
    3) Cannot easily handle code residing in more than one file.

  6. Re:Beware the simple, elegant solution. by Dachannien · · Score: 4, Interesting

    What we should be most skeptical about is that Mr. Ladd wanted to study the effects of using a GA on optimization, yet he neglected to run a control sample involving random perturbation of options from the start case (-O1 or -O3), without selection.

    If, as I suspect, the search space is disorderly, then random perturbation should, among the same number of test compilations, be able to find a solution comparable to that which his GA finds.