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

From: Jun Sun <[email-masked]>
Date: Wed, 4 Jun 2003 15:39:30 -0700

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

---

From: "Michael Uhler" <[email-masked]>
Date: Wed, 4 Jun 2003 15:51:49 -0700

See interspersed comments.

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Jun Sun
> Sent: Wednesday, June 04, 2003 3:40 PM
> To: [email-masked]
> Cc: [email-masked]
> Subject: [RFC] synchronized CPU count registers on SMP machines
> 
> 
> 

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

> don't have the above issues (true?).  And it is probably 
> worthwile to synchronize count registers for them.
> 

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

---

From: Ralf Baechle <[email-masked]>
Date: Thu, 5 Jun 2003 01:15:47 +0200

> to synchronize count registers for them.

1) and 2) affect most SGI systems.

  Ralf

---

From: Jun Sun <[email-masked]>
Date: Wed, 4 Jun 2003 16:44:20 -0700

On Wed, Jun 04, 2003 at 03:51:49PM -0700, Michael Uhler wrote:
<snip>
> 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.

> different paths).  As such, you could see on order of memory latency

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

---

From: Jun Sun <[email-masked]>
Date: Wed, 4 Jun 2003 16:46:52 -0700

> 1) and 2) affect most SGI systems.

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

Jun

---

From: Ralf Baechle <[email-masked]>
Date: Thu, 5 Jun 2003 02:12:32 +0200

> Assuming SGI systems represent the past of MIPS, we are still ok

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

---

From: Keith Owens <[email-masked]>
Date: Thu, 05 Jun 2003 10:18:28 +1000

On Wed, 4 Jun 2003 15:39:30 -0700, 
>I wonder if this is something which have been done before,

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.

---

From: Jun Sun <[email-masked]>
Date: Wed, 4 Jun 2003 18:38:36 -0700

> slightest bit - among other things the standards mandate time to

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

---

From: Dominic Sweetman <[email-masked]>
Date: Thu, 5 Jun 2003 09:09:05 +0100

> I don't see how we can avoid this - unless we don't care about

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

---

From: "Kevin D. Kissell" <[email-masked]>
Date: Thu, 5 Jun 2003 10:55:10 +0200

----- Original Message ----- 
From: "Jun Sun" <[email-masked]>
> Assuming SGI systems represent the past of MIPS, we are still ok

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.

---

From: Ralf Baechle <[email-masked]>
Date: Thu, 5 Jun 2003 10:48:52 +0200

> 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

---

From: Ralf Baechle <[email-masked]>
Date: Thu, 5 Jun 2003 10:51:22 +0200

> 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

---

From: Alan Cox <[email-masked]>
Date: 05 Jun 2003 11:45:03 +0100

> slightest bit - among other things the standards mandate time to

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)

---

From: "Maciej W. Rozycki" <[email-masked]>
Date: Thu, 5 Jun 2003 13:08:19 +0200 (MET DST)

> 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: [email-masked], PGP key available        +

---

From: Jun Sun <[email-masked]>
Date: Thu, 5 Jun 2003 09:53:48 -0700

> 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

---

From: Greg Lindahl <[email-masked]>
Date: Thu, 5 Jun 2003 13:06:32 -0700

> 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