Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #2293 > unrolled thread

Notions of Time in Computer Architecture

Back to article view | Back to comp.arch

Contents

  Notions of Time in Computer Architecture "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-06-29 15:12 -0700
    Re: Notions of Time in Computer Architecture Robert Myers <rbmyersusa@gmail.com> - 2011-06-29 22:08 -0400
    Re: Notions of Time in Computer Architecture Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-06-30 14:13 +0200
      Re: Notions of Time in Computer Architecture Morten Reistad <first@last.name> - 2011-06-30 18:19 +0200
      Re: Notions of Time in Computer Architecture ChrisQ <meru@devnull.com> - 2011-06-30 21:23 +0100
        Re: Notions of Time in Computer Architecture Rick Jones <rick.jones2@hp.com> - 2011-06-30 19:42 +0000
          Re: Notions of Time in Computer Architecture Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-07-01 10:46 +0200
            Re: Notions of Time in Computer Architecture Rick Jones <rick.jones2@hp.com> - 2011-07-01 15:17 +0000
              Re: Notions of Time in Computer Architecture ChrisQ <meru@devnull.com> - 2011-07-04 16:51 +0100
        Re: Notions of Time in Computer Architecture nmm1@cam.ac.uk - 2011-07-01 05:54 +0100
      Re: Notions of Time in Computer Architecture "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-06-30 22:42 -0700
      Re: Notions of Time in Computer Architecture jsavard@excxn.aNOSPAMb.cdn.invalid (John Savard) - 2011-07-01 20:16 +0000
        Re: Notions of Time in Computer Architecture Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-07-02 10:33 +0200
          Re: Notions of Time in Computer Architecture nmm1@cam.ac.uk - 2011-07-02 09:26 +0100
          Re: Notions of Time in Computer Architecture jsavard@excxn.aNOSPAMb.cdn.invalid (John Savard) - 2011-07-02 12:40 +0000
            Re: Notions of Time in Computer Architecture nmm1@cam.ac.uk - 2011-07-02 16:14 +0100
            Re: Notions of Time in Computer Architecture Robert Myers <rbmyersusa@gmail.com> - 2011-07-02 16:48 -0400
              Re: Notions of Time in Computer Architecture Quadibloc <jsavard@ecn.ab.ca> - 2011-07-02 14:27 -0700
                Re: Notions of Time in Computer Architecture Stephen Sprunk <stephen@sprunk.org> - 2011-07-03 15:07 -0500
                  Re: Notions of Time in Computer Architecture Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-07-04 08:15 +0200
                    Re: Notions of Time in Computer Architecture Morten Reistad <first@last.name> - 2011-07-04 17:50 +0200
                      Re: Notions of Time in Computer Architecture Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-07-04 21:21 +0200
                        Re: Notions of Time in Computer Architecture Robert Wessel <robertwessel2@yahoo.com> - 2011-07-04 23:44 -0500
                          Re: Notions of Time in Computer Architecture Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-07-05 07:51 +0200
                            Re: Notions of Time in Computer Architecture Robert Wessel <robertwessel2@yahoo.com> - 2011-07-05 01:56 -0500
              Re: Notions of Time in Computer Architecture Morten Reistad <first@last.name> - 2011-07-03 19:28 +0200
            Re: Notions of Time in Computer Architecture "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-03 11:27 -0700
              Re: Notions of Time in Computer Architecture nmm1@cam.ac.uk - 2011-07-03 22:13 +0100
                Re: Notions of Time in Computer Architecture "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-03 18:53 -0700
                  Re: Notions of Time in Computer Architecture nmm1@cam.ac.uk - 2011-07-04 08:34 +0100
              Re: Notions of Time in Computer Architecture "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-03 18:51 -0700
              Re: Notions of Time in Computer Architecture anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-07-04 09:20 +0000
                Re: Notions of Time in Computer Architecture Robert Myers <rbmyersusa@gmail.com> - 2011-07-04 12:26 -0700
                  Re: Notions of Time in Computer Architecture EricP <ThatWouldBeTelling@thevillage.com> - 2011-07-04 19:35 -0400
                  Re: Notions of Time in Computer Architecture Bernd Paysan <bernd.paysan@gmx.de> - 2011-07-08 15:48 +0200
              Re: Notions of Time in Computer Architecture Michael S <already5chosen@yahoo.com> - 2011-07-05 15:24 -0700
                Re: Notions of Time in Computer Architecture "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-08 09:25 -0700
                  Re: Notions of Time in Computer Architecture Robert Myers <rbmyersusa@gmail.com> - 2011-07-08 12:12 -0700
                    Re: Notions of Time in Computer Architecture "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-07-08 17:27 -0700
                      Re: Notions of Time in Computer Architecture Robert Myers <rbmyersusa@gmail.com> - 2011-07-09 18:07 -0400
                        Re: Notions of Time in Computer Architecture EricP <ThatWouldBeTelling@thevillage.com> - 2011-07-10 12:03 -0400
                          Re: Notions of Time in Computer Architecture Robert Myers <rbmyersusa@gmail.com> - 2011-07-10 13:02 -0700
      Re: Notions of Time in Computer Architecture Bernd Paysan <bernd.paysan@gmx.de> - 2011-07-08 15:13 +0200
    Re: Notions of Time in Computer Architecture Gubbi <gubsan100@hotmail.com> - 2011-07-01 00:50 -0700

