**Next message:**Lee Jones: "Re: [PATCH 3/9] ARM: ux500: Remove AB8500 regulator register initialisationinformation"**Previous message:**Paulo Marques: "Re: "Inconsistent kallsyms data" error"**In reply to:**Peter Zijlstra: "Re: [PATCH 09/16] sched: normalize tg load contributions againstrunnable time"**Next in thread:**Peter Zijlstra: "Re: [PATCH 09/16] sched: normalize tg load contributions againstrunnable time"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

On Wed, 2012-07-04 at 21:48 +0200, Peter Zijlstra wrote:

>

>

>

>

>

>

>

>

>

>

>

>

>

>

>

>

>

>

So if we treat the per-cpu utilization u_i as probability, then we're

looking for:

P(\Union_{i=1..n} u_i) :=

\Sum_{k=1..n} (-1)^(k-1) P(\Intersection_{i=1..k} u_i)

Computing this however is far too expensive, what we can do is

approximate by setting u = avg(u_i) and then using:

u_i == u_j for all i,j

and assuming all variables are independent, giving us:

P(A \Intersection B) = P(A)P(B)

This then yields:

P(\Union_{i=1..n} u_i) ~= \Sum_{k=1..n} (-1)^(k-1) (n choose k) u^k

Which unfortunately isn't a series I found a sane solution for, but

numerically (see below) we can see it very quickly approaches 1 when n

>

Therefore, the chosen approximation of min(1, \Sum_i u_i) is indeed a

sane approximation since for very small u_i and/or small n the sum is

less likely to exceed 1 and for big u_i and/or big n the clip to 1 is

indeed correct.

*phew*

Was this what you meant? :-)

Now all that is left is grok the actual code..

probability_union.bc

---

define f (x) {

if (x <= 1) return (1);

return (f(x-1) * x);

}

define choose (n,k) {

return f(n) / (f(n-k) * f(k));

}

define pu (p,n) {

auto s, k

s = 0;

for (k = 1; k <= n; k++) {

s += (-1)^(k-1) * choose(n,k) * p^k;

}

return s;

}

for (n=2; n<128; n*=2) {

print n, ": "

for (p = 1; p < 11; p++) {

print pu(p/10,n), " "

}

print "\n"

}

quit

--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

the body of a message to majordomo@xxxxxxxxxxxxxxx

More majordomo info at http://vger.kernel.org/majordomo-info.html

Please read the FAQ at http://www.tux.org/lkml/

**Next message:**Lee Jones: "Re: [PATCH 3/9] ARM: ux500: Remove AB8500 regulator register initialisationinformation"**Previous message:**Paulo Marques: "Re: "Inconsistent kallsyms data" error"**In reply to:**Peter Zijlstra: "Re: [PATCH 09/16] sched: normalize tg load contributions againstrunnable time"**Next in thread:**Peter Zijlstra: "Re: [PATCH 09/16] sched: normalize tg load contributions againstrunnable time"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]