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.'"
A common criticism of Open Source is the accusation that it lacks innovation.
:-)
I mean, common. Just look at this. Amazing.
And even if it turns out to be not that good, it was still a good read
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.
So how much additional complexity is added for a 1-3% perfomance improvement? I'm all for more speed, but keeping thinks simple can often be more improtant when it comes to maintainablity and adding additional features.
And the knowledge that they fear is a weapon to be used against them...
If a parameter space is complex enough that you can use a genetic algorithm to tune it, the solutions it finds may have all sorts of unexpected potholes, bugs, etc.
In other words, non-competitive genetic algorithms are only as smart as the fitness function you give them. If your fitness criteria aren't smart enough to cover all the bases, your solutions will have unpredictable deficiencies.
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.
So will this means that if I install this kernel on my computer I will have baby Pentiums or baby Athlons soon?
1-2% gain is in the borders of statistical error. Definitely not worth the increased complexity of the solution.
http://tinyurl.com/6pkzc
"Daystrom felt that such an act was an offense against the laws of God and man, and the computer that carried his engrams also believed it."
--Kirk
Humor from a Genetically Molested Mind
Nice troll, but your sarcasm presents a common fallacy: that work on one issue (adding features like this) means that less work is being done on some other issue (cleaning up security problems). The fact is, throwing more people at a problem does not always make it better, especially if the people you throw at it don't know the subject (which the author of this algorithm may not, can't speak for him).
In other words: if you have someone who's good at writing Genetic Algorithms, but not so good at searching for kernel vulns, why devote that person to security? Why not let them write their contribution, and have the guys who are good at security do their part separately? Why should we only do one thing at once?
As mentioned previously on Slashdot, uselib() comes from Linux 0.13. It was kept for the a.out to ELF transition. Someone recently noticed it and said, "What is _that_ doing in my system?" This is new code that's being looked at by hundreds of developers. It's pretty hard to get root kernel exploits when it's like that. Plus, this code doesn't introduce any calls with user level priviliges. (Read: no exploit)
Bran muffins and whiskey.
That's where 'Simulated Annealing' comes in. It can often avoid local maxima that aren't optimal.
Did SCO allow him to modify their kernel?
We suffer more in our imagination than in reality. - Seneca
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
Go grab the patches. They're commited into the BK repositories already. Sheesh.
:p
Patches for 2.4 can be found in this changeset.
Patches for 2.6 can be found in this changeset.
Click on the little "diff -Nur style" link for a an actual usable patch.
In the course of a few hours, you have the fixes already. Yay for open source.
Btw, nice troll
"Backups are for wimps. Real men upload their data to an FTP site and have everyone else mirror it." -- Linus Torvalds
Would it be possible to apply a genetic algorithm on a packet scheduler? IMO the packet schedulers available today needs too much manual tweaking.
It's pretty funny considering he is talking in his grave and totally serious robo-voice...
You mean there is another voice?
Life is just nature's way of keeping meat fresh.
The main problem with this or any other adaptive tuning mechanism is actually acquiring performance metrics.
What is the system using to decide if a new parameter set is better than a previous? What is the fitness test?
Some applications are disk-bound, others are CPU-bound, others are network bound. The performance dance is often non-obvious (e.g. some applications will achieve generally higher performance by allowing I/O higher priority than context switching, while others that appear to perform in a similar manner will achive higher performance by reversing that order).
The kernel does not have any mechanism to determine if a particular application is performing better or worse, it can only really get a guage of throughput and load. While this MAY be enough to get small systemwide performance gains, in order to really acheive significant application-specific performance gains, I think that applications would need to explicitly add support for adaptive tuning by logging relevant performance metrics for the kernel to tune around.
Thoughts?
The reason that it can be true that 1+1 > 2 is that very peculiar nonzero value of the + operator
Does this means Linux will be effected by genetical diseases sooner or later?
In reality, the basic GA framework is "just" another efficient search algorithm, no cooler or more complex than, say, a hash table or a binary search tree; at its simplest, a GA is a way to find an optimal configuration of components without looking at all possible (potentially explosively exponential) combinations; instead, you look at just some permutations, and as you iterate through generations, applying breeding and mutation, you arrive at a generation which is statistically close to optimal.
GAs are also in no way new or unproven technology; a nice example of mainstream use is PostgreSQL's query planner, which uses GAs to optimize query plans.
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.
Obviously any tuning must involve data collection on what is going on in a process. This means that some kind of logging must go on in the software.
Anyone who has ever created a logging interface understands that a log will slow down a system.
And so, even if one were to run the GA and have it show things, it will still mean that later that GA should be removed or swithced off. Otherwise the workings of the GA and its requisite log will slow down the system.
So, use a GA,and then intellegently remove it after you decide what it has shown how it will actually increase performance.
It is very common to do one build with logging enabled, and another that does not have logging at all. And then you link in both. At the whim of the engineers (because this is usually done in real-time systems that are designed by degreed engineers) the one can be turned on.
or you can design a system with lists of modules that each have two versions, a logging one and a non-logging one. Then you use a function pointer based calling method and switch the modules between logging and non-logging at your whim.
When you say things like Wont work you shut yourself off from possibly useful tools. Naturally you will need an intellegent person to oversee the use of this tool of Genetic Algorithms. You could be that person.
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
Have you??
Proof
Beware he who would deny you access to information, for in his heart he dreams himself your master. -Anonymous
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.