Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Fri, 16 Jun 2023 14:17:00 +0800
From:   Chen Yu <yu.c.chen@intel.com>
To:     "Gautham R. Shenoy" <gautham.shenoy@amd.com>
CC:     Peter Zijlstra <peterz@infradead.org>,
        Vincent Guittot <vincent.guittot@linaro.org>,
        Ingo Molnar <mingo@redhat.com>,
        Juri Lelli <juri.lelli@redhat.com>,
        Tim Chen <tim.c.chen@intel.com>,
        Mel Gorman <mgorman@techsingularity.net>,
        Dietmar Eggemann <dietmar.eggemann@arm.com>,
        "K Prateek Nayak" <kprateek.nayak@amd.com>,
        Abel Wu <wuyun.abel@bytedance.com>,
        Len Brown <len.brown@intel.com>,
        Chen Yu <yu.chen.surf@gmail.com>,
        "Yicong Yang" <yangyicong@hisilicon.com>,
        <linux-kernel@vger.kernel.org>
Subject: Re: [RFC PATCH 3/4] sched/fair: Calculate the scan depth for idle
 balance based on system utilization
Message-ID: <ZIv+XK830mDeq/JL@chenyu5-mobl2.ccr.corp.intel.com>
References: <cover.1686554037.git.yu.c.chen@intel.com>
 <bc96b53efb712337a645e2c2a340975545ed5a28.1686554037.git.yu.c.chen@intel.com>
 <ZIqpI0ScCT5pmrAO@BLR-5CG11610CF.amd.com>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <ZIqpI0ScCT5pmrAO@BLR-5CG11610CF.amd.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?NfQ49fbQ7UHHwwGSXM5iEHyBNbKlybpnEmDm88lV0iOxOnmBNPw+abhzlDiF?=
 =?us-ascii?Q?AMUMLoolVaEpNfZX80eDwgp6FtK9HWQzg2pU3+Uq2yw1LnDecCzsQvLruh0B?=
 =?us-ascii?Q?flS0gVEFCyWWmul4MAvTn7KaWSJmytwHi+E9ySEVxJeNyFh0cy0YkFWnUAuR?=
 =?us-ascii?Q?TWUqV/fQrbZmFYEAaCh3uaYmrONYIzS9wlOO9OaJfl6Y86A16hL0Oh1pQCPR?=
 =?us-ascii?Q?7AqcFfEv3Ve0p6OUc4grnyT1KNuBAW3Z81f06RUSmyqRmhUF0Co5rrIEAbQd?=
 =?us-ascii?Q?IUkQVpU0ZdJ5NDSvJNntGGSYV1ngkHVmW9HmRcN6+HglBByY8Tinn5ypDgK8?=
 =?us-ascii?Q?fGnIt8SihL1AkOxDtf2psrYWajuSwahq8FNo4QATikzybJSkaj+sqqro6Hpc?=
 =?us-ascii?Q?a7buF2rGmU98ej7ZO1umBFZvFR8fJmNafDY8C6iW6e12EB8q5mm9G3dJcdPT?=
 =?us-ascii?Q?sQYzcXvWMnpKRMrnHypqXFf2aELb+0/qMW4yRox0nu7pGnEDDfHIPTuis3Ul?=
 =?us-ascii?Q?ZZbAU6gyD9P43jbjVVGPIYkC6hFewoQNfwS5yzdPHKsLQn5R4iMO2fa/wtYR?=
 =?us-ascii?Q?aeqAjVuU6JiriyFmYcdMp5QScnBkqnqazRqQkJCerHTQnje63uapEY5OGapV?=
 =?us-ascii?Q?xchkVjDXWWQPirz07ZnjTXjea50O+OtgxIHZgbfF7+zrNAzi/N5nXkPN0QVY?=
 =?us-ascii?Q?QXhHw1xwq0ovcH9I7VLTWev1/VwxTK0ZK102KSB3CnTL10BMdIdrpX5u7bKO?=
 =?us-ascii?Q?Ueag2epfUiYKCPtLXu74XqsKsfprU329reG7/p3YofI9pdz6ADQgRFa4EQyQ?=
 =?us-ascii?Q?WBOQ9/2YWeq2k7t6FRfKf5Vm0r8avV1Dd0jlKFcH9yAR4L4ouv/fHQFST1Gq?=
 =?us-ascii?Q?e/Pc0VVVrkJbUdtWhdmjc/A2OQhm3XqY6Qcu89MH3ynlMvZ3v2YANWYW3v1K?=
 =?us-ascii?Q?D+VSEbhSRSV4gsfIj3RqvzUGZfYbq2Fpv60LBIfw0Fy2AcvuJyxxmuMOHG+p?=
 =?us-ascii?Q?nMxQvXI8qMC9xYrPSyLFNoE1bguWS6nTSomlBCLlURUNmJa0a6xdS0s273uY?=
 =?us-ascii?Q?PQlUYSMZyIgS/dUNyoIw9etlniYUt6K7L8RglOpJYh9eeafp+F1OWYw4t0v5?=
 =?us-ascii?Q?gEG15PTlpvc+YiIN43EBMf7RkaC/XmEl5LkE7xzncwRBdP/mDWT1e7qIlpQ3?=
 =?us-ascii?Q?8rQAl3qZjxub/qWjX2bV7d4TqY0yUa4BJma4MVcXPsLeT27ShMgqkhemL1gf?=
 =?us-ascii?Q?ICd4q3dx4f8nacQzRQWVF6RxRwXyzyxhWFlalJm65753pcStUFfQeAhhszJi?=
 =?us-ascii?Q?+t+SzYYkHhrRqE4me6yBDm7Y8Knf5wKdSazOI4qqFPuubaEj+YufcRKKQJVw?=
 =?us-ascii?Q?HV1fA443Jvt7EKxS1E7qm87yy1hMZ34H5ae0rzXLTQKes/9Ux5lGODjTBb2/?=
 =?us-ascii?Q?6JasNYsAX2xP3GB+QzSxWwcwYWdQw0WYD3eLROXIbZFZsIKDUyPCsNlZc7vH?=
 =?us-ascii?Q?Xkux4zKC/YUkJA5SCWzmci5ZTSoCKlyqNHIJpcVMgha/9PIWLmVe+wyPJdKk?=
 =?us-ascii?Q?JnMKV2DoymTVeETRp22T6JwqlQ7wGuaisjgIjg51?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 47c5f865-3a4d-4577-9425-08db6e3154d7
