A Coherence-Free Processor Design
A Thread-Safe Computer
(Design published in Journal of Computer Science and Technology)
In
late 1960s my Dad, Prof. C.N. Yang (Nobel Prize Physics, 1957), was
teaching his physics gauge field theory when he realized that
math bundle theory had the exact same formula. The terms and symbols
were different, but it was the exact same formula. Dad joked that
mathematicians were able to solve the same problem even though they have
no connection with the physical world. Coming from a Theoretical
Physicist!
Coherence and Thread-Safe:
Coherence and thread-safe address the same issue.
However thread safety handles infinite tasks while coherence allows only four processors.
However thread safety handles infinite tasks while coherence allows only four processors.
Software Issue:
Thread safety -
"Thread safety is the avoidance of data races—situations in which data
are set to either correct or incorrect values, depending upon the order
in which multiple threads access and modify the data."
Hardware Issue:
Cache Coherence - "In
computer architecture, cache coherence is the uniformity of shared
resource data that ends up stored in multiple local caches. When clients
in a system maintain caches of a common memory resource, problems may
arise with incoherent data, which is particularly the case with CPUs in a
multiprocessing system."
The solution is thread safe hardware. (overview below)
The Same Problem:
The thread safety algorithm works for multiple software processes sharing data.
The same algorithm could apply to multiple processors with caches sharing memory.
They are manifestations of the same problem. (detailed explanation)
The algorithm the software uses supports infinite tasks.The algorithm the hardware uses becomes inefficient at 5.
The software algorithm can be used on the hardware, entirely eliminating coherence.
This eliminates the core processor limit on multiprocessors.
It is an algorithm, so it is universal.
JVMs have thread safety which enables java concurrency.
The Hardware is Missing Information:
The hardware does not know what data is shared. However the software does.
Actually the software does not, but the programmer knows.
The program logic knows.
The Solution - Thread-Safe Design:
The solution uses current software.
The new computer design manages memory differently so it is always coherent.
The new computer design manages memory differently so it is always coherent.
The solution enables two different algorithms creating two caches. (Albeit one cache is pass-through.)
A new memory allocation instruction specifies the cache where the data must be allocated.
The hardware now knows whether data is exclusive or shared.
One cache is private and the other cache is thread-safe.
The thread-safe cache can be made virtual by making it pass-through.
The atomic swap must be implemented as uninterruptible in main memory. This eliminates coherence.
Requires:
Two new caches, a new instruction, and a modified atomic swap that is atomic and uninterruptible in main memory.
The modified swap eliminates coherence. The new instruction just enables the new caches.
The result - Thread-Safe computers:
Shared data bypasses the cache, there is no cache coherence.
Private data is stored in a cache that does not perform coherence.
Poof, coherence disappears from both caches.
Because the software algorithm does not have coherence!
The programmer knows what data is shared!
The new design runs current software because it uses current software logic.
Instructions are the same but memory is kept coherent.
Nothing changes except for the cache. And the cache is transparent.
The new instruction is required only for performance (speed comparison).
History:
Coherence dates to 1965 and relational databases were invented in 1970.
Relational databases taught programmers to store data in one place.
Compare and Swap was implemented in 1973.
Compare and Swap was implemented in 1973.
However it was implemented in the cache and all instructions still are.
And having shared data in more than one cache requires coherence.
But coherence was required because the hardware did not know what data was shared.
Till now.
Needed:
A computer model.
Published article, the Algorithm, and the New Architecture:
A Coherence-Free Processor Design - Peer reviewed and published article
Introducing Thread-Safe Computers - The 2 Step Implementation Approach. Step 1 improves performance. Step 2 eliminates coherence.
Mutex - In brief, how the mutex works.
JVM is Thread-Safe - Why a JVM is thread-safe but processors are not.
An Alternative to Coherence - Detailed description of the implementation.
Speed Comparison - Why thread-safe computers are faster even at two cores.
Further Detail:
The Thread-safe Algorithm - The Algorithm Enabling Updates without Coherence.
Multitasking vs Concurrent vs Thread-safe vs Coherence - How thread-safe can replace coherence.
Coherence Equals Data Race - More on why they are the same problem.
Coherence-Free Thread-Safe Hardware - Main blog page.
Why Atomic currently has coherence - Why current atomic instructions are not atomic.
Thread-Safe Java Concurrency Eliminates Coherence - How Java Virtual Machines have no coherence.
Hardware Conundrum - The current hardware has insufficient information.
Draft for wiki (not an entry due to COI)
Franklin Yang 杨光诺
FrankYang43338@acm.org
FrankYang43338@gmail.com
No comments:
Post a Comment