Re: [RFC PATCH 2/3] clk: sunxi-ng: Implement precalculated NKM rate selection

[Frank Oltmanns <frank@oltmanns.dev>]

Hi Julian,

On 2023-05-28 at 09:19:36 +1000, Julian Calaby <julian.calaby@gmail.com> wrote:
> Hi Frank,
>
> On Sat, May 27, 2023 at 11:37 PM Frank Oltmanns <frank@oltmanns.dev> wrote:
>>
>> Add a new precalculation method for NKM clock rate selection in the
>> sunxi-ng clock driver. Introduce ccu_nkm_find_best_precalc which uses a
>> precalculated table of valid NKM combinations (struct clk_nkm_table and
>> struct clk_nkm_combo) to find the best rate. This approach provides
>> faster rate selection by searching a table of valid combinations rather
>> than calculating for all possible combinations.
>>
>> The table of NKM combinations needs to be initialized with meaningful
>> combinations only, i.e. removing redundant combinations that result in
>> the same rate.
>>
>> Keep the existing ccu_nkm_find_best function in place and use it as a
>> fallback if no precalculated table is provided.
>>
>> Signed-off-by: Frank Oltmanns <frank@oltmanns.dev>
>> ---
>>  drivers/clk/sunxi-ng/ccu_nkm.c | 84 +++++++++++++++++++++++++++-------
>>  drivers/clk/sunxi-ng/ccu_nkm.h | 26 +++++++++++
>>  2 files changed, 94 insertions(+), 16 deletions(-)
>>
>> diff --git a/drivers/clk/sunxi-ng/ccu_nkm.c b/drivers/clk/sunxi-ng/ccu_nkm.c
>> index 94d2a83992b2..9652f6df17bd 100644
>> --- a/drivers/clk/sunxi-ng/ccu_nkm.c
>> +++ b/drivers/clk/sunxi-ng/ccu_nkm.c
>> @@ -54,6 +54,49 @@ static unsigned long ccu_nkm_find_best(unsigned long parent, unsigned long rate,
>>         return best_rate;
>>  }
>>
>> +static unsigned long ccu_nkm_find_best_precalc(unsigned long parent,
>> +                                              unsigned long rate,
>> +                                              struct _ccu_nkm *nkm,
>> +                                              struct clk_nkm_table *table)
>> +{
>> +       unsigned long best_rate = 0, best_diff = ULONG_MAX;
>> +       unsigned long best_n = 0, best_k = 0, best_m = 0;
>> +       int start = 0, end = table->num - 1, mid;
>> +
>> +       while (start <= end) {
>> +               unsigned long tmp_rate;
>> +               unsigned long tmp_diff;
>> +
>> +               mid = (start + end) / 2;
>> +
>> +               tmp_rate = parent * table->combos[mid].n * table->combos[mid].k /
>> +                          table->combos[mid].m;
>> +
>> +               tmp_diff = abs(rate - tmp_rate);
>> +
>> +               if (tmp_diff < best_diff) {
>> +                       best_rate = tmp_rate;
>> +                       best_diff = tmp_diff;
>> +                       best_n = table->combos[mid].n;
>> +                       best_k = table->combos[mid].k;
>> +                       best_m = table->combos[mid].m;
>> +                       if (best_diff == 0)
>> +                               goto out;
>> +               }
>

Thank you for your feedback!

In my proposal, the code performs a binary search by
 1. taking the element in the middle (mid)
 2. calculating the rate of the element (tmp_rate)
 3. calculating the difference to the requested rate (tmp_diff)
 4. if the diff is better than the best_diff making it the new best
    n-k-m-combo (the if block)

> If the table was sorted by n * k / m, this could just be a process of

Please note, the table already has to be sorted for the function to
work, as is the nature of a binary search. I should definitely add
comments. I'm sorry, the code was intended more as a basis to discuss
the general idea that I described in the cover letter. I should have
made that clearer.

> searching through until we either:
> - find that the first rate in the table is too high

I could see that I could add two steps in the beginning, before the loop:
 - Take the first element and see if its rate is greater than the
   requested rate, if so immediatly return it
 - Take the last element and see if its rate is less than the requested
   rate, if so immediatly return it

Is that what you mean? I'd have to run some simulations to see, if this
is a real improvement, because we would need two additional rate
calculations. Worst case would therefore be 2+log(n) calculations
instead of log(n) and the code would be slightly more complicated in my
opinion. But if we run this function with all possible parents rate (as
suggested in the end of my cover letter) these two special cases could
very well be often applicable. Thanks!

> - find an exact rate

What do you mean by "exact rate"? Do you mean a rate that matches the
requested rate exactly. This is what the code is already trying to do.
But, as this is not always possible, in cases where it does not find an
exact match, it takes the closest match instead.

> - go above the requested rate, then there's only two to compare: our
> current rate and the previous one

Sorry, you've lost me here. How would I go above the requested rate? You
would have to do the binary search to find that rate, but then why not
search the closest rate directly (as the code does) instead of searching
the closest rate above the requested (as you proposed). I feel like
either one of us is missing something. :)

> This should massively simplify this function and would still work with
> a binary search.

Sidenote, we could store best_index instead of best_n, best_k, best_m,
but for the first iteration I tried to keep it as close as possible to
the original ccu_nkm_find_best() function.

>
>> +               if (rate < tmp_rate)
>> +                       end = mid - 1;
>> +               else
>> +                       start = mid + 1;
>> +       }
>> +
>> +out:
>> +       nkm->n = best_n;
>> +       nkm->k = best_k;
>> +       nkm->m = best_m;
>> +
>> +       return best_rate;
>> +}
>> +
>>  static void ccu_nkm_disable(struct clk_hw *hw)
>>  {
>>         struct ccu_nkm *nkm = hw_to_ccu_nkm(hw);
>> diff --git a/drivers/clk/sunxi-ng/ccu_nkm.h b/drivers/clk/sunxi-ng/ccu_nkm.h
>> index 6601defb3f38..fa5551724921 100644
>> --- a/drivers/clk/sunxi-ng/ccu_nkm.h
>> +++ b/drivers/clk/sunxi-ng/ccu_nkm.h
>> @@ -12,6 +12,30 @@
>>  #include "ccu_div.h"
>>  #include "ccu_mult.h"
>>
>> +struct clk_nkm_combo {
>> +       u8      n;
>> +       u8      k;
>> +       u8      m;
>> +};
>> +
>> +/**
>> + * struct clk_nkm_table - Table of all meaningful combinations for n, k, and m
>> + *
>> + * @num: Number of entries in the table
>> + * @combos: Array of combos (of size num) that are supported by this clock.
>> + *
>> + * This table shall contain all meaningful combinations of n, k, and m. That
>> + * means that combinations that result in the same clock rate shall only be
>> + * listed once. For example, if both
>> + * { .n = 1, .k = 2, .m = 2} and  { .n = 2, .k = 2, .m = 4}
>> + * are valid values for n, k, and m, only one of them would be allowed because
>> + * both result in a factor of 1.0.
>> + */
>> +struct clk_nkm_table {
>> +       size_t                  num;
>> +       struct clk_nkm_combo    *combos;
>
> Should this be a "flex" array, i.e.
>
> struct clk_nkm_combo combos[]

Thanks, noted. I'll look into that once we have an agreement on the
general concept. I think it depends on the fact if we want to use values
that have been calculated off-line (i.e. prior to compilation) or if we
want to create the table at run-time (i.e. when needed) using kmalloc.
See my alternate proposals in the cover letter for details. I'll need to
check if the run-time approach works with "flex" arrays.

Thanks,
  Frank

>
>> +};
>> +
>>  /*
>>   * struct ccu_nkm - Definition of an N-K-M clock
>>   *
>
> Thanks,