[RFC] synchronized CPU count registers on SMP machines

[RFC] synchronized CPU count registers on SMP machines

[Jun Sun]

There are many benefits of having perfectly synchronized CPU
count registers on SMP machines.

I wonder if this is something which have been done before,
and if this is feasible.

Apparently, this scheme won't work if any of the following
conditions are true:

1) clocks on different CPUs don't have the same frequency
2) clocks on different CPUs drift to each other
2) some fancy power saving feature such as frequency scaling

But I think for a foreseeable future most MIPS SMP machines
don't have the above issues (true?).  And it is probably worthwile
to synchronize count registers for them.

I think some pseudo code like the below could get the 
job done:

CPU 0:
	send interrupt to all other CPUs and ask them to sync count
	wait for all other CPUs to gather at rendevous point
	flip a flag
	set count to 0

other CPUs:
	trapped by IPI
	reach the rendevous point (busy spin locking)
	wait for the flip of the flag
	set count to 0

I wonder after the above code how synchronized are the count regsiters.
Are they perfectly synchronized or still differ by a few counts?

Any comments?

Jun

RE: [RFC] synchronized CPU count registers on SMP machines

[Michael Uhler]

See interspersed comments.

> -----Original Message-----
> From: linux-mips-bounce@linux-mips.org 
> [mailto:linux-mips-bounce@linux-mips.org] On Behalf Of Jun Sun
> Sent: Wednesday, June 04, 2003 3:40 PM
> To: linux-mips@linux-mips.org
> Cc: jsun@mvista.com
> Subject: [RFC] synchronized CPU count registers on SMP machines
> 
> 
> 
> There are many benefits of having perfectly synchronized CPU 
> count registers on SMP machines.
> 
> I wonder if this is something which have been done before,
> and if this is feasible.

I remember doing something like this about 20 years ago on a much
different operating system in which the goal was to move the count
registers apart by a predictable amount such that a clock interrupt
didn't occur on all the CPUs at once.  But even in that case, we weren't
looking for precise matching.
> 
> Apparently, this scheme won't work if any of the following 
> conditions are true:
> 
> 1) clocks on different CPUs don't have the same frequency
> 2) clocks on different CPUs drift to each other

Depending on the precise system configuration (including whether the
CPUs are on different SOCs, different boards, where the PLLs are, and
what the ultimate clock source is), I'd guess that drift is pretty
likely on almost all systems unless the clocks are intentionally driven
by some sort of synchronize source.

> 2) some fancy power saving feature such as frequency scaling
> 
> But I think for a foreseeable future most MIPS SMP machines 
> don't have the above issues (true?).  And it is probably 
> worthwile to synchronize count registers for them.
> 
> I think some pseudo code like the below could get the 
> job done:
> 
> CPU 0:
> 	send interrupt to all other CPUs and ask them to sync count
> 	wait for all other CPUs to gather at rendevous point
> 	flip a flag
> 	set count to 0
> 
> other CPUs:
> 	trapped by IPI
> 	reach the rendevous point (busy spin locking)
> 	wait for the flip of the flag
> 	set count to 0

The biggest problem here is latency on the spinlocks and observation of
the flag state changing.  Depending on the memory architecture, the
point at which each CPU will see the change could be very different
(consider a NUMA mesh architecture in which the data movement can take
different paths).  As such, you could see on order of memory latency
different in the clocks.

You could run a counter adjustment periodically, or try to calibrate the
adjustment to make this closer, but I'm not sure that you can get
perfect synchronization.

> 
> I wonder after the above code how synchronized are the count 
> regsiters. Are they perfectly synchronized or still differ by 
> a few counts?
> 
> Any comments?
> 
> Jun
> 
> 

RE: [RFC] synchronized CPU count registers on SMP machines

[Michael Uhler]

See interspersed comments.

> -----Original Message-----
> From: linux-mips-bounce@linux-mips.org 
> [mailto:linux-mips-bounce@linux-mips.org] On Behalf Of Jun Sun
> Sent: Wednesday, June 04, 2003 3:40 PM
> To: linux-mips@linux-mips.org
> Cc: jsun@mvista.com
> Subject: [RFC] synchronized CPU count registers on SMP machines
> 
> 
> 
> There are many benefits of having perfectly synchronized CPU 
> count registers on SMP machines.
> 
> I wonder if this is something which have been done before,
> and if this is feasible.

