login
Search
Jake Moilanen provided a series of four patches against the 2.6.9 Linux kernel [story] that introduce a simple genetic algorithm used for automatic tuning. The patches update the anticipatory IO scheduler [story] and the zaphod CPU scheduler [story] 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."
Genetic algorithms as used in machine learning are modeled after the process of evolution as observed in nature, and are a field within the science of artificial intelligence. The idea is to generate a "population" defined with unique strings of "chromosomes", to test each of these chromosome strings for "fitness", to select a subset of the chromosome strings with the best fitness and use them to create new chromosomes, to apply random mutation to a small subset, and finally to start the process all over again. Over time, all the chromosomes should "evolve" toward having the best possible fitness, as defined by the algorithm.
In Jake's patch, the chromosome strings are possible tunings for Linux kernel internals, and fitness is measured in overall performance. Essentially, a large pool of possible tunings are selected (referred to above as chromosome strings). Each of these possible tunings is tested under the current workload, measured for best performance (referred to above as fitness). 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. Finally, random mutation is applied to slightly modify some of the tunings. Jake explains, "over time the tunables should converge toward the optimal settings for that workload. If the workload changes, the tunables should converge to the new optimal settings (this is part of the reason for mutation)."
From: Jake Moilanen [email blocked] To: linux-kernel Subject: [ANNOUNCE 0/4][RFC] Genetic Algorithm Library Date: Thu, 6 Jan 2005 10:08:44 -0600 I'm pleased to announce a new in-kernel library to do kernel tuning using a genetic algorithm. This library provides hooks for kernel components to take advantage of a genetic algorithm. There are patches to hook the different schedulers included. The basic flow of the genetic algorithm is as follows: 1.) Start w/ a broad list of initial tunable values (each set of tunables is called a child) 2.) Let each child run for a timeslice. 3.) Once the timeslice is up, calculate the fitness of the child (how well performed). 4.) Run the next child in the list. 5.) Once all the children have run, compare the fitnesses of each child and throw away the bottom-half performers. 6.) Create new children to take the place of the bottom-half performers using the tunables from the top-half performers. 7.) Mutate a set number of children to keep variance. 8.) Goto step 2. Over time the tunables should converge toward the optimal settings for that workload. If the workload changes, the tunables should converge to the new optimal settings (this is part of the reason for mutation). This algorithm is used extensively in AI. 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. The main area that could use reworking is the fitness calculation. The problem is that the kernel is looking more at the micro of what's going on, instead of the macro. I am thinking of moving the fitness calculation to outside the kernel. However, I would advocate keeping the number of layers needed to communicate between the genetic library and the hooked component down in order to keep it as lightweight as possible. The patches are based on 2.6.9 and still a little rough, but here is the descriptions: [1/4 genetic-lib]: This is the base patch for the genetic algorithm. It's based against 2.6.9. [2/4 genetic-io-sched]: The base patch for the IO schedulers to use the genetic library. [3/4 genetic-as-sched]: A genetic-lib hooked anticipatory IO scheduler. [4/4 genetic-zaphod-cpu-sched]: A hooked zaphod CPU scheduler. Depends on the zaphod-v6 patch. Please send comments, Jake Moilanen
From: Jake Moilanen [email blocked] Subject: [ANNOUNCE 1/4][RFC] Genetic Algorithm Library Date: Thu, 6 Jan 2005 10:14:47 -0600 Here is the base patch for the genetic-library. It includes generic routines for modifying and manipulating genes of children. If a specific routine is needed, that can be used instead. Signed-off-by: Jake Moilanen [email blocked] --- [patch]
From: Jake Moilanen [email blocked] Subject: [ANNOUNCE 2/4][RFC] Genetic Algorithm Library Date: Thu, 6 Jan 2005 10:18:38 -0600 This is the base patch for the io-schedulers. It contains the fitness routine, disk_calc_fitness(), that could use a rework. Signed-off-by: Jake Moilanen [email blocked] --- [patch]
From: Jake Moilanen [email blocked] Subject: [ANNOUNCE 3/4][RFC] Genetic Algorithm Library Date: Thu, 6 Jan 2005 10:22:49 -0600 This is the hooked anticipatory IO scheduler. Here is an example of the hooked scheduler. It should optimally tweak the tunables for the current workload. If nothing else, hopefully the genetic-lib will help scheduler writers find the optimal tunable settings. Signed-off-by: Jake Moilanen [email blocked] --- [patch]
From: Jake Moilanen [email blocked] Subject: [ANNOUNCE 4/4][RFC] Genetic Algorithm Library Date: Thu, 6 Jan 2005 10:27:42 -0600 The hooked zaphod CPU scheduler patch. It depends on the zaphod-v6 patch. The ranges for the tunables could be tweaked better. Signed-off-by: Jake Moilanen [email blocked] --- [patch]
| Attachment | Size |
|---|---|
| genetic-lib.patch | 18.17 KB |
| genetic-io-sched.patch | 4.11 KB |
| genetic-as-sched.patch | 6.25 KB |
| genetic-zaphod-cpu-sched.patch | 10.57 KB |
I like the idea of autonomic
I like the idea of autonomic computing for a long time, obviously, the GA is one implementation. But another question reminds me, Linux always keep the scheduler so easy according to its so-called philosophy. So i think it is not fitful introducting some machine-learning related algorithm into the scheduler which is core of OS.
In my opinion, loadable scheduler is the next generation of Linux scheduler for varied workload.
Woah
That's is friggin _awesome_....good work Jake! ^_^
Cool!
This is the most interesting feature for the kernel I have read about. I don't care if it doesn't give any performance bost or not, it's cool and it's a must have.
re: Cool!
..let me guess: you must run Gentoo (see http://funroll-loops.org)
I can see why you would come
I can see why you would come to this conclusion - I would too. To take a feature which is intended only to improve performance and do nothing else, and say you want it whether it improves it or not, is just damn idiotic. What for some complex reason, it just doesn't work at all? Then what? Still want it? Ingenious.
So you're implying that Gento
So you're implying that Gentoo Linux "doesn't work at all"?
I don't see the correlation.
Let me guess, you've never ru
Let me guess, you've never run Gentoo (see http://www.gentoo.org)
Dear proprietary OS developers...
Open Source and Free Software never innovate, huh? ;-)
Whoa..
just the simplest solution, the right thing an os should do.
I'm just concerned about benchmark reliability, yes, unixbench test performance for different workloads, but how often it does? and for how much time it runs the benchmark?
... and giving hthreading, can it be run the genetic algorithm work while in a system call optimizing cpu usage and reducing overhead?
This may be of interest as well, though it is mostly a skeleton
http://magicgardenlabs.com/magicgarden
http://magicgardenlabs.com/magicgarden/src/greenparrot
excellent idea - needs support
I think this is a great idea. However, I do have one suggestion. Instead of writing your own fitness routine, the scheduler should provide you with it's own metrics. Let the scheduler report it's metrics to the algorithm instead of vice versa. That way, should someone want to try a different approach than GA they can write a program to do that fairly easily. And you have the added benefit of a higher quality (maintained) performance metric.
Overhead of genetic diversity?
The thing I wonder is: what overhead is caused by running all the mutant algorithms all the time in the scheduler? Lets say that the algorithm has run for a while and has come up with a great set of tunings for the current workset as the best of all the tried "chromosome" sets. This (currently) most-optimal tuning is only one of the many tune-sets that are being actively used in the running system (otherwise the algorithm wouldn't be able to adapt). How much of the time (percentage wise) is spent running the mutated tunings? The more mutations that are tested, the more the system runs with less-optimal tunings (since most of the mutations will produce a less optimal tuning than the current best-of-breed tuning). The fewer mutations it tests, the more slowly it adapts to changes in worksets.
It would be interesting to see a measurement of the genetic overhead as follows:
Program the algorithm to not only determine the current best-of-breed tunings, but to cache off the tuning that did the best for the longest amount of time. Run a benchmark both under the normal geneticly-enhanced scheduler and then lock the tunings down to the best-of-the-best and run it again. Does the performance go up or down? Switch benchmarks and repeat. The interesting thing to determine is if the X% of inefficency in the genetic algorthm's trials is better than that Y% of inefficency in a static tuning.
Also, could the algorithm be modifed to remember several known-to-be-good "organisms" that it can use as "punctuated evolution" to respond to changes in worksets? I.e., if it has a cache of tunings that did very well over extended periods of time, it could pop each one of these creatures into the trial set at various intervals and let the fitness algorithm decide if one of these alternate tunings was better than the current slowly-mutating set for the active workset. This might make a system that switches between several common worksets adapt to the changes more quickly.
I think you are right on targ
I think you are right on target with your suggestions.
I can understand concerns about using something like this in a realtime environment. There is potential to reduce performance especially in time-sensitive applications.
But, as with most statistical arguments, the "randomness" confuses. If the patch is producing an improvement in performance, then clearly it is making up for it's own performance penalties (in the mean). This makes it better as an average policy, and points out that there are non-random factors that can be leveraged into performance gains.
Perhaps a scheduler will ultimately realize these gains, and make the search unwarranted (thus no performance increase). But until that time, I can see that this tool can improve identification of the outstanding non-random factors.
So unless you have some specific factor requiring you to be anal about this, I don't see what the fuss is. This is a clever and useful development. Some might call that a good hack!
Cheers!
Possible incorrect assumption
If the patch is producing an improvement in performance, then clearly it is making up for it's own performance penalties (in the mean).
Not necessarily. It might just mean that it found a better static tuning that could be used without having the genetic algorithm active, in which case the performance would go up even further if that tuning were hard-wired in and the genetic algorithm turned off. However, we can't know which of the two possibilities is true without running the experiment I suggested.
Overhead of genetic diversity?
GA and statistical classifier (with a bit of hand waving)
One issue raised by earlier posters is that a GA would have difficulty tracking constantly changing user workloads (surf the web aimlessly 10 minutes, take a break, run my nuclear reactor simulator, etc). The GA could run continuously, but that might result in lags while the tunables converge on something appropriate for the moment. Perhaps this approach could be combined with a simple statistical classifier that could identify workloads, initially with something simple for features (application names, number of processes, do the apps use Gtk, Qt or wx, do they use libssl, etc). With some training the classifier could identify 3 or 4 regions in the feature space (I'm guessing most desktop users wouldn't need more) and the GA would work to come up with tunables for only those workloads.
Genetic Algorithms and SMP
Several of you mention realtime tasks. I just wanted to point out that multi-core procs are coming on the desktop and have already arrived in both the embedded spaces and the highend platforms. What I was thinking was maybe both the procs use different schedulers; 1 does anything that you might think of as "hard real-time (which tend not to exist for normal workloads)" or "soft real-time (which is much more common, e.g. MPEG2 software decoding (which is also becoming rarer - the VIAs for instance include it with their IGP northbridge) or sound card positional rendering (which is done in hardware by high end consumer models)" and the normal stuff where you might tolerate a 20 ms delay while it comes back up to speed. The real reason why this sort of thing would be interesting is for embedded stuff, though, where running DSP algos can be hard real-time (ADSL) (winmodems - which are also becoming rarer thanks to ADSL).
Hope this rant was interesting,
Michael
Evolution Review
I am new to posting here. I would like to address genetic algorithm from Macro-View. I am observer of things, not a kernel hacker.
This is not an attack/flaim. Other commenters kindly observe.
In Science, we have "base facts/assumptions" about what we are talking so that others can have a reference from there to judge. Hypothesis come from such foundations. Some are logically proven, some are empirically proven, and many more believes/theories that seem agreeable but not totally accepted.
Genetic algorithms grow out of evolution domain, therefore they MUST-NOT deviate extremely from their root, else all the foundation they rely on will be in question including the algorithms themselves.
From Macro-view, Human presently is the dominant life form on Earth. It follows that evolution has given us the right-kind of characteristics, for now. But human is NOT the FASTEST, BIGGEST, STRONGEST, LONGEST LIVING (+ misc) life forms on earth. There are many more living things excel in other ways compared to human being. Nevertheless, at present, human still ranks high on the food chain.
Applied the nature observation/pattern matching back to the current discussion, the nature already shows us all the answer, isn't it?
We are NOT the BEST in many categories, WHAT keeps us high in the current hierachy?
Humans are NOT the dominant l
Humans are NOT the dominant life form on our planet. That honor goes (if you're counting by sheer numbers, which are good indicators of species prosperity) to the insect family. There are (Iirc) more than 50000 insects on earth for every 1 human being.
Humbling, isn't it.
I cannot see big ovation amon
I cannot see big ovation amongst hackers on LKML. Why? This is a bad idea? Or poorly implemented? Or what?
again, not a flaim, When y
again, not a flaim,
When you apply genetic/evolutionary ideas/practices into other domain, ALL the underlining things/characteristics from the evolution domain will be carried along.
Have you ever seen, on a major scale, all living creatures agreeing with each other on what is best for nature? or themselves? that some will volunteer to be at the bottom of the food chain, or some that don't have easy way to deal with their natural enemies, and therefore choose to multiply quickly to increase their odds, and many many more combinations/mutations etc,
That's just the way it is. no special reason needed, except evolution to the next level that will encourage continour species survival. Sometimes they reached an equibilium where they sort of keeping the right balance, so it is tolerable for majority. Until the next big thing hits...
Now applies all the description to the discussion of genetic algorithm in kernel, proposal, replies, stakes and many more....
Genetic Algos
Be aware that there are three steps in genetic algos: mutate, evaluate and select. These are run through iterations. We are only looking at *one* species and *we* determine its fitness. This is very different to natural selection where you are looking at multiple ecological pressures to reach equilibrium - the criteria keep changing. Our criteria keep changing too, but the evaluation of fitness is different from that in nature - survival (do you breed enough, etc.) vs. simply do you get the best results (latency of key processes is alright (-1->1 or something) and performance (-1->1).
See a textbook for more details.
HTH,
Michael
I understand your points. I
I understand your points. I think I need to give clearer views and example because I am seeing it from very different angle. This is very long reply I hope it is sensible reading :)
1. I am looking at the whole thing from macro-view, philosophical, and biological aspects.
2. Take human as example, we develop over millions of years into current form (according to evolutional theories)
3. We definately look different from our supposed ancestors.
4. We know life forms evolve, but we do not know exactly how it really function. Example, our ancestor did not wake up one day, look in the water reflection, think big teeths are biologically not suitable anymore, and magically produce next generation with smaller white teeths :-) (maybe sometime miracle happens you get what you wish for:) (that's what the current genetic engineering wanted to do, altering stuff at will, it's another story)
5. We know these genetic understanding is also extremely critical for artificial intelligence because one of ultimate achievement is to create (Inteligent life form that can rival human) (Inteligency defined wrt human being) and genetic field is one of the inter-relating fields. You must understand human critically so that one day you can create AI Lifeform in its image. Ok's that's my view. I know the deepest religious debate so I will close it here.
6. We know artificial inteligence is nowhere close to critical understanding of life for now.
7. We also know genetic engineering is nowhere close to critical understanding of life forms for now.
So how does everything tied together?
--> this is observation, not for or against the idea.
A. Genetic codes come from a domain where we know its understanding is still very much in its early stage.
B. Nobody is able to tell you this species will mutate in this way tomorrow, that another species will grow bigger, that another one will develop toxic as new defence, etc based on thier current knowledge.
C. We do know all life forms will try something new if needed. Some will succeed, some will fail and go extinct.
D. If you come from this background, knowing things in your domain is still in full flux (I supposed for long-time, or forever?), anything you apply to other domain will carry the same signatures of your own domain. (Eastern views, everything is inter-related, there's no such thing as narrow field selective application, cause and effect, one thing leads to another, medical examples)
E. So if the genetic kernel patch author strongly believe in the stuff, he and agreeing team will just go ahead and start operation, just like the natural world, mutation and natural selection kicks in. life form do not need permission from others to evolve, mutate and the rest. They also sometimes evolve capabilities that are not easily understood until much later time. This includes integrating good stuffs (multiple scheduling components) discarding stuffs that failed the evolutionality test, while adding its own.
F. Like natural world, if you initiate an evolutional action, your will get an evolutional response. If the preys evolves longer legs to runs faster, Cheetah will have to evolve to sprint quicker, as a result its sustain pursue range will be shorter. At one stage, Cheetah will decide its not worth the extra effort to develop much faster speed. Currently we do not know how that decision is made.
G. Unlike the currently trial and error stuff in biological engineering fields, Computer Science tries to be logical-based (Math-based). Example, Your hear kernel people arguing about O(1) to O(N) algorithms.
H. To borrow rough analogy from movie, creator want to give soul to an always logical Robot with capability of emotion, unpredictability.
I. Existing kernel people have their points. Example, you do not want your body part to evolve out of control on its own without apparent benefits for the entire host to continue survival. In medical term, is called cancerous growth.
J. See point B again. Since none can give concrete answer, you can only implement Gene codes and trial (If someone can give deterministic answer, I trust their time will be better spent on solving the real biological science challenges rather than testing kernel.)
K. If that stuff really doesn't make sense, it will go extinct. Else see point F.
Misunderstanding of "Genetic Algorithms"
Genetic algorithms tune a limited set of tunables - that's *all*. It doesn't come up with new scheduling algos or anything like that. Google is your friend - "Genetic Algorithms".
Cheers
Lack of understanding
I know this is an old list, but I just had to say this.
I'm afraid your arguments show a complete lack of understanding about what genetic algorithms are. GA writers are _not_ simulating biological relationships such as predator/prey interactions. They are _not_ simulating complex biology or thought. They are _not_ producing scary evil beings residing in your computer that could mutate into viruses and take over the world. It looks like you've been watching too many movies.
A genetic algorithm is a simple means of creating a computer _equivalent_ of evolutionary optimisation. This is nothing to do with dominance between completely different forms. You should not be thinking of species interactions as an analogy here. Think more along the lines of this, but don't take it too literally:
Picture that each form of an algorithm is like a member of a strange species of ant. Some ants are big and slow but can carry heavy weights. Some ants are small and fast but can't carry much. Each ant represents a tradeoff between speed and carrying capacity. They have one task: carrying food. If the food comes in the form of big grains, the big ants are best suited to the task. If the food comes in the form of small grains, the small ants are best suited to the task. If there were just one grain size, a single size of ant would be best at performing the task. However, this one form cannot effectively cope with _all_ food sizes so it doesn't perform so well if the food size is too different from that which it can best cope with.
GAs are effectively where you say that you aren't going to have one solution. You are going to create variation where some forms of the algorithm (ants) lean more to one side of the tradeoff while others lean towards the other. Successful algorithms in the current situation are perpetuated while others are removed. This means that if I have a situation where "big food" is present, "big ants" will perform better, the population becomes dominated by these "big ants" and overall the population becomes more successful. If I change the work type to "small food", then "small ants" become more successful and the population 'evolves' a smaller size, changing to manage that form of work more effectively.
Don't take this too literally, but in this case the ant size simply _represents_ a tunable factor of our algorithm. Food size _represents_ a property of the work that the algorithm must do. Unless this property is always constant, the optimum for the tunable factor may change from moment to moment. GAs are a method of using _simulated_ evolution to optimise an algorithm for the current situation at any given time.
I hope this is clear enough, I'm afraid I'm a biologist, not a serious programmer. I have played with evolutionary computing though and suggest that you should read a textbook before drawing conclusions about things you don't understand. A genetic algorithm is really just a method of altering a variable to better suit your situation, not a simulation of life. Remember where to draw the line between metaphor and reality.
GA for scheduler tuning
Very interesting, but the discussion, I think, goes the
wrong way. GA as a kind of replacement for a regular
scheduler should be highly ineffective.
The better idea is to make GA to 'invent' the optimal
set of rules and of their ordering for optimal scheduler.
If such a task could be solved by some deterministic method,
then it should be solved just this way - once and for all.
That is to produce the best scheduler we can afford
(in a SINGLE, well defined sense, for example to maximize
the expected thoroughput; remember 'fitness' is just
a scalar, single real number).
Well, this may be achieved equaly well with GA's, but there
is almost no sense to force the kernel to do it continuosly.
The better set of rules, or their better ordering (precedence)
may be found quickly or only after one month - I'm not
joking. The better set is a good reason to release a new
version of the scheduler.
The nature of GA's is such, that the biggest gains are found
quickly, but the successive improvments come less and less
often, if ever. 1-3% gain at the beginning suggests strongly,
that we are trying to optimize something what is already
almost perfect.
The rule saying, that there are no invariable rules - is
fine, but the rule, that there are no rules at all (all
is solved ad hoc) - only brings chaos.
Actually I agree with most of
Actually I agree with most of the posted comments, it is just that I am trying to look at much broader scope, you can say it is academic, and yes sorry I am actually offtopic quite a bit.
1. Current topic is "How GA will specifically help enhance kernel" The impact is short-term visible.
2. I am drifting toward thinking "How the ACT of applying biological/evolutional ideas/practices in the natural world will help kernel" The impact is likely gradual and long-term.
Example : We teach human to learn piece by piece. We do not know how the brain actually store and apply the info/knowlegde in zillions ways. But we DO know some of them creatively process those info and integrate randomness to generate new useful ideas (that was NOT taught to them)
If we have such a hybrid-bio-chemical-electrical-kernel evolving (it is going to take very very long time, I cannot estimate), we may one day initiate AI to next level. A self learning autonomous kernel that not only deal with scheduling (just like a human being making decision based on his/her available free time, but also consider resources, other people, communications, driving car(in this case, how the bio-kernel transport info/goods to remote user, example) and many many more, just like a real human. And this hybrid-kernel will continue to evolve carrying with it all the knowledge of its inventors, the many kernel hackers that once coded its core. It may even invent things that its creators never imagine.
I am probably in the wrong forum. :)
rjBHZPpAin
DV9vBk moxkttndenhi, [url=http://jinsrhkquhic.com/]jinsrhkquhic[/url], [link=http://soyzsefomchd.com/]soyzsefomchd[/link], http://yqtvrfylwrbr.com/