Slashdot Mirror
Tuning The Kernel With A Genetic Algorithm
fsck! writes "Jake Moilanen provided a series of four patches against the 2.6.9 Linux kernel that introduce a simple genetic algorithm used for automatic tuning. The patches update the anticipatory IO scheduler and the zaphod CPU scheduler to both use the new in-kernel library, theoretically allowing them to automatically tune themselves for the best possible performance for any given workload. Jake says, 'using these patches, there are small gains (1-3%) in Unixbench & SpecJBB. I am hoping a scheduler guru will able to rework them to give higher gains.'"
You know, in the german translation of Terminator 2 Arnold talks about how his brain is made of "Neutrale Netze" or "neutral nets" re-translated.
It's pretty funny considering he is talking in his grave and totally serious robo-voice...
--
All extremists should be taken out and shot.
They might converge on a point of attraction that is not the highest possible.
Sure the only way is to exhaustively search the "chromosome" space for every possibile combination, and computers are good at brute force!
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
Could this be extended to include other kernel parameters as well? Depending on your app, things like TCP timeouts and other muck can have a large impact. Tuning this stuff is currently somewhat of a black art. Then as the user community of the app becomes familiar after rollout, a lot of the usage patterns change. In a few cases, this means we end up having to re-tune the kernel.
If this package could be extended to the other parameters, it would save my customers a *lot* of time and money.
If nothing else, this could be a deciding factor for some of our clients to use linux instead of windows.
That's where 'Simulated Annealing' comes in. It can often avoid local maxima that aren't optimal.
First thing: A GA is only truly effective if you let it exhaustively search the search space - which is why GAs are run against simulations rather than in operational systems. Imagine trying to tune a kernel at runtime by occassionally switching to random tuning parameters. I think this is extremely non-optimal. Of course, if most of the heavy lifting is done before-hand and the GA is simply examining pre-defined parameter sets on your machine, it could work. But it's not really much of a GA anymore.
As an alternative, perhaps using some form of pseduo-GA that tries to find pre-tuned parameters that most closely match your operating environment and then letting a Hill-Climbing algorithm hit it would be a better solution.
Hill climbing can also be used in a GA type manner by letting the GA determine witch parameters to climb and in what order. The climbing itself is pretty straightforward, allow vectors to interact with individual parameters. If the result is worse, reverse the vectors or switch to new parameters. Rinse, repeat.
Yes, GA can produce odd bugs and potholes. Yes, it is the fitness test that determines if that will be true. But a good GA will generally find solutions that are as good or better than hand tuning for search spaces that are very complex. Overall, this is a good idea but is probably more complex than advertised.
The reason that it can be true that 1+1 > 2 is that very peculiar nonzero value of the + operator
Would it be possible to apply a genetic algorithm on a packet scheduler? IMO the packet schedulers available today needs too much manual tweaking.
and also find good values of tunables for common workloads, eg: web server, database, misc server, desktop and put them as templates in /Documentation.
while performance gains of 1-3% in a well defined set of tasks (in this case the benchmarks) is a marginal improvement well inside statistical error...
this is a really interesting idea.
Moving the genetic algorithm processing to another machine may be warranted. If you had a good idea of what you were going to be doing (heavy database work for instance), a dedicated machine could be used to find an optimal scheduling solution and then that could be implemented on the production machine.
or maintain a list of optimal solutions on the production machine and change based on context.
This implementation might not be all that useful but I hope it spurs interest and a lot more development in the area.
The author did an awesome job coming up with the idea.
Genetic algorithms are pretty simple, compared to what the bulk of what the kernel is doing. Furthermore, the technology is a known quantity, and probably won't be running at run time. Given the existing size of the kernel (6 million lines), I don't think that it'll add a lot to complexity.
Wikileaks, no DNS
Just compiled this stuff on an old testbox, now running it for about 100 generations. At first it was feeling very slow, ok, it's a Pentium2 ;-) but it was much slower than running vanilla 2.6.9 or 2.6.10, for example.
...
...
But it is getting much better now, I don't know how much generations there will be needed to get things right. It feels pretty much the same as with the vanilla kernels, let's see where this leads
Anyone else with experiences? AFAIK this thingy can only be tweaked by editing the code and recompiling, there are a few hardcoded parameters
Genetic programming is a known quanitity, but if it "wont be running at run time" then its borderline useless. The whole idea is that the genetic algorithm adapts to a workload. Currently, scheduling is about fine tuning at the expense of flexibility. You tune the scheduler for a desktop setup, or for a database server, or whatever you have. Most tweaks yield a few percentage point gains in theory and maybe a single percent in practice for the given problem set, at the expense of about a ten percent penalty in the worst case scenario. Essentially, the genetic algorithm attempts to fine tune the kernel for you in ways.
Its not really that complex, but reasoning about how well it could perform is VERY difficult comparitively speaking. Furthermore, it introduces a much fuzzier notion of fine tuning. Rather than playing with variables like "swappiness" and cpu affinity, you're messing with a fitness function, where minute changes can move you from a percentage gained over a stock kernel to a percentage (or worse) loss. Certainly, I'm impressed that he's managed to make an improvement over stock with it, which puts interested kernel developers on a good first step. Nobody wants to chase technology that doesn't even show a hint of unlocking performance potential.
I Browse at +4 Flamebait
Open Source Sysadmin
How do you know the margin of error? I've seen systems/measurements where 50% difference is a statistical error, and systems where it needs to be less than 0.2% to be a statistical error.
Pragmatism and statistics are _not_ a good mix.
Note that, for example, many hosting providers host hundreds of web sites per system. Adding a couple of percent in performance then adds a couple of percent to the bottom line of the cost picture for those companies. The same is true for supercomputer clusters used by many companies and universities with hundreds of nodes.
Even though 1-2% sounds like 'next to nothing', but that's not how you should look at it. If you ignore 2% only five times, you've really already ignored 10.5%...
There is a dutch saying that, when translated in english is like this: "If you don't honour the small things, you're not worth the big ones".
--- Hindsight is 20/20, but walking backwards is not the answer.
I was not thinking about just desktop computers.
In general any software has initialization routines. My work has been in robotics, automation, and telecom switching equipment written in C and C++. We spent a lot of time worrying about efficiency, but not for startup routines unless the start lag became annoying. But for the most part people expect things to take a little time to start up. There are a lot of things to do, especially if you have no way of knowing how the thing shut down. I am digressing.
I think that a genetic algorithm to tune sounds like a great idea. I would just want a way to say check this code and not this other code.
I hope that there is much success with this GA.