Page 1 of 3  [1] 2 3  Next page →

#2293 — Notions of Time in Computer Architecture

http://semipublic.comp-arch.net/wiki/Notions_of_Time_in_Computer_Architecture

Advanced computer architecture admits several different notions of time.

= Real World Time =

First, there is [[real time]] or [[wall clock time]].  Time in the real 
world (forgetting Einsteinian relativistic issues for the moment).

Unfortunately, the term [[real time]], which would be the best term for 
this, is often overloaded with the additional meaning
of pertaining to a system that must respond in real time - e.g. "Drop 
the rods in the nuclear power plant quickly or the nuclear fuel will 
melt down."
Or "adjust the aileron pitch with a few milliseconds, or the plane will 
stall and crash."
These applications are often called [[hard real time]], and there are 
also [[soft real time]] applications that have less stringent timing 
requirements.

Because of the use of real time in phrases such as [[real time operating 
system]] or [[real time response]], terms such as [[wall clock time]] 
may be used.

== Absolute versus Relative ==

Real time (and, indeed, other times) may be absolute or relative.

Absolute time is wall clock time, or calendar time.

Relative time is the amount of elapsed time since some other event. 
E.g. one might start a timer on entering a function, and read it on exit.

Obviously, you can calculate relative timer from absolute time samples.
But, it can be considerably easier to build the hardware to measure 
relative time that it is to measure ab solute time.
Timers used in relative timing may be in isolation, whereas clocks 
measuring absolute time may need to be kept in synchronization
with other clocks in other systems.

== [[Timers versus Timestamps]] ==

Oftentimes appplications do not need actual time.
Instead, what they really need is timestamps that indicate relative 
position.
The application may care who came first or second, but not how much time 
elapsed between arrivals.

Therefore, some timer architectures provide absolute time in uppper bits,
but simply indicate a unique counter in the lower bits of a timestamp.

= Von Neuman Time =

In out-of-order and speculative processors,
even when single threaded, it is often convenient to talk about the
[[Von Neumann sequence number]] or [[Von Neumann time]].

On a single threaded program, this is the sequence number at which every 
and any [[dynamic instruction sequence]] executes.

The [[Von Neumann time]] or sequence number for an instruction is NOT 
the [[wall clock time]]
at which an instruction executes.
Even on simple in-order processors, where instructions may have 
differing [[instruction latency]],
the VN time is not linearly related to the wall clock time.
On complex out-of-order processors instructions that are later in the 
Von Neumman instruction sequence
may execute earlier in wall clock time (that's what makes them 
out-of-order).

The [[Von Neumann time]] or sequence number may be a convenient 
book-keeping tool.
* it is often made available in a [[simulator]] user interface
* I have proposed using it it [[hardware data structures]] such as store 
buffers and schedulers.
** When I talk about an "age based scheduler", I usually mean a [[Von 
Neumann age]] based scheduler.
** Of course, real hardware must implement a finite number of bits, 
typically wrapping

== Multithreading ==

The [[Von Neumann time]] or sequence number is unambiguous for a single 
threaded program.

For multithreaded programs that interact, it is necessary to establish 
correspondences - VN1 time of thread A corresponds to VN time of thread B,
at different points if interaction.

