[uml-devel] [RFC] (How to) Let idle CPUs sleep

[uml-devel] [RFC] (How to) Let idle CPUs sleep

[Srivatsa Vaddagiri]

Hello,
	I need some inputs from the community (specifically from virtual
machine and embedded/power-management folks) on something that I am working on.

	This is regarding cutting off the regular timer ticks when a CPU
becomes idle and it does not have any next timer set to expire in the "near"
term. Both CONFIG_VST and CONFIG_NO_IDLE_HZ deal with this. Both embedded and
virtualized platforms (ex: UML/S390) benefit from this. For ex: if 100s
of guest are running on a single box, then cutting off some useless HZ ticks
in the idle CPUs of all guests will lead to efficient use of host CPU's cycles.

Cutting of local timer ticks has an effect on the scheduler load balance
activity and I am trying to see how best to reduce the impact.

Two solutions have been proposed so far:

	A. As per Nick's suggestion, impose a max limit (say some 100 ms or
	   say a second, Nick?) on how long a idle CPU can avoid taking
	   local-timer ticks. As a result, the load imbalance could exist only
	   for this max duration, after which the sleeping CPU will wake up
	   and balance itself. If there is no imbalance, it can go and sleep
	   again for the max duration.

 	   For ex, lets say a idle CPU found that it doesn't have any near timer
	   for the next 1 minute. Instead of letting it sleep for 1 minute in
	   a single stretch, we let it sleep in bursts of 100 msec (or whatever
	   is the max. duration chosen). This still is better than having
	   the idle CPU take HZ ticks a second.

	   As a special case, when all the CPUs of an image go idle, we
	   could consider completely shutting off local timer ticks
	   across all CPUs (till the next non-timer interrupt).


	B. Don't impose any max limit on how long a idle CPU can sleep.
	   Here we let the idle CPU sleep as long as it wants. It is
	   woken up by a "busy" CPU when it detects an imbalance. The
	   busy CPU acts as a watchdog here. If there are no such
	   busy CPUs, then it means that nobody will acts as watchdogs
	   and idle CPUs sleep as long as they want. A possible watchdog
	   implementation has been discussed at:

	http://marc.theaimsgroup.com/?l=linux-kernel&m=111287808905764&w=2

A is obviously more simpler to implement compared to B!
Whether both are more or less equally efficient is something that I dont know.

To help us decide which way to go, could I have some comments from the virtual
machine and embedded folks on which solution they prefer and why?



--


Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017


-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Rusty Russell]

On Sat, 2005-05-07 at 23:57 +0530, Srivatsa Vaddagiri wrote:
> Two solutions have been proposed so far:
> 
> 	A. As per Nick's suggestion, impose a max limit (say some 100 ms or
> 	   say a second, Nick?) on how long a idle CPU can avoid taking
> 	   local-timer ticks. As a result, the load imbalance could exist only
> 	   for this max duration, after which the sleeping CPU will wake up
> 	   and balance itself. If there is no imbalance, it can go and sleep
> 	   again for the max duration.
> 
>  	   For ex, lets say a idle CPU found that it doesn't have any near timer
> 	   for the next 1 minute. Instead of letting it sleep for 1 minute in
> 	   a single stretch, we let it sleep in bursts of 100 msec (or whatever
> 	   is the max. duration chosen). This still is better than having
> 	   the idle CPU take HZ ticks a second.
> 
> 	   As a special case, when all the CPUs of an image go idle, we
> 	   could consider completely shutting off local timer ticks
> 	   across all CPUs (till the next non-timer interrupt).
> 
> 
> 	B. Don't impose any max limit on how long a idle CPU can sleep.
> 	   Here we let the idle CPU sleep as long as it wants. It is
> 	   woken up by a "busy" CPU when it detects an imbalance. The
> 	   busy CPU acts as a watchdog here. If there are no such
> 	   busy CPUs, then it means that nobody will acts as watchdogs
> 	   and idle CPUs sleep as long as they want. A possible watchdog
> 	   implementation has been discussed at:
> 
> 	http://marc.theaimsgroup.com/?l=linux-kernel&m=111287808905764&w=2

