linux-kernel - Re: [RFC] A new CPU load metric for power-efficient scheduler: CPU ConCurrency

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Tue, 29 Apr 2014 03:26:21 +0800
From:	Yuyang Du <yuyang.du@...el.com>
To:	Morten Rasmussen <morten.rasmussen@....com>
Cc:	"Rafael J. Wysocki" <rjw@...ysocki.net>,
	"mingo@...hat.com" <mingo@...hat.com>,
	"peterz@...radead.org" <peterz@...radead.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"linux-pm@...r.kernel.org" <linux-pm@...r.kernel.org>,
	"arjan.van.de.ven@...el.com" <arjan.van.de.ven@...el.com>,
	"len.brown@...el.com" <len.brown@...el.com>,
	"rafael.j.wysocki@...el.com" <rafael.j.wysocki@...el.com>,
	"alan.cox@...el.com" <alan.cox@...el.com>,
	"mark.gross@...el.com" <mark.gross@...el.com>,
	"vincent.guittot@...aro.org" <vincent.guittot@...aro.org>,
	"rajeev.d.muralidhar@...el.com" <rajeev.d.muralidhar@...el.com>,
	"vishwesh.m.rudramuni@...el.com" <vishwesh.m.rudramuni@...el.com>,
	"nicole.chalhoub@...el.com" <nicole.chalhoub@...el.com>,
	"ajaya.durg@...el.com" <ajaya.durg@...el.com>,
	"harinarayanan.seshadri@...el.com" <harinarayanan.seshadri@...el.com>,
	yuyang.du@...el.com
Subject: Re: [RFC] A new CPU load metric for power-efficient scheduler: CPU
 ConCurrency

> I'm a bit confused, do you have one global CC that tracks the number of
> tasks across all runqueues in the system or one for each cpu? There
> could be some contention when updating that value on larger systems if
> it one global CC. If they are separate, how do you then decide when to
> consolidate? 

Oh, we are getting down to business. Currently, CC is per CPU. To consolidate,
the formula is based on a heuristic. Because:

suppose we have 2 CPUs, their task concurrency over time is ('-' means no
task, 'x' having tasks):

1)
CPU0: ---xxxx---------- (CC[0])
CPU1: ---------xxxx---- (CC[1])

2)
CPU0: ---xxxx---------- (CC[0])
CPU1: ---xxxx---------- (CC[1])

If we consolidate CPU0 and CPU1, the consolidated CC will be: CC' = CC[0] +
CC[1] for case 1 and CC'' = (CC[0] + CC[1]) * 2 for case 2. For the cases
in between case 1 and 2 in terms of how xxx overlaps, the CC should be between
CC' and CC''. So, we uniformly use this condition to evaluate for
consolidation (suppose we consolidate m CPUs to n CPUs, m > n):

(CC[0] + CC[1] + ... + CC[m-2] + CC[m-1]) * (n + log(m-n)) >=<? (1 * n) * n *
consolidate_coefficient

The consolidate_coeffient could be like 100% or more or less.

> How do you determine your "f" parameter? How fast is the reaction time?
> If you have had a period of consolidation and have a bunch of tasks
> waking up at the same time. How long will it be until you spread the
> load to all cpus?

Per CPU vs. per task? This is really not about who is (more) informative or
not, or why not both or not. It is about when you have task concurrency and
CPU utilization at the same time, and you must make a fast decision right now,
then what? Actually, it is also about how I want to position the whole CC
fuss. CC and the associated CPU workload consolidation can be regarded as
another "layer" beneath the current sophisticated load balancing, such that
this layer senses globally how many CPUs are needed and then do whatever it is
currently supposed to do in the needed CPUs. I think this is only a design
choice that is effective but simpler and less intrusive to just realize
consolidation/packing.

> It seems to me that you are loosing some important information by
> tracking per cpu and not per task. Also, your load balance behaviour is
> very sensitive to the choice of decay factor. We have that issue with
> the runqueue load tracking already. It reacts very slowly to load
> changes, so it can't really be used for periodic load-balancing
> decisions.

The current halflife is 1 period, and the period was 32ms, and now 64ms for
more aggressive consolidation.

Thanks,
Yuyang
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/