It should be seen that this multithreaded time is a partial order. 
Ideally one from which a total order can be constructed.
(Although certain microarchitectural interactions may imply cycles in 
such a time graph.)

I know of no standard term for this [[multithreaded time]]. 
[[Multithreaded Von Neuman time]].

I think that it might be nice to call it [[Lamport time]],
since Leslie Lamport was a pioneer in this area.


= Pipeline Time(s) =

Any given [[dynamic instruction instance]] desn't execute at a single 
point in time.,
Rather, it executes in different ways at many different points in tiime:
* [[instruction fetch time]]
* [[decode time]]
* [[schedule time]]
* [[operand ready time]]
* [[execution time]]
* [[register read time]]
* [[writeback time]]
* re-execution time]] or [[replay time]]
* [[commit time]]
* [[retirement time]]

Plus of course there is the
* [[Von Neuman time]] or [[Von Neumann sequence number]] of a [[dynamic 
instruction instance]].

For that matter
* the [[Von Neumann time]] relative to a given thread of execution
may differe from the
* [[Von Neuman time]] relative to the processor it is executed on
because of [[timesharing]] or [[multitasking]] between threads or 
processors.

= Simulator Times =

Consider
* Real time of the machine on which the simulator runs: [[simulator real 
time]]
* [[Simulated real time]] of the workload running on the simulator: 
[[simulatee real time]]
* [[Von Neumann time]] or sequence number for the workload running on 
the simulator.

This can be fully recursive.  A simulator may be ruunning on top of a 
simulator on top of ...

= Conclusion =

Be careful what notion of time you are talking about.
It may not be the notion of time for the person you are talking to.

[[Microarchitecture]] is concerned with [[real time]].
[[Macroarchitecture]] is concerned more with abstract time, such as 
[[Von Neumann time]].
Systems that have different microarchitectures and hence different real 
time behavior,
may execute the same [[macroarchitecture]].
But, of course, [[macroarchitecture]] features such as [[ISA]] greatly 
influence [[real time]] performance.

[toc] | [next] | [standalone]

#2294

On 6/29/2011 6:12 PM, Andy "Krazy" Glew wrote:

>
> [[Microarchitecture]] is concerned with [[real time]].
> [[Macroarchitecture]] is concerned more with abstract time

And the boundary between microarchitecture and macroarchitecture is like 
approaching the event horizon of a black hole: everything slows to a crawl.

Robert.

[toc] | [prev] | [next] | [standalone]

#2295

Andy "Krazy" Glew wrote:
> First, there is [[real time]] or [[wall clock time]]. Time in the real
> world (forgetting Einsteinian relativistic issues for the moment).

With the sub-ns time scales in modern cpus, any large cluster (even if 
presented as a single image CC-NUMA system to the programmer) will get 
into trouble here:

You cannot have a globally consistent, totally distributed clock: Unless 
you designate a single point of control, there's no way to always be 
able to figure out the absolute order of two or more distributed events, 
right?

You simply have to fall back on workarounds, like having N bits for the 
clock, of which the lower M bits is the clock ID. This way all 
timestamps will be globally unique and sortable, even if the resulting 
order might not be the "real" order as observed by some omniscient entity.

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#2296

In article <6s5ud8-ikv2.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>Andy "Krazy" Glew wrote:
>> First, there is [[real time]] or [[wall clock time]]. Time in the real
>> world (forgetting Einsteinian relativistic issues for the moment).
>
>With the sub-ns time scales in modern cpus, any large cluster (even if 
>presented as a single image CC-NUMA system to the programmer) will get 
>into trouble here:

You don't need to invoke NUMA. Even a single processor is a stretch to
keep under harmonius time, and we have stayed at the edge of what is
possible to synchronise ever since the KA10 (1967). 

As they get smaller, they also get faster. 

>You cannot have a globally consistent, totally distributed clock: Unless 
>you designate a single point of control, there's no way to always be 
>able to figure out the absolute order of two or more distributed events, 
>right?
>
>You simply have to fall back on workarounds, like having N bits for the 
>clock, of which the lower M bits is the clock ID. This way all 
>timestamps will be globally unique and sortable, even if the resulting 
>order might not be the "real" order as observed by some omniscient entity.

This ordering problem crept up on the financial markets ca 1985, and 
has never been resolved. Financial transactions do not rely on timestamps
for this reason, they just have a unique ID.

