From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756297AbcDDTpV (ORCPT ); Mon, 4 Apr 2016 15:45:21 -0400 Received: from mx1.redhat.com ([209.132.183.28]:55174 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754749AbcDDTpU (ORCPT ); Mon, 4 Apr 2016 15:45:20 -0400 Message-ID: <1459799116.6219.24.camel@redhat.com> Subject: Re: [RFC] sched: unused cpu in affine workload From: Rik van Riel To: Peter Zijlstra , Ingo Molnar Cc: Jiri Olsa , James Hartsock , Srivatsa Vaddagiri , Kirill Tkhai , linux-kernel@vger.kernel.org Date: Mon, 04 Apr 2016 15:45:16 -0400 In-Reply-To: <20160404132321.GZ3448@twins.programming.kicks-ass.net> References: <20160404082302.GB2137@krava.local> <20160404085944.GA3030@gmail.com> <20160404091951.GA10360@gmail.com> <20160404093844.GA16017@gmail.com> <20160404132321.GZ3448@twins.programming.kicks-ass.net> Content-Type: multipart/signed; micalg="pgp-sha256"; protocol="application/pgp-signature"; boundary="=-fycHXkSkq/nvd/RWR98l" Mime-Version: 1.0 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.38]); Mon, 04 Apr 2016 19:45:19 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org --=-fycHXkSkq/nvd/RWR98l Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Mon, 2016-04-04 at 15:23 +0200, Peter Zijlstra wrote: > On Mon, Apr 04, 2016 at 11:38:44AM +0200, Ingo Molnar wrote: > >=20 > > We'd upgrade that to O(nr_cpus^2), which is totally unrealistic > > with 16,000 CPUs=C2=A0 > > even in a slowpath - but it would probably cause problems even with > > 120 CPUs. It=C2=A0 > > will get quadratically worse as the number of CPUs in a system > > increases on its=C2=A0 > > current exponential trajectory ... > The arbitrary affinity thing is I think a packing problem, which is > NP > hard IIRC. An optimal solution is NP hard. Heuristics that "move tasks with pressure" may be much more doable, and lead to perfectly satisfactory results, especially if most migrations happen within a socket (and the same shared L3 cache). --=20 All Rights Reversed. --=-fycHXkSkq/nvd/RWR98l Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQEcBAABCAAGBQJXAsRMAAoJEM553pKExN6D+2IH+wZisXqFUa+CvHFSc8SOTpAM Q1RBsidtqvNqIzl4l5VXp4VaGe+XzcK5wFbpSG9HnT4RzR56zEkPRQiSh7zxOEum gnFK4nWzKXo8l0g3e/c7zbjn44omtEBZFGeBvWJAf34hC+Qa5OlXdCpAixbIxNxJ 8ARTBZVZG/tczomzW5YOfQGp4j5CWrJouvStjdCDounpkISwo981xSj0oqjo1Els Ze+OLDNctik/JPS0gjW2/Bp4HAHwVXvfRUr3vBIe01Ywz1lJHwy12LiLZUahWCUf nEQA8ztBBbm2Pcxd2vIJZzW64t1z75ZsQPhUW9RoOivJSiiNAjHnxJBN0TsVDBk= =5bpN -----END PGP SIGNATURE----- --=-fycHXkSkq/nvd/RWR98l--