Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) client-ip=2620:137:e000::3:7;
Date:   Wed, 11 Oct 2023 18:16:49 +0800
From:   Chen Yu <yu.c.chen@intel.com>
To:     Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC:     Peter Zijlstra <peterz@infradead.org>,
        <linux-kernel@vger.kernel.org>, Ingo Molnar <mingo@redhat.com>,
        Valentin Schneider <vschneid@redhat.com>,
        Steven Rostedt <rostedt@goodmis.org>,
        Ben Segall <bsegall@google.com>,
        "Mel Gorman" <mgorman@suse.de>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        Vincent Guittot <vincent.guittot@linaro.org>,
        Juri Lelli <juri.lelli@redhat.com>,
        Swapnil Sapkal <Swapnil.Sapkal@amd.com>,
        Aaron Lu <aaron.lu@intel.com>, Tim Chen <tim.c.chen@intel.com>,
        K Prateek Nayak <kprateek.nayak@amd.com>,
        "Gautham R . Shenoy" <gautham.shenoy@amd.com>, <x86@kernel.org>
Subject: Re: [RFC PATCH] sched/fair: Bias runqueue selection towards almost
 idle prev CPU
Message-ID: <ZSZ2ERMysY7iEo+x@chenyu5-mobl2.ccr.corp.intel.com>
References: <20230929183350.239721-1-mathieu.desnoyers@efficios.com>
 <ZRfKKxBzfu+kf0tM@chenyu5-mobl2.ccr.corp.intel.com>
 <0f3cfff3-0df4-3cb7-95cb-ea378517e13b@efficios.com>
 <ZSOMOhhkPIFmvz97@chenyu5-mobl2.ccr.corp.intel.com>
 <ebe4e40f-37df-40a9-9dfc-7f2a458151bd@efficios.com>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <ebe4e40f-37df-40a9-9dfc-7f2a458151bd@efficios.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?DKGq4SMjjFm0jLYy6KatIZxLy3yQVW71OpscgEodpQrps14/N4oKPzZucgaM?=
 =?us-ascii?Q?HBjUMBuLlSF3vZwFhELWeDPHdwH+gMk8XiPxm4wn3gl6xR1xiiFudeAL2k0q?=
 =?us-ascii?Q?AisgtDVIgnxDunjUuVkCty++cIxcn7F51+PbtEhgGk3ahqTbUfp+MRhg5ud/?=
 =?us-ascii?Q?GbkIx0+XGtPpAqH4Dj00wCHMOSHDl1um+dO63TBAAyBWjVvM+QsN4d2rJ9C2?=
 =?us-ascii?Q?UPgYT33seSLgvVwfqeVyVTIeWtJTVd2Ls8HqoceMU+p300ZbS+Y57HQ990rW?=
 =?us-ascii?Q?3ex5GLAxqawSiyHGIUBJvRPN3o62tiGhiYM+bFMd9mryQKPibth+6iHrt+0g?=
 =?us-ascii?Q?Ghwu620TH28+W36kgg1fW/OfLIOxSYq0PsjLsq9zziGhl9KlvdDPH710KKDa?=
 =?us-ascii?Q?iismZJTpRzlz1Q4jedo8pLce608e4oh22L5oS3bPfrd1+ICFBmIPE1aD2Mzk?=
 =?us-ascii?Q?qHgIzYr7MnAAd9wHdQ85GojYBvcLj6K5sGJn6OR2zCaaA7s6/ZCRjCgUycxN?=
 =?us-ascii?Q?a1qW/GOBzvqVtEqerZ1GYEO8NVttUHRYdlI+LJKVAoHt0j5zMBKxIYC83Ezk?=
 =?us-ascii?Q?XZbYC28hi4V7FHzxG47w4fc6XqYGbwcV8pJR/qGsRvruqHxEU3lwWFrE0e+c?=
 =?us-ascii?Q?DIjQMPMRAkgNRH2Zx7Terzv6Ue93CbkVA+23+PNaSfv5TLUraRD53i2BVJwi?=
 =?us-ascii?Q?Ul2cVu/K/d77SOxtpyx2PHLziw93eBPDoXvoDyFfdYOnPqeR5RAlhkXCk/YR?=
 =?us-ascii?Q?ZAf4TnIYHAJTSPFxisFDElLvlki/aX/Cg1sKh293K/miNmdSX4uA99AivZGh?=
 =?us-ascii?Q?gpROLSZGIA76sfr72hPFwr65YY4j+QmreJs2UGgPFHyemJHoKwwJ07OOZezC?=
 =?us-ascii?Q?dxPWcjKoaE7UrefFWLHVataxwB8aP54KXUFeYAi1jsO0qIp8Ebo3Aqh3WybZ?=
 =?us-ascii?Q?YTrHhx1e66tI+voIkTE933g4qL+knts/CemP+93O6Lm7T1VmjKIxMnm1ZVZK?=
 =?us-ascii?Q?7qSe93ZauSN9MB+DQbpa+1s61GkU7JqWwFWEUQirK+lu60Jz54nbqOGWYiIb?=
 =?us-ascii?Q?AGtZIbvhlJw++DSikkS3Fxq3kTmQZduIGkCc9QWF8guOlC3Ks81j+fMLM78V?=
 =?us-ascii?Q?8geHh/q0HyYpcGNKmVrN6BSjrLNMHFI4RAh0suVwBkuv6EBXtqx9f3//iOri?=
 =?us-ascii?Q?jGk1i4ZXJukrTRSkBwy7JBzugEB1U+2jm6Q/TtAOA9Rz2hXsk5byTx+O1JsR?=
 =?us-ascii?Q?R7/W4QgoLNngrb99SKZjXb9ALyd/7i2iFv9xJMNZgmRVKb1VqeB6N4EZXKGT?=
 =?us-ascii?Q?y5IS2k8t6VJwhvYlm4VaDF0KhtW5hhcDpv6YczWc4ilc4E4JlHGlQYmt67F9?=
 =?us-ascii?Q?yUFRNqkYlvy3x5+KkAB07kuldH1ufeVT25pjU2T2IYg62io/7gSmqDQR00Nk?=
 =?us-ascii?Q?Lq0rxqDz5BM+CXLxtLQ0vrC3wXbQUVMIOnrdfo2o5Jccyt3M3auZW4wtmllu?=
 =?us-ascii?Q?C43f7wu0XGtMcVddIITXSpJiK9O1zo9yaOPcMAvFR/Bo0o1yvOfF4jS6dmxg?=
 =?us-ascii?Q?TrwVAaH6DKkZ/ptX0pMg5Ra89Vh/DuJaMQ/3GHvH?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 304f126f-b24c-4f51-d802-08dbca43388f