-- mrr

[toc] | [prev] | [next] | [standalone]

#2297

Terje Mathisen wrote:
> Andy "Krazy" Glew wrote:
>> First, there is [[real time]] or [[wall clock time]]. Time in the real
>> world (forgetting Einsteinian relativistic issues for the moment).
> 
> With the sub-ns time scales in modern cpus, any large cluster (even if 
> presented as a single image CC-NUMA system to the programmer) will get 
> into trouble here:
> 
> You cannot have a globally consistent, totally distributed clock: Unless 
> you designate a single point of control, there's no way to always be 
> able to figure out the absolute order of two or more distributed events, 
> right?
> 
> You simply have to fall back on workarounds, like having N bits for the 
> clock, of which the lower M bits is the clock ID. This way all 
> timestamps will be globally unique and sortable, even if the resulting 
> order might not be the "real" order as observed by some omniscient entity.
> 
> Terje
> 

You can have a globally consistent clock, up to a point, by using gps
based frequency standards, which approach caesium in terms of short and
long term stability. Standard, off the shelf gps based standards are
good just about anywhere in the world to a few 10's of nS in terms of
time displacement error and this can be improved still further by using
beacon stations.

Arguably the most common application is the gsm phone system, which uses
a gps based frequency standard at each and every cell base station...

Regards,

Chris

[toc] | [prev] | [next] | [standalone]

#2298

ChrisQ <meru@devnull.com> wrote:
> You can have a globally consistent clock, up to a point, by using
> gps based frequency standards, which approach caesium in terms of
> short and long term stability. Standard, off the shelf gps based
> standards are good just about anywhere in the world to a few 10's of
> nS in terms of time displacement error and this can be improved
> still further by using beacon stations.

> Arguably the most common application is the gsm phone system, which
> uses a gps based frequency standard at each and every cell base
> station...

Which benefits from having (almost) everything out of doors.

rick jones
-- 
The glass is neither half-empty nor half-full. The glass has a leak.
The real question is "Can it be patched?"
these opinions are mine, all mine; HP might not want them anyway... :)
feel free to post, OR email to rick.jones2 in hp.com but NOT BOTH...

[toc] | [prev] | [next] | [standalone]

#2302

Rick Jones wrote:
> ChrisQ<meru@devnull.com>  wrote:
>> You can have a globally consistent clock, up to a point, by using
>> gps based frequency standards, which approach caesium in terms of
>> short and long term stability. Standard, off the shelf gps based
>> standards are good just about anywhere in the world to a few 10's of
>> nS in terms of time displacement error and this can be improved
>> still further by using beacon stations.
>
>> Arguably the most common application is the gsm phone system, which
>> uses a gps based frequency standard at each and every cell base
>> station...
>
> Which benefits from having (almost) everything out of doors.

Actually,I believe it is the US CDMA system which requires us-level time 
sync for all base stations, and which supplies all handsets with sub-10 
us time reference.

I know that I have setup an NTP server in Tampa which used this system 
to get coverage inside a computer room in the middle of an office building.

Terje


-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#2304

Terje Mathisen <"terje.mathisen at tmsw.no"> wrote:
> Rick Jones wrote:
> > ChrisQ<meru@devnull.com>  wrote:

> >> Arguably the most common application is the gsm phone system,
> >> which uses a gps based frequency standard at each and every cell
> >> base station...
> >
> > Which benefits from having (almost) everything out of doors.

> Actually,I believe it is the US CDMA system which requires us-level
> time sync for all base stations, and which supplies all handsets
> with sub-10 us time reference.

> I know that I have setup an NTP server in Tampa which used this
> system to get coverage inside a computer room in the middle of an
> office building.

Indeed, based on my eavsedropping in comp.protocols.time.ntp I got the
impression that CDMA could penetrate reasonably far into buildings.
GPS, fuggedaboudit...

rick jones
-- 
The glass is neither half-empty nor half-full. The glass has a leak.
The real question is "Can it be patched?"
these opinions are mine, all mine; HP might not want them anyway... :)
feel free to post, OR email to rick.jones2 in hp.com but NOT BOTH...

[toc] | [prev] | [next] | [standalone]

#2352

Rick Jones wrote:

> 
> Indeed, based on my eavsedropping in comp.protocols.time.ntp I got the
> impression that CDMA could penetrate reasonably far into buildings.
> GPS, fuggedaboudit...
> 

