| Author |
Message |
Guest
|
 Posted:
Thu Jul 21, 2005 8:15 am Post subject:
Re: stalling the TSC? |
|
|
Joe Seigh <jseigh_01@xemaps.com> writes:
| Quote: | Colin Andrew Percival wrote:
Terje Mathisen <terje.mathisen@hda.hydro.com> wrote:
Rob Warnock wrote:
[...] poll the MSW, the LSW, and the MSW again (in that order)
until the two MSW values are the same [...]
|
Argh... Why just just return "September", that at least will complete
in bounded time ;)
| Quote: | Sure, I didn't mention this particular workaround simply because it
has been quotes so often on c.arch that I considered it obvious.
Yes, that works.
Yes, it is the only real way to handle such problems.
No, it is not good, since it leads to non-deterministic counter
read latencies. :-(
Only if it is possible for reading the counters twice to take more
than 2^32 cycles (in which case you've got larger problems to worry
about). Assuming that the least significant 32-bit word doesn't
repeat itself within this process, the sequence (read MSW, read
LSW, read MSW, read LSW) allows you to determine the value of the
complete 64-bit counter at the time of the last read.
One too many reads. You wan't Lamport's algorithm which only
requires the read MSW, read LSW, read MSW.
If you have control of the hardware implementation you could do a 63
bit counter in 64 bits which can be atomically read with 2 32 bit
reads. I posted the logic in the x86 asm newsgroup a while back.
|
Read the LSW, this keep the low order bits as close to the event as possible.
Read the WSM, re-read the LSW. If LSW2 > LSW1 decrement MSW. Return. For
best results, do the decrement as a subtract 1 or a subtract 0 so
as to have equal code paths.
--
Paul Repacholi 1 Crescent Rd.,
+61 (08) 9257-1001 Kalamunda.
West Australia 6076
comp.os.vms,- The Older, Grumpier Slashdot
Raw, Cooked or Well-done, it's all half baked.
EPIC, The Architecture of the future, always has been, always will be. |
|
| Back to top |
|
 |
Joe Seigh
Guest
|
| Posted:
Thu Jul 21, 2005 2:30 pm Post subject:
Re: stalling the TSC? |
|
|
prep@prep.synonet.com wrote:
| Quote: | Joe Seigh <jseigh_01@xemaps.com> writes:
One too many reads. You wan't Lamport's algorithm which only
requires the read MSW, read LSW, read MSW.
If you have control of the hardware implementation you could do a 63
bit counter in 64 bits which can be atomically read with 2 32 bit
reads. I posted the logic in the x86 asm newsgroup a while back.
Read the LSW, this keep the low order bits as close to the event as possible.
Read the WSM, re-read the LSW. If LSW2 > LSW1 decrement MSW. Return. For
best results, do the decrement as a subtract 1 or a subtract 0 so
as to have equal code paths.
Assuming the reads are in order. I checked a 32 bit powerpc architecture doc |
and the code example appears to assume this is so. Does that mean the MFTB
powerpc instructions are serialized or at least partially serialized?
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software. |
|
| Back to top |
|
|
Joe Seigh
Guest
|
| Posted:
Thu Jul 21, 2005 2:56 pm Post subject:
Re: stalling the TSC? |
|
|
prep@prep.synonet.com wrote:
| Quote: | Joe Seigh <jseigh_01@xemaps.com> writes:
Colin Andrew Percival wrote:
Only if it is possible for reading the counters twice to take more
than 2^32 cycles (in which case you've got larger problems to worry
about). Assuming that the least significant 32-bit word doesn't
repeat itself within this process, the sequence (read MSW, read
LSW, read MSW, read LSW) allows you to determine the value of the
complete 64-bit counter at the time of the last read.
One too many reads. You wan't Lamport's algorithm which only
requires the read MSW, read LSW, read MSW.
If you have control of the hardware implementation you could do a 63
bit counter in 64 bits which can be atomically read with 2 32 bit
reads. I posted the logic in the x86 asm newsgroup a while back.
Read the LSW, this keep the low order bits as close to the event as possible.
Read the WSM, re-read the LSW. If LSW2 > LSW1 decrement MSW. Return. For
best results, do the decrement as a subtract 1 or a subtract 0 so
as to have equal code paths.
You want to decrement if LSW2 < LSW1 I think. Assuming you know if the |
MSW was read after the carry. You have to read the MSW twice to determine
this.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software. |
|
| Back to top |
|
|
Joe Seigh
Guest
|
| Posted:
Thu Jul 21, 2005 4:15 pm Post subject:
Re: stalling the TSC? |
|
|
Terje Mathisen wrote:
| Quote: | Colin Andrew Percival wrote:
Terje Mathisen <terje.mathisen@hda.hydro.com> wrote:
No, it is not good, since it leads to non-deterministic counter read
latencies. :-(
Only if it is possible for reading the counters twice to take more than
2^32 cycles (in which case you've got larger problems to worry about).
Assuming that the least significant 32-bit word doesn't repeat itself
within this process, the sequence (read MSW, read LSW, read MSW, read
LSW) allows you to determine the value of the complete 64-bit counter at
the time of the last read.
OK, you _can_ use conditional moves to generate the final count without
using a variable number of cycles and without looping or branching:
[...] |
Where would non-deterministic read latencies be important? If you're
timing code statictically it should average out.
If you're doing NTP synchronization I suppose it could be an issue.
What happens if you just consider the two clock halves separate
clocks for the purpose of NTP synchronization? The reads the clock
halves would be independent. Normally you would have less certainty
with the high order half due to its apparent slower clock rate but
since the two half clocks aren't independent the certainty of the
low order clock should apply to both. But I could be way off here
as my statistics is really rusty at this point.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software. |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Thu Jul 21, 2005 4:15 pm Post subject:
Re: stalling the TSC? |
|
|
In article <iJSdnSy2PKK7G0LfRVn-hw@comcast.com>,
Joe Seigh <jseigh_01@xemaps.com> writes:
|>
|> Where would non-deterministic read latencies be important? If you're
|> timing code statictically it should average out.
You are, at best, adding a source of noise.
|> If you're doing NTP synchronization I suppose it could be an issue.
|> What happens if you just consider the two clock halves separate
|> clocks for the purpose of NTP synchronization?
The simple code would be unreliable, and the reliable code would
have a non-deterministic read time. Been there - done that.
|> The reads the clock
|> halves would be independent. Normally you would have less certainty
|> with the high order half due to its apparent slower clock rate but
|> since the two half clocks aren't independent the certainty of the
|> low order clock should apply to both. But I could be way off here
|> as my statistics is really rusty at this point.
You're not way off, but not close.
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
Joe Seigh
Guest
|
| Posted:
Thu Jul 21, 2005 4:15 pm Post subject:
Re: stalling the TSC? |
|
|
Nick Maclaren wrote:
| Quote: | |> If you're doing NTP synchronization I suppose it could be an issue.
|> What happens if you just consider the two clock halves separate
|> clocks for the purpose of NTP synchronization?
The simple code would be unreliable, and the reliable code would
have a non-deterministic read time. Been there - done that.
|> The reads the clock
|> halves would be independent. Normally you would have less certainty
|> with the high order half due to its apparent slower clock rate but
|> since the two half clocks aren't independent the certainty of the
|> low order clock should apply to both. But I could be way off here
|> as my statistics is really rusty at this point.
You're not way off, but not close.
There's additional information that you need to exploit to figure out |
where you are relative to the carries. This is hypothetical. I'm
not sure it would be worth the extra trouble.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software. |
|
| Back to top |
|
|
Guest
|
| Posted:
Sat Jul 23, 2005 9:04 am Post subject:
Re: stalling the TSC? |
|
|
Joe Seigh <jseigh_01@xemaps.com> writes:
| Quote: | prep@prep.synonet.com wrote:
Joe Seigh <jseigh_01@xemaps.com> writes:
Colin Andrew Percival wrote:
Only if it is possible for reading the counters twice to take more
than 2^32 cycles (in which case you've got larger problems to worry
about). Assuming that the least significant 32-bit word doesn't
repeat itself within this process, the sequence (read MSW, read
LSW, read MSW, read LSW) allows you to determine the value of the
complete 64-bit counter at the time of the last read.
One too many reads. You wan't Lamport's algorithm which only
requires the read MSW, read LSW, read MSW.
If you have control of the hardware implementation you could do a
63 bit counter in 64 bits which can be atomically read with 2 32
bit reads. I posted the logic in the x86 asm newsgroup a while
back.
Read the LSW, this keep the low order bits as close to the event as
possible.
Read the WSM, re-read the LSW. If LSW2 > LSW1 decrement
MSW. Return. For best results, do the decrement as a subtract 1 or
a subtract 0 so as to have equal code paths.
You want to decrement if LSW2 < LSW1 I think.
|
Yes, well caught.
| Quote: | Assuming you know if the MSW was read after the carry. You have to
read the MSW twice to determine this.
|
--
Paul Repacholi 1 Crescent Rd.,
+61 (08) 9257-1001 Kalamunda.
West Australia 6076
comp.os.vms,- The Older, Grumpier Slashdot
Raw, Cooked or Well-done, it's all half baked.
EPIC, The Architecture of the future, always has been, always will be. |
|
| Back to top |
|
|
Terje Mathisen
Guest
|
| Posted:
Sat Jul 23, 2005 9:35 pm Post subject:
Re: stalling the TSC? |
|
|
prep@prep.synonet.com wrote:
| Quote: | Read the LSW, this keep the low order bits as close to the event as possible.
Read the WSM, re-read the LSW. If LSW2 > LSW1 decrement MSW. Return. For
best results, do the decrement as a subtract 1 or a subtract 0 so
as to have equal code paths.
|
This does not work, since there's no way to know if the MSW value
changed before or after you read it.
Besides, I assume you meant 'if LSW1 > LSW2' and not the opposite? I.e.
you want to detect wraparound?
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in