Use of AI for process scheduling

Use of AI for process scheduling

[Timothy Miller]

I just got back from vacation and have 3278 list messages to sift
through.  (Yay.)  I wouldn't be surprised, therefore, if others were
already discussing this, but I've been thinking of some ideas over the
past week that we may be helpful for the advancement of intelligent
process scheduling.

To begin with, let's consider the parts of an intelligent system:

1) Inputs (ie. properties and behaviors of processes)
2) Heuristics
3) Outputs (ie. dynamic priorities, etc.)

Up to this point, the interactive scheduler has been designed in a very
expert-system-like manner.  Human experts observe behaviors and define
heuristics.  Ultimately, we do want a solid set of heuristics that are
coded in C, and that's what the current development process has been
working directly toward.

The progress has been slow, and there have been a lot of false starts
and tangents which have been discarded.  This is all how development
works, and it's important to explore all possibilities.  But what I
would like to propose is that we work on a way to accelerate that
process, and that is to make use of machine learning.  We move from
expert systems to artificial intelligence, because the heuristics are
determined by the machine and are therefore dynamic.

Basically, we need to write and install into the kernel an AI engine
which uses user feedback about the "feel" of the system to adjust
heuristics dynamically.  For instance, if the user sees that the system
is misbehaving, they can pause the system in the kernel debugger,
examine process priorities, and indicate what "outputs" from the AI
engine are wrong.  It then learns from that.  Heuristics can be tweaked
until things run as desired.  At that point, scheduler developers trade
emails in the AI heuristic language.

Obviously, this AI engine will be slow and add a huge amount of
processing overhead.  The idea is to determine what the heuristics are,
and then to release a kernel, recode the heuristics in C.

We have a number of options for what kinds of AI engines we use.  A 
neural net is something that's relatively easy to train, but beyond a 
certain level of complexity, it's impossible to make much sense out of 
the weights.  Genetic algorithms are probably out of the question.

The ideal situation would be to have a rule processor that uses a script 
language of sorts (lots of if-thens with some math, etc.) to compute on 
inputs and produce directives to the scheduler (dynamic priorities, but 
perhaps more) -- but what would produce the script?  How do you turn 
user feedback automatically into better rules?  But at the very least, 
it could speed up development by making scheduler behavior dynamically 
programmable.  If a priority inversion occurs and you stop the kernel to 
examine it, the AI engine could report to you what combination of rules 
were used to cause that condition.  You then dynamically change the 
rules and observe the effects.

I have huge gaps in my knowledge of AI, so I'm hoping some LKML members 
who are experts on this will engage in this discussion.

I think use of AI could be applied to the development of MANY parts of 
the kernel.  Obviously, the I/O scheduler could benefit.  But what about 
intelligently dealing with failure conditions?

Maybe AI could be useful in a running kernel, at least as an observer. 
I read an article about self-correcting systems in space craft.  There 
is the logic of the system, and then there is an AI model of it.  When 
some component fails to operate properly or the system behaves in an 
unexpected manner, the "model" finds a way to work around the problem. 
This kind of redundancy in a kernel being debugged could be invaluable. 
  In a deployment kernel, it could exist at a reduced level of 
sophistocation.

Another freaky idea is that large parts of the kernel could be rewritten 
in the heuristic language and interpreted during debugging and then 
compiled for release.

Also, some logic which is not computationally intensive could be always 
interpreted because the size of the interpretor plus the size of the 
pcode would be smaller than the size of the object code for the compiled 
version.  This would not be for performance-critical logic in a deployed 
system.

Ok, I know I'm going too far.  Right now, the best application would be 
the process scheduler, but we should start thinking about ways of making 
the system "self aware" and "self correcting" so that when the model 
observes the logic to misbehave, detailed information can be produced 
for debugging purposes.

Naturally, I am interested in contributing to this, but some of what I 
will have to learn to participate will come out of ensuing discussions. 
  I have a lot to learn, but I think if these ideas are valuable, others 
who already know enough will start to do something with them.

Re: Use of AI for process scheduling

[Jeff Sipek]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I think that this makes sense. It would definitely help with designing the 
perfect scheduler. One thing tho, I wouldn't use kgdb or any other debugger, 
instead I would say that /proc or /sys interface would make more sense. 
Simply copy the weights somewhere else, dissect them, and then act 
accordingly.

Jeff.