The gps standards use an active antenna, usually on a pole outside the
building, so cdma doesn't really come into the picture. Typically, such
standards use a gps receiver module to discipline a low phase noise
crystal or rubidium oscillator, with long time constants in the phase
locked loop. The result is a standard which approaches caesium in
accuracy. Outputs are typically 1 PPS, 10 Mhz and a timing signal to
suit the digital logic in use. I've used an HP ex cdma unit as a lab
standard for 5 years or more, feeding test gear such as counters, signal
generators etc. Here's a printout from the HP unit, reformatted to suit
the page width:

HP Z3816
------- Receiver Status --------
SYNCHRONIZATION ... [ Outputs Valid ]
SmartClock Mode ___________________________
>> Locked to GPS                             
    Recovery
    Holdover
    Power-up

  Reference Outputs _______________
  TFOM     3             FFOM     0
  1PPS TI -3.8 ns relative to GPS
  HOLD THR 1.000 us
  Holdover Uncertainty ____________
  Predict  432.0 us/initial 24 hrs


ACQUISITION ............. [ GPS 1PPS Valid ]

Tracking: 8 ____   Not Tracking: 1 ________
PRN  El  Az  C/N   PRN  El  Az
   2  14 104   46    31  10 299
   4  16  62   43
   9  39 124   49
  12  79  57   51
  14  50 274   49
  25  58 256   51
  27  27 125   42
  29  20 190   45
ELEV MASK 10 deg

Time ____________________________
UTC      14:19:16     04 Jul 2011
GPS 1PPS Synchronized to UTC
ANT DLY  25 ns
Position ________________________
MODE     Hold

LAT      N  51:45:46.723
LON      W   1:11:48.403 (Note: Coordinates changed slightly)
HGT         +163.21 m  (GPS)

HEALTH MONITOR ..................... [ OK ]
Self Test: OK    Int Pwr: OK   Oven Pwr: OK
                OCXO: OK   EFC: OK   GPS Rcv: OK

Typically, the 1pps output is synchronised to the gps to withing a few
nS. This varies a little, due to control loop limitations and also time
of day, but could be improved further. The Symmetricom site has loads of
info on precision timing and more, for those interested.

Using such techniques, clocks could be synchronised over a several
thousand mile range, to within a few tens of nS. A cpu clock could be
phase locked to this. If you were using such a scheme for transaction level
synchronisation, the transmit / receive signal delay over several
thousand miles would be orders of magnitude greater than the accuracy of
clock synchronisation between the nodes, even if you had the speed of
light available.

Of course, that begs the question, what use is it anyway ?...

Regards,

Chris

[toc] | [prev] | [next] | [standalone]

#2299

In article <RW4Pp.20256$NX1.7489@newsfe18.ams2>,
ChrisQ  <meru@devnull.com> wrote:
>Terje Mathisen wrote:
>> Andy "Krazy" Glew wrote:
>>> First, there is [[real time]] or [[wall clock time]]. Time in the real
>>> world (forgetting Einsteinian relativistic issues for the moment).
>> 
>> With the sub-ns time scales in modern cpus, any large cluster (even if 
>> presented as a single image CC-NUMA system to the programmer) will get 
>> into trouble here:
>> 
>> You cannot have a globally consistent, totally distributed clock: Unless 
>> you designate a single point of control, there's no way to always be 
>> able to figure out the absolute order of two or more distributed events, 
>> right?
>> 
>> You simply have to fall back on workarounds, like having N bits for the 
>> clock, of which the lower M bits is the clock ID. This way all 
>> timestamps will be globally unique and sortable, even if the resulting 
>> order might not be the "real" order as observed by some omniscient entity.
>
>You can have a globally consistent clock, up to a point, by using gps
>based frequency standards, which approach caesium in terms of short and
>long term stability. Standard, off the shelf gps based standards are
>good just about anywhere in the world to a few 10's of nS in terms of
>time displacement error and this can be improved still further by using
>beacon stations.

Well, in THEORY.  In any case, that is nowhere near good enough for
many of the clock-based algorithms, which need timestamps consistent
to the clock cycle level - while those are mathematically neat,
they are also impractical.

If you have a communication method with the consistency of its
latency X, and a quartz clock with low latency of access, you can
get global consistency of X with no great trouble; I have code
to do it.

