Thread-safe Algorithm

 

The Paradox:

The software performs logical update protection without coherence.

The hardware performs hardware update protection with coherence.

Coherence imposes a processor limit.

 

The Software Solution:

Allocate memory when needed to self-protect data from other processes.

(The remainder of this article pertains to shared data only. This excludes static or common data that has change control, such as programs. It also excludes read-only data which changes but the the process does not modify, such as timestamps. Shared data is defined as data the process modifies that is also subject to change by another process during execution.)

Logically protect shared data memory updates by coding for a data race.

An atomic Hardware Synchronization Primitive (HSP, i.e. CMPXCHG or Compare and Swap) provides logical shared memory update protection using a combination of three methods.

An HSP logically protects shared memory updates with a lock, data swap, or pointer swap. This permits programs to be thread-safe and eliminates the data race.

The software is thread-safe because it recognizes and executes shared data differently.

 

Thread-Safe Algorithm:

Thread-Safe requires an update with an uninterruptible instruction and for data to be stored in only one place.

The Hardware Issue:

An HSP must be uninterruptible on a uni-processor.

An HSP must be atomic on a multiprocessor.

Current HSPs are pseudo-atomic since they are implemented in the cache and multiple caches require coherence to synchronize.

 

No Benefit:

However there is no benefit to implementing the HSP in main memory because coherence is required for all shared data, not just the swap address.

So make the cache pass-through for all shared data. This eliminates the coherence requirement on shared data. And non-shared data does not require coherence.

The misconception is that the cache benefits repeat reads of shared data. It does not because the software avoids repeat reads of shared data. Repeat reads should only occur when different processes on the same core processor read the same shared data address; software resolves this without coherence. The software is thread-safe.

 

The Hardware Solution:

Implement the HSP in main memory and the HSP becomes atomic and coherence is eliminated.

Instructions that update main memory with a data swap are logically protected from a data race. 

Instructions that update main memory within a lock or before a pointer swap, are logically protected by that lock or swap.

The result is hardware update protection without coherence.

Current coherence methods are write-through so it is only the modified HSP instruction that incurs increased overhead.

The result is Thread-Safe Hardware.

Thread-safe computers eliminate coherence by using the thread-safe software algorithm.

It has no core processor limit.

Different Algorithms for the Same Problem

 

 Patent Pending