- -- 
A computer without Microsoft is like chocolate cake without mustard.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQE/XPrCwFP0+seVj/4RAvopAJ0VvG9Z+nxl6Tr+0Ry9pgHXBPmOXgCffalk
wJujLlpHTWGzehMRKmcBw9s=
=awXk
-----END PGP SIGNATURE-----

Re: Use of AI for process scheduling

[Timothy Miller]

Jeff Sipek wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> I think that this makes sense. It would definitely help with designing the 
> perfect scheduler. One thing tho, I wouldn't use kgdb or any other debugger, 
> instead I would say that /proc or /sys interface would make more sense. 
> Simply copy the weights somewhere else, dissect them, and then act 
> accordingly.
> 
> Jeff.


Well, we have this to deal with:  Someone is exercising the scheduler 
and notices some kind of misscheduling which causes the system to crawl.

How are they going to get to the /proc and /sys directories to do much 
of anything?  The system is completely unresponsive.  Furthermore, even 
if the system IS responsive, we need some way to for the user to hit a 
key and freeze the current state for examination.  Some slow-downs last 
only seconds, but we need to be able to catch them.


You talk about weights.  Would the linux community be willing to put a 
neural net into the kernel?  I'm sure we could optimize it to not take a 
lot of processing overhead, but it's an "unknown".  It would be scary to 
some people to be unable to disect the actual workings of it and have no 
way of determining corner-case behavior from examining code.  But if we 
have, say, only a 2-layer neural net, we might still be able to 
reverse-engineer it.


One thing I was thinking of is that if there is some information about a 
process which is inconvenient to get normally but could be accessed by a 
kernel or user-space thread, then this process could feed back info to 
the scheduler AI for it to do automatic tuning.  Some information that 
the scheduler doesn't have direct (or efficient) access to could be 
inferred from information it DOES have access to, and that would be 
learned through adjustment of weights via backpropogation.

Re: Use of AI for process scheduling

[Felipe Alfaro Solana]

On Mon, 2003-09-08 at 21:28, Timothy Miller wrote:

> Basically, we need to write and install into the kernel an AI engine
> which uses user feedback about the "feel" of the system to adjust
> heuristics dynamically.  For instance, if the user sees that the system
> is misbehaving, they can pause the system in the kernel debugger,
> examine process priorities, and indicate what "outputs" from the AI
> engine are wrong.  It then learns from that.  Heuristics can be tweaked
> until things run as desired.  At that point, scheduler developers trade
> emails in the AI heuristic language.

I'm no kernel expert but I think that doing what you suggest would take
an enormous amount of time and resources to do. Also, the scheduler must
be a real-time piece of software, and needs to take decisions as fast
and as accurately as possible. I think that implementing an IA-like
engine would take an great deal of resources. By the time the IA-like
scheduler has taken its decision, the whole world could have changed
since.

Re: Use of AI for process scheduling

[Timothy Miller]

Felipe Alfaro Solana wrote:
> On Mon, 2003-09-08 at 21:28, Timothy Miller wrote:
> 
> 
>>Basically, we need to write and install into the kernel an AI engine
>>which uses user feedback about the "feel" of the system to adjust
>>heuristics dynamically.  For instance, if the user sees that the system
>>is misbehaving, they can pause the system in the kernel debugger,
>>examine process priorities, and indicate what "outputs" from the AI
>>engine are wrong.  It then learns from that.  Heuristics can be tweaked
>>until things run as desired.  At that point, scheduler developers trade
>>emails in the AI heuristic language.
> 
> 
> I'm no kernel expert but I think that doing what you suggest would take
> an enormous amount of time and resources to do. Also, the scheduler must
> be a real-time piece of software, and needs to take decisions as fast
> and as accurately as possible. I think that implementing an IA-like
> engine would take an great deal of resources. By the time the IA-like
> scheduler has taken its decision, the whole world could have changed
> since.

The AI scheduler is only used for _development_.

For deployment, the rules learned from the AI scheduler are converted to 
C code (or compiled directly to machine language) and used in real-time. 
  I don't expect the rules to be so complex that the C version would use 
much more CPU than the current interactive schedulers being worked on by 
Con, Ingo, and Nick.

During development, the AI scheduler would be used in real-time, and 
that would have a significant effect on the performance of the system. 
But since it's a constant, the relative interactive behavior should be 
about the same between AI and deployed versions, even though the AI 
version uses a lot more CPU time in the kernel.  That is, if the system 
works well with the AI scheduler, it'll work even BETTER with the 
compiled version.