But, beyond that, you are onto a loser, and I agree with Terje.
Don't go there, because it isn't a practically reasonable objective.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#2300

On 6/30/2011 5:13 AM, Terje Mathisen wrote:
> Andy "Krazy" Glew wrote:
>> First, there is [[real time]] or [[wall clock time]]. Time in the real
>> world (forgetting Einsteinian relativistic issues for the moment).
>
> With the sub-ns time scales in modern cpus, any large cluster (even if
> presented as a single image CC-NUMA system to the programmer) will get
> into trouble here:
>
> You cannot have a globally consistent, totally distributed clock: Unless
> you designate a single point of control, there's no way to always be
> able to figure out the absolute order of two or more distributed events,
> right?
>
> You simply have to fall back on workarounds, like having N bits for the
> clock, of which the lower M bits is the clock ID. This way all
> timestamps will be globally unique and sortable, even if the resulting
> order might not be the "real" order as observed by some omniscient entity.
>
> Terje
>


I think Lamport clocks are probably buildable - wasn't it Mark Hill 
and/or David Wood who have a paper on that?  But whether it is worth 
building them is another question.

Myself, I doubt that it is worth the effort to have synchronized the 
clocks in shared memory systems.

[toc] | [prev] | [next] | [standalone]

#2307

On Thu, 30 Jun 2011 14:13:23 +0200, Terje Mathisen <"terje.mathisen at
tmsw.no"> wrote, in part:

>With the sub-ns time scales in modern cpus, any large cluster (even if 
>presented as a single image CC-NUMA system to the programmer) will get 
>into trouble here:
>
>You cannot have a globally consistent, totally distributed clock: Unless 
>you designate a single point of control, there's no way to always be 
>able to figure out the absolute order of two or more distributed events, 
>right?

Actually, no. This is not really a problem. If you want to have a clock
distributed on a chip that's accurate to a small fraction of the time
that light takes to travel across the chip, you *can* do it.

Think of the letter H. Assume you have a pin on the edge of the chip
where an external high-frequency clock signal comes in. Take that to the
exact center of traces having the form of the letter H. Clearly, when
the signal reaches the four corners of the H, it will have travelled an
equal distance in each of the four cases.

