* Re: [patch] sched: auto-tuning task-migration
[not found] <200411110851.30819.habanero@us.ibm.com>
@ 2004-11-11 15:04 ` Andrew Theurer
0 siblings, 0 replies; 9+ messages in thread
From: Andrew Theurer @ 2004-11-11 15:04 UTC (permalink / raw)
To: linux-kernel; +Cc: kenneth.w.chen, Nick Piggin, mingo
> Ingo Molnar wrote on Wednesday, October 06, 2004 1:05 PM
>
> > could you try the replacement patch below - what results does it give?
>
> By the way, I wonder why you chose to round down, but not up.
>
>
> arch cache_decay_nsec: 10000000
> migration cost matrix (cache_size: 9437184, cpu: 1500 MHz):
> [00] [01] [02] [03]
> [00]: 9.1 8.5 8.5 8.5
> [01]: 8.5 9.1 8.5 8.5
> [02]: 8.5 8.5 9.1 8.5
> [03]: 8.5 8.5 8.5 9.1
> min_delta: 8909202
> using cache_decay nsec: 8909202 (8 msec)
I tried this patch on power5. This is a 2 node system, 2 chips (1 per node),
2 cores per chip, 2 siblings per core. Cores share and L2 & L3 cache.
Hard coding 1920KB for cache size (L2) I get:
migration cost matrix (cache_size: 1966080, cpu: 1656 MHz):
[00] [01] [02] [03] [04] [05] [06] [07]
[00]: 1.3 1.3 1.3 1.3 2.3 1.4 1.4 1.4
[01]: 1.3 1.4 1.3 1.3 1.4 1.4 1.4 1.4
[02]: 1.3 1.4 1.3 1.3 1.4 1.4 1.4 1.4
[03]: 1.4 1.4 1.4 1.3 1.4 1.4 1.4 1.4
[04]: 1.3 1.3 1.3 1.3 1.3 1.3 1.3 1.3
[05]: 1.3 1.4 1.3 1.3 1.3 1.4 1.4 1.3
[06]: 1.3 1.4 1.4 1.3 1.3 1.3 1.3 1.3
[07]: 1.3 1.3 1.3 1.3 1.3 1.4 1.3 1.3
min_delta: 1422824
using cache_decay nsec: 1422824 (1 msec)
I ran again for L3, but could not vmalloc the whole amount (cache is 36MB). I
tried 19200KB
and got:
migration cost matrix (cache_size: 19660800, cpu: 1656 MHz):
[00] [01] [02] [03] [04] [05] [06] [07]
[00]: 16.9 16.8 16.0 16.0 16.7 16.9 16.7 16.9
[01]: 16.0 17.1 16.0 16.0 16.8 16.9 16.7 16.9
[02]: 17.0 17.1 17.0 16.0 16.7 16.9 16.7 16.9
[03]: 17.0 17.1 16.0 16.0 16.7 16.9 16.8 16.9
[04]: 16.0 16.0 16.0 16.9 17.2 17.1 17.2 17.2
[05]: 16.0 16.0 16.0 16.9 17.2 17.2 17.2 17.2
[06]: 16.0 16.0 16.0 16.9 17.2 17.1 17.2 17.2
[07]: 16.0 16.0 16.0 16.9 17.2 17.1 17.2 17.1
min_delta: 17492688
using cache_decay nsec: 17492688 (16 msec)
First, I am going to assume this test is not designed to show effects of
shared cache. For power5, since cores on a same chip share L2 & L3, I would
conclude that cache_hot_time for level 0 (siblings in a core) and level 1
(cores in a chip) domains should probably be "0". For level 2 domains (all
chips in a system), I guess it needs to be somewhere above 16ms.
We had someone run that online transaction DB workload with 10ms
cache_hot_time on both level1 & 2 domains and performance regressed. If we
get a chance to run again, I will probably try level0: 0ms level1: 0ms
level2: 10-20ms.
-Andrew Theurer
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [patch] sched: auto-tuning task-migration
2004-10-06 13:29 ` [patch] sched: auto-tuning task-migration Ingo Molnar
2004-10-06 13:44 ` Nick Piggin
2004-10-06 17:49 ` Chen, Kenneth W
@ 2005-02-21 5:08 ` Paul Jackson
2 siblings, 0 replies; 9+ messages in thread
From: Paul Jackson @ 2005-02-21 5:08 UTC (permalink / raw)
To: Ingo Molnar; +Cc: kenneth.w.chen, linux-kernel, akpm, nickpiggin
A long long time ago (Oct 2004) Ingo wrote:
> the following patch adds a new feature to the scheduler: during bootup
> it measures migration costs and sets up cache_hot value accordingly.
Ingo - what became of this patch?
I made a quick search for it in Linus's bk tree and Andrew's *-mm
patches, but didn't find it. Perhaps I didn't know what to look for.
The metric it exposes looks like something I might want to expose to
userland, so the performance guys can begin optimizing the placement of
tasks on CPUs, depending on whether they would benefit from, or be
harmed by, sharing cache. Would the two halves of a hyper threaded core
show up as particularly close on this metric? I presume so.
It seems to me to be a good complement to the current cpu-memory
distance we have now in node_distance() exposing the ACPI 2.0 SLIT
table distances.
I view the two key numbers here as (1) how fast can a cpu get stuff out
of a memory node (an amalgam of bandwidth and latency), and (2) how much
cache and buses and such do two cpus share (which can be good or bad,
depending on whether the two tasks on those two cpus share much of their
cache footprint).
The SLIT table provides (1) just fine. Your patch seems to compute a
sensible estimate of (2).
I had one worry - was there a potential O(N**2) cost in computing this
at boottime, where N is the number of nodes? Us SGI folks are usually
amongst the first to notice such details, when they blow up on us ;).
I never actually saw the original patch -- perhaps if I had, some of
my questions above would have obvious answers.
Thanks. (and thanks for cpus_allowed -- I've practically made a
profession out of building stuff on top of that one ... ;).
--
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <pj@sgi.com> 1.650.933.1373, 1.925.600.0401
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [patch] sched: auto-tuning task-migration
2004-10-06 21:18 ` Chen, Kenneth W
@ 2004-10-07 6:10 ` Ingo Molnar
0 siblings, 0 replies; 9+ messages in thread
From: Ingo Molnar @ 2004-10-07 6:10 UTC (permalink / raw)
To: Chen, Kenneth W
Cc: linux-kernel, 'Andrew Morton', 'Nick Piggin'
* Chen, Kenneth W <kenneth.w.chen@intel.com> wrote:
> > could you try the replacement patch below - what results does it give?
>
> By the way, I wonder why you chose to round down, but not up.
what do you mean - the minimum search within the matrix?
Ingo
^ permalink raw reply [flat|nested] 9+ messages in thread
* RE: [patch] sched: auto-tuning task-migration
2004-10-06 20:04 ` Ingo Molnar
@ 2004-10-06 21:18 ` Chen, Kenneth W
2004-10-07 6:10 ` Ingo Molnar
0 siblings, 1 reply; 9+ messages in thread
From: Chen, Kenneth W @ 2004-10-06 21:18 UTC (permalink / raw)
To: 'Ingo Molnar'
Cc: linux-kernel, 'Andrew Morton', 'Nick Piggin'
Ingo Molnar wrote on Wednesday, October 06, 2004 1:05 PM
> could you try the replacement patch below - what results does it give?
By the way, I wonder why you chose to round down, but not up.
arch cache_decay_nsec: 10000000
migration cost matrix (cache_size: 9437184, cpu: 1500 MHz):
[00] [01] [02] [03]
[00]: 9.1 8.5 8.5 8.5
[01]: 8.5 9.1 8.5 8.5
[02]: 8.5 8.5 9.1 8.5
[03]: 8.5 8.5 8.5 9.1
min_delta: 8909202
using cache_decay nsec: 8909202 (8 msec)
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [patch] sched: auto-tuning task-migration
2004-10-06 17:49 ` Chen, Kenneth W
@ 2004-10-06 20:04 ` Ingo Molnar
2004-10-06 21:18 ` Chen, Kenneth W
0 siblings, 1 reply; 9+ messages in thread
From: Ingo Molnar @ 2004-10-06 20:04 UTC (permalink / raw)
To: Chen, Kenneth W
Cc: linux-kernel, 'Andrew Morton', 'Nick Piggin'
* Chen, Kenneth W <kenneth.w.chen@intel.com> wrote:
> Ran it on a similar system. Below is the output. Haven't tried to
> get a real benchmark run with 42 ms cache_hot_time. I don't think it
> will get peak throughput as we already start tapering off at 12.5 ms.
> arch cache_decay_nsec: 10000000
> migration cost matrix (cache_size: 9437184, cpu: 1500 MHz):
> [00] [01] [02] [03]
> [00]: 50.2 42.8 42.9 42.8
> [01]: 42.9 50.2 42.1 42.9
> [02]: 42.9 42.9 50.2 42.8
> [03]: 42.9 42.9 42.9 50.2
> min_delta: 44785782
> using cache_decay nsec: 44785782 (42 msec)
could you try the replacement patch below - what results does it give?
Ingo
--- linux/kernel/sched.c.orig
+++ linux/kernel/sched.c
@@ -388,7 +388,7 @@ struct sched_domain {
.max_interval = 4, \
.busy_factor = 64, \
.imbalance_pct = 125, \
- .cache_hot_time = (5*1000000/2), \
+ .cache_hot_time = cache_decay_nsec, \
.cache_nice_tries = 1, \
.per_cpu_gain = 100, \
.flags = SD_BALANCE_NEWIDLE \
@@ -410,7 +410,7 @@ struct sched_domain {
.max_interval = 32, \
.busy_factor = 32, \
.imbalance_pct = 125, \
- .cache_hot_time = (10*1000000), \
+ .cache_hot_time = cache_decay_nsec, \
.cache_nice_tries = 1, \
.per_cpu_gain = 100, \
.flags = SD_BALANCE_EXEC \
@@ -4420,11 +4420,232 @@ __init static void init_sched_build_grou
last->next = first;
}
-__init static void arch_init_sched_domains(void)
+/*
+ * Task migration cost measurement between source and target CPUs.
+ *
+ * This is done by measuring the worst-case cost. Here are the
+ * steps that are taken:
+ *
+ * 1) the source CPU dirties its L2 cache with a shared buffer
+ * 2) the target CPU dirties its L2 cache with a local buffer
+ * 3) the target CPU dirties the shared buffer
+ *
+ * We measure the time step #3 takes - this is the cost of migrating
+ * a cache-hot task that has a large, dirty dataset in the L2 cache,
+ * to another CPU.
+ */
+
+
+/*
+ * Dirty a big buffer in a hard-to-predict (for the L2 cache) way. This
+ * is the operation that is timed, so we try to generate unpredictable
+ * cachemisses that still end up filling the L2 cache:
+ */
+__init static void fill_cache(void *__cache, unsigned long __size)
{
+ unsigned long size = __size/sizeof(long);
+ unsigned long *cache = __cache;
+ unsigned long data = 0xdeadbeef;
int i;
+
+ for (i = 0; i < size/4; i++) {
+ if ((i & 3) == 0)
+ cache[i] = data;
+ if ((i & 3) == 1)
+ cache[size-1-i] = data;
+ if ((i & 3) == 2)
+ cache[size/2-i] = data;
+ if ((i & 3) == 3)
+ cache[size/2+i] = data;
+ }
+}
+
+struct flush_data {
+ unsigned long source, target;
+ void (*fn)(void *, unsigned long);
+ void *cache;
+ void *local_cache;
+ unsigned long size;
+ unsigned long long delta;
+};
+
+/*
+ * Dirty L2 on the source CPU:
+ */
+__init static void source_handler(void *__data)
+{
+ struct flush_data *data = __data;
+
+ if (smp_processor_id() != data->source)
+ return;
+
+ memset(data->cache, 0, data->size);
+}
+
+/*
+ * Dirty the L2 cache on this CPU and then access the shared
+ * buffer. (which represents the working set of the migrated task.)
+ */
+__init static void target_handler(void *__data)
+{
+ struct flush_data *data = __data;
+ unsigned long long t0, t1;
+ unsigned long flags;
+
+ if (smp_processor_id() != data->target)
+ return;
+
+ memset(data->local_cache, 0, data->size);
+ local_irq_save(flags);
+ t0 = sched_clock();
+ fill_cache(data->cache, data->size);
+ t1 = sched_clock();
+ local_irq_restore(flags);
+
+ data->delta = t1 - t0;
+}
+
+/*
+ * Measure the cache-cost of one task migration:
+ */
+__init static unsigned long long measure_one(void *cache, unsigned long size,
+ int source, int target)
+{
+ struct flush_data data;
+ unsigned long flags;
+ void *local_cache;
+
+ local_cache = vmalloc(size);
+ if (!local_cache) {
+ printk("couldnt allocate local cache ...\n");
+ return 0;
+ }
+ memset(local_cache, 0, size);
+
+ local_irq_save(flags);
+ local_irq_enable();
+
+ data.source = source;
+ data.target = target;
+ data.size = size;
+ data.cache = cache;
+ data.local_cache = local_cache;
+
+ if (on_each_cpu(source_handler, &data, 1, 1) != 0) {
+ printk("measure_one: timed out waiting for other CPUs\n");
+ local_irq_restore(flags);
+ return -1;
+ }
+ if (on_each_cpu(target_handler, &data, 1, 1) != 0) {
+ printk("measure_one: timed out waiting for other CPUs\n");
+ local_irq_restore(flags);
+ return -1;
+ }
+
+ vfree(local_cache);
+
+ return data.delta;
+}
+
+__initdata unsigned long sched_cache_size;
+
+/*
+ * Measure a series of task migrations and return the maximum
+ * result - the worst-case. Since this code runs early during
+ * bootup the system is 'undisturbed' and the maximum latency
+ * makes sense.
+ *
+ * As the working set we use 2.1 times the L2 cache size, this is
+ * chosen in such a nonsymmetric way so that fill_cache() doesnt
+ * iterate at power-of-2 boundaries (which might hit cache mapping
+ * artifacts and pessimise the results).
+ */
+__init static unsigned long long measure_cacheflush_time(int cpu1, int cpu2)
+{
+ unsigned long size = sched_cache_size*21/10;
+ unsigned long long delta, max = 0;
+ void *cache;
+ int i;
+
+ if (!size) {
+ printk("arch has not set cachesize - using default.\n");
+ return 0;
+ }
+ if (!cpu_online(cpu1) || !cpu_online(cpu2)) {
+ printk("cpu %d and %d not both online!\n", cpu1, cpu2);
+ return 0;
+ }
+ cache = vmalloc(size);
+ if (!cache) {
+ printk("could not vmalloc %ld bytes for cache!\n", size);
+ return 0;
+ }
+ memset(cache, 0, size);
+ for (i = 0; i < 20; i++) {
+ delta = measure_one(cache, size, cpu1, cpu2);
+ if (delta > max)
+ max = delta;
+ }
+
+ vfree(cache);
+
+ /*
+ * A task is considered 'cache cold' if at least 2 times
+ * the worst-case cost of migration has passed.
+ * (this limit is only listened to if the load-balancing
+ * situation is 'nice' - if there is a large imbalance we
+ * ignore it for the sake of CPU utilization and
+ * processing fairness.)
+ *
+ * (We use 2.1 times the L2 cachesize in our measurement,
+ * we keep this factor when returning.)
+ */
+ return max;
+}
+
+__initdata static unsigned long long cache_decay_nsec;
+
+__init static void arch_init_sched_domains(void)
+{
+ int i, cpu1 = -1, cpu2 = -1;
+ unsigned long long min_delta = -1ULL;
+
cpumask_t cpu_default_map;
+ printk("arch cache_decay_nsec: %ld\n", cache_decay_ticks*1000000);
+ printk("migration cost matrix (cache_size: %ld, cpu: %ld MHz):\n",
+ sched_cache_size, cpu_khz/1000);
+ printk(" ");
+ for (cpu1 = 0; cpu1 < NR_CPUS; cpu1++) {
+ if (!cpu_online(cpu1))
+ continue;
+ printk(" [%02d]", cpu1);
+ }
+ printk("\n");
+ for (cpu1 = 0; cpu1 < NR_CPUS; cpu1++) {
+ if (!cpu_online(cpu1))
+ continue;
+ printk("[%02d]: ", cpu1);
+ for (cpu2 = 0; cpu2 < NR_CPUS; cpu2++) {
+ unsigned long long delta;
+
+ if (!cpu_online(cpu2))
+ continue;
+ delta = measure_cacheflush_time(cpu1, cpu2);
+
+ printk(" %3Ld.%ld", delta >> 20,
+ (((long)delta >> 10) / 102) % 10);
+ if ((cpu1 != cpu2) && (delta < min_delta))
+ min_delta = delta;
+ }
+ printk("\n");
+ }
+ printk("min_delta: %Ld\n", min_delta);
+ if (min_delta != -1ULL)
+ cache_decay_nsec = min_delta;
+ printk("using cache_decay nsec: %Ld (%Ld msec)\n",
+ cache_decay_nsec, cache_decay_nsec >> 20);
+
/*
* Setup mask for cpus without special case scheduling requirements.
* For now this just excludes isolated cpus, but could be used to
--- linux/arch/i386/kernel/smpboot.c.orig
+++ linux/arch/i386/kernel/smpboot.c
@@ -849,6 +849,8 @@ static int __init do_boot_cpu(int apicid
cycles_t cacheflush_time;
unsigned long cache_decay_ticks;
+extern unsigned long sched_cache_size;
+
static void smp_tune_scheduling (void)
{
unsigned long cachesize; /* kB */
@@ -879,6 +881,7 @@ static void smp_tune_scheduling (void)
}
cacheflush_time = (cpu_khz>>10) * (cachesize<<10) / bandwidth;
+ sched_cache_size = cachesize * 1024;
}
cache_decay_ticks = (long)cacheflush_time/cpu_khz + 1;
^ permalink raw reply [flat|nested] 9+ messages in thread
* RE: [patch] sched: auto-tuning task-migration
2004-10-06 13:29 ` [patch] sched: auto-tuning task-migration Ingo Molnar
2004-10-06 13:44 ` Nick Piggin
@ 2004-10-06 17:49 ` Chen, Kenneth W
2004-10-06 20:04 ` Ingo Molnar
2005-02-21 5:08 ` Paul Jackson
2 siblings, 1 reply; 9+ messages in thread
From: Chen, Kenneth W @ 2004-10-06 17:49 UTC (permalink / raw)
To: 'Ingo Molnar'
Cc: linux-kernel, 'Andrew Morton', 'Nick Piggin'
Ingo Molnar wrote on Wednesday, October 06, 2004 6:30 AM
> the following patch adds a new feature to the scheduler: during bootup
> it measures migration costs and sets up cache_hot value accordingly.
>
> could you try this patch on your testbox and send me the bootlog? How
> close does this method get us to the 10 msec value you measured to be
> close to the best value? The patch is against 2.6.9-rc3 + the last
> cache_hot fixpatch you tried.
Ran it on a similar system. Below is the output. Haven't tried to get a
real benchmark run with 42 ms cache_hot_time. I don't think it will get
peak throughput as we already start tapering off at 12.5 ms.
task migration cache decay timeout: 10 msecs.
CPU 1: base freq=199.458MHz, ITC ratio=15/2, ITC freq=1495.941MHz+/--1ppm
CPU 2: base freq=199.458MHz, ITC ratio=15/2, ITC freq=1495.941MHz+/--1ppm
CPU 3: base freq=199.458MHz, ITC ratio=15/2, ITC freq=1495.941MHz+/--1ppm
Calibrating delay loop... 2232.84 BogoMIPS (lpj=1089536)
Brought up 4 CPUs
Total of 4 processors activated (8939.60 BogoMIPS).
arch cache_decay_nsec: 10000000
migration cost matrix (cache_size: 9437184, cpu: 1500 MHz):
[00] [01] [02] [03]
[00]: 50.2 42.8 42.9 42.8
[01]: 42.9 50.2 42.1 42.9
[02]: 42.9 42.9 50.2 42.8
[03]: 42.9 42.9 42.9 50.2
min_delta: 44785782
using cache_decay nsec: 44785782 (42 msec)
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [patch] sched: auto-tuning task-migration
@ 2004-10-06 14:22 emmanuel.fuste
0 siblings, 0 replies; 9+ messages in thread
From: emmanuel.fuste @ 2004-10-06 14:22 UTC (permalink / raw)
To: linux-kernel
>the following patch adds a new feature to the scheduler:
during >bootup
>it measures migration costs and sets up cache_hot value
>accordingly.
>
>The measurement is point-to-point, i.e. it can be used to measure
>the
>migration costs in cache hierarchies - e.g. by NUMA setup
code. >The
>patch prints out a matrix of migration costs between CPUs.
>(self-migration means pure cache dirtying cost)
Hi Ingo,
Is your auto-tunig patch is supposed to work on a shared L2
cache arch like my i586 SMP system ?
Just to know.
Thanks.
E.F.
Accédez au courrier électronique de La Poste : www.laposte.net ;
3615 LAPOSTENET (0,34/mn) ; tél : 08 92 68 13 50 (0,34/mn)
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [patch] sched: auto-tuning task-migration
2004-10-06 13:29 ` [patch] sched: auto-tuning task-migration Ingo Molnar
@ 2004-10-06 13:44 ` Nick Piggin
2004-10-06 17:49 ` Chen, Kenneth W
2005-02-21 5:08 ` Paul Jackson
2 siblings, 0 replies; 9+ messages in thread
From: Nick Piggin @ 2004-10-06 13:44 UTC (permalink / raw)
To: Ingo Molnar; +Cc: Chen, Kenneth W, linux-kernel, 'Andrew Morton'
Ingo Molnar wrote:
> * Chen, Kenneth W <kenneth.w.chen@intel.com> wrote:
>
>
>>Since we are talking about load balancing, we decided to measure
>>various value for cache_hot_time variable to see how it affects app
>>performance. We first establish baseline number with vanilla base
>>kernel (default at 2.5ms), then sweep that variable up to 1000ms. All
>>of the experiments are done with Ingo's patch posted earlier. Here
>>are the result (test environment is 4-way SMP machine, 32 GB memory,
>>500 disks running industry standard db transaction processing
>>workload):
>>
>>cache_hot_time | workload throughput
>>--------------------------------------
>> 2.5ms - 100.0 (0% idle)
>> 5ms - 106.0 (0% idle)
>> 10ms - 112.5 (1% idle)
>> 15ms - 111.6 (3% idle)
>> 25ms - 111.1 (5% idle)
>> 250ms - 105.6 (7% idle)
>> 1000ms - 105.4 (7% idle)
>
>
> the following patch adds a new feature to the scheduler: during bootup
> it measures migration costs and sets up cache_hot value accordingly.
>
> The measurement is point-to-point, i.e. it can be used to measure the
> migration costs in cache hierarchies - e.g. by NUMA setup code. The
> patch prints out a matrix of migration costs between CPUs.
> (self-migration means pure cache dirtying cost)
>
> Here are a couple of matrixes from testsystems:
>
> A 2-way Celeron/128K box:
>
> arch cache_decay_nsec: 1000000
> migration cost matrix (cache_size: 131072, cpu: 467 MHz):
> [00] [01]
> [00]: 9.6 12.0
> [01]: 12.2 9.8
> min_delta: 12586890
> using cache_decay nsec: 12586890 (12 msec)
>
> a 2-way/4-way P4/512K HT box:
>
> arch cache_decay_nsec: 2000000
> migration cost matrix (cache_size: 524288, cpu: 2379 MHz):
> [00] [01] [02] [03]
> [00]: 6.1 6.1 5.7 6.1
> [01]: 6.7 6.2 6.7 6.2
> [02]: 5.9 5.9 6.1 5.0
> [03]: 6.7 6.2 6.7 6.2
> min_delta: 6053016
> using cache_decay nsec: 6053016 (5 msec)
>
> an 8-way P3/2MB Xeon box:
>
> arch cache_decay_nsec: 6000000
> migration cost matrix (cache_size: 2097152, cpu: 700 MHz):
> [00] [01] [02] [03] [04] [05] [06] [07]
> [00]: 92.1 184.8 184.8 184.8 184.9 90.7 90.6 90.7
> [01]: 181.3 92.7 88.5 88.6 88.5 181.5 181.3 181.4
> [02]: 181.4 88.4 92.5 88.4 88.5 181.4 181.3 181.4
> [03]: 181.4 88.4 88.5 92.5 88.4 181.5 181.2 181.4
> [04]: 181.4 88.5 88.4 88.4 92.5 181.5 181.3 181.5
> [05]: 87.2 181.5 181.4 181.5 181.4 90.0 87.0 87.1
> [06]: 87.2 181.5 181.4 181.5 181.4 87.9 90.0 87.1
> [07]: 87.2 181.5 181.4 181.5 181.4 87.9 87.0 90.0
> min_delta: 91815564
> using cache_decay nsec: 91815564 (87 msec)
>
Very cool. I reckon you may want to make the final number
non linear if possible, because a 2MB cache probably doesn't
need double the cache decay time of a 1MB cache.
And possible things need to be tuned a bit, eg. 12ms for the
128K celeron may be a bit large (even though it does have a
slow bus).
But this is a nice starting point.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [patch] sched: auto-tuning task-migration
2004-10-06 0:42 Default cache_hot_time value back to 10ms Chen, Kenneth W
@ 2004-10-06 13:29 ` Ingo Molnar
2004-10-06 13:44 ` Nick Piggin
` (2 more replies)
0 siblings, 3 replies; 9+ messages in thread
From: Ingo Molnar @ 2004-10-06 13:29 UTC (permalink / raw)
To: Chen, Kenneth W
Cc: linux-kernel, 'Andrew Morton', 'Nick Piggin'
* Chen, Kenneth W <kenneth.w.chen@intel.com> wrote:
> Since we are talking about load balancing, we decided to measure
> various value for cache_hot_time variable to see how it affects app
> performance. We first establish baseline number with vanilla base
> kernel (default at 2.5ms), then sweep that variable up to 1000ms. All
> of the experiments are done with Ingo's patch posted earlier. Here
> are the result (test environment is 4-way SMP machine, 32 GB memory,
> 500 disks running industry standard db transaction processing
> workload):
>
> cache_hot_time | workload throughput
> --------------------------------------
> 2.5ms - 100.0 (0% idle)
> 5ms - 106.0 (0% idle)
> 10ms - 112.5 (1% idle)
> 15ms - 111.6 (3% idle)
> 25ms - 111.1 (5% idle)
> 250ms - 105.6 (7% idle)
> 1000ms - 105.4 (7% idle)
the following patch adds a new feature to the scheduler: during bootup
it measures migration costs and sets up cache_hot value accordingly.
The measurement is point-to-point, i.e. it can be used to measure the
migration costs in cache hierarchies - e.g. by NUMA setup code. The
patch prints out a matrix of migration costs between CPUs.
(self-migration means pure cache dirtying cost)
Here are a couple of matrixes from testsystems:
A 2-way Celeron/128K box:
arch cache_decay_nsec: 1000000
migration cost matrix (cache_size: 131072, cpu: 467 MHz):
[00] [01]
[00]: 9.6 12.0
[01]: 12.2 9.8
min_delta: 12586890
using cache_decay nsec: 12586890 (12 msec)
a 2-way/4-way P4/512K HT box:
arch cache_decay_nsec: 2000000
migration cost matrix (cache_size: 524288, cpu: 2379 MHz):
[00] [01] [02] [03]
[00]: 6.1 6.1 5.7 6.1
[01]: 6.7 6.2 6.7 6.2
[02]: 5.9 5.9 6.1 5.0
[03]: 6.7 6.2 6.7 6.2
min_delta: 6053016
using cache_decay nsec: 6053016 (5 msec)
an 8-way P3/2MB Xeon box:
arch cache_decay_nsec: 6000000
migration cost matrix (cache_size: 2097152, cpu: 700 MHz):
[00] [01] [02] [03] [04] [05] [06] [07]
[00]: 92.1 184.8 184.8 184.8 184.9 90.7 90.6 90.7
[01]: 181.3 92.7 88.5 88.6 88.5 181.5 181.3 181.4
[02]: 181.4 88.4 92.5 88.4 88.5 181.4 181.3 181.4
[03]: 181.4 88.4 88.5 92.5 88.4 181.5 181.2 181.4
[04]: 181.4 88.5 88.4 88.4 92.5 181.5 181.3 181.5
[05]: 87.2 181.5 181.4 181.5 181.4 90.0 87.0 87.1
[06]: 87.2 181.5 181.4 181.5 181.4 87.9 90.0 87.1
[07]: 87.2 181.5 181.4 181.5 181.4 87.9 87.0 90.0
min_delta: 91815564
using cache_decay nsec: 91815564 (87 msec)
(btw., this matrix shows nicely the 0,5,6,7/1,2,3,4 grouping of quads in
this semi-NUMA 8-way box.)
could you try this patch on your testbox and send me the bootlog? How
close does this method get us to the 10 msec value you measured to be
close to the best value? The patch is against 2.6.9-rc3 + the last
cache_hot fixpatch you tried.
the patch contains comments that explain how migration costs are
measured.
(NOTE: sched_cache_size is only filled in for x86 at the moment, so if
you have another architecture then please add those two lines to that
architecture's smpboot.c.)
this is only the first release of the patch - obviously we cannot print
such a matrix for 1024 CPUs. But this should be good enough for testing
purposes.
Ingo
--- linux/kernel/sched.c.orig
+++ linux/kernel/sched.c
@@ -388,7 +388,7 @@ struct sched_domain {
.max_interval = 4, \
.busy_factor = 64, \
.imbalance_pct = 125, \
- .cache_hot_time = (5*1000000/2), \
+ .cache_hot_time = cache_decay_nsec, \
.cache_nice_tries = 1, \
.per_cpu_gain = 100, \
.flags = SD_BALANCE_NEWIDLE \
@@ -410,7 +410,7 @@ struct sched_domain {
.max_interval = 32, \
.busy_factor = 32, \
.imbalance_pct = 125, \
- .cache_hot_time = (10*1000000), \
+ .cache_hot_time = cache_decay_nsec, \
.cache_nice_tries = 1, \
.per_cpu_gain = 100, \
.flags = SD_BALANCE_EXEC \
@@ -4420,11 +4420,233 @@ __init static void init_sched_build_grou
last->next = first;
}
-__init static void arch_init_sched_domains(void)
+/*
+ * Task migration cost measurement between source and target CPUs.
+ *
+ * This is done by measuring the worst-case cost. Here are the
+ * steps that are taken:
+ *
+ * 1) the source CPU dirties its L2 cache with a shared buffer
+ * 2) the target CPU dirties its L2 cache with a local buffer
+ * 3) the target CPU dirties the shared buffer
+ *
+ * We measure the time step #3 takes - this is the cost of migrating
+ * a cache-hot task that has a large, dirty dataset in the L2 cache,
+ * to another CPU.
+ */
+
+
+/*
+ * Dirty a big buffer in a hard-to-predict (for the L2 cache) way. This
+ * is the operation that is timed, so we try to generate unpredictable
+ * cachemisses that still end up filling the L2 cache:
+ */
+static void fill_cache(void *__cache, unsigned long __size)
{
+ unsigned long size = __size/sizeof(long);
+ unsigned long *cache = __cache;
+ unsigned long data = 0xdeadbeef;
int i;
+
+ for (i = 0; i < size/4; i++) {
+ if ((i & 3) == 0)
+ cache[i] = data;
+ if ((i & 3) == 1)
+ cache[size-1-i] = data;
+ if ((i & 3) == 2)
+ cache[size/2-i] = data;
+ if ((i & 3) == 3)
+ cache[size/2+i] = data;
+ }
+}
+
+struct flush_data {
+ unsigned long source, target;
+ void (*fn)(void *, unsigned long);
+ void *cache;
+ void *local_cache;
+ unsigned long size;
+ unsigned long long delta;
+};
+
+/*
+ * Dirty L2 on the source CPU:
+ */
+static void source_handler(void *__data)
+{
+ struct flush_data *data = __data;
+
+ if (smp_processor_id() != data->source)
+ return;
+
+ memset(data->cache, 0, data->size);
+}
+
+/*
+ * Dirty the L2 cache on this CPU and then access the shared
+ * buffer. (which represents the working set of the migrated task.)
+ */
+static void target_handler(void *__data)
+{
+ struct flush_data *data = __data;
+ unsigned long long t0, t1;
+ unsigned long flags;
+
+ if (smp_processor_id() != data->target)
+ return;
+
+ memset(data->local_cache, 0, data->size);
+ local_irq_save(flags);
+ t0 = sched_clock();
+ fill_cache(data->cache, data->size);
+ t1 = sched_clock();
+ local_irq_restore(flags);
+
+ data->delta = t1 - t0;
+}
+
+/*
+ * Measure the cache-cost of one task migration:
+ */
+static unsigned long long measure_one(void *cache, unsigned long size,
+ int source, int target)
+{
+ struct flush_data data;
+ unsigned long flags;
+ void *local_cache;
+
+ local_cache = vmalloc(size);
+ if (!local_cache) {
+ printk("couldnt allocate local cache ...\n");
+ return 0;
+ }
+ memset(local_cache, 0, size);
+
+ local_irq_save(flags);
+ local_irq_enable();
+
+ data.source = source;
+ data.target = target;
+ data.size = size;
+ data.cache = cache;
+ data.local_cache = local_cache;
+
+ if (on_each_cpu(source_handler, &data, 1, 1) != 0) {
+ printk("measure_one: timed out waiting for other CPUs\n");
+ local_irq_restore(flags);
+ return -1;
+ }
+ if (on_each_cpu(target_handler, &data, 1, 1) != 0) {
+ printk("measure_one: timed out waiting for other CPUs\n");
+ local_irq_restore(flags);
+ return -1;
+ }
+
+ vfree(local_cache);
+
+ return data.delta;
+}
+
+unsigned long sched_cache_size;
+
+/*
+ * Measure a series of task migrations and return the maximum
+ * result - the worst-case. Since this code runs early during
+ * bootup the system is 'undisturbed' and the maximum latency
+ * makes sense.
+ *
+ * As the working set we use 1.66 times the L2 cache size, this is
+ * chosen in such a nonsymmetric way so that fill_cache() doesnt
+ * iterate at power-of-2 boundaries (which might hit cache mapping
+ * artifacts and pessimise the results).
+ */
+static __init unsigned long long measure_cacheflush_time(int cpu1, int cpu2)
+{
+ unsigned long size = sched_cache_size*5/3;
+ unsigned long long delta, max = 0;
+ void *cache;
+ int i;
+
+ if (!size) {
+ printk("arch has not set cachesize - using default.\n");
+ return 0;
+ }
+ if (!cpu_online(cpu1) || !cpu_online(cpu2)) {
+ printk("cpu %d and %d not both online!\n", cpu1, cpu2);
+ return 0;
+ }
+ cache = vmalloc(size);
+ if (!cache) {
+ printk("could not vmalloc %ld bytes for cache!\n", size);
+ return 0;
+ }
+ memset(cache, 0, size);
+ for (i = 0; i < 20; i++) {
+ delta = measure_one(cache, size, cpu1, cpu2);
+ if (delta > max)
+ max = delta;
+ }
+
+ vfree(cache);
+
+ /*
+ * A task is considered 'cache cold' if at least 10 times
+ * the cost of migration has passed. I.e. in the rare and
+ * absolutely worst-case we should see a 10% degradation
+ * due to migration. (this limit is only listened to if the
+ * load-balancing situation is 'nice' - if there is a large
+ * imbalance we ignore it for the sake of CPU utilization and
+ * processing fairness.)
+ *
+ * (We use 5/3 times the L2 cachesize in our measurement,
+ * hence factor 6 here: 10 == 6*5/3.)
+ */
+ return max * 6;
+}
+
+static unsigned long long cache_decay_nsec;
+
+__init static void arch_init_sched_domains(void)
+{
+ int i, cpu1 = -1, cpu2 = -1;
+ unsigned long long min_delta = -1ULL;
+
cpumask_t cpu_default_map;
+ printk("arch cache_decay_nsec: %ld\n", cache_decay_ticks*1000000);
+ printk("migration cost matrix (cache_size: %ld, cpu: %ld MHz):\n",
+ sched_cache_size, cpu_khz/1000);
+ printk(" ");
+ for (cpu1 = 0; cpu1 < NR_CPUS; cpu1++) {
+ if (!cpu_online(cpu1))
+ continue;
+ printk(" [%02d]", cpu1);
+ }
+ printk("\n");
+ for (cpu1 = 0; cpu1 < NR_CPUS; cpu1++) {
+ if (!cpu_online(cpu1))
+ continue;
+ printk("[%02d]: ", cpu1);
+ for (cpu2 = 0; cpu2 < NR_CPUS; cpu2++) {
+ unsigned long long delta;
+
+ if (!cpu_online(cpu2))
+ continue;
+ delta = measure_cacheflush_time(cpu1, cpu2);
+
+ printk(" %3Ld.%ld", delta >> 20,
+ (((long)delta >> 10) / 102) % 10);
+ if ((cpu1 != cpu2) && (delta < min_delta))
+ min_delta = delta;
+ }
+ printk("\n");
+ }
+ printk("min_delta: %Ld\n", min_delta);
+ if (min_delta != -1ULL)
+ cache_decay_nsec = min_delta;
+ printk("using cache_decay nsec: %Ld (%Ld msec)\n",
+ cache_decay_nsec, cache_decay_nsec >> 20);
+
/*
* Setup mask for cpus without special case scheduling requirements.
* For now this just excludes isolated cpus, but could be used to
--- linux/arch/i386/kernel/smpboot.c.orig
+++ linux/arch/i386/kernel/smpboot.c
@@ -849,6 +849,8 @@ static int __init do_boot_cpu(int apicid
cycles_t cacheflush_time;
unsigned long cache_decay_ticks;
+extern unsigned long sched_cache_size;
+
static void smp_tune_scheduling (void)
{
unsigned long cachesize; /* kB */
@@ -879,6 +881,7 @@ static void smp_tune_scheduling (void)
}
cacheflush_time = (cpu_khz>>10) * (cachesize<<10) / bandwidth;
+ sched_cache_size = cachesize * 1024;
}
cache_decay_ticks = (long)cacheflush_time/cpu_khz + 1;
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2005-02-21 5:10 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <200411110851.30819.habanero@us.ibm.com>
2004-11-11 15:04 ` [patch] sched: auto-tuning task-migration Andrew Theurer
2004-10-06 14:22 emmanuel.fuste
-- strict thread matches above, loose matches on Subject: below --
2004-10-06 0:42 Default cache_hot_time value back to 10ms Chen, Kenneth W
2004-10-06 13:29 ` [patch] sched: auto-tuning task-migration Ingo Molnar
2004-10-06 13:44 ` Nick Piggin
2004-10-06 17:49 ` Chen, Kenneth W
2004-10-06 20:04 ` Ingo Molnar
2004-10-06 21:18 ` Chen, Kenneth W
2004-10-07 6:10 ` Ingo Molnar
2005-02-21 5:08 ` Paul Jackson
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®