X-MS-Exchange-CrossTenant-AuthSource: MN0PR11MB6206.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 Jun 2023 06:17:16.0889
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: 2NNBjx8p9WLa4DctaXaZeEDfua3dTDdxh/DpGIFuWwB38LmbwyiopPXGGPuq+FKYzvlFYZPrKkirgodt2EECFg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CO1PR11MB4819
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-4.4 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,
        DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_MED,
        RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,
        T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED autolearn=ham autolearn_force=no
        version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

Hi Gautham,
On 2023-06-15 at 11:31:07 +0530, Gautham R. Shenoy wrote:
> Hello Chen Yu,
> 
> 
> On Tue, Jun 13, 2023 at 12:18:57AM +0800, Chen Yu wrote:
> > When CPU is about to enter idle, it invokes newidle_balance() to pull
> > some tasks from other runqueues. Although there is per domain
> > max_newidle_lb_cost to throttle the newidle_balance(), it would be
> > good to further limit the scan based on overall system utilization.
> > The reason is that there is no limitation for newidle_balance() to
> > launch this balance simultaneously on multiple CPUs. Since each
> > newidle_balance() has to traverse all the CPUs to calculate the
> > statistics one by one, this total time cost on newidle_balance()
> > could be O(n^2). This is not good for performance or power saving.
> > 
> > For example, sqlite has spent quite some time on newidle balance()
> > on Intel Sapphire Rapids, which has 2 x 56C/112T = 224 CPUs:
> > 6.69%    0.09%  sqlite3     [kernel.kallsyms]   [k] newidle_balance
> > 5.39%    4.71%  sqlite3     [kernel.kallsyms]   [k] update_sd_lb_stats
> > 
> > Based on this observation, limit the scan depth of newidle_balance()
> > by considering the utilization of the LLC domain. Let the number of
> > scanned groups be a linear function of the utilization ratio:
> >
> 
> Is there any particular reason why this is being limited only to the
> LLC domain ?
> 
Thank you for your interest in this change. The original thought as you
might know is that our LLC has a huge number of groups.
And since SIS_UTIL has done similar thing for LLC, we want to propose
a simple prototype to demonstrate the idea.
> On architectures where the LLC domain may not be so large (POWER9/10,
> AMD), the additional cost is usually paid at the higher domains where
> the number of groups is greater / equal to the number of groups in the
> LLC domain and where sd_span is pretty large. It would be good to
> explore avoiding the scan cost on those domains as well, right?
> 
Exactly.
> > nr_groups_to_scan = nr_groups * (1 - util_ratio)
> 
> If we can extend this logic to higher domains, on a Zen3 1 Socket
> server with 128 CPUs at the DIE domain containing 8 groups, we can
> expect a significant reduction in the time spent doing
> update_sg_lb_stats() at higher utilizations.
> 
> util_ratio     nr_groups_to_scan        nr_cpus_scanned
> ========================================================
> 0.9              1                       16     (-87.5%)
> 0.75             2                       32     (-75%)
> 0.5              4                       64     (-50%)
> 0.25             6                       96     (-25%)
> 0.1              7                      112     (-12.5%) 
> 
> 
> On a Zen 4 1 socket server with 192 CPUs at the DIE domain containing
> 12 groups, values will be:
> 
> util_ratio     nr_groups_to_scan        nr_cpus_scanned
> ========================================================
> 0.9              1                       16     (-91%)
> 0.75             3                       48     (-75%)
> 0.5              6                       96     (-50%)
> 0.25             9                      144     (-25%)
> 0.1             10                      160     (-16.7%)
> 
Thanks for this information, I think we can extend the scan limitation
for not only LLC(MC domain) but also higher domains. I'll think about
it.

thanks,
Chenyu