Now, make each of those four corners the center of a smaller letter H.
Repeat (but not infinitely, as we don't need a _true_ fractal.)

In fact, this actually *is* how clock signals are distributed on some
chips.

John Savard
http://www.quadibloc.com/index.html

[toc] | [prev] | [next] | [standalone]

#2314

John Savard wrote:
> On Thu, 30 Jun 2011 14:13:23 +0200, Terje Mathisen<"terje.mathisen at
> tmsw.no">  wrote, in part:
>
>> With the sub-ns time scales in modern cpus, any large cluster (even if
>> presented as a single image CC-NUMA system to the programmer) will get
>> into trouble here:
>>
>> You cannot have a globally consistent, totally distributed clock: Unless
>> you designate a single point of control, there's no way to always be
>> able to figure out the absolute order of two or more distributed events,
>> right?
>
> Actually, no. This is not really a problem. If you want to have a clock
> distributed on a chip that's accurate to a small fraction of the time
> that light takes to travel across the chip, you *can* do it.
>
> Think of the letter H. Assume you have a pin on the edge of the chip
> where an external high-frequency clock signal comes in. Take that to the
> exact center of traces having the form of the letter H. Clearly, when
> the signal reaches the four corners of the H, it will have travelled an
> equal distance in each of the four cases.
>
> Now, make each of those four corners the center of a smaller letter H.
> Repeat (but not infinitely, as we don't need a _true_ fractal.)
>
> In fact, this actually *is* how clock signals are distributed on some
> chips.

John, please re-read what I wrote:

Having a single clock source is of course doable, what I claimed was 
that with a totally distributed setup, i.e. _no_ central distribution 
point, you can't do the same.

OTOH, even with a central clock there's no way to guarantee that you can 
determine the absolute order of distributed events, you must also have a 
central time stamp authority, and that would be an impossible bottleneck.

You always end up with the need for some other way (i.e. something like 
a cpu id) to arbitrate between "close enough" events, things that happen 
within the clock resolution steps.

Add in relativity and you realize that it might not be even 
theoretically possible to determine which of two events happened "first".

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#2315

In article <ko13e8-bm4.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>John Savard wrote:
>>
>> Actually, no. This is not really a problem. If you want to have a clock
>> distributed on a chip that's accurate to a small fraction of the time
>> that light takes to travel across the chip, you *can* do it.
>>
>> Think of the letter H. Assume you have a pin on the edge of the chip
>> where an external high-frequency clock signal comes in. Take that to the
>> exact center of traces having the form of the letter H. Clearly, when
>> the signal reaches the four corners of the H, it will have travelled an
>> equal distance in each of the four cases.
>>
>> Now, make each of those four corners the center of a smaller letter H.
>> Repeat (but not infinitely, as we don't need a _true_ fractal.)
>>
>> In fact, this actually *is* how clock signals are distributed on some
>> chips.
>
>John, please re-read what I wrote:
>
>Having a single clock source is of course doable, what I claimed was 
>that with a totally distributed setup, i.e. _no_ central distribution 
>point, you can't do the same.

Actually, I disagree.  You can achieve exactly the same in a truly
distributed design, though you need rather more clock traffic.
In both cases, you can get the time down to O(log^K(N)) times the
uncertainty on a single-point-to-point message with a reasonably
economical design.

>OTOH, even with a central clock there's no way to guarantee that you can 
>determine the absolute order of distributed events, you must also have a 
>central time stamp authority, and that would be an impossible bottleneck.

Yes.  O(log N) times the uncertainty on a single-point-to-point message
is close to a theoretical limit; it isn't, quite, because you can do
better if you allow essentially unlimited synchronisation traffic.

>You always end up with the need for some other way (i.e. something like 
>a cpu id) to arbitrate between "close enough" events, things that happen 
>within the clock resolution steps.

Yes.  Vide Lamport and others.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#2316

On Sat, 02 Jul 2011 10:33:53 +0200, Terje Mathisen <"terje.mathisen at
tmsw.no"> wrote, in part:

>John, please re-read what I wrote:
>
>Having a single clock source is of course doable, what I claimed was 
>that with a totally distributed setup, i.e. _no_ central distribution 
>point, you can't do the same.

It is indeed true that I didn't fully address your real point, and that
I even may have misunderstood part of what you wrote.

>OTOH, even with a central clock there's no way to guarantee that you can 
>determine the absolute order of distributed events, you must also have a 
>central time stamp authority, and that would be an impossible bottleneck.

Multiple synchronized time stamp authorities, of course, could establish
order down to some minimal granularity below which events are seen as
simultaneous.

>You always end up with the need for some other way (i.e. something like 
>a cpu id) to arbitrate between "close enough" events, things that happen 
>within the clock resolution steps.

But you've noted this. One thing, though; with a single clock, "close
enough" really is simultaneous.

>Add in relativity and you realize that it might not be even 
>theoretically possible to determine which of two events happened "first".

Silly me. I was thinking in terms of parallel computers that are wired
together and sitting on a floor somewhere, if not bolted to it. So a
default reference frame would be obvious.

Due to extreme propagation delays, a network of computers spanning the
Solar System would not normally serve for tightly-coupled calculations.
But someday such things might have applications at least as
communications networks... and why shouldn't someone on Mars join in one
of those "@home" projects, since embarassingly parallel problems don't
have propagation to worry about much?

So it could indeed be that relativistic considerations would someday
impact the definition of priority...

John Savard
http://www.quadibloc.com/index.html

[toc] | [prev] | [next] | [standalone]

#2319

In article <4e0f0fb6.148514@news.aioe.org>,
John Savard <jsavard@excxn.aNOSPAMb.cdn.invalid> wrote:
>On Sat, 02 Jul 2011 10:33:53 +0200, Terje Mathisen <"terje.mathisen at
>tmsw.no"> wrote, in part:
>
>>OTOH, even with a central clock there's no way to guarantee that you can 
>>determine the absolute order of distributed events, you must also have a 
>>central time stamp authority, and that would be an impossible bottleneck.
>
>Multiple synchronized time stamp authorities, of course, could establish
>order down to some minimal granularity below which events are seen as
>simultaneous.

That is NOT true!  There is invariably some uncertainty, whether
due to jitter or retry, and that is almost always larger than the
smallest detectable time interval.  Indeed, one could say always,
though that might not be theoretically provable.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#2320

On 7/2/2011 8:40 AM, John Savard wrote:
>
> So it could indeed be that relativistic considerations would someday
> impact the definition of priority.

So far as I know, and some of the most careful work is probably 
classified, they have been for a long time, because the most important 
case is not computers bolted to the floor, but satellites in orbit with 
profound implications for military operations.

It would be worth a note in Physical Review Letters if someone could 
nail down some of the uncertainties or show without a doubt that it was 
physics and not electronics causing the problems.

As it is, things are moving around pretty fast inside computers, even 
when they are bolted to the floor, and I'd be reluctant to stake my 
reputation on sweeping claims about the unimportance of even classical 
relativistic, never mind quantum, limits on the ability to define 
simultaneity, even within a computing center with the computers safely 
bolted to the floor.  There are just too many numbers to make to rule 
out any possible measurable effect.

Robert.

[toc] | [prev] | [next] | [standalone]

#2321

On Jul 2, 2:48 pm, Robert Myers <rbmyers...@gmail.com> wrote:

> So far as I know, and some of the most careful work is probably
> classified, they have been for a long time, because the most important
> case is not computers bolted to the floor, but satellites in orbit with
> profound implications for military operations.

I suppose it could be, but I'm not sure that priority and interlocks
and so on would normally be significant between one satellite and
another. Each satellite does its own work; they're not fighting over
the same memory or disk drives.

And antennas are usually pointed at one satellite at a time, which
allows the receiver to give a particular satellite its undivided
attention. While it might be possible for such considerations to
become an issue, while I might be wrong, I would suspect that to do so
would be poor design.

John Savard

[toc] | [prev] | [next] | [standalone]

#2332

On 02-Jul-11 16:27, Quadibloc wrote:
> On Jul 2, 2:48 pm, Robert Myers <rbmyers...@gmail.com> wrote:
>> So far as I know, and some of the most careful work is probably
>> classified, they have been for a long time, because the most important
>> case is not computers bolted to the floor, but satellites in orbit with
>> profound implications for military operations.
> 
> I suppose it could be, but I'm not sure that priority and interlocks
> and so on would normally be significant between one satellite and
> another. Each satellite does its own work; they're not fighting over
> the same memory or disk drives.
> 
> And antennas are usually pointed at one satellite at a time, which
> allows the receiver to give a particular satellite its undivided
> attention. While it might be possible for such considerations to
> become an issue, while I might be wrong, I would suspect that to do so
> would be poor design.

GPS is a prime counterexample: any given receiver must be able to track
at least three satellites, and many can track a dozen or more.  The
satellites move at speeds where relativity becomes relevant, and AIUI
receivers have to compensate for it.  I don't know if the satellites
talk to each other directly or if their signals are coordinated solely
by ground stations, but the same concerns would apply there as well.

Keeping time is an embarrassingly parallel problem, but I wouldn't be
surprised if the military had other satellites in orbit for which
relativity was an even greater concern.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#2338

Stephen Sprunk wrote:
> GPS is a prime counterexample: any given receiver must be able to track
> at least three satellites, and many can track a dozen or more.  The
> satellites move at speeds where relativity becomes relevant, and AIUI
> receivers have to compensate for it.  I don't know if the satellites

GPS receivers do compensate for one (purely) relativistic effect:

Since the orbits are only nearly circular, the sats experience slightly 
variable gravity fields, depending upon current orbit height.

This means that the onboard clocks run (very slightly) slower during the 
lower parts of each orbit and faster during the higher parts, right?

Each receiver will then adjust the received clock signal from each sat 
(via the calculated pseudorange and the current sat orbit position and 
calculate how much the onboard clock should be early/late due to the 
integrated gravity drag.

> talk to each other directly or if their signals are coordinated solely
> by ground stations, but the same concerns would apply there as well.

GPS sats don't talk between themselves, they are just updated by the 
monitoring base stations ("the control segment") exactly what they 
should transmit from now on, i.e. based on orbit and clock adjustments 
parameters.

The requirement is to keep each sat clock within 10 us of UTC(USNO), but 
they have been doing much better than this for many years.
>
> Keeping time is an embarrassingly parallel problem, but I wouldn't be
> surprised if the military had other satellites in orbit for which
> relativity was an even greater concern.

As in highly elliptical, semi-polar orbits? :-)

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.arch

csiph-web