Skip to contentSkip to conversation

Need better is_better_time_interpolator() algorithm

DISCUSSION Alex Williamson 5 participants 12 messages Aug 25, 2005 – Aug 29, 2005

lore
Share & tools
lore
#0 lore raw

Hi,

In playing with an HPET device, I noticed that
kernel/timer.c:is_better_time_interpolator() is completely non-symmetric in the timer it returns. The test is simply:

return new->frequency > 2*time_interpolator->frequency ||
(unsigned long)new->drift < (unsigned long)time_interpolator->drift;

Given two timers:

(a) 1.5GHz, 750ppm
(b) 250Mhz, 500ppm

the resulting "better" timer is completely dependent on the order they're passed in. For example, (a),(b) = (b); (b),(a) = (a).

What are we really looking for in a "better" timer? There are at
least 4 factors that I can think of that seem important to determining a better clock:

* resolution (frequency)
* accuracy (drift)
* access latency (may be non-uniform across the system?)
* jitter (monotonically increasing)

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,

Alex

Signature · 1 line
Alex Williamson                             HP Linux & Open Source Lab
#1 lore raw
Quoted 19 lines · Alex Williamson

In playing with an HPET device, I noticed that
kernel/timer.c:is_better_time_interpolator() is completely non-symmetric in the timer it returns. The test is simply:

return new->frequency > 2*time_interpolator->frequency ||
(unsigned long)new->drift < (unsigned long)time_interpolator->drift;

Given two timers:

(a) 1.5GHz, 750ppm
(b) 250Mhz, 500ppm

the resulting "better" timer is completely dependent on the order they're passed in. For example, (a),(b) = (b); (b),(a) = (a).

What are we really looking for in a "better" timer? There are at
least 4 factors that I can think of that seem important to determining a better clock:

Quoted 8 lines

* resolution (frequency)
* accuracy (drift)
* access latency (may be non-uniform across the system?)
* jitter (monotonically increasing)

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. This value can be changed as needed (for example: We lower the tsc timesource priority if the TSCs are found to be out of sync).

In order to have some scale of goodness and avoid priority inflation, I put a comment suggesting what the different priority levels mean.

ie:
0-99: Terrible. Only use at bootup or when there's nothing else available
100-199: Functional but not desired
200-299: Good. a correct and usable timesource
300-399: Desired. A reasonably fast and accurate timesource. 400-499: Perfect. The ideal timesource. A must-use where available.

Additionally, I created a sysfs interface that could be used to override the priority selected timesource.

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.

thanks
-john

#2 lore raw
Quoted 7 lines · john stultz
Quoted 3 lines · Alex Williamson

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.

...

Quoted 6 lines

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? 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))

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,

Alex

Signature · 1 line
Alex Williamson                             HP Linux & Open Source Lab
#3 lore raw
Quoted 16 lines · Alex Williamson
Quoted 7 lines · john stultz
Quoted 3 lines · Alex Williamson

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.

...

Quoted 6 lines

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.

Quoted 6 lines

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.

Quoted 7 lines

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.

Quoted 6 lines

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

#4 lore raw
In reply to Alex Williamson
Quoted 8 lines · Alex Williamson

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? 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.

I think a priority is something useful for the interpolators. Some of the decisions about which time sources to use also have criteria different from drift/latency/jitter/cpu. F.e. timers may not survive various power-saving configurations. Thus I would think that we need a priority plus some flags.

Some of the criteria for choosing a time source may be:

1. If a system boots up with a single cpu then there is no question that the ITC/TSC should be used because of the fast access.

2. If the BIOS is capable of perfect ITC/TSC synchronization then use the ITC/TSC. However, this is typically restricted to SMP configs and there is an issue on IA64 that the PAL can indicate a nodrift configuration but Linux is not capable of perfects sync on bootup.

3. If a memory mapped global clock is available then make sure to first use a distributed timer over a centralized time source because distributed timer have fast local access even under contention. I.e. use Altix RTC over HPET/Cyclone.

4. Use any memory mapped global clock source

5. Abuse some other system component for time keeping (PIT, i/o devices etc)

The criteria for drift/latency can only be established after we gone through the above. The low-power stuff adds additional complexity.

We may need to dynamically change timer interpolators / time sources if the power situation changes. Nothing like that exists today for time interpolators since they are mostly used in server configurations.

#5 lore raw
Quoted 7 lines · Christoph Lameter

I think a priority is something useful for the interpolators. Some of the decisions about which time sources to use also have criteria different from drift/latency/jitter/cpu. F.e. timers may not survive various power-saving configurations. Thus I would think that we need a priority plus some flags.

Some of the criteria for choosing a time source may be:

Hi Christoph,

I sent another followup to this thread with a patch containing a
fairly crude algorithm that I think better explains my starting point. I'm sure the weighting and scaling factors need work, but I think many of the criteria you describe will favor the right clock.

Quoted 2 lines

1. If a system boots up with a single cpu then there is no question that the ITC/TSC should be used because of the fast access.

I'm hoping the jitter/cpu and latency calculation will always end up favoring the cycle counter in the scenario.

Quoted 4 lines

2. If the BIOS is capable of perfect ITC/TSC synchronization then use the ITC/TSC. However, this is typically restricted to SMP configs and there is an issue on IA64 that the PAL can indicate a nodrift configuration but Linux is not capable of perfects sync on bootup.

If we're setting the jitter flag appropriately, which I think we are, then the low latency of the ITC and lack of jitter penalty should do the right thing here.

Quoted 6 lines

3. If a memory mapped global clock is available then make sure to first use a distributed timer over a centralized time source because distributed timer have fast local access even under contention. I.e. use Altix RTC over HPET/Cyclone.