Re: Use of AI for process scheduling

[David Lang]

The biggest problem is that  the developers basicly can't suplicate the
problems. the best that could be done would be to add something to let a
user who runs into a problem hit a key and gather info to then send to a
developer to try and duplicate the problem on their 'development' kernel,
but since the development kernel doesn't make the same decisions in the
same amount of time it's going to be very hard to duplicate the problem
state.

even more fundamentally you don't know what info to feed into your AI
program to let it make it's decision, you can't feed in every detail that
the kernel knows about every program on the system or you will take
multiple seconds to make each scheduling decision

if it could be made fast enough to permanently replace the existing
scheduler then I think you would have a very interesting idea, but as long
as you are talking about a 'develop with AI and put the result into an
expert system' design I don't see how you could generate useful results.

the scheduler is by definition a real-time entity, if it takes twice as
long to make a decision that in itself alters what the correct decision
should be.

David Lang


 On Mon, 8 Sep 2003,
Timothy Miller wrote:

> Date: Mon, 08 Sep 2003 19:01:21 -0400
> From: Timothy Miller <miller@techsource.com>
> To: Felipe Alfaro Solana <felipe_alfaro@linuxmail.org>
> Cc: Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
> Subject: Re: Use of AI for process scheduling
>
>
>
> Felipe Alfaro Solana wrote:
> > On Mon, 2003-09-08 at 21:28, Timothy Miller wrote:
> >
> >
> >>Basically, we need to write and install into the kernel an AI engine
> >>which uses user feedback about the "feel" of the system to adjust
> >>heuristics dynamically.  For instance, if the user sees that the system
> >>is misbehaving, they can pause the system in the kernel debugger,
> >>examine process priorities, and indicate what "outputs" from the AI
> >>engine are wrong.  It then learns from that.  Heuristics can be tweaked
> >>until things run as desired.  At that point, scheduler developers trade
> >>emails in the AI heuristic language.
> >
> >
> > I'm no kernel expert but I think that doing what you suggest would take
> > an enormous amount of time and resources to do. Also, the scheduler must
> > be a real-time piece of software, and needs to take decisions as fast
> > and as accurately as possible. I think that implementing an IA-like
> > engine would take an great deal of resources. By the time the IA-like
> > scheduler has taken its decision, the whole world could have changed
> > since.
>
> The AI scheduler is only used for _development_.
>
> For deployment, the rules learned from the AI scheduler are converted to
> C code (or compiled directly to machine language) and used in real-time.
>   I don't expect the rules to be so complex that the C version would use
> much more CPU than the current interactive schedulers being worked on by
> Con, Ingo, and Nick.
>
> During development, the AI scheduler would be used in real-time, and
> that would have a significant effect on the performance of the system.
> But since it's a constant, the relative interactive behavior should be
> about the same between AI and deployed versions, even though the AI
> version uses a lot more CPU time in the kernel.  That is, if the system
> works well with the AI scheduler, it'll work even BETTER with the
> compiled version.
>
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: Use of AI for process scheduling

[Timothy Miller]

David Lang wrote:

> 
> the scheduler is by definition a real-time entity, if it takes twice as
> long to make a decision that in itself alters what the correct decision
> should be.
> 


My idea is to have the AI work in real-time just like the expert system 
would.  And I realize that this alters the situation, but it alters the 
situation in a constant way.  For a given number of context switches, 
the same number of scheduling decisions will be made.  That means that 
if the scheduler takes 100 times as long to decide, then all it will do 
is affect both the throughput and the latency in a constant way.

The only time it really matters is when the scheduler decision time 
makes something which would APPEAR to be interactive in the compiled 
case appear to be non-interactive in the AI case.  But that is no 
different from using a slower CPU.  There are LOTS of things that will 
feel smoother on a faster CPU.

So, if we can get a good interactive feel out of the AI case, then you 
will only get better results out of the compiled case.  Furthermore, 
good interactive results out of a fast CPU with the AI would imply good 
results out of a slower CPU in the compiled case.

I do realize that the balance is shifted.  The proportion of scheduler 
computation to user computation is thrown off.  (Still, same as using a 
slower CPU.)  But I don't think it matters.  If the scheduler were 100 
times slower, it would still require far far less than timeslice 
granularity to compute!