I remember doing something like this about 20 years ago on a much
different operating system in which the goal was to move the count
registers apart by a predictable amount such that a clock interrupt
didn't occur on all the CPUs at once.  But even in that case, we weren't
looking for precise matching.
> 
> Apparently, this scheme won't work if any of the following 
> conditions are true:
> 
> 1) clocks on different CPUs don't have the same frequency
> 2) clocks on different CPUs drift to each other

Depending on the precise system configuration (including whether the
CPUs are on different SOCs, different boards, where the PLLs are, and
what the ultimate clock source is), I'd guess that drift is pretty
likely on almost all systems unless the clocks are intentionally driven
by some sort of synchronize source.

> 2) some fancy power saving feature such as frequency scaling
> 
> But I think for a foreseeable future most MIPS SMP machines 
> don't have the above issues (true?).  And it is probably 
> worthwile to synchronize count registers for them.
> 
> I think some pseudo code like the below could get the 
> job done:
> 
> CPU 0:
> 	send interrupt to all other CPUs and ask them to sync count
> 	wait for all other CPUs to gather at rendevous point
> 	flip a flag
> 	set count to 0
> 
> other CPUs:
> 	trapped by IPI
> 	reach the rendevous point (busy spin locking)
> 	wait for the flip of the flag
> 	set count to 0

The biggest problem here is latency on the spinlocks and observation of
the flag state changing.  Depending on the memory architecture, the
point at which each CPU will see the change could be very different
(consider a NUMA mesh architecture in which the data movement can take
different paths).  As such, you could see on order of memory latency
different in the clocks.

You could run a counter adjustment periodically, or try to calibrate the
adjustment to make this closer, but I'm not sure that you can get
perfect synchronization.

> 
> I wonder after the above code how synchronized are the count 
> regsiters. Are they perfectly synchronized or still differ by 
> a few counts?
> 
> Any comments?
> 
> Jun
> 
> 

Re: [RFC] synchronized CPU count registers on SMP machines

[Jun Sun]

On Wed, Jun 04, 2003 at 03:51:49PM -0700, Michael Uhler wrote:
<snip>
> > 
> > Apparently, this scheme won't work if any of the following 
> > conditions are true:
> > 
> > 1) clocks on different CPUs don't have the same frequency
> > 2) clocks on different CPUs drift to each other
> 
> Depending on the precise system configuration (including whether the
> CPUs are on different SOCs, different boards, where the PLLs are, and
> what the ultimate clock source is), I'd guess that drift is pretty
> likely on almost all systems unless the clocks are intentionally driven
> by some sort of synchronize source.
>

Yes, if there are physically multiple boards, it is likely to have
drifting clocks.

I don't suppose the count synchronization code will work for
all SMP systems.  I hope to get an idea whether it is worth the effort
for the systems that it does work.

For example, it will work on Broadcom's BCM91250 chip and probably a
couple of coming ones.

To give an idea of my original motivation on this RFC, I found out
it is pretty _hard_ just to get a micro-second resolution gettimeofday()
on a SMP system.  And apparently this is an issue on other arches
as well.  I think i386 uses synchronized TSCs, which is the same
idea as what we are talking about here.

> The biggest problem here is latency on the spinlocks and observation of
> the flag state changing.  Depending on the memory architecture, the
> point at which each CPU will see the change could be very different
> (consider a NUMA mesh architecture in which the data movement can take
> different paths).  As such, you could see on order of memory latency
> different in the clocks.
>

If it is a few clocks in difference, it should be acceptable.

Basically, imagine a spin lock protected read_count routine:

unsigned read_count() 
{
	spin_lock(&count_lock);
	count = read_c0_count();
	spin_unlock(&count_lock);
	return count;
}

and imagine there are randomly calls to this function by different
CPUs, the calls are serialized due to the spinlock.  As long as
the return values are monotonically increasing, we are fine.

Thanks for the reply.  And congrads on your new post. :)

Jun

Re: [RFC] synchronized CPU count registers on SMP machines

[Ralf Baechle]

On Wed, Jun 04, 2003 at 03:39:30PM -0700, Jun Sun wrote:

> 1) clocks on different CPUs don't have the same frequency
> 2) clocks on different CPUs drift to each other
> 2) some fancy power saving feature such as frequency scaling
> 
> But I think for a foreseeable future most MIPS SMP machines
> don't have the above issues (true?).  And it is probably worthwile
> to synchronize count registers for them.

1) and 2) affect most SGI systems.

  Ralf

Re: [RFC] synchronized CPU count registers on SMP machines

[Jun Sun]

