Slashdot Mirror
Genetic Algorithms and Compiler Optimizations
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."
I met SRL when I was teenager visiting Gunnison Colorado for the Rocky Mountain SOG. That was over 15 years ago. He was well into GA's then. Good to see he's still at it!
An important thing to note is that this isn't coming up with new optimizations, but rather finding the optimal mix of pre-existing gcc optimizations.
It's an important distinction. When you're trying to do breed some really new system using Genetic Algorithms, it's possible to get some very fragile results, i.e. systems that do the job incredibly efficiently, but only under certain conditions...
For instance, I remember reading some folks were trying to "breed" a circuit using Genetic Algorithm like techniques that created a "pulser" using as few gates as possible. They got something that used like one tenth the number of logic gates of the previous low record...but didn't work when they moved the setup away from their desktop PCs. Turned out what they "discovered" was a sensitive RF receiver that picked up (I think) something like the normal 120V cycling, and utilized. Similarly, a lot of the bred ciruits are extremely sensitive to temperature and other conditions.
So breeding for efficiency can be a bit dangerous, you get things that rely on odd side-effects and environmental states. Though I think the method the article describes isn't much more dangerous than normal optimization selection, though admittedly more likely to stumble over some unusual flag combination that might break under certain circumstances.
In short, *if* GA is ever going to let software development become more like gardening than engineering, (something I've herd as a goal) we're going to have to find ways to apply very general evolutionary pressures, complex test environments.
SO YOU'RE GOING TO DIE: The Comic for Dealing with Death
A scheme for automating optimization choices is not fragile (when the code changes, just re-run the optimizer) and portable (when compiling on another machine, just re-run the optimizer). Beats assembly hands down.
The use of GAs here seems like more of a gimmick, the same thing could have been achieved using conventional benchmarking.
Lastly, 10% or 20% improvements in compiler performance are of largely academic interest only these days most software's time is spent waiting on user input, disk IO, or network activity anyway?
There is more information on his webpage. It's not strictly true -- compilers have moving targets (different architectures and hardware optimisations over time, greater complexity in languages, etc etc), and for important things like scientific applications compilers can really optimise code; but in general R&D towards compiler development seems to be sorely lacking compared to other areas.
I work on IA64, which is fundamentally designed to take advantage of smarter compilers. While there are some interesting projects (ORC for example) nothing is really close to ready to take over gcc/intel compiler. We really want something that compiles once, can profile code execution and then recompile to optimise based on the execution profile; something along the lines of what this article talks about but built right into the compiler.
You could probably get equally good results with plain hill-climbing. Turn on all the optimizations. Then turn them off one at a time and see if things get better. Repeat until no improvement is observed.
It is known that some optimisations can disable others. For example, "merge frequently called functions with parent" will penalise "store frequently used variables in registers" or "give priority to inner-most loop variables in registers". You could certainly build on the research in this article. What are the best types of optimisations for different types of algorithm (B-tree traversal, matrix-vector mathematics, text-editing). Does compiling different modules of an application provide improved performance over compiling all modules with the same set of flags?
Neural networks are well-suited for tweaking the (possibly numerous) parameters of an established algorithm. It's good for finding good local maxima on n-parameter functions. Another technique for this is simulated annealing.
It's the cleverness of the algorithm that makes a computerised Go player good. Using a simple stinky algorithm and tweaking its parameters isn't going to turn a mediocre Go player program into a great one.
As always, you pick the solution that fits the problem.
If construction was anything like programming, an incorrectly fitted lock would bring down the entire building...
as make up the core of much custom scientific computing packages (or even libraries like the "Gnu Scientific Library")
Basically the jist is atlas "empirically" (read: use an optimizer for instance like GA, though empirical may actually mean brute force in this case) to optimize various parameters that will affect things like optimize the routine for the cache size of the processor etc. The cool thing about this, is they can get w/in 10% of hand machine coded BLAS/LAPACK libraries w/out the pain!
The "folks" you refer to is Professor Adrian Thompson of the University of Sussex. A paper describing his interesting experiment can be found here. It was actually a flawed FPGA chip he was programming.
Another example of this tendency of Genetic Algorithms to make use of helpful "flaws" in their environments can be found in the works of Karl Sims. A round-off error in his physics model resulted in some weird locomotion by a branch of virtual creatures.
You will find details of both examples in this entry on my Wetware blog.
I think this is actually what most two pass compilers will do. The intel compilers have this option for instance. Basically you compile w/ profiling on and on the second pass it using the runtime profiling data to recompile source to a new object code. (btw the intel compilers are "free" for opensource/nonprofit use). W/ regards to using GA/SA as part of the optimization it would be (to be honest) a bit weird to have a nondeterministic compiler since in different runs you may end up w/ different optimizations.
-bloo
Good, because that's not the original intent of the project. When he first contacted the GCC maintainers about the project which would later be called Acovea, the idea was to see which underlying -f/-m options shod be turned on by the -O? options by default. More and more projects using 3.2 and 3.3 were using "-Osomething -fno-something -msomething" so he took the 3.4 (in development) code to see what should additionally be turned on and what should be turned off instead.
While you can use it to tune for particular programs, and particular patterns of use, it will mostly be useful to GCC itself.
You cannot apply a technological solution to a sociological problem. (Edwards' Law)
union { char c[8]; double d; } u;
u.d = 1.0;
char c = u.c[1];
yields undefined results? The compiler is allowed (and under -O3, encouraged) to generate code that will erase your disk and impregnate your sister.)
Sorry, you're wrong, for two reasons:
- A char* can be used to point to anything.
- You can write to one member of a union and read from another.
Both of those are implementation-defined, not undefined. Undefined means the compiler can blow up your computer. Implementation-defined means that the compiler must do something consistent and documented.
If, however, you had writtenyou would have been correct.
Human/Ranger/Zangband
I'm a good friend of Nat's,and I talked with him a lot about GROPE when he was doing it (as an undergrad back in 1998 at MIT). I recall many nights of him ranting:
... :-)
/. story and could do something about it ...
... but no one can accuse me of name dropping.)
"So I'm actually sitting here writing a fucking toolchain."
He says he's gotten several requests for code, mailed said code, and nothing happened. (i'm a physicist, so perhaps my thinking this prjoject was cool was misguided. Anyway, it brought back pleasant (?) memories. No, I don't really know what toolchains are.)
I mentioned this thread to him this evening. He found it nice, but he's a bit busy with Ximian at the moment
For what its worth, I asked him if he'd put the code on nat.org, as at least one person is interested in it.
So, for once I read a
(yeah, posting AC is weak