Re: Use of AI for process scheduling

[Robin Rosenberg]

tisdag 09 september 2003 02:34 skrev Timothy Miller:
[...]
> The only time it really matters is when the scheduler decision time
> makes something which would APPEAR to be interactive in the compiled
> case appear to be non-interactive in the AI case.  But that is no
> different from using a slower CPU.  There are LOTS of things that will
> feel smoother on a faster CPU.
>
> So, if we can get a good interactive feel out of the AI case, then you
> will only get better results out of the compiled case.  Furthermore,
> good interactive results out of a fast CPU with the AI would imply good
> results out of a slower CPU in the compiled case.
>
> I do realize that the balance is shifted.  The proportion of scheduler
> computation to user computation is thrown off.  (Still, same as using a
> slower CPU.)  But I don't think it matters.  If the scheduler were 100
> times slower, it would still require far far less than timeslice
> granularity to compute!

Change the name. AI has a bad touch, as if things would happen
through magic. A neural is magic to me, but most other AI techniques
are quite predictable.

A rule-based system can be evaluated quite efficiently if the numer of 
rules are reasonable small. A PC can a million of "LIPS" (logical Inferences
per second so you can fit something useful. Say you can afford (on
average one percent of the CPU, that becomes 10000 inferences per
second available per second and with 50 switches pers second that is 2000
inferences per switch. I think can do useful rules with much fewer inferences.
The numbers are guestimates from memory and a few quick googles lookups.

The problem might be efficient collection of useful input to the rules. On the other
hand everything does not have to be recalculated every time the scheduler
makes a decision.

You can split the rules into 1) switching decision making rules 2) strategy selection rules
and 3) environment evaluation rules. The first category of course has to evaluated
every time, while the last set can be a slow process that looks at swapping and I/O
statistics over time withe a recation time on the order of a second. The second is
for simplifying the structure of the rules (might be redundant).

A benefit of a rule based scheduler could be as a good test bed for experimentation.
Changes could be implemented in "real time" (from a user perspective) I.e. you 
change the rule and the  scheduler immediately changes its behaviour. And the scheduler would
be more customizable to the end user or administrator. You could try out
rules for identifying interactive tasks, CPU hogs and tell the scheduler what
/you/ think is importan instead of the one-size-fits-all.

The idea is not bad unless someone proves it. On the other hand its useless
unless manifested in code.

-- robin

Re: Use of AI for process scheduling

[Robin Rosenberg]

tisdag 09 september 2003 03:40 skrev Robin Rosenberg:
> A rule-based system can be evaluated quite efficiently if the numer of
> rules are reasonable small. A PC can a million of "LIPS" (logical
> Inferences per second so you can fit something useful. Say you can afford
> (on average one percent of the CPU, that becomes 10000 inferences per
> second available per second and with 50 switches pers second that is 2000
Math oops, That makes 200 inferences per secons. Probably still more than needed
but the margin is not that huge.

> inferences per switch. I think can do useful rules with much fewer
> inferences. The numbers are guestimates from memory and a few quick googles
> lookups.

-- robin

Re: Use of AI for process scheduling

[Timothy Miller]

Robin Rosenberg wrote:

 > [snip]


At the risk of violating netiquette, I just wanted to mention that what 
Robin wrote is exactly what I had in mind, although certainly 
better-written.

Re: Use of AI for process scheduling

[Robin Rosenberg]

After I did the post I reread your original post (instead of just the ones farther down
the thread). I guess I'm the one violating the netiquette. 

-- robin

tisdag 09 september 2003 17:16 skrev Timothy Miller:
> Robin Rosenberg wrote:
>  > [snip]
>
> At the risk of violating netiquette, I just wanted to mention that what
> Robin wrote is exactly what I had in mind, although certainly
> better-written.

Re: Use of AI for process scheduling

[William Lee Irwin III]

On Mon, Sep 08, 2003 at 03:28:35PM -0400, Timothy Miller wrote:
> Ok, I know I'm going too far.  Right now, the best application would be 
> the process scheduler, but we should start thinking about ways of making 
> the system "self aware" and "self correcting" so that when the model 
> observes the logic to misbehave, detailed information can be produced 
> for debugging purposes.
> Naturally, I am interested in contributing to this, but some of what I 
> will have to learn to participate will come out of ensuing discussions. 
>  I have a lot to learn, but I think if these ideas are valuable, others 
> who already know enough will start to do something with them.

Show me the code.


-- wli

Re: Use of AI for process scheduling

[Mike Fedyk]

On Mon, Sep 08, 2003 at 03:57:49PM -0700, William Lee Irwin III wrote:
> On Mon, Sep 08, 2003 at 03:28:35PM -0400, Timothy Miller wrote:
> > Ok, I know I'm going too far.  Right now, the best application would be 
> > the process scheduler, but we should start thinking about ways of making 
> > the system "self aware" and "self correcting" so that when the model 
> > observes the logic to misbehave, detailed information can be produced 
> > for debugging purposes.
> > Naturally, I am interested in contributing to this, but some of what I 
> > will have to learn to participate will come out of ensuing discussions. 
> >  I have a lot to learn, but I think if these ideas are valuable, others 
> > who already know enough will start to do something with them.
> 
> Show me the code.

I think he's working on a draft, not implementation.

Any chance we'll see any code from you (or the group you seem to be trying
to build) Tim?

Re: Use of AI for process scheduling

[William Lee Irwin III]

On Mon, Sep 08, 2003 at 03:57:49PM -0700, William Lee Irwin III wrote:
>> Show me the code.

On Mon, Sep 08, 2003 at 04:06:21PM -0700, Mike Fedyk wrote:
> I think he's working on a draft, not implementation.
> Any chance we'll see any code from you (or the group you seem to be trying
> to build) Tim?