My preference would be the second: fix the scheduler so it doesn't rely
on regular polling.  However, as long as the UP case runs with no timer
interrupts when idle, many people will be happy (eg. most embedded).

Rusty.
-- 
A bad analogy is like a leaky screwdriver -- Richard Braakman



-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Nick Piggin]

Rusty Russell wrote:
> On Sat, 2005-05-07 at 23:57 +0530, Srivatsa Vaddagiri wrote:
> 
>>Two solutions have been proposed so far:
>>
>>	A. As per Nick's suggestion, impose a max limit (say some 100 ms or
>>	   say a second, Nick?) on how long a idle CPU can avoid taking

Yeah probably something around that order of magnitude. I suspect
there will fast be a point where either you'll get other timers
going off more frequently, and / or you simply get very quickly
diminishing returns on the amount of power saving gained from
increasing the period.

>>	   local-timer ticks. As a result, the load imbalance could exist only
>>	   for this max duration, after which the sleeping CPU will wake up
>>	   and balance itself. If there is no imbalance, it can go and sleep
>>	   again for the max duration.
>>
>> 	   For ex, lets say a idle CPU found that it doesn't have any near timer
>>	   for the next 1 minute. Instead of letting it sleep for 1 minute in
>>	   a single stretch, we let it sleep in bursts of 100 msec (or whatever
>>	   is the max. duration chosen). This still is better than having
>>	   the idle CPU take HZ ticks a second.
>>
>>	   As a special case, when all the CPUs of an image go idle, we
>>	   could consider completely shutting off local timer ticks
>>	   across all CPUs (till the next non-timer interrupt).
>>
>>
>>	B. Don't impose any max limit on how long a idle CPU can sleep.
>>	   Here we let the idle CPU sleep as long as it wants. It is
>>	   woken up by a "busy" CPU when it detects an imbalance. The
>>	   busy CPU acts as a watchdog here. If there are no such
>>	   busy CPUs, then it means that nobody will acts as watchdogs
>>	   and idle CPUs sleep as long as they want. A possible watchdog
>>	   implementation has been discussed at:
>>
>>	http://marc.theaimsgroup.com/?l=linux-kernel&m=111287808905764&w=2
> 
> 
> My preference would be the second: fix the scheduler so it doesn't rely
> on regular polling.

It is not so much a matter of "fixing" the scheduler as just adding
more heuristics. When are we too busy? When should we wake another
CPU? What if that CPU is an SMT sibling? What if it is across the
other side of the topology, and other CPUs closer to it are busy
as well? What if they're busy but not as busy as we are? etc.

We've already got that covered in the existing periodic pull balancing,
so instead of duplicating this logic and moving this extra work to busy
CPUs, we can just use the existing framework.

At least we should try method A first, and if that isn't good enough
(though I suspect it will be), then think about adding more complexity
to the scheduler.

>  However, as long as the UP case runs with no timer
> interrupts when idle, many people will be happy (eg. most embedded).
> 

Well in the UP case, both A and B should basically degenerate to the
same thing.

Probably the more important case for the scheduler is to be able to
turn off idle SMP hypervisor clients, Srivatsa?

-- 
SUSE Labs, Novell Inc.




-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Arjan van de Ven]

On Sun, 2005-05-08 at 13:50 +1000, Rusty Russell wrote:
> My preference would be the second: fix the scheduler so it doesn't rely
> on regular polling.  However, as long as the UP case runs with no timer
> interrupts when idle, many people will be happy (eg. most embedded).

alternatively; if a CPU is idle a long time we could do a software level
hotunplug on it (after setting it to the lowest possible frequency and
power state), and have some sort of thing that keeps track of "spare but
unplugged" cpus that can plug cpus back in on demand.

That also be nice for all the virtual environments where this could
interact with the hypervisor etc





-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Srivatsa Vaddagiri]

