The Two-Headed UltraSPARC Client

The Two-Headed UltraSPARC Client

(or Why Two Heads are Better Than One)

The 64-bit UltraSPARC client actually runs two 32-bit bitslice clients in parallel on each processor (starting with version V0.215-dk003).

One of the clients uses the low-order 32-bits of the UltraSPARC's 64-bit words. The other client uses the high-order 32-bits of the 64-bit words.

On a single-CPU system, you will see two clients start up together, and work in tandem.

On a dual-CPU system, if you tell the client you have 2 CPUs, you will see two pairs of clients start up together. Each pair will work in tandem on one CPU.

Darrell Kindred developed the UltraSPARC (and other) bitslice clients, using the fast keysearch algorithm Rocke devised. The UltraSPARC client also uses optimized "S-box" circuits Rocke constructed.

Background

The UltraSPARC is a 64-bit processor, so in principle it can perform operations on 64-bit integers in a single step. However, Sun's operating system (Solaris) doesn't support applications that use these 64-bit operations. Every time a context switch occurs, the contents of the high-order 32 bits of the 64-bit registers may be destroyed.

In order to overcome this problem, the UltraSPARC DESCHALL client periodically checkpoints the state of the computation. It then attempts to detect when a context switch has occurred, and when it does, it rolls the computation back to the most recent safe checkpoint and restarts from there.

This checkpoint/roll-back scheme incurs a very small performance penalty, but it is 100% reliable, provided we can always detect the context switches.

We have tested this code extensively. So far, it has been 100% reliable in a test environment.

It appears to be 100% reliable to run a 64-bit client.

But since the operating system doesn't support 64-bit registers, and since the real world is sometimes more harsh than a laboratory environment, we've hedged our bets.

We run a 32-bit client in the low-order 32 bits. The results of this client are 100% reliable, even if the detection of a context switch isn't perfect.

We run a separate 32-bit client in the high-order 32-bits. The results of this client are 100% reliable, as long as the context-switch detection is perfect. But the results from this 32-bit client are logged at the server with a special code.

We will be spot-checking the results of these clients. If we find there are certain environments where the context switches are not reliably detected, we may have to re-test keys processed by the "B" clients, but we can always rely on the other half of the results, from the "A" clients.

Let me re-emphasize...We believe this is 100% reliable, and we do not anticipate purging any keys from the tested keyspace.


Footnote: Context Switches

In a preemptive multitasking operating system (like Unix, Windows 95, and Windows NT), the operating system can run several applications at once by allowing the applications to "take turns" using the processor. When one application has had the CPU for long enough, the OS suspends it, saves its state, and allows another application to use the CPU. When the first application's turn comes again, the OS restores the state it saved before, so the application can continue. This act of suspending one application, saving its state, restoring another application's state, and allowing it to resume, is called a context switch, since the CPU's "context" switches from one application to another.

This technique has the advantage that applications don't have the responsibility of sharing the CPU. An application can just pretend it has the CPU all to itself, since the context switches are "invisible" to the application.

However, this invisibility breaks down when the operating system doesn't save and restore the full state of the application. That's what happens when you try to operate on 64-bit integers under Solaris; the OS only saves 32 bits of each register, so if you're operating on 64-bit integers when the context switch occurs, the next restore won't restore all your data.

Since the whole idea of preemptive multitasking is to hide context switches from applications, it's a bit tricky for an application to detect when a context switch has occurred, but that's what we must do to recover from the 64-bit data corruptions.

[DESCHALL home page]


Darrell Kindred
Last modified: Sun Jun 15 18:19:17 EDT 1997