Worse than useless unless backed by code. We have enough managers already.


-- wli

Re: Use of AI for process scheduling

[Timothy Miller]

William Lee Irwin III wrote:
> On Mon, Sep 08, 2003 at 03:57:49PM -0700, William Lee Irwin III wrote:
> 
>>>Show me the code.
>>
> 
> On Mon, Sep 08, 2003 at 04:06:21PM -0700, Mike Fedyk wrote:
> 
>>I think he's working on a draft, not implementation.
>>Any chance we'll see any code from you (or the group you seem to be trying
>>to build) Tim?
> 
> 
> Worse than useless unless backed by code. We have enough managers already.

Your hostility is misplaced.  I have been participating in discussions 
of a number of things for a while now, and if you've paid attention, 
mostly what I do is discuss ideas.  I'm more of a lurker than a hacker. 
  I do intend to get into kernel hacking, but I have decided, 
particularly with my limited free time, that it would be best to watch 
and learn before blindly diving into kernel development.  In the time 
I've been on LKML, I've learned a great deal about the Linux culture 
which has direct bearing on how one goes about doing just about any kind 
of kernel hacking.  At least as I see it, the social aspect is as 
important as actual coding.  The definition of Free Software is 
something which is shared, and sharing is social.

As for the idea I suggested, I don't expect some other person to "run 
with it", although I'd be delighted if someone did.

I proposed the idea in order to get people's thoughts on it.  If, for 
instance, enough people had logical reasons why it was a _bad_idea_, 
then I would drop it before writing a line of code.

Don't you ever discuss your ideas with anyone before writing code?  I 
do.  I'm reasonably intelligent, but not arrogant enough to think that I 
always know the right thing to do before bouncing ideas off of other 
intelligent people.  Perhaps it is not your style, but it is my style to 
begin discussing ideas very early in development.

Are we on the same page here?  If it's generally agreed that a 
kernel-related discussion is "off topic" unless code is involved, then 
I'll shut up and go work on the code in silence until I have something. 
  But keep in mind that this is a purely academic (in both meanings) 
issue until we can interface it with some real kernel scheduler code.

Re: Use of AI for process scheduling

[William Lee Irwin III]

I thought better of sending this as it seemed perhaps too unfriendly,
but after pasting a few lines of it on IRC, it appears some people
found it humorous. So, on with the diatribe^Wshow:

William Lee Irwin III wrote:
>> Worse than useless unless backed by code. We have enough managers already.

On Mon, Sep 08, 2003 at 08:22:10PM -0400, Timothy Miller wrote:
> Your hostility is misplaced.  I have been participating in discussions 
> of a number of things for a while now, and if you've paid attention, 
> mostly what I do is discuss ideas.  I'm more of a lurker than a hacker. 
>  I do intend to get into kernel hacking, but I have decided, 
> particularly with my limited free time, that it would be best to watch 
> and learn before blindly diving into kernel development.  In the time 
> I've been on LKML, I've learned a great deal about the Linux culture 
> which has direct bearing on how one goes about doing just about any kind 
> of kernel hacking.  At least as I see it, the social aspect is as 
> important as actual coding.  The definition of Free Software is 
> something which is shared, and sharing is social.