On Thu, Jun 05, 2003 at 01:15:47AM +0200, Ralf Baechle wrote:
> On Wed, Jun 04, 2003 at 03:39:30PM -0700, Jun Sun wrote:
> 
> > 1) clocks on different CPUs don't have the same frequency
> > 2) clocks on different CPUs drift to each other
> > 2) some fancy power saving feature such as frequency scaling
> > 
> > But I think for a foreseeable future most MIPS SMP machines
> > don't have the above issues (true?).  And it is probably worthwile
> > to synchronize count registers for them.
> 
> 1) and 2) affect most SGI systems.
>

Assuming SGI systems represent the past of MIPS, we are still ok
future-wise. :)

Jun

Re: [RFC] synchronized CPU count registers on SMP machines

[Ralf Baechle]

On Wed, Jun 04, 2003 at 04:46:52PM -0700, Jun Sun wrote:

> Assuming SGI systems represent the past of MIPS, we are still ok
> future-wise. :)

You loose.  The reasons why SGI did construct their systems that way are
still valid.  It can be quite tricky to distribute the clock in large
systems - even for a moderate definition of large.  And for ccNUMAs which
are going to show up on the embedded market sooner or later it's easy
for the lazy designer to use several clock sources anyway.  Note our
current time code for will not work properly if clocks diverge on the
slightest bit - among other things the standards mandate time to
monotonically increase.

  Ralf

Re: [RFC] synchronized CPU count registers on SMP machines

[Jun Sun]

On Thu, Jun 05, 2003 at 02:12:32AM +0200, Ralf Baechle wrote:
> On Wed, Jun 04, 2003 at 04:46:52PM -0700, Jun Sun wrote:
> 
> > Assuming SGI systems represent the past of MIPS, we are still ok
> > future-wise. :)
> 
> You loose.  The reasons why SGI did construct their systems that way are
> still valid.  It can be quite tricky to distribute the clock in large
> systems - even for a moderate definition of large.  And for ccNUMAs which
> are going to show up on the embedded market sooner or later it's easy
> for the lazy designer to use several clock sources anyway.  Note our
> current time code for will not work properly if clocks diverge on the
> slightest bit - among other things the standards mandate time to
> monotonically increase.
>

Aside from aficionado of SGI legacy, do you see any value in
implementing this just for the applicable SMP systems?

Here is my take:

To implement an efficient and correct time management in SMP
is a hard problem.  I don't think there is a generic solution
here.  (Convince me if I am wrong.)

Therefore for a set of "conforming" SMP systems which don't
have the listed 3 issues, we provide a feasible solution.
I don't see how we can avoid this - unless we don't care about
getting time right.

Jun

Re: [RFC] synchronized CPU count registers on SMP machines

[Dominic Sweetman]

> Therefore for a set of "conforming" SMP systems which don't
> have the listed 3 issues, we provide a feasible solution.
> I don't see how we can avoid this - unless we don't care about
> getting time right.

Interesting.  I guess you only need to get time "right enough" -
there's an unavoidable fuzziness about the synchronisation of events
on different CPUs (corresponding to the uncertainties of the timing of
any rendezvous between them).

A naive network synchronisation protocol - analogous to your first
proposal - would leave clocks differing by a network round-trip time
or so: but NTP does a lot better.  So in principle you should be able
to scale NTP to create a clock synchronised within some fraction of
the time taken by a CPU-to-CPU communication... but compressing the
essence of the NTP protocol into something which runs fast enough
might be interesting!

My 5-minutes-over-breakfast feeling is that you should be able to
figure out a way to get time right enough; try reading up how NTP
works and see whether it can be made to work?

--
Dominic

Re: [RFC] synchronized CPU count registers on SMP machines

[Ralf Baechle]

On Thu, Jun 05, 2003 at 09:09:05AM +0100, Dominic Sweetman wrote:

> A naive network synchronisation protocol - analogous to your first
> proposal - would leave clocks differing by a network round-trip time
> or so: but NTP does a lot better.  So in principle you should be able
> to scale NTP to create a clock synchronised within some fraction of
> the time taken by a CPU-to-CPU communication... but compressing the
> essence of the NTP protocol into something which runs fast enough
> might be interesting!
> 
> My 5-minutes-over-breakfast feeling is that you should be able to
> figure out a way to get time right enough; try reading up how NTP
> works and see whether it can be made to work?

Yes, already been thinking about that.  The essence of NTP is a software
implementation of a phase locked loop.  The full NTP protocol is way to
heavy of course but the subset we're talking about would be rather
lightweight.  I'd expect the phase noise to be in the low ppb range,
little problems with unlocking.  And it'll be usable for arbitrary
combinations of clock frequencies.  So an approach to try.

Enjoy your breakfast :-)

  Ralf

