lkml.org 
[lkml]   [2011]   [Dec]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Subject[RFC PATCH 0/4] Gang scheduling in CFS
    Date
        The following patches implements gang scheduling. These patches
    are *highly* experimental in nature and are not proposed for
    inclusion at this time.

    Gang scheduling is an approach where we make an effort to run
    related tasks (the gang) at the same time on a number of CPUs.

    Gang scheduling can be helpful in virtualization scenario. It will
    help in avoiding the lock-holder-preemption[1] problem and other
    benefits include improved lock-acquisition times. This feature
    will help address some limitations of KVM on Power

    On Power, we have an interesting hardware restriction on guests
    running across SMT theads: on any single core, we can only run one
    mm context at any given time. That means that we can run 4
    threads from one guest, but we can not mix and match threads from
    different guests or host. In KVM's case, QEMU also counts as
    another mm context, so any VM exits or hypercalls that trap in to
    QEMU will stop all the other threads on the core except the one
    making the call.

    The gang scheduling problem can be broken into two parts:
    a) Placement of the tasks to be gang scheduled
    b) Synchronized scheduling of the tasks across a set of cpu.

    This patch takes care of point "b" and the placement part(pinning)
    is handled manually in user space currently.

    Approach:

    Whenever a task is picked, and the task is supposed to be gang
    scheduled we will do some post_schedule magic. post_schedule magic
    for once will decide whether this cpu is the gang_leader or not.

    So what is this gang_leader?

    We need one of the cpu to start the gang on behalf of the set of
    cpus, IOW the gang granularity. The gang_leader will be sending
    IPIs to fellow cpus, as per the gang granularity. This granularity
    can be decided depending upon the architecture as well.

    All the fellow cpus on receiving an IPI will do the following: If
    the cpu's runqueue has a task belonging to the gang which was
    initiated by the gang_leader, favour the task to be picked up and
    set need_resched.

    The favouring of task can be done in different ways. I have tried
    two options here(patch3 and patch4) and have results from them.

    Interface to invoke a gang for a task group:
    echo 1 > /cgroup/test/cpu.gang

    patch 1: Implements the interface of enabling/disabling gang using
    cpu cgroup.

    patch 2: Infrastructure to invoke gang scheduling. A gang leader
    would be electected once depending on the gang scheduling
    granularity, IOW, gang across how many cpus(gang_cpus).
    And then on, gang leader will be sending gang initiations
    to gang_cpus.

    patch 3: Uses set_next_buddy to favour gang tasks to be picked up

    patch 4: Introduces set_gang_buddy to favour gang task
    unconditionally.

    I have rebased patches for latest scheduler changes
    (3.2-rc4-tip_93e44306).

    PLE - Test Setup:
    - x3850x5 machine - PLE enabled
    - 8 CPUs (HT disabled)
    - 264GB memory
    - VM details:
    - Guest kernel: 2.6.32 based enterprise kernel
    - 4096MB memory
    - 8 VCPUs
    - During gang runs, vcpus are pinned

    Results:
    * Below numbers are average across 2runs
    * GangVsBase - Gang vs Baseline kernel
    * GangVsPin - Gang vs Baseline kernel + vcpus pinned
    * V1 - patch 1, 2 and 3
    * V2 - v1 + patch4
    * Results are % improvement/degradation

    +-------------+---------------------------+-------------------------+
    | | V1 (%) | V2 (%) |
    + Benchmarks +-------------+-------------+-------------------------+
    | | GangVsBase | GangVsPin | GangVsBase | GangVsPin |
    +-------------+-------------+-------------+-------------------------+
    | kbench 2vm | -1 | 1 | 1 | 3 |
    | kbench 4vm | -10 | -14 | 11 | 7 |
    | kbench 8vm | -10 | -13 | 8 | 6 |
    +-------------+-------------+-------------+-------------------------+
    | ebizzy 2vm | 0 | 3 | 2 | 5 |
    | ebizzy 4vm | 1 | 0 | 4 | 3 |
    | ebizzy 8vm | 0 | 1 | 23 | 26 |
    +-------------+-------------+-------------+-------------------------+
    | specjbb 2vm | -3 | -3 | -17 | -18 |
    | specjbb 4vm | -9 | -10 | -33 | -34 |
    | specjbb 8vm | -19 | -2 | 28 | 55 |
    +-------------+-------------+-------------+-------------------------+
    | hbench 2vm | 3 | -14 | 28 | 15 |
    | hbench 4vm | -66 | -55 | -20 | -12 |
    | hbench 8vm | -239 | -92 | -189 | -64 |
    +-------------+-------------+-------------+-------------------------+
    | dbench 2vm | -3 | -3 | -3 | -3 |
    | dbench 4vm | -11 | 3 | -13 | 0 |
    | dbench 8vm | 25 | -1 | 12 | -12 |
    +-------------+-------------+-------------+-------------------------+

    Here are some additional data for the best and worst case in
    V2(GangVsBase). I am not able to figure out one/two data point
    that stands out always, that will say the gang sched
    improved/degraded for this reason.

    specjbb 8VM (improved 28%)
    +------------+--------------------+--------------------+----------+
    | SPECJBB |
    +------------+--------------------+--------------------+----------+
    | Parameter | Baseline | gang:V2 | % imprv |
    +------------+--------------------+--------------------+----------+
    | Score| 4173.19 | 5343.69 | 28 |
    | BwUsage| 5745105989024.00 | 6566955369442.00 | 14 |
    | HostIdle| 63.00 | 79.00 | -25 |
    | kvmExit| 31611242.00 | 52477831.00 | -66 |
    | UsrTime| 13.00 | 20.00 | 53 |
    | SysTime| 16.00 | 12.00 | 25 |
    | IOWait| 7.00 | 4.00 | 42 |
    | IdleTime| 63.00 | 61.00 | -3 |
    | TPS| 7.00 | 6.00 | -14 |
    | CacheMisses| 14272997833.00 | 14800182895.00 | -3 |
    | CacheRefs| 58143057220.00 | 69914413043.00 | 20 |
    |Instructions| 4397381980479.00 | 4572303159016.00 | -3 |
    | Cycles| 5884437898653.00 | 6489379310428.00 | -10 |
    | ContextSW| 10008378.00 | 14705944.00 | -46 |
    | CPUMigrat| 10501.00 | 21705.00 | -106 |
    +-----------------------------------------------------------------+

    hbench 8VM (degraded 189%)
    +------------+--------------------+--------------------+----------+
    | Hackbench |
    +------------+--------------------+--------------------+----------+
    | Parameter | Baseline | gang:V2 | % imprv |
    +------------+--------------------+--------------------+----------+
    | HbenchAvg| 28.27 | 81.75 | -189 |
    | BwUsage| 1278656649466.00 | 2352504202657.00 | 83 |
    | HostIdle| 82.00 | 80.00 | 2 |
    | kvmExit| 6859301.00 | 31853895.00 | -364 |
    | UsrTime| 11.00 | 17.00 | 54 |
    | SysTime| 17.00 | 13.00 | 23 |
    | IOWait| 7.00 | 5.00 | 28 |
    | IdleTime| 63.00 | 62.00 | -1 |
    | TPS| 8.00 | 7.00 | -12 |
    | CacheMisses| 194565014.00 | 140098020.00 | 27 |
    | CacheRefs| 4793875790.00 | 15942118793.00 | 232 |
    |Instructions| 430356490646.00 | 1006560006432.00 | -133 |
    | Cycles| 559463222878.00 | 1578421826236.00 | -182 |
    | ContextSW| 2587635.00 | 8110060.00 | -213 |
    | CPUMigrat| 967.00 | 3844.00 | -297 |
    +-----------------------------------------------------------------+

    non-PLE - Test Setup:
    - x3650 M2 machine
    - 8 CPUs (HT disabled)
    - 64GB memory
    - VM details:
    - Guest kernel: 2.6.32 based enterprise kernel
    - 1024MB memory
    - 8 VCPUs
    - During gang runs, vcpus are pinned

    Results:
    * GangVsBase - Gang vs Baseline kernel
    * GangVsPin - Gang vs Baseline kernel + vcpus pinned
    * V1 - patch 1, 2 and 3
    * V2 - V1 + patch4
    * Results are % improvement/degradation
    +-------------+---------------------------+-------------------------+
    | | V1 | V2 |
    +-------------+-------------+-------------+-------------------------+
    | | GangVsBase | GangVsPin | GangVsBase | GangVsPin |
    +-------------+-------------+-------------+-------------------------+
    | kbench 2vm | -3 | -42 | 22 | -6 |
    | kbench 4vm | 4 | -11 | -11 | -29 |
    | kbench 8vm | -4 | -11 | 12 | 6 |
    +-------------+-------------+-------------+-------------------------+
    | ebizzy 2vm | 1333 | 772 | 1520 | 885 |
    | ebizzy 4vm | 525 | 423 | 930 | 761 |
    | ebizzy 8vm | 373 | 281 | 771 | 602 |
    +-------------+-------------+-------------+-------------------------+
    | specjbb 2vm | -2 | -1 | 0 | 0 |
    | specjbb 4vm | -4 | -7 | 2 | 0 |
    | specjbb 8vm | -14 | -17 | -8 | -11 |
    +-------------+-------------+-------------+-------------------------+
    | hbench 2vm | 12 | 0 | -32 | -49 |
    | hbench 4vm | -234 | -95 | 12 | 48 |
    | hbench 8vm | -364 | -69 | -7 | 60 |
    +-------------+-------------+-------------+-------------------------+
    | dbench 2vm | -13 | 3 | -17 | -1 |
    | dbench 4vm | 38 | 45 | -2 | 1 |
    | dbench 8vm | -36 | -10 | 44 | 102 |
    +-------------+-------------+-------------+-------------------------+

    Similar data for the best and worst case in V2(GangVsBase).

    ebizzy 2vm (improved 15 times, i.e. 1520%)
    +------------+--------------------+--------------------+----------+
    | Ebizzy |
    +------------+--------------------+--------------------+----------+
    | Parameter | Basline | gang:V2 | % imprv |
    +------------+--------------------+--------------------+----------+
    | EbzyRecords| 1709.50 | 27701.00 | 1520 |
    | EbzyUser| 20.48 | 376.64 | 1739 |
    | EbzySys| 1384.65 | 1071.40 | 22 |
    | EbzyReal| 300.00 | 300.00 | 0 |
    | BwUsage| 2456114173416.00 | 2483447784640.00 | 1 |
    | HostIdle| 34.00 | 35.00 | -2 |
    | UsrTime| 6.00 | 14.00 | 133 |
    | SysTime| 30.00 | 24.00 | 20 |
    | IOWait| 10.00 | 9.00 | 10 |
    | IdleTime| 51.00 | 51.00 | 0 |
    | TPS| 25.00 | 24.00 | -4 |
    | CacheMisses| 766543805.00 | 8113721819.00 | -958 |
    | CacheRefs| 9420204706.00 | 136290854100.00 | 1346 |
    |BranchMisses| 1191336154.00 | 11336436452.00 | -851 |
    | Branches| 618882621656.00 | 459161727370.00 | -25 |
    |Instructions| 2517045997661.00 | 2325227247092.00 | 7 |
    | Cycles| 7642374654922.00 | 7657626973214.00 | 0 |
    | PageFlt| 23779.00 | 22195.00 | 6 |
    | ContextSW| 1517241.00 | 1786319.00 | -17 |
    | CPUMigrat| 537.00 | 241.00 | 55 |
    +-----------------------------------------------------------------+

    hbench 2vm (degraded 44%)
    +------------+--------------------+--------------------+----------+
    | Hackbench |
    +------------+--------------------+--------------------+----------+
    | Parameter | Non-Gang | gang:V2 | % imprv |
    +------------+--------------------+--------------------+----------+
    | HbenchAvg| 8.95 | 11.84 | -32 |
    | BwUsage| 140751454716.00 | 188528508986.00 | 33 |
    | HostIdle| 46.00 | 41.00 | 10 |
    | UsrTime| 6.00 | 13.00 | 116 |
    | SysTime| 30.00 | 24.00 | 20 |
    | IOWait| 10.00 | 9.00 | 10 |
    | IdleTime| 52.00 | 52.00 | 0 |
    | TPS| 24.00 | 23.00 | -4 |
    | CacheMisses| 536001007.00 | 555837077.00 | -3 |
    | CacheRefs| 1388722056.00 | 1737837668.00 | 25 |
    |BranchMisses| 260102092.00 | 580784727.00 | -123 |
    | Branches| 25083812102.00 | 34960032641.00 | 39 |
    |Instructions| 136018192623.00 | 190522959512.00 | -40 |
    | Cycles| 232524382438.00 | 320669938332.00 | -37 |
    | PageFlt| 9562.00 | 10461.00 | -9 |
    | ContextSW| 78095.00 | 103097.00 | -32 |
    | CPUMigrat| 237.00 | 155.00 | 34 |
    +-----------------------------------------------------------------+

    For reference here are the benchmark parameters
    Kernbench: kernbench -f -M -H -o 16
    ebizzy: ebizzy -S 300 -t 16
    hbench: hackbench 8 (10000 loops)
    dbench: dbench 8 -t 120
    specjbb: 8 & 16 warehouses, 512MB heap, 120secs run

    Thanks,
    Nikunj

    1. http://xen.org/files/xensummitboston08/LHP.pdf

    ---

    Nikunj A. Dadhania (4):
    sched:Implement set_gang_buddy
    sched: Gang using set_next_buddy
    sched: Adding gang scheduling infrastrucure
    sched: Adding cpu.gang file to cpu cgroup


    kernel/sched/core.c | 28 ++++++++++
    kernel/sched/fair.c | 143 ++++++++++++++++++++++++++++++++++++++++++++++++++
    kernel/sched/sched.h | 8 ++-
    3 files changed, 178 insertions(+), 1 deletions(-)



    \
     
     \ /
      Last update: 2011-12-19 09:35    [W:0.038 / U:0.224 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site