The Same Problem

The Same Problem (detailed)

The algorithms are different so it is not apparent that the problem is the same.

 

Cache Coherence (current definition):

"Cache coherence is the regularity or consistency of data stored in cache memory. Maintaining cache and memory consistency is imperative for multiprocessors."

Cache Coherence problem restated:

Enables 1) multiple core processors 2) using cache copies to 3) update shared data when 4) other processors have different cache copies of the same data.

 

Part 4 is explicit in the current definition. Parts 1-3 are implicit. In particular, the hardware has no way to determine what is a shared data resource (3). The restatement is identical to the Thread safety problem below.

 

Thread safety problem:

Enables 1) multiple processes 2) to use copies of data to 3) update a shared resource when 4) other processes have different copies of the same resource.

The coherence algorithm is to invalidate other caches. This algorithm increases as a binomial with the number of caches. This algorithm resolves (4) which is the current definition of cache coherence.

The thread safety algorithm is to use an atomic uninterruptible swap to ensure update currency. This algorithm increases linearly with the number of processes. This algorithm renders (4) irrelevant. The software resolves the data race in (3).

Thread safe software provides update integrity for multiple records via either single thread or via mutex. Coherence synchronizes the caches with invalidation. However if you bypass the cache for shared data, then you do not need the cache invalidation which is coherence. Thread safe hardware requires bypassing the cache and performing atomic instructions in memory instead of in the cache. However this removes the cache. To create a cache that does not require coherence, merely designate at allocation that data IS private. The private cache does not require coherence and it does not even require write-through.

Coherence has many issues that thread safety resolves. The most important is that coherence is binomial with the number of processors while thread safety has linear contention for one record. Binomial overhead is why current multi-core is restricted to four. (*The fifth processor increases coherence overhead by 67%.) Hardware thread safety can not be implemented because the uninterruptible swap occurs in a cache. It is pseudo-atomic.

The thread safety algorithm requires that the uninterruptible swap is single threaded. This is ensured by executing at a single location which is the shared resource location to ensure update currency. A lock will suffice, because the lock is an uninterruptible swap. The software single threads through one shared resource location but the hardware can not. All current instructions are executed in the cache.

The change is to the hardware implementation of instructions. The software does not change.

* Each conversation is a conduit for invalidation. The fifth processor adds 4 conversations to the system while a 4 processor system has 6 conversations.

 

An Alternative to Coherence

Different Algorithms for the Same Problem