[lkml]   [2012]   [Mar]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [PATCH 11/39] autonuma: CPU follow memory algorithm
    On Mon, Mar 26, 2012 at 03:28:37PM -0400, Rik van Riel wrote:
    > Agreed, it looks O(N), but because every CPU will be calling
    > it its behaviour will be O(N^2) and has the potential to
    > completely break systems with a large number of CPUs.

    As I wrote in the comment before the function, math speaking, this
    looks like O(N) but it is O(1), not O(N) nor O(N^2). This is because N
    = NR_CPUS = 1.

    As I also wrote in the comment before the function, this is called at
    every schedule in the short term primarily because I want to see a
    flood if this algorithm does something wrong after I do.

    echo 1 >/sys/kernel/mm/autonuma/debug

    * This has O(N) complexity but N isn't the number of running
    * processes, but the number of CPUs, so if you assume a constant
    * number of CPUs (capped at NR_CPUS) it is O(1). O(1) misleading math
    * aside, the number of cachelines touched with thousands of CPU might
    * make it measurable. Calling this at every schedule may also be
    * overkill and it may be enough to call it with a frequency similar
    * to the load balancing, but by doing so we're also verifying the
    * algorithm is a converging one in all workloads if performance is
    * improved and there's no frequent CPU migration, so it's good in the
    * short term for stressing the algorithm.

    Over time (not urgent) this can be called at a regular interval like
    load_balance() or be more integrated within CFS so it doesn't need to
    be called at all.

    For the short term it shall be called at every schedule for debug
    reasons so I wouldn't suggest to make an effort to call it at lower
    frequency right now. If somebody wants to make an effort to make it
    more integrated in CFS that's welcome though, but I would still like a
    tweak to force the algorithm synchronously during every schedule
    decision like now so I can verify it converges at the scheduler level
    and there is not a flood of worthless bounces.

     \ /
      Last update: 2012-03-26 21:47    [W:4.150 / U:0.676 seconds]
    ©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site