On Sun, May 08, 2005 at 02:14:23PM +1000, Nick Piggin wrote:
> Yeah probably something around that order of magnitude. I suspect
> there will fast be a point where either you'll get other timers
> going off more frequently, and / or you simply get very quickly
> diminishing returns on the amount of power saving gained from
> increasing the period.

I am looking at it from the other perspective also i.e, virtualized
env. Any amount of unnecessary timer ticks will lead to equivalent amount
of unnecessary context switches among the guest OSes.

> It is not so much a matter of "fixing" the scheduler as just adding
> more heuristics. When are we too busy? When should we wake another
> CPU? What if that CPU is an SMT sibling? What if it is across the
> other side of the topology, and other CPUs closer to it are busy
> as well? What if they're busy but not as busy as we are? etc.
> 
> We've already got that covered in the existing periodic pull balancing,
> so instead of duplicating this logic and moving this extra work to busy
> CPUs, we can just use the existing framework.

I don't think we have to duplicate the logic, just "reuse" whatever logic
exists (in find_busiest_group etc). However I do agree there is movement
of extra work to busy CPUs, but that is only to help the idle CPU sleep longer.
Whether it justifies the additional complexity or not is what this RFC is
about I guess!

FWIW, I have also made some modifications in the original proposal 
for reducing the watchdog workload (instead of the same non-idle cpu waking 
up all the sleeping CPUs it finds in the same rebalance_tick, the task
is spread over multiple non-idle tasks in different rebalance_ticks).
New (lightly tested) patch is in the mail below.


> At least we should try method A first, and if that isn't good enough
> (though I suspect it will be), then think about adding more complexity
> to the scheduler.

What would be good to measure between the two approaches is the CPU utilization 
(over a period of time - say 10 hrs) of somewhat lightly loaded SMP guest OSes 
(i.e some CPUs are idle and other CPUs of the same guest are not idle), when 
multiple such guest OSes are running simultaneously on the same box.  This 
means I need a port of VST to UML :(

> Well in the UP case, both A and B should basically degenerate to the
> same thing.

I agree.

> Probably the more important case for the scheduler is to be able to
> turn off idle SMP hypervisor clients, Srivatsa?

True. To make a distinction, these SMP clients can be either completely
idle (all their CPUs idle) or partially idle (only fraction of CPUs idle).
It would be good to cater to both kind of clients.

My latest watchdog implementation is below for reference:

---

 linux-2.6.12-rc3-mm2-vatsa/include/linux/sched.h |    1 
 linux-2.6.12-rc3-mm2-vatsa/kernel/sched.c        |  150 ++++++++++++++++++++++-
 2 files changed, 146 insertions(+), 5 deletions(-)

diff -puN kernel/sched.c~sched-nohz kernel/sched.c
--- linux-2.6.12-rc3-mm2/kernel/sched.c~sched-nohz	2005-05-04 18:23:30.000000000 +0530
+++ linux-2.6.12-rc3-mm2-vatsa/kernel/sched.c	2005-05-07 22:09:04.000000000 +0530
@@ -1875,6 +1875,25 @@ out:
 	return pulled;
 }
 
