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

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)

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

Re:Moderators on drugs?

[JFitzsimmons]

Have you??

Proof

Re:Innovation and open source

[AstroDrabb]

gPhoto is an image _viewer_ not an editor. In WinXP the default image viewer is "Windows Picture and Fax Viewer" and it doesn't allow you to copy an image from it and paste it into paint or photoShop, so it is no different than gPhoto. Have you ever tried to drag an image into Gimp? It works quit well.

Oh, and X supports many formats on the clipboard

One of the really cool, yet rarely used, features of the selection mechanism is that it can negotiate what data formats to use. It's not just about text. When one application asks another for the selection, part of their communication involves the requester asking the owner for the list of types in which they are capable of delivering the selection data; then the requester picks the format they like best, and asks for it that way.

As a simple example, suppose there is a program displaying text in multiple fonts. When pasting that into a text-only program, you'd want to paste only the text. But when pasting that into a word processor, you'd want to keep the font information: if both applications spoke HTML, they could use that as the intermediate format by which they transferred the data.

More complex things are possible, too: for example, when an image is selected on a web page, the web page displayer could offer to serve that up as raw image bits; or as JPEG data; or as the original URL of the image. When trying to copy and paste an image into a text editor that can't do images, the text editor might decide that the next best thing would be to paste the filename of the image, or the URL.