Rounding methods (precise vs coarse)

[lucacutrignelli]

Hello @francof2a,

I would like to discuss the rounding methods of fxpmath in comparison with other existing solutions.

Throughout the explanation I'll refer to the documents
http://cfs-vision.com/2017/08/14/learning-systemc-001-data-types/
https://nl.mathworks.com/help/fixedpoint/ug/rounding.html

Precise rounding:

I define this way the rounding methods that only differ for handling of tie cases

Rounding method	SystemC	Matlab	fxpmath	Explanation
Convergent rounding	SC_RND_CONV	convergent	around	https://nl.mathworks.com/help/fixedpoint/ug/rounding-mode-convergent.html
Rounding to infinity	SC_RND_INF	round	N/A	https://nl.mathworks.com/help/fixedpoint/ug/rounding-mode-round.html
Rounding to plus infinity	SC_RND	nearest	N/A	https://nl.mathworks.com/help/fixedpoint/ug/rounding-mode-nearest.html
Rounding to zero	SC_RND_ZERO	N/A	N/A
Rounding to minus infinity	SC_RND_MIN_INF	N/A	N/A

Coarse rounding:

I define this way the rounding methods that are actually operating a truncation of the data to a neighbouring code, so they produce a larger rounding error than the Precise rounding

Rounding method	SystemC	Matlab	fxpmath	Explanation
Truncation	SC_TRN	floor	floor	https://nl.mathworks.com/help/fixedpoint/ug/rounding-mode-floor.html
Truncation to zero	SC_TRN_ZERO	zero	fix/trunc	https://nl.mathworks.com/help/fixedpoint/ug/rounding-mode-zero.html
Truncation to plus infinity	N/A	ceil	ceil	https://nl.mathworks.com/help/fixedpoint/ug/rounding-mode-ceiling.html

I hope these comparison tables are clear and might be a useful summary of the current supported roundings.

From the tables above, Fxp is well covered for the coarse rounding cases, but only provides one precise rounding case (the convergent rounding). My assumption is that this is due to the underlying python rounding functions that fxpmath is using.
Nonetheless, in my experience in hardware modeling the other precise rounding methods might prove useful. Particularly the Round to infinity and Round to plus infinity.

My question is: would there be a big performance penalty in implementing the other precise rounding methods mentioned above?
Could you comment on the complexity of the implementation?

Thanks!

[francof2a]

Hello @lucacutrignelli

First of all, sorry about the delay in the answer, but I was busy with other projects!

Thank you for such a detailed post, it is very clear.
You're right about rounding implementations in fxpmath, all of them are related with numpy rounding implementations. However that is not a impediment to implement more method, but it's pretty sure those method will perform worst (foot note: fxpmath prioritizes functionality over performance).

I was thinking about some straightforward implementations of remaining methods you're proposing and I think there a some could work:

Rounding to infinity

$$ \text{trunc}(x + 2 \cdot \text{sign}(x) \cdot 2^{(-2 \cdot n_{frac})}) $$

where $n_{frac}$ is the number of fractional bit of Fxp variable and $x$ is the float value(s).

For example:

# Fxp template
n_frac = 2
n_int = 0
n_word = n_int + n_frac
overflow = 'saturate'

fxp_ref = Fxp(None, signed=True, n_int=n_int, n_frac=n_frac, overflow=overflow)

# float values
ratio = 4
float_precision = fxp_ref.precision / ratio
x = np.arange(fxp_ref.lower - (ratio*float_precision), fxp_ref.upper + ratio*float_precision, step=float_precision)

# fxp
rounding = 'trunc'
fxp_var = Fxp(x + 2*np.sign(x)*2**(-2*n_frac), rounding=rounding, like=fxp_ref)

Rounding to plus infinity

$$ \lceil x - 2^{(-2 \cdot n_{frac})} \rceil $$

rounding = 'ceil'
fxp_var = Fxp(x-2**(-2*n_frac), rounding=rounding, like=fxp_ref)

Rounding to zero

$$ \text{trunc}(x + \text{sign}(x) \cdot 2^{(-2 \cdot n_{frac})}) $$

rounding = 'trunc'
fxp_var = Fxp(x + np.sign(x)*2**(-2*n_frac), rounding=rounding, like=fxp_ref)

Rounding to minus infinity

$$ \lfloor x - 2^{(-2 \cdot n_{frac})} \rfloor $$

rounding = 'floor'
fxp_var = Fxp(x+2**(-2*n_frac), rounding=rounding, like=fxp_ref)

Conclusion

If these approaches are right, those method can be implemented into Fxp with no problems and without a significant reduction of performance

What do you think?

[lucacutrignelli]

Hello @francof2a,

thanks for taking the time to look into this topic. Let me comment on your proposed implementation.

I found you had a good intuition to implement the missing precise rounding on top of trunc/ceil/floor rather than on top of around, as the convergent rounding would be more problematic to reuse due to the special treatment of tie conditions.
From this perspective, the question becomes whether doing manipulations/corrections on the input values in Fxp assignments, we can obtain the correct result expected by the precise rounding.

If I understood correctly your approach, as I tried to summarize above, I agree with it: it looks viable and probably not adding much performance penalty.

Concerning the correction formulas, I reviewed them and they don't seem correct to me. From what I understand when sketching input/output relationship, in order to match the behavior of trunc/ceil/floor with the expected one from round_inf/round_plus_inf/... we need to always correct the input data by adding/subtracting half of the precision of the target Fxp variable. So add/subtract 2** (-n_frac-1).

The corrections you proposed are different and don't seem to generalize when n_frac is different than 2
Let me propose another set of corrections and try to see where the two sets of corrections differ.

Rounding to infinity

fxp_var=Fxp(x+np.sign(x)*2**(-n_frac-1), rounding='trunc', like=fxp_ref)

Rounding to plus infinity

fxp_var=Fxp(x+ 2**(-n_frac-1), rounding='floor', like=fxp_ref)

Rounding to minus infinity

fxp_var=Fxp(x - 2**(-n_frac-1), rounding='ceil', like=fxp_ref)

Rounding to zero

This looks trickier, as it would seem easier to distinguish two cases:

For positive input values
fxp_var=Fxp(x - 2**(-n_frac-1), rounding='ceil', like=fxp_ref)

For negative input values
fxp_var=Fxp(x + 2**(-n_frac-1), rounding='floor', like=fxp_ref)

Trying to put it together in a general (both positive and negative inputs) but cumbersome formula:
fxp_var=Fxp (np.sign(x) * Fxp(np.sign(x)*x - 2**(-n_frac-1), rounding='ceil', like=fxp_ref), like=fxp_ref)

Examples of supposedly incorrect behavior of the original proposal

These cases seem not correct to me.

Rounding to infinity
if n_frac = 3, there are too many x values that are rounded to code 0 (x=-0.0625 should be rounded to code -0.125 instead of code 0)

Rounding to plus infinity
if n_frac =3, we are switching too soon to code 0.125 (for x=0.03125 instead of 0.0625)

Conclusion

Please have a look at my proposal and let's see if we agree with the corrections to the input data.
I still might be overlooking something and there could be a better way to handle Rounding to zero, but I could not find easily.
I am sorry I have not made any graph. I can come back with graphs, if I am not clear.