+static inline struct sched_domain *
+sched_domain_ptr(int dst_cpu, int src_cpu, struct sched_domain *src_ptr)
+{
+	struct sched_domain *tmp, *dst_ptr;
+
+	dst_ptr = cpu_rq(dst_cpu)->sd;
+
+	for_each_domain(src_cpu, tmp) {
+		if (tmp == src_ptr || !dst_ptr)
+			break;
+		dst_ptr = dst_ptr->parent;
+	}
+
+	if (tmp == NULL)
+		dst_ptr = NULL;
+
+	return dst_ptr;
+}
+
 /*
  * find_busiest_group finds and returns the busiest CPU group within the
  * domain. It calculates and returns the number of tasks which should be
@@ -1882,11 +1901,18 @@ out:
  */
 static struct sched_group *
 find_busiest_group(struct sched_domain *sd, int this_cpu,
-		   unsigned long *imbalance, enum idle_type idle)
+		   unsigned long *imbalance, enum idle_type idle,
+		   cpumask_t *wakemaskp)
 {
 	struct sched_group *busiest = NULL, *this = NULL, *group = sd->groups;
 	unsigned long max_load, avg_load, total_load, this_load, total_pwr;
 	int load_idx;
+#ifdef CONFIG_NO_IDLE_HZ
+	int grp_sleeping = 0, woken = 0;
+	cpumask_t tmpmask;
+	struct sched_domain *sd1;
+	unsigned long interval;
+#endif
 
 	max_load = this_load = total_load = total_pwr = 0;
 	if (idle == NOT_IDLE)
@@ -1896,6 +1922,11 @@ find_busiest_group(struct sched_domain *
 	else
 		load_idx = sd->idle_idx;
 
+#ifdef CONFIG_NO_IDLE_HZ
+	if (wakemaskp)
+		cpus_clear(*wakemaskp);
+#endif
+
 	do {
 		unsigned long load;
 		int local_group;
@@ -1906,6 +1937,17 @@ find_busiest_group(struct sched_domain *
 		/* Tally up the load of all CPUs in the group */
 		avg_load = 0;
 
+#ifdef CONFIG_NO_IDLE_HZ
+		grp_sleeping = 0;
+		woken = 0;
+		if (wakemaskp && idle == NOT_IDLE) {
+			/* Are all CPUs in the group sleeping ? */
+			cpus_and(tmpmask, group->cpumask, nohz_cpu_mask);
+			if (cpus_equal(tmpmask, group->cpumask))
+				grp_sleeping = 1;
+		}
+#endif
+
 		for_each_cpu_mask(i, group->cpumask) {
 			/* Bias balancing toward cpus of our domain */
 			if (local_group)
@@ -1914,6 +1956,36 @@ find_busiest_group(struct sched_domain *
 				load = source_load(i, load_idx);
 
 			avg_load += load;
+
+#ifdef CONFIG_NO_IDLE_HZ
+			/* Try to find a CPU that can be woken up from the
+			 * sleeping group. After we wake up one CPU, we will let
+			 * it wakeup others in its group.
+			 */
+			if (!grp_sleeping || woken)
+				continue;
+
+			sd1 = sched_domain_ptr(i, this_cpu, sd);
+
+			if (!sd1 || !sd1->flags & SD_LOAD_BALANCE)
+				continue;
+
+			interval = sd1->balance_interval;
+			/* scale ms to jiffies */
+			interval = msecs_to_jiffies(interval);
+	                if (unlikely(!interval))
+        	                interval = 1;
+
+			if (jiffies - sd1->last_balance >= interval) {
+				/* Lets record this CPU as a possible target
+				 * to be woken up. Whether we actually wake it
+				 * up or not depends on the CPU's imbalance wrt
+				 * others in the domain.
+				 */
+				woken = 1;
+				cpu_set(i, *wakemaskp);
+			}
+#endif
 		}
 
 		total_load += avg_load;
@@ -2050,11 +2122,15 @@ static int load_balance(int this_cpu, ru
 	unsigned long imbalance;
 	int nr_moved, all_pinned = 0;
 	int active_balance = 0;
+	cpumask_t wakemask;
+#ifdef CONFIG_NO_IDLE_HZ
+	struct sched_domain *sd1;
+#endif
 
 	spin_lock(&this_rq->lock);
 	schedstat_inc(sd, lb_cnt[idle]);
 
-	group = find_busiest_group(sd, this_cpu, &imbalance, idle);
+	group = find_busiest_group(sd, this_cpu, &imbalance, idle, &wakemask);
 	if (!group) {
 		schedstat_inc(sd, lb_nobusyg[idle]);
 		goto out_balanced;
@@ -2130,9 +2206,11 @@ static int load_balance(int this_cpu, ru
 			sd->balance_interval *= 2;
 	}
 
-	return nr_moved;
+	goto out_nohz;
 
 out_balanced:
+	nr_moved = 0;
+
 	spin_unlock(&this_rq->lock);
 
 	schedstat_inc(sd, lb_balanced[idle]);
@@ -2143,7 +2221,36 @@ out_balanced:
 			(sd->balance_interval < sd->max_interval))
 		sd->balance_interval *= 2;
 
-	return 0;
+out_nohz:
+#ifdef CONFIG_NO_IDLE_HZ
+	if (!cpus_empty(wakemask)) {
+		int i;
+
+		/* Lets try to wakeup one CPU from the mask. Rest of the cpus
+		 * in the mask can be woken up by other CPUs when they do load
+		 * balancing in this domain. That way, the overhead of watchdog
+		 * functionality is spread across (non-idle) CPUs in the domain.
+		 */
+
+		for_each_cpu_mask(i, wakemask) {
+
+			sd1 = sched_domain_ptr(i, this_cpu, sd);
+
+			if (!sd1)
+				continue;
+
+			find_busiest_group(sd1, i, &imbalance, SCHED_IDLE,
+					   			NULL);
+			if (imbalance > 0) {
+				spin_lock(&cpu_rq(i)->lock);
+				resched_task(cpu_rq(i)->idle);
+				spin_unlock(&cpu_rq(i)->lock);
+				break;
+			}
+		}
+	}
+#endif
+	return nr_moved;
 }
 
 /*
@@ -2162,7 +2269,7 @@ static int load_balance_newidle(int this
 	int nr_moved = 0;
 
 	schedstat_inc(sd, lb_cnt[NEWLY_IDLE]);
-	group = find_busiest_group(sd, this_cpu, &imbalance, NEWLY_IDLE);
+	group = find_busiest_group(sd, this_cpu, &imbalance, NEWLY_IDLE, NULL);
 	if (!group) {
 		schedstat_inc(sd, lb_nobusyg[NEWLY_IDLE]);
 		goto out_balanced;
@@ -2323,6 +2430,39 @@ static void rebalance_tick(int this_cpu,
 		}
 	}
 }
+
+#ifdef CONFIG_NO_IDLE_HZ
+/*
+ * Try hard to pull tasks. Called by idle task before it sleeps cutting off
+ * local timer ticks.  This clears the various load counters and tries to pull
+ * tasks.
+ *
+ * Returns 1 if tasks were pulled over, 0 otherwise.
+ */
+int idle_balance_retry(void)
+{
+	int j, moved = 0, this_cpu = smp_processor_id();
+	runqueue_t *this_rq = this_rq();
+	unsigned long flags;
+
+	local_irq_save(flags);
+
+	for (j = 0; j < 3; j++)
+		this_rq->cpu_load[j] = 0;
+
+	rebalance_tick(this_cpu, this_rq, SCHED_IDLE);
+
+	if (this_rq->nr_running) {
+		moved = 1;
+		set_tsk_need_resched(current);
+	}
+
+	local_irq_restore(flags);
+
+	return moved;
+}
+#endif
+
 #else
 /*
  * on UP we do not need to balance between CPUs:
diff -puN include/linux/sched.h~sched-nohz include/linux/sched.h
--- linux-2.6.12-rc3-mm2/include/linux/sched.h~sched-nohz	2005-05-04 18:23:30.000000000 +0530
+++ linux-2.6.12-rc3-mm2-vatsa/include/linux/sched.h	2005-05-04 18:23:37.000000000 +0530
@@ -897,6 +897,7 @@ extern int task_curr(const task_t *p);
 extern int idle_cpu(int cpu);
 extern int sched_setscheduler(struct task_struct *, int, struct sched_param *);
 extern task_t *idle_task(int cpu);
+extern int idle_balance_retry(void);
 
 void yield(void);
 

_

-- 


Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017


-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Andi Kleen]

Srivatsa Vaddagiri <vatsa@in.ibm.com> writes:

> Hello,
> 	I need some inputs from the community (specifically from virtual
> machine and embedded/power-management folks) on something that I am working on.


I think the best way is to let other CPUs handle the load balancing
for idle CPUs. Basically when a CPU goes fully idle then you mark
this in some global data structure, and CPUs doing load balancing
after doing their own thing look for others that need to be balanced
too and handle them too. When no CPU is left non idle then nothing needs
to be load balanced anyways. When a idle CPU gets a task it just gets
an reschedule IPI as usual, that wakes it up. 

I call this the "scoreboard".

The trick is to evenly load balance the work over the remaining CPUs.
Something simple like never doing work for more than 1/idlecpus is
probably enough. In theory one could even use machine NUMA topology
information for this, but that would be probably overkill for the
first implementation.

With the scoreboard implementation CPus could be virtually idle
forever, which I think is best for virtualization.

BTW we need a very similar thing for RCU too.

-Andi


-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Andi Kleen]

Arjan van de Ven <arjan@infradead.org> writes:

> On Sun, 2005-05-08 at 13:50 +1000, Rusty Russell wrote:
>> My preference would be the second: fix the scheduler so it doesn't rely
>> on regular polling.  However, as long as the UP case runs with no timer
>> interrupts when idle, many people will be happy (eg. most embedded).
>
> alternatively; if a CPU is idle a long time we could do a software level
> hotunplug on it (after setting it to the lowest possible frequency and
> power state), and have some sort of thing that keeps track of "spare but
> unplugged" cpus that can plug cpus back in on demand.


We need to do this anyways for RCU, because fully idle CPUs don't go
through quiescent states and could stall the whole RCU system.

But it has to be *really* lightweight because these transistion can
happen a lot (consider a CPU that very often goes to sleep for a short time)
>
> That also be nice for all the virtual environments where this could
> interact with the hypervisor etc

I am not sure how useful it is to make this heavy weight by involving
more subsystems. I would try to keep the idle state as lightweight
as possible, to keep the cost of going to sleep/waking up low.

-Andi


-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Arjan van de Ven]

> But it has to be *really* lightweight because these transistion can
> happen a lot (consider a CPU that very often goes to sleep for a short time)

lightweight is good of course. But even if it's medium weight.. it just
means you need to be REALLY idle (eg for longer time) for it to trigger.
I guess we need some sort of per arch "idleness threshhold" for this.




-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Andi Kleen]

On Sun, May 08, 2005 at 03:44:14PM +0200, Arjan van de Ven wrote:
> 
> > But it has to be *really* lightweight because these transistion can
> > happen a lot (consider a CPU that very often goes to sleep for a short time)
> 
> lightweight is good of course. But even if it's medium weight.. it just
> means you need to be REALLY idle (eg for longer time) for it to trigger.
> I guess we need some sort of per arch "idleness threshhold" for this.

The question is how useful it is for the hypervisor to even know that.
Why can't it just detect long idle periods by itself if it really wants?

-Andi


-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Srivatsa Vaddagiri]

On Sun, May 08, 2005 at 03:31:00PM +0200, Andi Kleen wrote:
> I think the best way is to let other CPUs handle the load balancing
> for idle CPUs. Basically when a CPU goes fully idle then you mark
> this in some global data structure, 

nohz_cpu_mask already exists for this purpose.

> and CPUs doing load balancing after doing their own thing look for others 
> that need to be balanced too and handle them too. 

This is precisely what I had proposed in my watchdog implementation.

> When no CPU is left non idle then nothing needs to be load balanced anyways. 
> When a idle CPU gets a task it just gets an reschedule IPI as usual, that 
> wakes it up. 

True.

> 
> I call this the "scoreboard".
> 
> The trick is to evenly load balance the work over the remaining CPUs.
> Something simple like never doing work for more than 1/idlecpus is
> probably enough. 

Well, there is this imbalance_pct which acts as a trigger threshold before
which load balance won't happen.  I do take this into account before
waking up the sleeping idle cpu (the same imbalance_pct logic would 
have been followed by the idle CPU if it were to continue taking timer
ticks).

So I guess your 1/idlecpus and the imbalance_pct may act on parallel lines.

> In theory one could even use machine NUMA topology
> information for this, but that would be probably overkill for the
> first implementation.
> 
> With the scoreboard implementation CPus could be virtually idle
> forever, which I think is best for virtualization.
> 
> BTW we need a very similar thing for RCU too.

RCU is taken care of already, except it is broken. There is a small
race which is not fixed. Following patch (which I wrote aainst 2.6.10 kernel
maybe) should fix that race. I intend to post this patch after test
agaist more recent kernel.


--- kernel/rcupdate.c.org	2005-02-11 11:38:47.000000000 +0530
+++ kernel/rcupdate.c	2005-02-11 11:44:08.000000000 +0530
@@ -199,8 +199,11 @@ static void rcu_start_batch(struct rcu_c
  */
 static void cpu_quiet(int cpu, struct rcu_ctrlblk *rcp, struct rcu_state *rsp)
 {
+	cpumask_t tmpmask;
+
 	cpu_clear(cpu, rsp->cpumask);
-	if (cpus_empty(rsp->cpumask)) {
+	cpus_andnot(tmpmask, rsp->cpumask, nohz_cpu_mask);
+	if (cpus_empty(tmpmask)) {
 		/* batch completed ! */
 		rcp->completed = rcp->cur;
 		rcu_start_batch(rcp, rsp, 0);



-- 


Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017


-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Nick Piggin]

Srivatsa Vaddagiri wrote:
> On Sun, May 08, 2005 at 02:14:23PM +1000, Nick Piggin wrote:
> 
>>Yeah probably something around that order of magnitude. I suspect
>>there will fast be a point where either you'll get other timers
>>going off more frequently, and / or you simply get very quickly
>>diminishing returns on the amount of power saving gained from
>>increasing the period.
> 
> 
> I am looking at it from the other perspective also i.e, virtualized
> env. Any amount of unnecessary timer ticks will lead to equivalent amount
> of unnecessary context switches among the guest OSes.
> 

Yep.

> 
>>It is not so much a matter of "fixing" the scheduler as just adding
>>more heuristics. When are we too busy? When should we wake another
>>CPU? What if that CPU is an SMT sibling? What if it is across the
>>other side of the topology, and other CPUs closer to it are busy
>>as well? What if they're busy but not as busy as we are? etc.
>>
>>We've already got that covered in the existing periodic pull balancing,
>>so instead of duplicating this logic and moving this extra work to busy
>>CPUs, we can just use the existing framework.
> 
> 
> I don't think we have to duplicate the logic, just "reuse" whatever logic
> exists (in find_busiest_group etc). However I do agree there is movement

OK, that may possibly be an option... however:

> of extra work to busy CPUs, but that is only to help the idle CPU sleep longer.
> Whether it justifies the additional complexity or not is what this RFC is
> about I guess!
> 

Yeah, this is a bit worrying. In general we should not be loading
up busy CPUs with any more work, and sleeping idle CPUs should be
done as a blunt "slowpath" operation. Ie. something that works well
enough.

> FWIW, I have also made some modifications in the original proposal 
> for reducing the watchdog workload (instead of the same non-idle cpu waking 
> up all the sleeping CPUs it finds in the same rebalance_tick, the task
> is spread over multiple non-idle tasks in different rebalance_ticks).
> New (lightly tested) patch is in the mail below.
> 

Mmyeah, I'm not a big fan :)

I could probably find some time to do my implementation if you have
a complete working patch for eg. UML.

> 
> 
>>At least we should try method A first, and if that isn't good enough
>>(though I suspect it will be), then think about adding more complexity
>>to the scheduler.
> 
> 
> What would be good to measure between the two approaches is the CPU utilization 
> (over a period of time - say 10 hrs) of somewhat lightly loaded SMP guest OSes 
> (i.e some CPUs are idle and other CPUs of the same guest are not idle), when 
> multiple such guest OSes are running simultaneously on the same box.  This 
> means I need a port of VST to UML :(
> 

Yeah that would be good.

-- 
SUSE Labs, Novell Inc.




-------------------------------------------------------
This SF.Net email is sponsored by: NEC IT Guy Games.
Get your fingers limbered up and give it your best shot. 4 great events, 4
opportunities to win big! Highest score wins.NEC IT Guy Games. Play to
win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: [RFC] (How to) Let idle CPUs sleep

[Tony Lindgren]

* Nick Piggin <nickpiggin@yahoo.com.au> [050507 21:15]:
> Rusty Russell wrote:
> >On Sat, 2005-05-07 at 23:57 +0530, Srivatsa Vaddagiri wrote:
> >
> >>Two solutions have been proposed so far:
> >>
> >>	A. As per Nick's suggestion, impose a max limit (say some 100 ms or
> >>	   say a second, Nick?) on how long a idle CPU can avoid taking
> 
> Yeah probably something around that order of magnitude. I suspect
> there will fast be a point where either you'll get other timers
> going off more frequently, and / or you simply get very quickly
> diminishing returns on the amount of power saving gained from
> increasing the period.
> 
> >>	   local-timer ticks. As a result, the load imbalance could exist 
> >>	   only
> >>	   for this max duration, after which the sleeping CPU will wake up
> >>	   and balance itself. If there is no imbalance, it can go and sleep
> >>	   again for the max duration.
> >>
> >>	   For ex, lets say a idle CPU found that it doesn't have any near 
> >>	   timer
> >>	   for the next 1 minute. Instead of letting it sleep for 1 minute in
> >>	   a single stretch, we let it sleep in bursts of 100 msec (or 
> >>	   whatever
> >>	   is the max. duration chosen). This still is better than having
> >>	   the idle CPU take HZ ticks a second.
> >>
> >>	   As a special case, when all the CPUs of an image go idle, we
> >>	   could consider completely shutting off local timer ticks
> >>	   across all CPUs (till the next non-timer interrupt).
> >>
> >>
> >>	B. Don't impose any max limit on how long a idle CPU can sleep.
> >>	   Here we let the idle CPU sleep as long as it wants. It is
> >>	   woken up by a "busy" CPU when it detects an imbalance. The
> >>	   busy CPU acts as a watchdog here. If there are no such
> >>	   busy CPUs, then it means that nobody will acts as watchdogs
> >>	   and idle CPUs sleep as long as they want. A possible watchdog
> >>	   implementation has been discussed at:
> >>
> >>	http://marc.theaimsgroup.com/?l=linux-kernel&m=111287808905764&w=2
> >
> >
> >My preference would be the second: fix the scheduler so it doesn't rely
> >on regular polling.
> 
> It is not so much a matter of "fixing" the scheduler as just adding
> more heuristics. When are we too busy? When should we wake another
> CPU? What if that CPU is an SMT sibling? What if it is across the
> other side of the topology, and other CPUs closer to it are busy
> as well? What if they're busy but not as busy as we are? etc.
> 
> We've already got that covered in the existing periodic pull balancing,
> so instead of duplicating this logic and moving this extra work to busy
> CPUs, we can just use the existing framework.
> 
> At least we should try method A first, and if that isn't good enough
> (though I suspect it will be), then think about adding more complexity
> to the scheduler.
> 
> > However, as long as the UP case runs with no timer
> >interrupts when idle, many people will be happy (eg. most embedded).
> >
> 
> Well in the UP case, both A and B should basically degenerate to the
> same thing.
> 
> Probably the more important case for the scheduler is to be able to
> turn off idle SMP hypervisor clients, Srivatsa?

Sorry to jump in late. For embedded stuff we should be able to skip
ticks until something _really_ happens, like an interrupt.

So we need to be able to skip ticks several seconds at a time. Ticks
should be event driven. For embedded systems option B is really
the only way to go to take advantage of the power savings.

Of course the situation is different on servers, where the goal is
to save ticks to be able to run more virtual machines. And then
cutting down the ticks down to few per second does the trick.

Regards,

Tony


-------------------------------------------------------
This SF.Net email is sponsored by Oracle Space Sweepstakes
Want to be the first software developer in space?
Enter now for the Oracle Space Sweepstakes!
http://ads.osdn.com/?ad_id=7393&alloc_id=16281&op=click
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel