Nick's scheduler v17
Hi,
http://www.kerneltrap.org/~npiggin/v17/
Still working on SMP and NUMA. Some (maybe) interesting things I put in are
- Sequential CPU balancing so you don't get a big storm of balances every 1/4s.
- Balancing is trying to err more on the side of caution, I have to start analysing it more thoroughly though.
- Attacked the NUMA balancing code. There should now be less buslocked ops / cache pingpongs in some fastpaths. Volanomark likes it, more realistic
loads
won't improve so much http://www.kerneltrap.org/~npiggin/v17/volano.png
This improvement is NUMA only.
I haven't had time to reproduce Cliff's serious reaim performance dropoffs so they're probably still there. I couldn't reproduce Martin's kernbench dropoff, but the 16-way I'm using only has 512K cache which might not show it up.
Quoted 14 lines · On Sat, 25 Oct 2003 04:10:24 +1000 Nick Piggin <[email protected]> wrote:
Hi,
http://www.kerneltrap.org/~npiggin/v17/Still working on SMP and NUMA. Some (maybe) interesting things I put in are
- Sequential CPU balancing so you don't get a big storm of balances every 1/4s.
- Balancing is trying to err more on the side of caution, I have to start analysing it more thoroughly though.
- Attacked the NUMA balancing code. There should now be less buslocked ops / cache pingpongs in some fastpaths. Volanomark likes it, more realistic
loads
won't improve so much http://www.kerneltrap.org/~npiggin/v17/volano.png
This improvement is NUMA only.
Quoted 6 lines
I haven't had time to reproduce Cliff's serious reaim performance dropoffs so
they're probably still there. I couldn't reproduce Martin's kernbench dropoff,
but the 16-way I'm using only has 512K cache which might not show it up.
Okay, i put both v17 patches in the OSDL Patch Lifecycle Manager ( http://www.osdl.org/plm-cgi/plm/ )
sched-v17 is PLM #2251
sched-nopolicy-v17 is PLM #2252
Results asap.
cliffw
Quoted 7 lines
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Signature · 2 lines
The church is near, but the road is icy. The bar is far, but i will walk carefully. - Russian proverb
Quoted 8 lines · Nick Piggin
Hi,
http://www.kerneltrap.org/~npiggin/v17/Still working on SMP and NUMA. Some (maybe) interesting things I put in are
- Sequential CPU balancing so you don't get a big storm of balances every 1/4s.
- Balancing is trying to err more on the side of caution, I have to start analysing it more thoroughly though.
+
+ *imbalance /= 2;
+ *imbalance = (*imbalance + FPT - 1) / FPT;
I think I see what is going on here, but would something like this work out better?
*imbalance = min(this_load - load_avg, load_avg - max_load)
That way you take just enough to either have busiest_queue or this_rq's length be the load_avg. I suppose you could take even less, but IMO, the /=2 is what I really don't like. Perhaps:
*imbalance = min(this_load - load_avg, load_avg - max_load); *imbalance = (*imbalance + FPT - 1) / FPT;
This should work well for intranode balances, internode balances may need a little optimization, since the load_avg really does not really represent the load avg of the two nodes in question, just one cpu from one of them and all the cpus from another.
Quoted 16 lines · Andrew Theurer
Quoted 9 lines · Nick Piggin
Hi,
http://www.kerneltrap.org/~npiggin/v17/Still working on SMP and NUMA. Some (maybe) interesting things I put in are
- Sequential CPU balancing so you don't get a big storm of balances every 1/4s.
- Balancing is trying to err more on the side of caution, I have to start analysing it more thoroughly though.(quoted diff) +3
-0+ + *imbalance /= 2; + *imbalance = (*imbalance + FPT - 1) / FPT;
Quoted 2 lines
I think I see what is going on here, but would something like this work out better?
Yeah, sorry its not well commented. Its still changing quite quickly.
Quoted 5 lines
*imbalance =
min(this_load - load_avg, load_avg - max_load)That way you take just enough to either have
busiest_queueor this_rq's length be theload_avg. I suppose you could take even less, but IMO, the /=2 is what I really don't like. Perhaps:
That is _exactly_ what I had before! Thats probably the way to go. Thanks for having a look at it.
Quoted 7 lines
*imbalance =
min(this_load - load_avg, load_avg - max_load); *imbalance = (*imbalance + FPT - 1) / FPT;This should work well for intranode balances, internode balances may need a little optimization, since the
load_avgreally does not really represent the load avg of the two nodes in question, just one cpu from one of them and all the cpus from another.
Yeah that does need a bit of rethinking.
Quoted 27 lines · Nick Piggin
Quoted 17 lines · Andrew Theurer
Quoted 10 lines · Nick Piggin
Hi,
http://www.kerneltrap.org/~npiggin/v17/Still working on SMP and NUMA. Some (maybe) interesting things I put in are
- Sequential CPU balancing so you don't get a big storm of balances every 1/4s.
- Balancing is trying to err more on the side of caution, I have to start
analysing it more thoroughly though.(quoted diff) +3
-0+ + *imbalance /= 2; + *imbalance = (*imbalance + FPT - 1) / FPT;Quoted 2 lines
I think I see what is going on here, but would something like this work out better?
Yeah, sorry its not well commented. Its still changing quite quickly.
Quoted 1 line
Quoted 15 lines
Quoted 4 lines
*imbalance =
min(this_load - load_avg, load_avg - max_load)That way you take just enough to either have
busiest_queueor this_rq's length be theload_avg. I suppose you could take even less, but IMO, the /=2 is what I really don't like. Perhaps:That is _exactly_ what I had before! Thats probably the way to go. Thanks for having a look at it.
Quoted 7 lines
*imbalance =
min(this_load - load_avg, load_avg - max_load); *imbalance = (*imbalance + FPT - 1) / FPT;This should work well for intranode balances, internode balances may need a little optimization, since the
load_avgreally does not really represent the load avg of the two nodes in question, just one cpu from one of them and all the cpus from another.
Oh, actually, after my path, load_avg represents the load average of _all_ the nodes. Have a look at find_busiest_node. Which jogs my memory of why its not always a good idea to do your *imbalance min(...) thing (I actually saw this happening).
5 CPUs, 4 processes running on one cpu. load_avg would be 0.8 for all cpus. balancing doesn't happen. I have to think about this a bit more...
Quoted 17 lines
Quoted 16 lines
Quoted 5 lines
*imbalance =
min(this_load - load_avg, load_avg - max_load)That way you take just enough to either have
busiest_queueor this_rq's length be theload_avg. I suppose you could take even less, but IMO, the /=2 is what I really don't like. Perhaps:That is _exactly_ what I had before! Thats probably the way to go. Thanks for having a look at it.
Quoted 7 lines
*imbalance =
min(this_load - load_avg, load_avg - max_load); *imbalance = (*imbalance + FPT - 1) / FPT;This should work well for intranode balances, internode balances may need a little optimization, since the
load_avgreally does not really represent the load avg of the two nodes in question, just one cpu from one of them and all the cpus from another.
Quoted 4 lines
Oh, actually, after my path,
load_avgrepresents the load average of _all_ the nodes. Have a look atfind_busiest_node. Which jogs my memory of why its not always a good idea to do your *imbalance min(...) thing (I actually saw this happening).
Oops, I meant avg_load, which you calculate in find_busiest_queue on the fly.
Quoted 2 lines
5 CPUs, 4 processes running on one cpu.
load_avgwould be 0.8 for all cpus. balancing doesn't happen. I have to think about this a bit more...
Actually, if we use avg_load, I guess it would be 0, since this is an unsigned long. Maybe avg_load needs to have a min value of 1. Then if we apply:
*imbalance = min(max_load - avg_load, avg_load - this_load)
min(4 - 1, 1 - 0)
And imbalance looks a lot better. Only concern would be an idle cpu stealing from another, leaving the other cpu idle. I guess a check could be put there.
Quoted 18 lines · Andrew Theurer
Quoted 18 lines
Quoted 18 lines
Quoted 6 lines
*imbalance =
min(this_load - load_avg, load_avg - max_load)That way you take just enough to either have
busiest_queueor this_rq's length be theload_avg. I suppose you could take even less, but IMO, the /=2 is what I really don't like. Perhaps:That is _exactly_ what I had before! Thats probably the way to go. Thanks for having a look at it.
Quoted 8 lines
*imbalance =
min(this_load - load_avg, load_avg - max_load); *imbalance = (*imbalance + FPT - 1) / FPT;This should work well for intranode balances, internode balances may need a little optimization, since the
load_avgreally does not really represent the load avg of the two nodes in question, just one cpu from one of them and all the cpus from another.
Quoted 8 lines
Quoted 5 lines
Oh, actually, after my path,
load_avgrepresents the load average of _all_ the nodes. Have a look atfind_busiest_node. Which jogs my memory of why its not always a good idea to do your *imbalance min(...) thing (I actually saw this happening).Oops, I meant
avg_load, which you calculate infind_busiest_queueon the fly.
OK
Quoted 7 lines
Quoted 4 lines
5 CPUs, 4 processes running on one cpu.
load_avgwould be 0.8 for all cpus. balancing doesn't happen. I have to think about this a bit more...Actually, if we use
avg_load, I guess it would be 0, since this is an unsigned long. Maybeavg_loadneeds to have a min value of 1. Then if we apply:
Well its got a fixed point scaling factor.
Quoted 5 lines
*imbalance =
min(max_load - avg_load, avg_load - this_load)min(4 - 1, 1 - 0)
I think you want:
*imbalance = min(max_load - avg_load, avg_load - this_load) if ( (*imbalance < 1*FPT) &&
(max_load - this_load) > 1*FPT )
*imbalance = 1*FPT;
So if there is a total imbalance of more than 1 task, at least one will be moved.
Quoted 4 lines
And imbalance looks a lot better. Only concern would be an idle cpu stealing from another, leaving the other cpu idle. I guess a check could be put there.
pull_task won't pull a running task, so you get some protection there.