From patchwork Thu Dec 3 14:11:14 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mel Gorman X-Patchwork-Id: 11948953 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.2 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3901DC43211 for ; Thu, 3 Dec 2020 14:13:44 +0000 (UTC) Received: from merlin.infradead.org (merlin.infradead.org [205.233.59.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id C444820705 for ; Thu, 3 Dec 2020 14:13:43 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org C444820705 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=techsingularity.net Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=merlin.20170209; h=Sender:Content-Transfer-Encoding: Content-Type:Cc:List-Subscribe:List-Help:List-Post:List-Archive: List-Unsubscribe:List-Id:MIME-Version:Message-Id:Date:Subject:To:From: Reply-To:Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender :Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To:References:List-Owner; bh=vs6hgIv+BAN42vHfDdz/W0IZ6VM9gaKduap1HenAi84=; b=X99NLqZCyZnp3enqDzbkz+8icg K3Fil+j5BEpunCG7zBuVTSaWHSC0s+WOK5k8zpGlqPimwo33I1XIlXQMeao/scN0uBIX0SyisQx9v iME3YpNvzXpRVYhBjuI495JcEYIkE7btpH+9sd0sdCeaiDEiE1/L2cXosfA+XSEbkBpu7QjsSE3qF jidfVNKJDPOoqzEZGX8rNzJDSz+2N2P9Y1rPuphiHkHDkfJl0zu+ZDOIiCglhrRHR40KKo3ykox8m RpeNodylSwv3qdZtXqRnXTdW3mg80gwysBor8m1PSI8ZFB5K4EI75M2ieQeNYfnvIEc7Orl9+/ygj vWeHE0cQ==; Received: from localhost ([::1] helo=merlin.infradead.org) by merlin.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1kkpLD-000417-V6; Thu, 03 Dec 2020 14:12:16 +0000 Received: from outbound-smtp55.blacknight.com ([46.22.136.239]) by merlin.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1kkpKU-0003gt-52 for linux-arm-kernel@lists.infradead.org; Thu, 03 Dec 2020 14:11:41 +0000 Received: from mail.blacknight.com (pemlinmail03.blacknight.ie [81.17.254.16]) by outbound-smtp55.blacknight.com (Postfix) with ESMTPS id BCBFAFA8C7 for ; Thu, 3 Dec 2020 14:11:24 +0000 (GMT) Received: (qmail 22633 invoked from network); 3 Dec 2020 14:11:24 -0000 Received: from unknown (HELO stampy.112glenside.lan) (mgorman@techsingularity.net@[84.203.22.4]) by 81.17.254.9 with ESMTPA; 3 Dec 2020 14:11:24 -0000 From: Mel Gorman To: LKML Subject: [RFC PATCH 00/10] Reduce time complexity of select_idle_sibling Date: Thu, 3 Dec 2020 14:11:14 +0000 Message-Id: <20201203141124.7391-1-mgorman@techsingularity.net> X-Mailer: git-send-email 2.26.2 MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20201203_091130_361949_9F4B69F6 X-CRM114-Status: GOOD ( 14.30 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Barry Song , Juri Lelli , Vincent Guittot , Peter Ziljstra , Aubrey Li , Ingo Molnar , Mel Gorman , Valentin Schneider , Linux-ARM Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org This is an early prototype that has not been tested heavily. While parts of it may stand on its own, the motivation to release early is Aubrey Li's series on using an idle cpumask to optimise the search and Barry Song's series on representing clusters on die. The series is based on tip/sched/core rebased to 5.10-rc6. Patches 1-2 add schedstats to track the search efficiency of select_idle_sibling. They can be dropped from the final version but are useful when looking at select_idle_sibling in general. MMTests can already parse the stats and generate useful data including graphs over time. Patch 3 kills SIS_AVG_CPU but is partially reintroduced later in the context of SIS_PROP. Patch 4 notes that select_idle_core() can find an idle CPU that is not a free core yet it is ignored and a second search is conducted in select_idle_cpu() which is wasteful. Note that this patch will definitely change in the final version. Patch 5 adjusts p->recent_used_cpu so that it has a higher success rate and avoids searching the domain in some cases. Patch 6 notes that select_idle_* always starts with a CPU that is definitely not idle and fixes that. Patch 7 notes that SIS_PROP is only partially accounting for search costs. While this might be accidentally beneficial, it makes it much harder to reason about the effectiveness of SIS_PROP. Patch 8 uses similar logic to SIS_AVG_CPU but in the context of SIS_PROP to throttle the search depth. Patches 9 and 10 are stupid in the context of this series. They are included even though it makes no sense to use SIS_PROP logic in select_idle_core() as it already has throttling logic. The point is to illustrate that the select_idle_mask can be initialised at the start of a domain search used to mask out CPUs that have already been visited. In the context of Aubrey's and Barry's work, select_idle_mask would be initialised *after* select_idle_core as select_idle_core uses select_idle_mask for its own purposes. In Aubrey's case, the next step would be to scan idle_cpus_span as those CPUs may still be idle and bias the search towards likely idle candidates. If that fails, select_idle_mask clears all the bits set in idle_cpus_span and then scans the remainder. Similar observations apply to Barry's work, scan the local domain first, mask out those bits then scan the remaining CPUs in the cluster. The final version of this series will drop patches 1-2 unless there is demand and definitely drop patches 9-10. However, all 4 patches may be useful in the context of Aubrey's and Barry's work. Patches 1-2 would give more precise results on exactly how much they are improving "SIS Domain Search Efficiency" which may be more illustrative than just the headline performance figures of a given workload. The final version of this series will also adjust patch 4. If select_idle_core() runs at all then it definitely should return a CPU -- either an idle CPU or the target as it has already searched the entire domain and no further searching should be conducted. Barry might change that back so that a cluster can be scanned but it would be done in the context of the cluster series.