Re: [RFC] synchronized CPU count registers on SMP machines

[Jun Sun]

On Thu, Jun 05, 2003 at 10:48:52AM +0200, Ralf Baechle wrote:
> On Thu, Jun 05, 2003 at 09:09:05AM +0100, Dominic Sweetman wrote:
> 
> > A naive network synchronisation protocol - analogous to your first
> > proposal - would leave clocks differing by a network round-trip time
> > or so: but NTP does a lot better.  So in principle you should be able
> > to scale NTP to create a clock synchronised within some fraction of
> > the time taken by a CPU-to-CPU communication... but compressing the
> > essence of the NTP protocol into something which runs fast enough
> > might be interesting!
> > 
> > My 5-minutes-over-breakfast feeling is that you should be able to
> > figure out a way to get time right enough; try reading up how NTP
> > works and see whether it can be made to work?
> 
> Yes, already been thinking about that.  The essence of NTP is a software
> implementation of a phase locked loop.  The full NTP protocol is way to
> heavy of course but the subset we're talking about would be rather
> lightweight.  I'd expect the phase noise to be in the low ppb range,
> little problems with unlocking.  And it'll be usable for arbitrary
> combinations of clock frequencies.  So an approach to try.
>

OK, I think you all convinced me that it is probably not a good
idea to do the synchronized CPU count registers, at least not until
we take a look of some alternatives.
 
> Enjoy your breakfast :-)
>

What are you eating?  I probably should have that when I was thinking
about this RFC. :)

In response to some other replies:

1) yes, it is always possible to use some external system-wide
timer source, if available, to solve this problem.  However, that could
get tricky too, and I wanted to do something generic which is hopefully 
applicable to more systems.

2) at least from my perspective, I see increasing demand for high
resolution timers that has monotonicity in both kernel space and user space.

Jun

Re: [RFC] synchronized CPU count registers on SMP machines

[Greg Lindahl]

On Thu, Jun 05, 2003 at 09:53:48AM -0700, Jun Sun wrote:

> 1) yes, it is always possible to use some external system-wide
> timer source, if available, to solve this problem.  However, that could
> get tricky too, and I wanted to do something generic which is hopefully 
> applicable to more systems.

Such sources are generally both much lower resolution, and they take a
long time to read. But a _consistent_ but higher overhead, lower
resolution number is better than an inconsistent number.

greg

Re: [RFC] synchronized CPU count registers on SMP machines

[Alan Cox]

On Iau, 2003-06-05 at 01:12, Ralf Baechle wrote:
> You loose.  The reasons why SGI did construct their systems that way are
> still valid.  It can be quite tricky to distribute the clock in large
> systems - even for a moderate definition of large.  And for ccNUMAs which
> are going to show up on the embedded market sooner or later it's easy
> for the lazy designer to use several clock sources anyway.  Note our
> current time code for will not work properly if clocks diverge on the
> slightest bit - among other things the standards mandate time to
> monotonically increase.

Actually the standards are suprisingly lax. I had the same assumptions
but people who went and read the spec in detail found Posix is a lot
more relaxed (except about CLOCK_MONOTONIC).

What seems to be happening in the PC and Sparc worlds is vendors are
running a seperate lower accuracy global clock source (eg the HPET on
AMD64)

Re: [RFC] synchronized CPU count registers on SMP machines

[Kevin D. Kissell]

----- Original Message ----- 
From: "Jun Sun" <jsun@mvista.com>
> On Thu, Jun 05, 2003 at 01:15:47AM +0200, Ralf Baechle wrote:
> > On Wed, Jun 04, 2003 at 03:39:30PM -0700, Jun Sun wrote:
> > 
> > > 1) clocks on different CPUs don't have the same frequency
> > > 2) clocks on different CPUs drift to each other
> > > 2) some fancy power saving feature such as frequency scaling
> > > 
> > > But I think for a foreseeable future most MIPS SMP machines
> > > don't have the above issues (true?).  And it is probably worthwile
> > > to synchronize count registers for them.
> > 
> > 1) and 2) affect most SGI systems.
> >
> 
> Assuming SGI systems represent the past of MIPS, we are still ok
> future-wise. :)

I personally think it would be foolish to assume that future MIPS 
MP systems will not be subject to one or more such constraint.

            Kevin K.

Re: [RFC] synchronized CPU count registers on SMP machines

[Ralf Baechle]

On Thu, Jun 05, 2003 at 10:55:10AM +0200, Kevin D. Kissell wrote:

> I personally think it would be foolish to assume that future MIPS 
> MP systems will not be subject to one or more such constraint.

