Re: [Xen-devel] [PATCH 1 of 3 v5/leftover] libxl: enable automatic placement of guests on NUMA nodes [and 1 more messages]

[Ian Campbell <Ian.Campbell@xxxxxxxxxx>]

On Tue, 2012-07-17 at 19:04 +0100, Ian Jackson wrote:
> Dario Faggioli writes ("[PATCH 1 of 3 v5/leftover] libxl: enable automatic 
> placement of guests on NUMA nodes"):
> > If a domain does not have a VCPU affinity, try to pin it
> > automatically to some PCPUs. This is done taking into account the
> > NUMA characteristics of the host.  In fact, we look for a
> > combination of host's NUMA nodes with enough free memory and number
> > of PCPUs for the new domain, and pin it to the VCPUs of those nodes.
> 
> Ian Jackson writes ("Re: [PATCH 1 of 3 v4/leftover] libxl: enable automatic 
> placement of guests on NUMA nodes"):
> ...
> > This part of the algorithm is quadratic in the number of combinations
> > divided by the number of nodes.  So the algorithm is
> >    O( (  C( nr_nodes, min_nodes ) / min_nodes  )^2 )
> > which is quite bad really.
> > 
> > At the very least this needs to be an exponential allocation, eg
> >   +                array_size += nr_nodes + array_size;
> > 
> > But if you didn't insist on creating the whole list and sorting it,
> > you would avoid this allocation entirely, wouldn't you ?
> > 
> > Should we bve worried that this algorithm will be too slow even if it
> > involves just
> >   O( C(nr_nodes,min_nodes) )
> > iterations ?
> 
> I've been told that boxes with 16 NUMA nodes are coming out about
> now.
> 
> This algorithm will start to have unreasonable performance with
> anything bigger than that.  Eg choosing 16 NUMA nodes out of 32 would
> involve searching 601,080,390 combinations.  32 out of 64 gives 10^18.
> 
> So I think we need a different approach :-(.

If 16 are coming out now then 32 nodes are at least a little in the
future, and 16 won't be common just yet.

The 4.2 freeze is starting to drag on and reworking this significantly
at this stage seems likely to take quite a while -- can we perhaps go
with the existing patches (with the known scalability limitation and
workaround of setting the explicit cpu affinity documented in the
release notes) and revisit for 4.3 and/or 4.2.1?

Ian.


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