Such far-flung notions have far better ways to be pursued, starting
with some kind of review of concrete issues they address and some kind
of meaningful prediction of the results. e.g. what performance metric
do you expect your AI-produced scheduler to optimize? How much better
than some other algorithm? What other algorithms? Does it do something
unique that other algorithms can't, e.g. predicting task behavior?
What's the advantage of its unique capability? How is it exploited?

I don't see any of this happening and don't really want/expect answers.


On Mon, Sep 08, 2003 at 08:22:10PM -0400, Timothy Miller wrote:
> As for the idea I suggested, I don't expect some other person to "run 
> with it", although I'd be delighted if someone did.
> I proposed the idea in order to get people's thoughts on it.  If, for 
> instance, enough people had logical reasons why it was a _bad_idea_, 
> then I would drop it before writing a line of code.
> Don't you ever discuss your ideas with anyone before writing code?  I 
> do.  I'm reasonably intelligent, but not arrogant enough to think that I 
> always know the right thing to do before bouncing ideas off of other 
> intelligent people.  Perhaps it is not your style, but it is my style to 
> begin discussing ideas very early in development.

The trouble with this is the implication that someone will do the hacking
for you. Ideas can be worthwhile, but ultimately only if backed by some
potential of ever being utilized, i.e. coded. As one of those frequently
pegged to run off and do various kinds of coding, I'm rather wary of
stuff like this cropping up as requirements phrased in Star Trek dialogue.


On Mon, Sep 08, 2003 at 08:22:10PM -0400, Timothy Miller wrote:
> Are we on the same page here?  If it's generally agreed that a 
> kernel-related discussion is "off topic" unless code is involved, then 
> I'll shut up and go work on the code in silence until I have something. 
>  But keep in mind that this is a purely academic (in both meanings) 
> issue until we can interface it with some real kernel scheduler code.

Yes and no. I know what you're on about, but frankly, the mere Subject:
line had me falling off my chair with laughter when I saw it. At the
level you're presenting it, this is coming off as unicorns, leprechauns,
dancing munchkins, and witches squished by falling houses. If it were
serious it wouldn't have been "AI" but rather some specific learning
method (probably a computationally inexpensive one) and a specific kind
of decision to improve.

Not that I mean to "verbally attack" at all. This is all dead serious.
"AI" is frankly a buzzword and suggests more science fiction than
science. The lack of detail and the fumbling around for general
categories of learning methods ruled out any coherent plan. There isn't
even a hint of what the thing is supposed to do inside the scheduler;
presumably the entire algorithm is supposed to spring forth from the
mind of some self-aware computational entity. It's just far too removed
from reality not to dismiss out of hand.

Sorry, this one was a turkey. Ideas for solutions to problems we're
having instead of not-yet-decided solutions looking for problems hoping
for a blast radius somewhere near kernel/sched.c would be far preferable.


-- wli

Re: Use of AI for process scheduling

[Timothy Miller]

William Lee Irwin III wrote:
> I thought better of sending this as it seemed perhaps too unfriendly,
> but after pasting a few lines of it on IRC, it appears some people
> found it humorous. So, on with the diatribe^Wshow:


Well, despite the fact that you have a somewhat offensive tone, I do 
take what you're saying seriously.  Not to say that I'm ENTIRELY 
discouraged, but your point that I need to have something a lot more 
solid is well taken.

Fortunately, my post has had the intended effect:  other people have 
responded with specific good ideas, ones which can possibly be used to 
produce something more concretely useful than the vague notion I posited.

I don't believe I will completely give up my habit of suggesting vague 
ideas, because it has been a successful approach in the past.  Other 
intelligent people naturally fill in the holes with knowedge and ideas 
of their own.  On the other hand, before I go off with something too 
vague, perhaps I will flesh it out with more thought on my own.  I hope 
adding too many of my own ideas won't bias others or prevent people from 
suggesting alternatives.

Re: Use of AI for process scheduling

[William Lee Irwin III]