I'm expecting something like hypertransport-based ccNUMAs to bring up
that problem again.

  Ralf

Re: [RFC] synchronized CPU count registers on SMP machines

[Kevin D. Kissell]

----- Original Message ----- 
From: "Jun Sun" <jsun@mvista.com>
> On Thu, Jun 05, 2003 at 01:15:47AM +0200, Ralf Baechle wrote:
> > On Wed, Jun 04, 2003 at 03:39:30PM -0700, Jun Sun wrote:
> > 
> > > 1) clocks on different CPUs don't have the same frequency
> > > 2) clocks on different CPUs drift to each other
> > > 2) some fancy power saving feature such as frequency scaling
> > > 
> > > But I think for a foreseeable future most MIPS SMP machines
> > > don't have the above issues (true?).  And it is probably worthwile
> > > to synchronize count registers for them.
> > 
> > 1) and 2) affect most SGI systems.
> >
> 
> Assuming SGI systems represent the past of MIPS, we are still ok
> future-wise. :)

I personally think it would be foolish to assume that future MIPS 
MP systems will not be subject to one or more such constraint.

            Kevin K.

Re: [RFC] synchronized CPU count registers on SMP machines

[Maciej W. Rozycki]

On Thu, 5 Jun 2003, Kevin D. Kissell wrote:

> > > > 1) clocks on different CPUs don't have the same frequency
> > > > 2) clocks on different CPUs drift to each other
> > > > 2) some fancy power saving feature such as frequency scaling
> > > > 
> > > > But I think for a foreseeable future most MIPS SMP machines
> > > > don't have the above issues (true?).  And it is probably worthwile
> > > > to synchronize count registers for them.
> > > 
> > > 1) and 2) affect most SGI systems.
> > >
> > 
> > Assuming SGI systems represent the past of MIPS, we are still ok
> > future-wise. :)
> 
> I personally think it would be foolish to assume that future MIPS 
> MP systems will not be subject to one or more such constraint.

 Depending on the system in use it may be easier to get a suitable
external clock reference, e.g. a chipset timer.  If an access to it would
be slow, it could be cached on timer interrupts and extended with
processors' timers.

-- 
+  Maciej W. Rozycki, Technical University of Gdansk, Poland   +
+--------------------------------------------------------------+
+        e-mail: macro@ds2.pg.gda.pl, PGP key available        +

Re: [RFC] synchronized CPU count registers on SMP machines

[Keith Owens]

On Wed, 4 Jun 2003 15:39:30 -0700, 
Jun Sun <jsun@mvista.com> wrote:
>There are many benefits of having perfectly synchronized CPU
>count registers on SMP machines.
>
>I wonder if this is something which have been done before,
>and if this is feasible.

IA64 has to do this, arch/ia64/kernel/smpboot.c:ia64_sync_itc.  That
function is only called at boot time, but there have been discussions
about calling it regularly to resync the itc values, like NTP.  Of
course, it has no chance of working if you install cpus with different
itc frequencies.

Re: [RFC] synchronized CPU count registers on SMP machines

[Tor Arntsen]

On Jun 5,  0:27, Ralf Baechle wrote:
>On Wed, Jun 04, 2003 at 03:39:30PM -0700, Jun Sun wrote:
>
>> 1) clocks on different CPUs don't have the same frequency
>> 2) clocks on different CPUs drift to each other
>> 2) some fancy power saving feature such as frequency scaling
>> 
>> But I think for a foreseeable future most MIPS SMP machines
>> don't have the above issues (true?).  And it is probably worthwile
>> to synchronize count registers for them.
>
>1) and 2) affect most SGI systems.
>
>  Ralf

1) sometimes to the extreme, on SGI Challenge systems:
 
>hinv -c processor
Processor 0: 150 MHZ IP19 
CPU: MIPS R4400 Processor Chip Revision: 5.0
FPU: MIPS R4000 Floating Point Coprocessor Revision: 0.0
Processor 1: 150 MHZ IP19 
CPU: MIPS R4400 Processor Chip Revision: 5.0
FPU: MIPS R4000 Floating Point Coprocessor Revision: 0.0
Processor 2: 200 MHZ IP19 
CPU: MIPS R4400 Processor Chip Revision: 6.0
FPU: MIPS R4000 Floating Point Coprocessor Revision: 0.0
Processor 3: 200 MHZ IP19 
CPU: MIPS R4400 Processor Chip Revision: 6.0
FPU: MIPS R4000 Floating Point Coprocessor Revision: 0.0

(and the secondary cache sizes are 1MB and 4MB respectively as well)

-Tor