lkml.org 
[lkml]   [2012]   [Apr]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [RFC][PATCH 0/3] gcc work-around and math128
From
Date
On Tue, 2012-04-24 at 14:15 -0700, Andy Lutomirski wrote:
> > The second two implement a few u128 operations so we can do 128bit math.. I
> > know a few people will die a little inside, but having nanosecond granularity
> > time accounting leads to very big numbers very quickly and when you need to
> > multiply them 64bit really isn't that much.
>
> I played with some of this stuff awhile ago, and for timekeeping, it
> seemed like a 64x32->96 bit multiply followed by a right shift was
> enough, and that operation is a lot faster on 32-bit architectures than
> a full 64x64->128 multiply.

The SCHED_DEADLINE use case is not that, it multiplies two time
intervals. Basically it needs to evaluate if a task activation still
fits in the old period or if it needs to shift the deadline and start a
new period.

It needs to do: runtime / (deadline - t) < budget / period
which transforms into: (deadline - t) * period < budget * runtime

hence the 64x64->128 mult and 128 compare.

> Something like:
>
> uint64_t mul_64_32_shift(uint64_t a, uint32_t mult, uint32_t shift)
> {
> return (uint64_t)( ((__uint128_t)a * (__uint128_t)mult) >> shift );
> }

That looks a lot like what we grew mult_frac() for, it does:

/*
* Multiplies an integer by a fraction, while avoiding unnecessary
* overflow or loss of precision.
*/
#define mult_frac(x, numer, denom)( \
{ \
typeof(x) quot = (x) / (denom); \
typeof(x) rem = (x) % (denom); \
(quot * (numer)) + ((rem * (numer)) / (denom)); \
} \
)


and is used in __cycles_2_ns() and friends.


\
 
 \ /
  Last update: 2012-04-24 23:37    [W:0.212 / U:0.072 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site