William Lee Irwin III wrote:
>> I thought better of sending this as it seemed perhaps too unfriendly,
>> but after pasting a few lines of it on IRC, it appears some people
>> found it humorous. So, on with the diatribe^Wshow:

On Tue, Sep 09, 2003 at 11:08:07AM -0400, Timothy Miller wrote:
> Well, despite the fact that you have a somewhat offensive tone, I do 
> take what you're saying seriously.  Not to say that I'm ENTIRELY 
> discouraged, but your point that I need to have something a lot more 
> solid is well taken.

I was hoping the preface would lighten whatever blow was involved with
it. It wasn't the friendliest way to go about it, but was considered
to have enough humorous highlights by some to be worth posting anyway.


-- wli

Re: Use of AI for process scheduling

[Timothy Miller]

Mike Fedyk wrote:
> On Mon, Sep 08, 2003 at 03:57:49PM -0700, William Lee Irwin III wrote:
> 
>>On Mon, Sep 08, 2003 at 03:28:35PM -0400, Timothy Miller wrote:
>>
>>>Ok, I know I'm going too far.  Right now, the best application would be 
>>>the process scheduler, but we should start thinking about ways of making 
>>>the system "self aware" and "self correcting" so that when the model 
>>>observes the logic to misbehave, detailed information can be produced 
>>>for debugging purposes.
>>>Naturally, I am interested in contributing to this, but some of what I 
>>>will have to learn to participate will come out of ensuing discussions. 
>>> I have a lot to learn, but I think if these ideas are valuable, others 
>>>who already know enough will start to do something with them.
>>
>>Show me the code.
> 
> 
> I think he's working on a draft, not implementation.

Yeah, I didn't think his comment was very helpful since I thought it was 
clear that I was working on a draft of an IDEA.

> Any chance we'll see any code from you (or the group you seem to be trying
> to build) Tim?

Well...

Since I don't know enough about the actual kernel, I thought perhaps I 
could start with writing a generic neural net that could be added to the 
kernel.  The fact that I need an integer-only algorithm will require 
that I largely start from scratch.

I also need to refresh my memory on how to do back-propogation.

Oh, and most importantly, I need ideas from others so I don't go down 
the wrong path.

Re: Use of AI for process scheduling

[Rick Lindsley]

    Yeah, I didn't think his comment was very helpful since I thought it was 
    clear that I was working on a draft of an IDEA.

How complex is your thinking where *ideas* need drafts? :)

A scheduler which modifies behavior based on its load is not unreasonable,
but it doesn't need a neural net to do so.  We just have to tell
it what's important.  To do that, WE have to know what's important.
And we haven't figured that all out yet.

For example, just-completed I/O by xmms, even though xmms performs
lots of I/O, is important, but just-completed I/O by the db app, which
also performs lots of I/O, is not. Well, unless you're on the server
instead of the laptop; then the db app is important.  Does there exist
sufficient context about the two types of processes that we, the human,
can make a decision?  Everything I've seen so far is just "well, that's
just what *I* want in that situation."  If so, we'll never get that right
even with a neural net.

However, once we characterize "what we want" we might be able to
communicate it (and code it) to the kernel.  To that end, here's an
update on scheduler statistics code.  In testing, it's proved fairly
non-intrusive and may provide some answers to "what we want".  If it
doesn't, it's fairly extensible if done carefully.

    http://eaglet.rain.com/rick/linux/schedstat/

This patch (against 2.6.0-test4 or 2.6.0-test5) collects data about
scheduler decisions, which may allow us, with 20/20 hindsight, to
determine which specific decisions we don't like and perhaps how to
modify them.

Rick

Re: Use of AI for process scheduling

[Timothy Miller]

Rick Lindsley wrote:
>     Yeah, I didn't think his comment was very helpful since I thought it was 
>     clear that I was working on a draft of an IDEA.
> 
> How complex is your thinking where *ideas* need drafts? :)

It wasn't so much complex as it was _vague_.  :)

[snip]
> However, once we characterize "what we want" we might be able to
> communicate it (and code it) to the kernel.  To that end, here's an
> update on scheduler statistics code.  In testing, it's proved fairly
> non-intrusive and may provide some answers to "what we want".  If it
> doesn't, it's fairly extensible if done carefully.
> 
>     http://eaglet.rain.com/rick/linux/schedstat/
> 
> This patch (against 2.6.0-test4 or 2.6.0-test5) collects data about
> scheduler decisions, which may allow us, with 20/20 hindsight, to
> determine which specific decisions we don't like and perhaps how to
> modify them.