X-MS-Exchange-CrossTenant-AuthSource: MN0PR11MB6206.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 11 Oct 2023 10:17:06.5246
 (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: p4Co/Nmnwix4Jng3fvo9pdNdAdRFXoA/Kes5Xe1MD0UEropPnyQZB8OVsas8ET7sFpfhv1fUSYKMVvp8MWw5pw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM4PR11MB5437
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,
        DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,
        RCVD_IN_DNSWL_BLOCKED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,
        SPF_HELO_NONE,SPF_NONE,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
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Wed, 11 Oct 2023 03:17:26 -0700 (PDT)

On 2023-10-10 at 09:49:54 -0400, Mathieu Desnoyers wrote:
> On 2023-10-09 01:14, Chen Yu wrote:
> > On 2023-09-30 at 07:45:38 -0400, Mathieu Desnoyers wrote:
> > > On 9/30/23 03:11, Chen Yu wrote:
> > > > Hi Mathieu,
> > > > 
> > > > On 2023-09-29 at 14:33:50 -0400, Mathieu Desnoyers wrote:
> > > > > Introduce the WAKEUP_BIAS_PREV_IDLE scheduler feature. It biases
> > > > > select_task_rq towards the previous CPU if it was almost idle
> > > > > (avg_load <= 0.1%).
> > > > 
> > > > Yes, this is a promising direction IMO. One question is that,
> > > > can cfs_rq->avg.load_avg be used for percentage comparison?
> > > > If I understand correctly, load_avg reflects that more than
> > > > 1 tasks could have been running this runqueue, and the
> > > > load_avg is the direct proportion to the load_weight of that
> > > > cfs_rq. Besides, LOAD_AVG_MAX seems to not be the max value
> > > > that load_avg can reach, it is the sum of
> > > > 1024 * (y + y^1 + y^2 ... )
> > > > 
> > > > For example,
> > > > taskset -c 1 nice -n -20 stress -c 1
> > > > cat /sys/kernel/debug/sched/debug | grep 'cfs_rq\[1\]' -A 12 | grep "\.load_avg"
> > > >     .load_avg                      : 88763
> > > >     .load_avg                      : 1024
> > > > 
> > > > 88763 is higher than LOAD_AVG_MAX=47742
> > > 
> > > I would have expected the load_avg to be limited to LOAD_AVG_MAX somehow,
> > > but it appears that it does not happen in practice.
> > > 
> > > That being said, if the cutoff is really at 0.1% or 0.2% of the real max,
> > > does it really matter ?
> > > 
> > > > Maybe the util_avg can be used for precentage comparison I suppose?
> > > [...]
> > > > Or
> > > > return cpu_util_without(cpu_rq(cpu), p) * 1000 <= capacity_orig_of(cpu) ?
> > > 
> > > Unfortunately using util_avg does not seem to work based on my testing.
> > > Even at utilization thresholds at 0.1%, 1% and 10%.
> > > 
> > > Based on comments in fair.c:
> > > 
> > >   * CPU utilization is the sum of running time of runnable tasks plus the
> > >   * recent utilization of currently non-runnable tasks on that CPU.
> > > 
> > > I think we don't want to include currently non-runnable tasks in the
> > > statistics we use, because we are trying to figure out if the cpu is a
> > > idle-enough target based on the tasks which are currently running, for the
> > > purpose of runqueue selection when waking up a task which is considered at
> > > that point in time a non-runnable task on that cpu, and which is about to
> > > become runnable again.
> > > 
> > 
> > Although LOAD_AVG_MAX is not the max possible load_avg, we still want to find
> > a proper threshold to decide if the CPU is almost idle. The LOAD_AVG_MAX
> > based threshold is modified a little bit:
> > 
> > The theory is, if there is only 1 task on the CPU, and that task has a nice
> > of 0, the task runs 50 us every 1000 us, then this CPU is regarded as almost
> > idle.
> > 
> > The load_sum of the task is:
> > 50 * (1 + y + y^2 + ... + y^n)
> > The corresponding avg_load of the task is approximately
> > NICE_0_WEIGHT * load_sum / LOAD_AVG_MAX = 50.
> > So:
> > 
> > /* which is close to LOAD_AVG_MAX/1000 = 47 */
> > #define ALMOST_IDLE_CPU_LOAD   50
> 
> Sorry to be slow at understanding this concept, but this whole "load" value
> is still somewhat magic to me.
> 
> Should it vary based on CONFIG_HZ_{100,250,300,1000}, or is it independent ?
> Where is it documented that the load is a value in "us" out of a window of
> 1000 us ?
>

My understanding is that, the load_sum of a single task is a value in "us" out
of a window of 1000 us, while the load_avg of the task will multiply the weight
of the task. In this case a task with nice 0 is NICE_0_WEIGHT = 1024.

__update_load_avg_se -> ___update_load_sum calculate the load_sum of a task(there
is comments around ___update_load_sum to describe the pelt calculation),
and ___update_load_avg() calculate the load_avg based on the task's weight.
 
> And with this value "50", it would cover the case where there is only a
> single task taking less than 50us per 1000us, and cases where the sum for
> the set of tasks on the runqueue is taking less than 50us per 1000us
> overall.
> 
> > 
> > static bool
> > almost_idle_cpu(int cpu, struct task_struct *p)
> > {
> >         if (!sched_feat(WAKEUP_BIAS_PREV_IDLE))
> >                 return false;
> >         return cpu_load_without(cpu_rq(cpu), p) <= ALMOST_IDLE_CPU_LOAD;
> > }
> > 
> > Tested this on Intel Xeon Platinum 8360Y, Ice Lake server, 36 core/package,
> > total 72 core/144 CPUs. Slight improvement is observed in hackbench socket mode:
> > 
> > socket mode:
> > hackbench -g 16 -f 20 -l 480000 -s 100
> > 
> > Before patch:
> > Running in process mode with 16 groups using 40 file descriptors each (== 640 tasks)
> > Each sender will pass 480000 messages of 100 bytes
> > Time: 81.084
> > 
> > After patch:
> > Running in process mode with 16 groups using 40 file descriptors each (== 640 tasks)
> > Each sender will pass 480000 messages of 100 bytes
> > Time: 78.083
> > 
> > 
> > pipe mode:
> > hackbench -g 16 -f 20 --pipe  -l 480000 -s 100
> > 
> > Before patch:
> > Running in process mode with 16 groups using 40 file descriptors each (== 640 tasks)
> > Each sender will pass 480000 messages of 100 bytes
> > Time: 38.219
> > 
> > After patch:
> > Running in process mode with 16 groups using 40 file descriptors each (== 640 tasks)
> > Each sender will pass 480000 messages of 100 bytes
> > Time: 38.348
> > 
> > It suggests that, if the workload has larger working-set/cache footprint, waking up
> > the task on its previous CPU could get more benefit.
> 
> In those tests, what is the average % of idleness of your cpus ?
> 

For hackbench -g 16 -f 20 --pipe  -l 480000 -s 100, it is around 8~10% idle
For hackbench -g 16 -f 20   -l 480000 -s 100, it is around 2~3% idle 

Then the CPUs in packge 1 are offlined to get stable result when the group number is low.
hackbench -g 1 -f 20 --pipe  -l 480000 -s 100
Some CPUs are busy, others are idle, and some are half-busy.
Core	CPU	Busy%
-	-	49.57
0	0	1.89
0	72	75.55
1	1	100.00
1	73	0.00
2	2	100.00
2	74	0.00
3	3	100.00
3	75	0.01
4	4	78.29
4	76	17.72
5	5	100.00
5	77	0.00


hackbench -g 1 -f 20  -l 480000 -s 100
Core	CPU	Busy%
-	-	48.29
0	0	57.94
0	72	21.41
1	1	83.28
1	73	0.00
2	2	11.44
2	74	83.38
3	3	21.45
3	75	77.27
4	4	26.89
4	76	80.95
5	5	5.01
5	77	83.09


echo NO_WAKEUP_BIAS_PREV_IDLE > /sys/kernel/debug/sched/features 
hackbench -g 1 -f 20 --pipe  -l 480000 -s 100
Running in process mode with 1 groups using 40 file descriptors each (== 40 tasks)
Each sender will pass 480000 messages of 100 bytes
Time: 9.434

echo WAKEUP_BIAS_PREV_IDLE > /sys/kernel/debug/sched/features 
hackbench -g 1 -f 20 --pipe  -l 480000 -s 100
Running in process mode with 1 groups using 40 file descriptors each (== 40 tasks)
Each sender will pass 480000 messages of 100 bytes
Time: 9.373

thanks,
Chenyu