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.'"

Comments

Innovation and open source

[Anonymous Coward]

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 :-)

Re:Innovation and open source

[ColaMan]

Sooo...... can I copy and paste an image from gPhoto into The Gimp yet? No? Call me when you guys manage to do what windows 3.0 could.

Complexity?

[BurntNickel]

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.

Re:Complexity?

[grammar fascist]

Understanding (basic of) GAs is easy and so is implementation.

I'm a machine learning researcher, and I'll second this. Also, the code for it will be quite self-contained (if done right), and shouldn't affect any parts of the kernel except where it's called to run an iteration.

They also work quite well. That's why they are so popular.

Sure they do. For a lot of problems, though, they're not so hot compared to other optimization methods like hill climbing and empirical gradient descent - they tend to run slowly - and I would like to ask Mr. Moilanen why he didn't use one. GAs are especially good with nominal parameters (discrete, unordered). But I would expect tuning parameters to be either discrete or continuous.

GAs are theoretically capable of finding global optima, except that's kind of a red herring. The only reason you can prove that is that, theoretically, no matter how small the probability, you'll eventually get exactly the right sequence of mutations to produce a global optimum. In practice, they tend to produce local optima like most other optimization algorithms - especially as Moilanen describes it:

All of the tunings are then ordered from best performance to worst, and the worst half of the performers are replaced with new possible tunings derived from the best half of the performers.

You generally have to be a little less selective (more random) than this.

good luck with that

[Illserve]

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.

Other kernel parameters?

[Feint]

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.

Re:Dear Kernel Coders

[kneeless]

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)

GA + Hill Climbing...

[Corpus_Callosum]

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.

Re:GA + Hill Climbing...

[Illserve]

First thing: A GA is only truly effective if you let it exhaustively search the search space

If you have the resources to exhastively search the space... you don't need a GA.

A GA is generally used when the search space is hopelessly huge and you need to chart a course from A to(wards) B but you don't know the way.

And in finding this solution, which is "grown", not engineered, it's much easier for unintended wierdnesses to creep in. A GA might solve problem X by ruining performance on problem Y, something that you, as a software engineer, would never even consider viable, and hence you forgot to force the fitness function to check problem Y along with problem X.

Re:Dear Kernel Coders

[Xpilot]

Go grab the patches. They're commited into the BK repositories already. Sheesh.

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 :p

Re:Not worth it...

[Corfe]

It's a unique idea - what's wrong with running it for a while with your typical load (say, for a fileserver), finding some better-than-average parameters for the kernel, then running an unpatched kernel with those parameters manually entered?

What is "on the borders of statistical error" depends on how many times the test was run, and how much variation there had been in his results before. I think it's pretty safe to assume that if he knows how to implement a genetic algorithm into the linux kernel, he knows how to handle statistics properly.

Genetic packet scheduler

[City Jim 3000]

Would it be possible to apply a genetic algorithm on a packet scheduler? IMO the packet schedulers available today needs too much manual tweaking.

Re:Futurology

[wertarbyte]

It's pretty funny considering he is talking in his grave and totally serious robo-voice...

You mean there is another voice?

The problem: Determining Performance

[Corpus_Callosum]

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?

GAs aren't rocket science

[Earlybird]

Because most people aren't intimately familiar with genetic algorithms, and because GAs are associated with machine learning/artificial intelligence, GAs are seen as somewhat mysterious and magical, and are therefore either accepted with "whoa, cool!" or rejected with "whoa, complex!" While GAs are indeed novel compared to many long-established algorithms, both mentalities are overreactions.

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.