• akpm@osdl.org's avatar
    [PATCH] scheduler cache-hot-autodetect · 198e2f18
    akpm@osdl.org authored
    )
    
    From: Ingo Molnar <mingo@elte.hu>
    
    This is the latest version of the scheduler cache-hot-auto-tune patch.
    
    The first problem was that detection time scaled with O(N^2), which is
    unacceptable on larger SMP and NUMA systems. To solve this:
    
    - I've added a 'domain distance' function, which is used to cache
      measurement results. Each distance is only measured once. This means
      that e.g. on NUMA distances of 0, 1 and 2 might be measured, on HT
      distances 0 and 1, and on SMP distance 0 is measured. The code walks
      the domain tree to determine the distance, so it automatically follows
      whatever hierarchy an architecture sets up. This cuts down on the boot
      time significantly and removes the O(N^2) limit. The only assumption
      is that migration costs can be expressed as a function of domain
      distance - this covers the overwhelming majority of existing systems,
      and is a good guess even for more assymetric systems.
    
      [ People hacking systems that have assymetries that break this
        assumption (e.g. different CPU speeds) should experiment a bit with
        the cpu_distance() function. Adding a ->migration_distance factor to
        the domain structure would be one possible solution - but lets first
        see the problem systems, if they exist at all. Lets not overdesign. ]
    
    Another problem was that only a single cache-size was used for measuring
    the cost of migration, and most architectures didnt set that variable
    up. Furthermore, a single cache-size does not fit NUMA hierarchies with
    L3 caches and does not fit HT setups, where different CPUs will often
    have different 'effective cache sizes'. To solve this problem:
    
    - Instead of relying on a single cache-size provided by the platform and
      sticking to it, the code now auto-detects the 'effective migration
      cost' between two measured CPUs, via iterating through a wide range of
      cachesizes. The code searches for the maximum migration cost, which
      occurs when the working set of the test-workload falls just below the
      'effective cache size'. I.e. real-life optimized search is done for
      the maximum migration cost, between two real CPUs.
    
      This, amongst other things, has the positive effect hat if e.g. two
      CPUs share a L2/L3 cache, a different (and accurate) migration cost
      will be found than between two CPUs on the same system that dont share
      any caches.
    
    (The reliable measurement of migration costs is tricky - see the source
    for details.)
    
    Furthermore i've added various boot-time options to override/tune
    migration behavior.
    
    Firstly, there's a blanket override for autodetection:
    
    	migration_cost=1000,2000,3000
    
    will override the depth 0/1/2 values with 1msec/2msec/3msec values.
    
    Secondly, there's a global factor that can be used to increase (or
    decrease) the autodetected values:
    
    	migration_factor=120
    
    will increase the autodetected values by 20%. This option is useful to
    tune things in a workload-dependent way - e.g. if a workload is
    cache-insensitive then CPU utilization can be maximized by specifying
    migration_factor=0.
    
    I've tested the autodetection code quite extensively on x86, on 3
    P3/Xeon/2MB, and the autodetected values look pretty good:
    
    Dual Celeron (128K L2 cache):
    
     ---------------------
     migration cost matrix (max_cache_size: 131072, cpu: 467 MHz):
     ---------------------
               [00]    [01]
     [00]:     -     1.7(1)
     [01]:   1.7(1)    -
     ---------------------
     cacheflush times [2]: 0.0 (0) 1.7 (1784008)
     ---------------------
    
    Here the slow memory subsystem dominates system performance, and even
    though caches are small, the migration cost is 1.7 msecs.
    
    Dual HT P4 (512K L2 cache):
    
     ---------------------
     migration cost matrix (max_cache_size: 524288, cpu: 2379 MHz):
     ---------------------
               [00]    [01]    [02]    [03]
     [00]:     -     0.4(1)  0.0(0)  0.4(1)
     [01]:   0.4(1)    -     0.4(1)  0.0(0)
     [02]:   0.0(0)  0.4(1)    -     0.4(1)
     [03]:   0.4(1)  0.0(0)  0.4(1)    -
     ---------------------
     cacheflush times [2]: 0.0 (33900) 0.4 (448514)
     ---------------------
    
    Here it can be seen that there is no migration cost between two HT
    siblings (CPU#0/2 and CPU#1/3 are separate physical CPUs). A fast memory
    system makes inter-physical-CPU migration pretty cheap: 0.4 msecs.
    
    8-way P3/Xeon [2MB L2 cache]:
    
     ---------------------
     migration cost matrix (max_cache_size: 2097152, cpu: 700 MHz):
     ---------------------
               [00]    [01]    [02]    [03]    [04]    [05]    [06]    [07]
     [00]:     -    19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1)
     [01]:  19.2(1)    -    19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1)
     [02]:  19.2(1) 19.2(1)    -    19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1)
     [03]:  19.2(1) 19.2(1) 19.2(1)    -    19.2(1) 19.2(1) 19.2(1) 19.2(1)
     [04]:  19.2(1) 19.2(1) 19.2(1) 19.2(1)    -    19.2(1) 19.2(1) 19.2(1)
     [05]:  19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1)    -    19.2(1) 19.2(1)
     [06]:  19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1)    -    19.2(1)
     [07]:  19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1) 19.2(1)    -
     ---------------------
     cacheflush times [2]: 0.0 (0) 19.2 (19281756)
     ---------------------
    
    This one has huge caches and a relatively slow memory subsystem - so the
    migration cost is 19 msecs.
    Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
    Signed-off-by: default avatarAshok Raj <ashok.raj@intel.com>
    Signed-off-by: default avatarKen Chen <kenneth.w.chen@intel.com>
    Cc: <wilder@us.ibm.com>
    Signed-off-by: default avatarJohn Hawkes <hawkes@sgi.com>
    Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
    198e2f18
setup.c 23.8 KB