Now, THIS is the kind of thing I wanted to see!  Very cool.  My thought 
then is that it might be helpful to have some tools to help analyze this 
  raw data.  I'm sure you thought of that already.  :)

Re: Use of AI for process scheduling

[John Yau]

>You talk about weights. Would the linux community be willing to put a
neural net into the kernel? I'm
>sure we could optimize it to not take a lot of processing overhead, but
it's an "unknown".

A neural net is a bad idea in something that requires very low processing
overhead.  There's really no way you can optimize it except through hardware
assistance (i.e. a neural network chip).  You have to iterate through every
node and every connection in the neural to get a result, there's no escape
from that.  Too much computing overhead to be of much use in today's general
purpose processors.

>It would
>be scary to some people to be unable to disect the actual workings of it
and have no way of
>determining corner-case behavior from examining code. But if we have, say,
only a 2-layer neural
>net, we might still be able to reverse-engineer it.

You need at the minimum 3 layers to simulate xor, which is a very important
logic function in any decision process, in a feed forward NN (the one you're
describing?).  NNs in general make decent nonlinear classifiers and not much
beyond that, so I doubt even if we were to reverse engineer it, it'd be very
useful except to classify tasks (e.g. CPU hog or not CPU hog), which can
already be done with very simple heuristics.  Most folks doing research in
AI tend to stay away from NNs these days, and use standard linear
regressions, decision trees, hidden markov models, and etc to do classifier
work.

>One thing I was thinking of is that if there is some information about a
process which is inconvenient
>to get normally but could be accessed by a kernel or user-space thread,
then this process could
>feed back info to the scheduler AI for it to do automatic tuning. Some
information that the scheduler
>doesn't have direct (or efficient) access to could be inferred from
information it DOES have access
>to, and that would be learned through adjustment of weights via
backpropogation.

Again, backpropagation training is computationally very very expensive
(actually a order of magnitude more expensive than extracting results from a
NN).  Using gradient descent, to "learn" something, you have to adjust every
single connection weight in the network thousands of times.  To have AI to
schedule something in realtime is asking too much right now and to put it
simply not necessary.

Where I do see AI can solve some problems is when we expose "tuning knobs"
and need some way to get optimal values offline and not realtime.  A very
good example is the connection matrix in the KLAT II beowulf cluster where
they used genetic algorithms to solve for the optimal solution.  In the
current scheduler situation I can see using genetic algorithms to get
optimal values for Ingo, Con, or Nick's schedulers so they can get compiled
into the scheduler.



John Yau

Use of AI for process scheduling

[Timothy Miller]

I just got back from vacation and have 3278 list messages to sift 
through.  (Yay.)  I wouldn't be surprised, therefore, if others were 
already discussing this, but I've been thinking of some ideas over the 
past week that we may be helpful for the advancement of intelligent 
process scheduling.

To begin with, let's consider the parts of an intelligent system:

1) Inputs (ie. properties and behaviors of processes)
2) Heuristics
3) Outputs (ie. dynamic priorities, etc.)

Up to this point, the interactive scheduler has been designed in a very 
expert-system-like manner.  Human experts observe behaviors and define 
heuristics.  Ultimately, we do want a solid set of heuristics that are 
coded in C, and that's what the current development process has been 
working directly toward.

The progress has been slow, and there have been a lot of false starts 
and tangents which have been discarded.  This is all how development 
works, and it's important to explore all possibilities.  But what I 
would like to propose is that we work on a way to accelerate that 
process, and that is to make use of machine learning.  We move from 
expert systems to artificial intelligence, because the heuristics are 
determined by the machine and are therefore dynamic.

Basically, we need to write and install into the kernel an AI engine 
which uses user feedback about the "feel" of the system to adjust 
heuristics dynamically.  For instance, if the user sees that the system 
is misbehaving, they can pause the system in the kernel debugger, 
examine process priorities, and indicate what "outputs" from the AI 
engine are wrong.  It then learns from that.  Heuristics can be tweaked 
until things run as desired.  At that point, scheduler developers trade 
emails in the AI heuristic language.

Obviously, this AI engine will be slow and add a huge amount of 
processing overhead.  The idea is to determine what the heuristics are, 
and then to release a kernel, recode the heuristics in C.