OmniOrder: Directory-Based Conflict Serialization of Transactions ∗

Effective execution of atomic blocks of instructions (also called transactions) can enhance the performance and pro-grammability of multiprocessors. Atomic blocks can be de-marcated in software as in Transactional Memory (TM) or dynamically generated by the hardware as in aggressive im-plementations of strict memory consistency. In most current designs, when two atomic blocks conflict, one is squashed — a performance loss that is often unnecessary. To avoid this waste, this paper presents OmniOrder, the first design that efficiently executes conflicting atomic blocks concurrently in a directory-based coherence environment. The idea is to keep only non-speculative data in the caches and, when the cache coherence protocol transfers a line, include in the message the history of speculative updates to the line. The coherence protocol transitions are unmodified. We evaluate OmniOrder with 64-core simulations. In a TM environment, OmniOrder reduces the execution time of the STAMP applica-tions by an average of 18.4 % over a scheme that squashes on conflict. In an environment with SC enforcement with specu-lation, we run 11 programs that implement concurrent algo-rithms. OmniOrder reduces the programs ’ execution time by an average of 15.3 % relative to a scheme that squashes on conflict. Finally, OmniOrder’s communication overhead of transferring the history of speculative updates is negligible. 1