Re: [Xen-devel] [PATCH 08 of 11 v3] libxl: optimize the calculation of how many VCPUs can run on a candidate

[George Dunlap <George.Dunlap@xxxxxxxxxxxxx>]

On Fri, Feb 1, 2013 at 11:01 AM, Dario Faggioli <dario.faggioli@xxxxxxxxxx> wrote:

For choosing the best NUMA placement candidate, we need to figure out
how many VCPUs are runnable on each of them. That requires going through
all the VCPUs of all the domains and check their affinities.

With this change, instead of doing the above for each candidate, we
do it once for all, populating an array while counting. This way, when
we later are evaluating candidates, all we need is summing up the right
elements of the array itself.

This reduces the complexity of the overall algorithm, as it moves a
potentially expensive operation (for_each_vcpu_of_each_domain {})
outside from the core placement loop, so that it is performed only
once instead of (potentially) tens or hundreds of times. More
specifically, we go from a worst case computation time complaxity of:

 O(2^n_nodes) * O(n_domains*n_domain_vcpus)

To, with this change:

 O(n_domains*n_domains_vcpus) + O(2^n_nodes) = O(2^n_nodes)

(with n_nodes<=16, otherwise the algorithm suggests partitioning with
cpupools and does not even start.)

Signed-off-by: Dario Faggioli <dario.faggioli@xxxxxxxxxx>

Acked-by: George Dunlap <george.dunlap@xxxxxxxxxxxxx>

 

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel