lkml.org 
[lkml]   [2022]   [May]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectRe: [PATCH v3] sched/fair: Introduce SIS_UTIL to search idle CPU based on sum of util_avg
Hi Prateek,
On Fri, May 13, 2022 at 12:07:00PM +0530, K Prateek Nayak wrote:
> Hello Chenyu,
>
> Sorry for the delay with analysis.
>
Thanks very much for the test and analysis in detail.
>
> Following are the results from dual socket Zen3 platform (2 x 64C/128T) running with
> various NPS configuration:
May I know if in all NPS mode, all LLC domains have 16 CPUs?
>
> Following is the NUMA configuration for each NPS mode on the system:
>
> NPS1: Each socket is a NUMA node.
>     Total 2 NUMA nodes in the dual socket machine.
>
>     Node 0: 0-63,   128-191
>     Node 1: 64-127, 192-255
>
> NPS2: Each socket is further logically divided into 2 NUMA regions.
>     Total 4 NUMA nodes exist over 2 socket.
>    
>     Node 0: 0-31,   128-159
>     Node 1: 32-63,  160-191
>     Node 2: 64-95,  192-223
>     Node 3: 96-127, 223-255
>
> NPS4: Each socket is logically divided into 4 NUMA regions.
>     Total 8 NUMA nodes exist over 2 socket.
>    
>     Node 0: 0-15,    128-143
>     Node 1: 16-31,   144-159
>     Node 2: 32-47,   160-175
>     Node 3: 48-63,   176-191
>     Node 4: 64-79,   192-207
>     Node 5: 80-95,   208-223
>     Node 6: 96-111,  223-231
>     Node 7: 112-127, 232-255
>
> Kernel versions:
> - tip:      5.18-rc1 tip sched/core
> - SIS_UTIL:    5.18-rc1 tip sched/core + this patch
>
> When we began testing, tip was at:
>
> commit: a658353167bf "sched/fair: Revise comment about lb decision matrix"
>
> Following are the results from the benchmark:
>
> * - Data points of concern
>
> ~~~~~~~~~
> hackbench
> ~~~~~~~~~
>
> NPS1
>
> Test:                   tip                     SIS_UTIL
>  1-groups:         4.64 (0.00 pct)         4.70 (-1.29 pct)
>  2-groups:         5.38 (0.00 pct)         5.45 (-1.30 pct)
>  4-groups:         6.15 (0.00 pct)         6.10 (0.81 pct)
>  8-groups:         7.42 (0.00 pct)         7.42 (0.00 pct)
> 16-groups:        10.70 (0.00 pct)        11.69 (-9.25 pct)  *
>
> NPS2
>
> Test:                   tip                     SIS_UTIL
>  1-groups:         4.70 (0.00 pct)         4.70 (0.00 pct)
>  2-groups:         5.45 (0.00 pct)         5.46 (-0.18 pct)
>  4-groups:         6.13 (0.00 pct)         6.05 (1.30 pct)
>  8-groups:         7.30 (0.00 pct)         7.05 (3.42 pct)
> 16-groups:        10.30 (0.00 pct)        10.12 (1.74 pct)
>
> NPS4
>
> Test:                   tip                     SIS_UTIL
>  1-groups:         4.60 (0.00 pct)         4.75 (-3.26 pct)  *
>  2-groups:         5.41 (0.00 pct)         5.42 (-0.18 pct)
>  4-groups:         6.12 (0.00 pct)         6.00 (1.96 pct)
>  8-groups:         7.22 (0.00 pct)         7.10 (1.66 pct)
> 16-groups:        10.24 (0.00 pct)        10.11 (1.26 pct)
>
> ~~~~~~~~
> schbench
> ~~~~~~~~
>
> NPS 1
>
> #workers:   tip                     SIS_UTIL
>   1:      29.00 (0.00 pct)        21.00 (27.58 pct)
>   2:      28.00 (0.00 pct)        28.00 (0.00 pct)
>   4:      31.50 (0.00 pct)        31.00 (1.58 pct)
>   8:      42.00 (0.00 pct)        39.00 (7.14 pct)
>  16:      56.50 (0.00 pct)        54.50 (3.53 pct)
>  32:      94.50 (0.00 pct)        94.00 (0.52 pct)
>  64:     176.00 (0.00 pct)       175.00 (0.56 pct)
> 128:     404.00 (0.00 pct)       394.00 (2.47 pct)
> 256:     869.00 (0.00 pct)       863.00 (0.69 pct)
> 512:     58432.00 (0.00 pct)     55424.00 (5.14 pct)
>
> NPS2
>
> #workers:      tip                     SIS_UTIL
>   1:      26.50 (0.00 pct)        25.00 (5.66 pct)
>   2:      26.50 (0.00 pct)        25.50 (3.77 pct)
>   4:      34.50 (0.00 pct)        34.00 (1.44 pct)
>   8:      45.00 (0.00 pct)        46.00 (-2.22 pct)
>  16:      56.50 (0.00 pct)        60.50 (-7.07 pct)        *
>  32:      95.50 (0.00 pct)        93.00 (2.61 pct)
>  64:     179.00 (0.00 pct)       179.00 (0.00 pct)
> 128:     369.00 (0.00 pct)       376.00 (-1.89 pct)
> 256:     898.00 (0.00 pct)       903.00 (-0.55 pct)
> 512:     56256.00 (0.00 pct)     57088.00 (-1.47 pct)
>
> NPS4
>
> #workers:    tip                     SIS_UTIL
>   1:      25.00 (0.00 pct)        21.00 (16.00 pct)
>   2:      28.00 (0.00 pct)        24.00 (14.28 pct)
>   4:      29.50 (0.00 pct)        29.50 (0.00 pct)
>   8:      41.00 (0.00 pct)        37.50 (8.53 pct)
>  16:      65.50 (0.00 pct)        64.00 (2.29 pct)
>  32:      93.00 (0.00 pct)        94.50 (-1.61 pct)
>  64:     170.50 (0.00 pct)       175.50 (-2.93 pct)
> 128:     377.00 (0.00 pct)       368.50 (2.25 pct)
> 256:     867.00 (0.00 pct)       902.00 (-4.03 pct)
> 512:     58048.00 (0.00 pct)     55488.00 (4.41 pct)
>
> ~~~~~~
> tbench
> ~~~~~~
>
> NPS 1
>
> Clients:     tip                     SIS_UTIL
>     1    443.31 (0.00 pct)       456.19 (2.90 pct)
>     2    877.32 (0.00 pct)       875.24 (-0.23 pct)
>     4    1665.11 (0.00 pct)      1647.31 (-1.06 pct)
>     8    3016.68 (0.00 pct)      2993.23 (-0.77 pct)
>    16    5374.30 (0.00 pct)      5246.93 (-2.36 pct)
>    32    8763.86 (0.00 pct)      7878.18 (-10.10 pct)     *
>    64    15786.93 (0.00 pct)     12958.47 (-17.91 pct)    *
>   128    26826.08 (0.00 pct)     26741.14 (-0.31 pct)
>   256    24207.35 (0.00 pct)     52041.89 (114.98 pct)
>   512    51740.58 (0.00 pct)     52084.44 (0.66 pct)
>  1024    51177.82 (0.00 pct)     53126.29 (3.80 pct)
>
> NPS 2
>
> Clients:     tip                     SIS_UTIL
>     1    449.49 (0.00 pct)       447.96 (-0.34 pct)
>     2    867.28 (0.00 pct)       869.52 (0.25 pct)
>     4    1643.60 (0.00 pct)      1625.91 (-1.07 pct)
>     8    3047.35 (0.00 pct)      2952.82 (-3.10 pct)
>    16    5340.77 (0.00 pct)      5251.41 (-1.67 pct)
>    32    10536.85 (0.00 pct)     8843.49 (-16.07 pct)     *
>    64    16543.23 (0.00 pct)     14265.35 (-13.76 pct)    *
>   128    26400.40 (0.00 pct)     25595.42 (-3.04 pct)
>   256    23436.75 (0.00 pct)     47090.03 (100.92 pct)
>   512    50902.60 (0.00 pct)     50036.58 (-1.70 pct)
>  1024    50216.10 (0.00 pct)     50639.74 (0.84 pct)
>
> NPS 4
>
> Clients:     tip                     SIS_UTIL
>     1    443.82 (0.00 pct)       459.93 (3.62 pct)
>     2    849.14 (0.00 pct)       882.17 (3.88 pct)
>     4    1603.26 (0.00 pct)      1629.64 (1.64 pct)
>     8    2972.37 (0.00 pct)      3003.09 (1.03 pct)
>    16    5277.13 (0.00 pct)      5234.07 (-0.81 pct)
>    32    9744.73 (0.00 pct)      9347.90 (-4.07 pct)      *
>    64    15854.80 (0.00 pct)     14180.27 (-10.56 pct)    *
>   128    26116.97 (0.00 pct)     24597.45 (-5.81 pct)     *
>   256    22403.25 (0.00 pct)     47385.09 (111.50 pct)
>   512    48317.20 (0.00 pct)     49781.02 (3.02 pct)
>  1024    50445.41 (0.00 pct)     51607.53 (2.30 pct)
>
> ~~~~~~
> Stream
> ~~~~~~
>
> - 10 runs
>
> NPS1
>
>               tip                     SIS_UTIL
>  Copy:   189113.11 (0.00 pct)    188490.27 (-0.32 pct)
> Scale:   201190.61 (0.00 pct)    204526.15 (1.65 pct)
>   Add:   232654.21 (0.00 pct)    234948.01 (0.98 pct)
> Triad:   226583.57 (0.00 pct)    228844.43 (0.99 pct)
>
> NPS2
>
> Test:         tip                     SIS_UTIL
>  Copy:   155347.14 (0.00 pct)    169386.29 (9.03 pct)
> Scale:   191701.53 (0.00 pct)    196110.51 (2.29 pct)
>   Add:   210013.97 (0.00 pct)    221088.45 (5.27 pct)
> Triad:   207602.00 (0.00 pct)    218072.52 (5.04 pct)
>
> NPS4
>
> Test:         tip                     SIS_UTIL
>  Copy:   136421.15 (0.00 pct)    140894.11 (3.27 pct)
> Scale:   191217.59 (0.00 pct)    190554.17 (-0.34 pct)
>   Add:   189229.52 (0.00 pct)    190871.88 (0.86 pct)
> Triad:   188052.99 (0.00 pct)    188417.63 (0.19 pct)
>
> - 100 runs
>
> NPS1
>
> Test:       tip                     SIS_UTIL
>  Copy:   244693.32 (0.00 pct)    232328.05 (-5.05 pct)
> Scale:   221874.99 (0.00 pct)    216858.39 (-2.26 pct)
>   Add:   268363.89 (0.00 pct)    265449.16 (-1.08 pct)
> Triad:   260945.24 (0.00 pct)    252240.56 (-3.33 pct)
>
> NPS2
>
> Test:       tip                     SIS_UTIL
>  Copy:   211262.00 (0.00 pct)    225240.03 (6.61 pct)
> Scale:   222493.34 (0.00 pct)    219094.65 (-1.52 pct)
>   Add:   280277.17 (0.00 pct)    275677.73 (-1.64 pct)
> Triad:   265860.49 (0.00 pct)    262584.22 (-1.23 pct)
>
> NPS4
>
> Test:       tip                     SIS_UTIL
>  Copy:   250171.40 (0.00 pct)    230983.60 (-7.66 pct)
> Scale:   222293.56 (0.00 pct)    215984.34 (-2.83 pct)
>   Add:   279222.16 (0.00 pct)    270402.64 (-3.15 pct)
> Triad:   262013.92 (0.00 pct)    254820.60 (-2.74 pct)
>
> ~~~~~~~~~~~~
> ycsb-mongodb
> ~~~~~~~~~~~~
>
> NPS1
>
> sched-tip:      303718.33 (var: 1.31)
> SIS_UTIL:       303529.33 (var: 0.67)    (-0.06%)
>
> NPS2
>
> sched-tip:      304536.33 (var: 2.46)
> SIS_UTIL:       303730.33 (var: 1.57)    (-0.26%)
>
> NPS4
>
> sched-tip:      301192.33 (var: 1.81)
> SIS_UTIL:       300101.33 (var: 0.35)   (-0.36%)
>
> ~~~~~~~~~~~~~~~~~~
>
> Notes:
>
> - There seems to be some noticeable regression for hackbench
>   with 16 groups in NPS1 mode.
Did the hackbench use the default fd number(20) in every group? If
this is the case, then there are 16 * 20 * 2 = 640 threads in the
system. I thought this should be overloaded, either in SIS_PROP or
SIS_UTIL, the search depth might be 4 and 0 respectively. And it
is also very likely the SIS_PROP will not find an idle CPU after
searching for 4 CPUs. So in theory there should be not much performance
difference with vs without the patch applied. But if the fd number is set
to a smaller one, the regression could be explained as you mentioned,
SIS_PROP search more aggressively.
> - There seems to be regression in tbench for case with number
>   of workers in range 32-128 (12.5% loaded to 50% loaded)
> - tbench reaches saturation early when system is fully loaded
>
> This probably show that the strategy in the initial v1 RFC
> seems to work better with our LLC where number of CPUs per LLC
> is low compared to systems with unified LLC. Given this is
> showing great results for unified LLC, maybe SIS_PROP and SIS_UTIL
> can be enabled based on the the size of LLC.
>
Yes, SIS_PROP searches more aggressively, but we attempts to replace
SIS_PROP with a more accurate policy.
> > [..snip..]
> >
> > [3]
> > Prateek mentioned that we should scan aggressively in an LLC domain
> > with 16 CPUs. Because the cost to search for an idle one among 16 CPUs is
> > negligible. The current patch aims to propose a generic solution and only
> > considers the util_avg. A follow-up change could enhance the scan policy
> > to adjust the scan_percent according to the CPU number in LLC.
>
> Following are some additional numbers I would like to share comparing SIS_PROP and
> SIS_UTIL:
>
Nice analysis.
> o Hackbench with 1 group
>
> With 1 group, following are the chances of SIS_PROP
> and SIS_UTIL finding an idle CPU when an idle CPU
> exists in LLC:
>
> +-----------------+---------------------------+---------------------------+--------+
> | Idle CPU in LLC | SIS_PROP able to find CPU | SIS_UTIL able to find CPU | Count  |
> +-----------------+---------------------------+---------------------------+--------+
> |        1        |             0             |             0             | 66444  |
> |        1        |             0             |             1             | 34153  |
> |        1        |             1             |             0             | 57204  |
> |        1        |             1             |             1             | 119263 |
> +-----------------+---------------------------+---------------------------+--------+
>
So SIS_PROP searches more, and get higher chance to find an idle CPU in a LLC with
16 CPUs.
> SIS_PROP vs no SIS_PROP CPU search stats:
>
> Total time without SIS_PROP: 90653653
> Total time with SIS_PROP: 53558942 (-40.92 pct)
> Total time saved: 37094711
>
What does no SIS_PROP mean? Is it with SIS_PROP disabled and
SIS_UTIL enabled? Or with both SIS_PROP and SIS_UTIL disabled?
If it is the latter, is there any performance difference between
the two?
> Following are number of CPUs SIS_UTIL will search when SIS_PROP limit >= 16 (LLC size):
>
> +--------------+-------+
> | CPU Searched | Count |
> +--------------+-------+
> |      0       | 10520 |
> |      1       |  7770 |
> |      2       | 11976 |
> |      3       | 17554 |
> |      4       | 13932 |
> |      5       | 15051 |
> |      6       |  8398 |
> |      7       |  4544 |
> |      8       |  3712 |
> |      9       |  2337 |
> |      10      |  4541 |
> |      11      |  1947 |
> |      12      |  3846 |
> |      13      |  3645 |
> |      14      |  2686 |
> |      15      |  8390 |
> |      16      | 26157 |
> +--------------+-------+
>
> - SIS_UTIL might be bailing out too early in some of these cases.
>
Right.
> o Hackbench with 16 group
>
> the success rate looks as follows:
>
> +-----------------+---------------------------+---------------------------+---------+
> | Idle CPU in LLC | SIS_PROP able to find CPU | SIS_UTIL able to find CPU |  Count  |
> +-----------------+---------------------------+---------------------------+---------+
> |        1        |             0             |             0             | 1313745 |
> |        1        |             0             |             1             |  694132 |
> |        1        |             1             |             0             | 2888450 |
> |        1        |             1             |             1             | 5343065 |
> +-----------------+---------------------------+---------------------------+---------+
>
> SIS_PROP vs no SIS_PROP CPU search stats:
>
> Total time without SIS_PROP: 5227299388
> Total time with SIS_PROP: 3866575188 (-26.03 pct)
> Total time saved: 1360724200
>
> Following are number of CPUs SIS_UTIL will search when SIS_PROP limit >= 16 (LLC size):
>
> +--------------+---------+
> | CPU Searched |  Count  |
> +--------------+---------+
> |      0       |  150351 |
> |      1       |  105116 |
> |      2       |  214291 |
> |      3       |  440053 |
> |      4       |  914116 |
> |      5       | 1757984 |
> |      6       | 2410484 |
> |      7       | 1867668 |
> |      8       |  379888 |
> |      9       |  84055  |
> |      10      |  55389  |
> |      11      |  26795  |
> |      12      |  43113  |
> |      13      |  24579  |
> |      14      |  32896  |
> |      15      |  70059  |
> |      16      |  150858 |
> +--------------+---------+
>
> - SIS_UTIL might be bailing out too early in most of these cases
>
It might be interesting to see what the current sum of util_avg is, and this suggested that,
even if util_avg is a little high, it might be still be worthwhile to search more CPUs.
> o tbench with 256 workers
>
> For tbench with 256 threads, SIS_UTIL works great as we have drastically cut down the number
> of CPUs to search.
>
> SIS_PROP vs no SIS_PROP CPU search stats:
>
> Total time without SIS_PROP: 64004752959
> Total time with SIS_PROP: 34695004390 (-45.79 pct)
> Total time saved: 29309748569
>
> Following are number of CPUs SIS_UTIL will search when SIS_PROP limit >= 16 (LLC size):
>
> +--------------+----------+
> | CPU Searched |  Count   |
> +--------------+----------+
> |      0       |  500077  |
> |      1       |  543865  |
> |      2       | 4257684  |
> |      3       | 27457498 |
> |      4       | 40208673 |
> |      5       | 3264358  |
> |      6       |  191631  |
> |      7       |  24658   |
> |      8       |   2469   |
> |      9       |   1374   |
> |      10      |   2008   |
> |      11      |   1300   |
> |      12      |   1226   |
> |      13      |   1179   |
> |      14      |   1631   |
> |      15      |  11678   |
> |      16      |   7793   |
> +--------------+----------+
>
> - This is where SIS_UTIL shines for tbench case with 256 workers as it is effective
>   at restricting search space well.
>
> o Observations
>
> SIS_PROP seems to have a higher chance of finding an idle CPU compared to SIS_UTIL
> in case of hackbench with 16-group. The gap between SIS_PROP and SIS_UTIL is wider
> with 16 groups compared to than with 1 group.
> Also SIS_PROP is more aggressive at saving time for 1-group compared to the
> case with 16-groups.
>
> The bailout from SIS_UTIL is fruitful for tbench with 256 workers leading to massive
> performance gain in a fully loaded system.
>
> Note: There might be some inaccuracies for the numbers presented for metrics that
> directly compare SIS_PROP and SIS_UTIL as both SIS_PROP and SIS_UTIL were enabled
> when gathering these data points and the results from SIS_PROP were returned from
> search_idle_cpu().
Do you mean the 'CPU Searched' calculated by SIS_PROP was collected with both SIS_UTIL
and SIS_PROP enabled?
> All the numbers for the above analysis were gathered in NPS1 mode.
>
I'm thinking of taking nr_llc number into consideration to adjust the search depth,
something like:
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index dd52fc5a034b..39b914599dce 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -9302,6 +9302,9 @@ static inline void update_idle_cpu_scan(struct lb_env *env,
llc_util_pct = (sum_util * 100) / (nr_llc * SCHED_CAPACITY_SCALE);
nr_scan = (100 - (llc_util_pct * llc_util_pct / 72)) * nr_llc / 100;
nr_scan = max(nr_scan, 0);
+ if (nr_llc <= 16 && nr_scan)
+ nr_scan = nr_llc;
+
WRITE_ONCE(sd_share->nr_idle_scan, nr_scan);
}

I'll offline the CPUs to make it 16 CPUs per LLC, and check what hackbench behaves.
thanks,
Chenyu

\
 
 \ /
  Last update: 2022-05-14 12:59    [W:0.164 / U:1.224 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site