boot-time slowdown for measure_migration_cost
The boot-time migration cost auto-tuning stuff seems to have been merged to Linus' tree since 2.6.15. On little one- or two-processor systems, the time required to measure the migration costs isn't very noticeable, but by the time we get to even a four-processor ia64 box, it adds about 30 seconds to the boot time, which seems like a lot.
Is that expected? Is the information we get really worth that much? Could the measurement be done at run-time instead? Is there a smaller hammer we could use, e.g., flushing just the buffer rather than the *entire* cache? Did we just implement sched_cacheflush() incorrectly for ia64?
Only ia64, x86, and x86_64 currently have a non-empty sched_cacheflush(), and the x86* ones contain only "wbinvd()". So I suspect that only ia64 sees this slowdown. But I would guess that other arches will implement it in the future.
Bjorn
Quoted 12 lines · Bjorn Helgaas
The boot-time migration cost auto-tuning stuff seems to have been merged to Linus' tree since 2.6.15. On little one- or two-processor systems, the time required to measure the migration costs isn't very noticeable, but by the time we get to even a four-processor ia64 box, it adds about 30 seconds to the boot time, which seems like a lot.
Is that expected? Is the information we get really worth that much? Could the measurement be done at run-time instead? Is there a smaller hammer we could use, e.g., flushing just the buffer rather than the *entire* cache? Did we just implement
sched_cacheflush()incorrectly for ia64?
Quoted 4 lines
Only ia64, x86, and
x86_64currently have a non-emptysched_cacheflush(), and the x86* ones contain only "wbinvd()". So I suspect that only ia64 sees this slowdown. But I would guess that other arches will implement it in the future.
the main cost comes from accessing the test-buffer when the buffer size gets above the real cachesize. There are a coupe of ways to improve that:
- double-check that max_cache_size gets set up correctly on your architecture - the code searches from ~64K to 2*max_cache_size.
- take the values that are auto-detected and use the migration_cost= boot parameter - see Documentation/kernel-parameters.txt:
migration_cost=
[KNL,SMP] debug: override scheduler migration costs
Format: <level-1-usecs>,<level-2-usecs>,... This debugging option can be used to override the default scheduler migration cost matrix. The numbers are indexed by 'CPU domain distance'. E.g. migration_cost=1000,2000,3000 on an SMT NUMA box will set up an intra-core migration cost of 1 msec, an inter-core migration cost of 2 msecs, and an inter-node migration cost of 3 msecs.
(a distribution could do this automatically as well in the installer, i've constructed the bootup printout to be in the format that is needed for migration_cost. I have not tested this too extensively though, so double-check the result via an additional migration_debug=2 printout as well! Let me know if you find any bugs here.)
via this solution you will get zero overhead on subsequent bootups.
- in kernel/sched.c, decrease ITERATIONS from 2 to 1. This will make the measurement more noisy though.
- in kernel/sched.c, change this line:
size = size * 20 / 19;
to:
size = size * 10 / 9;
this will probably halve the cost - against at the expense of accuracy and statistical stability.
Ingo
Quoted 2 lines · Ingo Molnar
- double-check that
max_cache_sizegets set up correctly on your architecture - the code searches from ~64K to 2*max_cache_size.
Ia64 gets that from PAL in get_max_cacheline_size() in ia64/kernel/setup.c A quick printk() in there confirms that we get the right answer (9MB for me), and that it happens before we compute the migration cost.
Quoted 4 lines
- take the values that are auto-detected and use the migration_cost= boot parameter - see
Documentation/kernel-parameters.txt:
...
via this solution you will get zero overhead on subsequent bootups.
But if you are going to go this route, you could drop all this code from the kernel and have a hard-wired constant, with a user-mode test program to compute the more accurate value.
Quoted 2 lines
- in
kernel/sched.c, decrease ITERATIONS from 2 to 1. This will make the measurement more noisy though.
Doing this drops the time to compute the value from 15.58s to 10.39s, while the value of migration_cost changes from 10112 to 9909.
Quoted 4 lines
- in
kernel/sched.c, change this line:size = size * 20 / 19; to: size = size * 10 / 9;
Doing this instead of changing ITERATIONS makes the computation take 7.79s and the computed migration_cost is 9987.
Doing both gets the time down to 5.20s, and the migration_cost™90.
So the variation in the computed value of migration_cost was at worst 2% with these modifications to the algorithm. Do you really need to know the value to this accuracy? What 2nd order bad effects would occur from using an off-by-2% value for scheduling decisions?
On the plus side Prarit's results show that this time isn't scaling with NR_CPUS ... apparently just cache size and number of domains are significant in the time to compute.
-Tony
Quoted 8 lines · Luck, Tony
Doing this drops the time to compute the value from 15.58s to 10.39s, while the value of
migration_costchanges from 10112 to 9909.Quoted 4 lines
- in
kernel/sched.c, change this line:size = size * 20 / 19; to: size = size * 10 / 9;
Quoted 4 lines
Doing this instead of changing ITERATIONS makes the computation take 7.79s and the computed
migration_costis 9987.Doing both gets the time down to 5.20s, and the migration_cost=9990.
ok, that's good enough i think - we could certainly do the patch below in v2.6.16.
Quoted 3 lines
On the plus side Prarit's results show that this time isn't scaling with
NR_CPUS... apparently just cache size and number of domains are significant in the time to compute.
yes, this comes from the algorithm, it only computes once per distance (and uses the cached value from then on), independently of the number of CPUs.
Ingo
---
reduce the amount of time the migration cost calculations cost during bootup.
kernel/sched.c renamed from kernel/sched.c.orig +3 -3
@@ -5141,7 +5141,7 @@ static void init_sched_build_groups(stru#define SEARCH_SCOPE 2#define MIN_CACHE_SIZE (64*1024U)#define DEFAULT_CACHE_SIZE (5*1024*1024U) -#define ITERATIONS 2 +#define ITERATIONS 1#define SIZE_THRESH 130#define COST_THRESH 130
@@ -5480,9 +5480,9 @@ static unsigned long long measure_migratbreak ; }/* -* Increase the cachesize in 5% steps: +* Increase the cachesize in 10% steps: */ - size = size *20 /19 ; + size = size *10 /9 ; }if (migration_debug)
Quoted 4 lines · Ingo Molnar
Quoted 1 line
Doing both gets the time down to 5.20s, and the migration_cost™90.
ok, that's good enough i think - we could certainly do the patch below in v2.6.16.
Might it be wise to see whether the 2% variation that I saw can be repeated on some other architecture? Bjorn's initial post was just questioning whether we need to spend this much time during boot to acquire this data. Now we have *one* data point that on an ia64 with four cpus with 9MB cache in a single domain that we can speed the calculation by a factor of three with only a 2% loss of accuracy. Can someone else try this patch and post the before/after values for migration_cost from dmesg?
-Tony
---
reduce the amount of time the migration cost calculations cost during bootup.
kernel/sched.c renamed from kernel/sched.c.orig +3 -3
@@ -5141,7 +5141,7 @@ static void init_sched_build_groups(stru#define SEARCH_SCOPE 2#define MIN_CACHE_SIZE (64*1024U)#define DEFAULT_CACHE_SIZE (5*1024*1024U) -#define ITERATIONS 2 +#define ITERATIONS 1#define SIZE_THRESH 130#define COST_THRESH 130
@@ -5480,9 +5480,9 @@ static unsigned long long measure_migratbreak ; }/* -* Increase the cachesize in 5% steps: +* Increase the cachesize in 10% steps: */ - size = size *20 /19 ; + size = size *10 /9 ; }if (migration_debug)
Tony,
Quoted 6 lines
Might it be wise to see whether the 2% variation that I saw can be
repeated on some other architecture? Can someone else try
this patch and post the before/after values formigration_costfrom dmesg?
Ask and ye shall receive ... on the 64p/64G system.
Pristine:
[ 9.942253] Brought up 64 CPUs [ 9.942904] Total of 64 processors activated (143654.91 BogoMIPS). [ 9.943995] build_sched_domains: start [ 32.108439] migration_cost=0,32232,39021 [ 37.894391] build_sched_domains: end
Patched:
[ 0.001307] Calibrating delay loop... 2244.60 BogoMIPS (lpjD89216) [ 9.942308] Brought up 64 CPUs [ 9.942812] Total of 64 processors activated (143654.91 BogoMIPS). [ 18.080441] migration_cost=0,31934,38750 [ 23.865993] checking if image is initramfs... it is
P.
Quoted 10 lines · Prarit Bhargava
Tony,
Quoted 7 lines
Might it be wise to see whether the 2% variation that I saw can be
repeated on some other architecture? Can someone else try
this patch and post the before/after values formigration_costfrom dmesg?
Whoops. Let's try that again:
Pristine (with build_sched_domains measurement):
[ 9.942253] Brought up 64 CPUs [ 9.942904] Total of 64 processors activated (143654.91 BogoMIPS). [ 9.943995] build_sched_domains: start [ 32.108439] migration_cost=0,32232,39021 [ 37.894391] build_sched_domains: end
Patched (with build_sched_domains measurement):
[ 9.942267] Brought up 64 CPUs [ 9.942930] Total of 64 processors activated (143654.91 BogoMIPS). [ 9.944032] build_sched_domains: beginmigration_cost=0,31854,38739 [ 23.868304] build_sched_domains: end
P.
Quoted 1 line
From: "Luck, Tony" <[email protected]>
...
Quoted 8 lines
So the variation in the computed value of
migration_costwas at worst 2% with these modifications to the algorithm. Do you really need to know the value to this accuracy? What 2nd order bad effects would occur from using an off-by-2% value for scheduling decisions?On the plus side Prarit's results show that this time isn't scaling with
NR_CPUS... apparently just cache size and number of domains are significant in the time to compute.
Yes, the calculation is done just once per domain level, and a desire to achieve great accuracy for the calculation presupposes that the cpuM-to-cpuN migration cost for a given domain level is identical (or very close) across all the CPU pairs. That is, for a given domain level, only one CPU pair are chosen for the calculation. For the ia64/sn2 NUMA Altix, and I suspect for other NUMA platforms, this just isn't true for the middle domain level (i.e., the level that appears when the CPU count is >32p) -- i.e., some CPU pairs are "closer" than other pairs. The variation for other CPU pairs in this domain level is certainly much greater than 2%.
John Hawkes
Ingo Molnar wrote on Monday, January 30, 2006 9:22 AM
Quoted 5 lines
- in
kernel/sched.c, decrease ITERATIONS from 2 to 1. This will make the measurement more noisy though.- in
kernel/sched.c, change this line:
Quoted 8 lines
size = size * 20 / 19;to:
size = size * 10 / 9;this will probably halve the cost - against at the expense of accuracy and statistical stability.
I think the kernel should keep the accuracy and stability. One option would be by default not to measure the migration cost. For people who wants to have an accurate scheduler parameter, they can turn on a boot time option to do the measure.
- Ken