By: sr (nobody.delete@this.nowhere.com), April 10, 2021 1:47 am
Room: Moderated Discussions
NoSpammer (no.delete@this.spam.com) on April 10, 2021 12:02 am wrote:
> Well, let's think through it with a simplistic top-level view. Suppose you limit the transaction footprint
> to something reasonable the software and CPU can handle, and let's say you can even prove you have an algorithm
> that can roll back intelligently to guarantee forward progress and correctness of execution (with respect
> to ordering etc.).
That roll back is done by hardware, the whole point of transactional memory.
Now, let's say you have 2 threads with interlocking transactions. You need to have a protocol
> to resolve this, and the two CPU cores will have to exchange some information in order to roll back intelligently.
Of course they have. Hardware can roll back either one or both and retry with different timing path.
> This will take some time. Now suppose you have 3 threads on physically different CPUs that need some protocol
> to resolve interlocking transactions. Sound like a fine mathematical exercise. I guess it can be done. Now
> throw in some IRQ/NMI and maybe a couple non-transactional threads trying to read some lines locked by some
> of the transactions. I'm sure I have forgotten something more, like debugging features or any exceptions.
Transactions do not lock lines, thats the definition. Two or more transactions could be interlocked but in a way that either part of them or all of them can be aborted.
> If needed, maybe add just one more layer of nested transactions for more fun.
>
> Can you see the combinatorial explosion of the state space? Can you easily envision a protocol
> to resolve all of possible situations correctly in a close to optimal way? Can you define a hardware
> test protocol for the implementation? Can you put timing estimates on resolution of transactions?
> What would be the waiting time for these to resolve vs. locking? I guess some advanced application
> of queuing theory could get you that far, with my post-grad math it would certainly take me quite
> some time to get anywhere near to correct analytical answers to these.
It's not about perfection. Hardware transactions do fail and retry. Perfect implementation is traditional locking - and if it fails there will be data corruption, deadlock or some other unwanted behaviour.
> Well, let's think through it with a simplistic top-level view. Suppose you limit the transaction footprint
> to something reasonable the software and CPU can handle, and let's say you can even prove you have an algorithm
> that can roll back intelligently to guarantee forward progress and correctness of execution (with respect
> to ordering etc.).
That roll back is done by hardware, the whole point of transactional memory.
Now, let's say you have 2 threads with interlocking transactions. You need to have a protocol
> to resolve this, and the two CPU cores will have to exchange some information in order to roll back intelligently.
Of course they have. Hardware can roll back either one or both and retry with different timing path.
> This will take some time. Now suppose you have 3 threads on physically different CPUs that need some protocol
> to resolve interlocking transactions. Sound like a fine mathematical exercise. I guess it can be done. Now
> throw in some IRQ/NMI and maybe a couple non-transactional threads trying to read some lines locked by some
> of the transactions. I'm sure I have forgotten something more, like debugging features or any exceptions.
Transactions do not lock lines, thats the definition. Two or more transactions could be interlocked but in a way that either part of them or all of them can be aborted.
> If needed, maybe add just one more layer of nested transactions for more fun.
>
> Can you see the combinatorial explosion of the state space? Can you easily envision a protocol
> to resolve all of possible situations correctly in a close to optimal way? Can you define a hardware
> test protocol for the implementation? Can you put timing estimates on resolution of transactions?
> What would be the waiting time for these to resolve vs. locking? I guess some advanced application
> of queuing theory could get you that far, with my post-grad math it would certainly take me quite
> some time to get anywhere near to correct analytical answers to these.
It's not about perfection. Hardware transactions do fail and retry. Perfect implementation is traditional locking - and if it fails there will be data corruption, deadlock or some other unwanted behaviour.
