The content of this blog is my personal opinion only. Although I am an employee - currently of Nvidia, in the past of other companies such as Iagination Technologies, MIPS, Intellectual Ventures, Intel, AMD, Motorola, and Gould - I reveal this only so that the reader may account for any possible bias I may have towards my employer's products. The statements I make here in no way represent my employer's position, nor am I authorized to speak on behalf of my employer. In fact, this posting may not even represent my personal opinion, since occasionally I play devil's advocate.

See http://docs.google.com/View?id=dcxddbtr_23cg5thdfj for photo credits.

Tuesday, March 06, 2012

Pseudo-atomic - atomic operations that can fail


[[Pseudo-atomic]] is a term that I (Glew) have coined to refer to atomic operations that can fail to be atomic, such as:
* [[Load-linked/store-conditional (LL/SC)]]
* even [[hardware transactional memory]]
** such as [[Intel Transactional Synchronization Extensions (TSX)]]'s [[Restricted Transactional Memory (RTM)]], where "the [[XBEGIN]] instruction takes an operand that provides a relative offset to the fallback instruction address if the RTM region could not be successfully executed transactionally."

Q: what does IBM transactional memory provide? Is it pseudo-atomic, or does it provide guarantees?

I.e. these [[pseudo-atomic]] operations do not guarantee completion.
At least not at the instruction level.
While it is possible to imagine implementations that detect use of pseudo-atomic instruction sequences
and provide guarantees that certain code sequences will eventually complete.
such mechanisms are
(1) not necessarily architectural
and (2) more complicated that non-pseudo[-atomic instructions.

E.g. for [[LL/SC]] hardware could "pick up" the instructions that lie between the load-linked and the store-conditional,
and map them onto a vocabulary of atomic instructions such as [[fetch-and-op]] that is supported by the memory subsystem.
Similarly, [[LL/SC]] might be implemented using [[transactional memory (TM)]].

Intel's TSX documentation says

    RTM instructions do not have any data memory location associated with them. While
    the hardware provides no guarantees as to whether an RTM region will ever successfully
    commit transactionally, most transactions that follow the recommended guidelines
    (See Section 8.3.8) are expected to successfully commit transactionally.
    However, programmers must always provide an alternative code sequence in the fallback
    path to guarantee forward progress. This may be as simple as acquiring a lock
    and executing the specified code region non-transactionally. Further, a transaction
    that always aborts on a given implementation may complete transactionally on a
    future implementation. Therefore, programmers must ensure the code paths for the
    transactional region and the alternative code sequence are functionally tested.

GLEW OPINION: requiring alternate code paths has historically been a bad idea.
E.g. [[Intel Intanium ALAT]]. Now [[RTM (Restricted Transactional Memory)]]

Why, then, provide pseudo-atomicity?

* Pseudo-atomic operations allow complicated atomic operations to be built up out of simpler
* Plus, of course, it is easier than providing real atomicity.  Most of the time it works.  Most of the time may be good enough for many people, who may not care if it occasionally crashes when the seldom used alternate path is exercised.

No comments: