Re: Need better is_better_time_interpolator() algorithm

From: john stultz
Date: Thu Aug 25 2005 - 14:04:06 EST


On Thu, 2005-08-25 at 12:43 -0600, Alex Williamson wrote:
> On Thu, 2005-08-25 at 10:36 -0700, john stultz wrote:
> > On Thu, 2005-08-25 at 10:44 -0600, Alex Williamson wrote:
> > > How can we munge these all together to come up with a single goodness
> > > factor for comparison? There's probably a thesis covering algorithms to
> > > handle this. Anyone know of one or have some good ideas? Thanks,
> >
> > With my timeofday rework code, the timesource structure (which was
> > influenced by the time interpolators) just uses a fixed "priority" vale.
> ...
> > Realistically I don't think too many systems will have multiple out of
> > tree timesources, so assigning the correct priority value shouldn't be
> > too difficult.
> >
> > This just seemed a bit more straight forward then sorting out some
> > weighting algorithm for their properties to select the best timesource.
>
> I don't know that it's that uncommon. Simply having one non-arch
> specific timer is enough to need to decided whether it's better than a
> generic timer. I assume pretty much every arch has a cycle timer. For
> smaller boxes, this might be the preferred timer given it's latency even
> if something like an hpet exists (mmio access are expensive). How do
> you hard code a value that can account for that?

Well, in my patches I set the default priority of cycle timer as being
very high, say 350, and the slower MMIO device as being a decent 250.
Then if we boot up on say a NUMA system, or if we find the cycle
counters to be out of sync, the cycle counter init code drops the
timesource priority of the cycle counter to something like 50.


> I agree, we could
> easily go too far and produce some bloated algorithm, but maybe it's
> simply a weighted product of a few variables.
>
> To start with, what would this do:
>
> (frequency) * (1/drift) * (1/latency) * (1/(jitter_factor * cpus))

It just seems that something like this could be for the most part
precomputed when you're writing the time_interpolator code into a single
priority value that the init code can tweak as needed.

> Something this simple at least starts to dynamically bring the factors
> together. All else being equal (and with no weighting), this would give
> the 1.5GHz/750ppm timer a higher priority than the 250MHz/500ppm timer.
> Is that good? I like your idea to make this user tunable after boot,
> but I still think there has to be a way to make a smarter decision up
> front. Thanks,

Shrug. I agree it needs improvement, so don't let me stop you from doing
something like what you have above. I just think its more complex then
necessary and might result in less predictable interpolator selections.

thanks
-john


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/