4. Use any memory mapped global clock source

Scaling the latency to the average across a NUMA system will automatically order these correctly. They will definitely have higher latency than the ITC, so should fall about here on the list. It's easy to make the Altix RTC have no node association and therefore not penalize the access latency further.

Quoted 9 lines

5. Abuse some other system component for time keeping (PIT, i/o devices etc)

The criteria for drift/latency can only be established after we gone through the above. The low-power stuff adds additional complexity.

We may need to dynamically change timer interpolators / time sources if the power situation changes. Nothing like that exists today for time interpolators since they are mostly used in server configurations.

Yes, I don't know how to handle low power situations other than have
a flag on the interpolators and a hook to switch to the best low power timer when the need arises. We may need to use the same hook to re-evaluate the timer when a CPU hotplug occurs. This way we could dynamically fall back to case 1 above if most of the CPUs are removed (and likewise move to an hpet if CPUs are added).

I was looking into the suggestion to use logarithms to try to
normalize some of the factors such that weighting is more logical. Hopefully that won't explode the complexity. Thanks,

Alex

Signature · 1 line
Alex Williamson                             HP Linux & Open Source Lab
#6 lore raw
Quoted 8 lines · Alex Williamson
Quoted 3 lines · Christoph Lameter

I think a priority is something useful for the interpolators. Some of the decisions about which time sources to use also have criteria different from drift/latency/jitter/cpu. F.e. timers may not survive various power-saving configurations. Thus I would think that we need a priority plus some flags.

Some of the criteria for choosing a time source may be:

Quoted 9 lines

Hi Christoph,

I sent another followup to this thread with a patch containing a
fairly crude algorithm that I think better explains my starting point. I'm sure the weighting and scaling factors need work, but I think many of the criteria you describe will favor the right clock.

Quoted 1 line

1. If a system boots up with a single cpu then there is no question that the ITC/TSC should be used because of the fast access.

We need to factor in frequency shifting here, especially if it happens with out notice.

~

Signature · 2 lines
George Anzinger   [email protected]
HRT (High-res-timers):  http://sourceforge.net/projects/high-res-timers/
#7 lore raw
Quoted 7 lines · George Anzinger
Quoted 3 lines · Alex Williamson
Quoted 2 lines · Christoph Lameter

1. If a system boots up with a single cpu then there is no question that the ITC/TSC should be used because of the fast access.

We need to factor in frequency shifting here, especially if it happens with out notice.

Would we ever want to favor a frequency shifting timer over anything
else in the system? If it was noticeable perhaps we'd just need a callback to re-evaluate the frequency and rescan for the best timer. If it happens without notice, a flag that statically assigns it the lowest priority will due. Or maybe if the driver factored the frequency shifting into the drift it would make the timer undesirable without resorting to flags. Thanks,

Alex

Signature · 1 line
Alex Williamson                             HP Linux & Open Source Lab
#8 lore raw
Quoted 7 lines · Alex Williamson

Would we ever want to favor a frequency shifting timer over anything
else in the system? If it was noticeable perhaps we'd just need a callback to re-evaluate the frequency and rescan for the best timer. If it happens without notice, a flag that statically assigns it the lowest priority will due. Or maybe if the driver factored the frequency shifting into the drift it would make the timer undesirable without resorting to flags. Thanks,

Timers are usually constant. AFAIK Frequency shifts only occur through power management. In that case we usually have some notifiers running before the change. These notifiers need to switch to a different time source if the timer frequency will be shifting or the timer will become unavailable.

#9 lore raw
Quoted 12 lines · Christoph Lameter
Quoted 7 lines · Alex Williamson

Would we ever want to favor a frequency shifting timer over anything
else in the system? If it was noticeable perhaps we'd just need a callback to re-evaluate the frequency and rescan for the best timer. If it happens without notice, a flag that statically assigns it the lowest priority will due. Or maybe if the driver factored the frequency shifting into the drift it would make the timer undesirable without resorting to flags. Thanks,

Quoted 2 lines

Timers are usually constant. AFAIK Frequency shifts only occur through power management. In that case we usually have some notifiers running before the change. These notifiers need to switch to a different time source if the timer frequency will be shifting or the timer will become unavailable.

If there is a notifier, I presume we can track it. We might want to refine things so as to not hit too big a bump when the shift occures, but I think it is doable. The desirability of doing it, I think, depends on the availablity of something better. The access time of the TSC is "really" enticing. Even so, I think a _good_ clock would not depend on long term accuracy of something as fast as the TSC. Vendors are even modulating these to reduce RFI, but still, because of its speed, it makes the best interpolator for the jiffie to jiffie times.

Signature · 2 lines
George Anzinger   [email protected]
HRT (High-res-timers):  http://sourceforge.net/projects/high-res-timers/
#10 lore raw
In reply to Christoph Lameter

Hi!

Quoted 10 lines
Quoted 7 lines

Would we ever want to favor a frequency shifting timer over anything
else in the system? If it was noticeable perhaps we'd just need a callback to re-evaluate the frequency and rescan for the best timer. If it happens without notice, a flag that statically assigns it the lowest priority will due. Or maybe if the driver factored the frequency shifting into the drift it would make the timer undesirable without resorting to flags. Thanks,

Timers are usually constant. AFAIK Frequency shifts only occur through power management. In that case we usually have some notifiers running

Usually is the key word here. Older APM stuff changes frequency behind your back, and sometimes frequency shift is time-critical.

Signature · 1 line
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms         
#11 lore raw
Quoted 2 lines · Pavel Machek

Usually is the key word here. Older APM stuff changes frequency behind your back, and sometimes frequency shift is time-critical.

In that case the clocks tied to the shifting frequency are not usable.