This doc file has the programs to generate the constants to compute sched averages.
Signed-off-by: Yuyang Du <[email protected]> --- Documentation/scheduler/sched-avg.txt | 160 +++++++++++++++++++++++++++++++++ 1 file changed, 160 insertions(+) create mode 100644 Documentation/scheduler/sched-avg.txt diff --git a/Documentation/scheduler/sched-avg.txt b/Documentation/scheduler/sched-avg.txt new file mode 100644 index 0000000..55fe900 --- /dev/null +++ b/Documentation/scheduler/sched-avg.txt @@ -0,0 +1,160 @@ +============================================================== + C program: +============================================================== + +#include <math.h> +#include <stdio.h> + +#define HALFLIFE 32 +#define SHIFT 32 + +/* +print " #: yN_inv yN_sum" +print "-----------------------" +y = (0.5)**(1/32.0) +x = 2**32 +xx = 1024 +for i in range(0, 32): + if i == 0: + x = x-1 + xx = xx*y + else: + x = x*y + xx = int(xx*y + 1024*y) + print "%2d: %#x %8d" % (i, int(x), int(xx)) + +print " #: sum_N32" +print "------------" +xxx = xx +for i in range(0, 11): + if i == 0: + xxx = xx + else: + xxx = xxx/2 + xx + print "%2d: %8d" % (i, xxx) +*/ + +double y; + +void calc_decay_inv_multiply() { + int i; + unsigned int x; + + printf("static const u32 __decay_inv_multiply_N[] = {"); + for(i = 0; i < HALFLIFE; i++) { + x = ((1UL<<32)-1)*pow(y, i); + + if (i % 6 == 0) printf("\n\t"); + printf("0x%8x, ", x); + } + printf("\n};\n\n"); +} + +int sum = 1024; +void calc_accumulated_sum() { + int i; + + printf("static const u32 __accumulated_sum_N[] = {\n\t 0,"); + for(i = 1; i <= HALFLIFE; i++) { + if (i == 1) + sum *= y; + else + sum = sum*y + 1024*y; + + if (i % 11 == 0) printf("\n\t"); + printf("%5d,", sum); + } + printf("\n};\n\n"); +} + +int n = 1; +/* first period */ +long max = 1024; + +void calc_converged_max() { + long last = 0, y_inv = ((1UL<<32)-1)*y; + + for (; ; n++) { + if (n > 1) + max = ((max*y_inv)>>SHIFT) + 1024; + /* This is the same as */ + //max = max*y + 1024; + + if (last == max) + break; + + last = max; + } + n--; + printf("#define SCHED_AVG_HALFLIFE %d\n", HALFLIFE); + printf("#define SCHED_AVG_MAX %ld\n", max); + printf("#define SCHED_AVG_MAX_N %d\n\n", n); +} + +void calc_accumulated_sum_32() { + int i, x = sum; + + printf("static const u32 __accumulated_sum_N32[] = {\n\t 0,"); + for(i = 1; i <= n/HALFLIFE+1; i++) { + if (i > 1) + x = x/2 + sum; + + if (i % 6 == 0) printf("\n\t"); + printf("%6d,", x); + } + printf("\n};\n\n"); +} + +void main() { + y = pow(0.5, 1/(double)HALFLIFE); + + calc_decay_inv_multiply(); + calc_accumulated_sum(); + calc_converged_max(); + calc_accumulated_sum_32(); +} + +============================================================== + Python script if you speak snake +============================================================== + +#!/usr/bin/env python + +print " #: yN_inv yN_sum" +print "-----------------------" +y = (0.5)**(1/32.0) +x = 2**32 +xx = 1024 +for i in range(0, 32): + if i == 0: + x = x-1 + xx = xx*y + else: + x = x*y + xx = int(xx*y + 1024*y) + print "%2d: %#x %8d" % (i, int(x), int(xx)) + +print +print " #: sum_N32" +print "------------" +xxx = xx +for i in range(0, 11): + if i == 0: + xxx = xx + else: + xxx = xxx/2 + xx + print "%2d: %8d" % (i, xxx) + +print +print " n: max" +print "------------" +xxxx = 1024 +old = 0 +i = 2 +while (1): + xxxx = int(xxxx*y + 1024) + if old == xxxx: + break + i = i+1 + old = xxxx +print "%3d: %7d" % (i-1, xxxx) -- 1.7.9.5
