transactional
memory
why is it only a research toy?

environment is that we want to capture the overheads at the instruction level and eliminate any other nondeterminism introduced by real hardware. The simulator eliminates all other bookkeeping operations introduced by instrumentation and provides an accurate breakdown of the STM overheads.

We study the performance of two STM algorithms: one that fully validates (fv) the read set after each transactional read and one that uses a global version number (gv#) to avoid the full validation, while maintaining the correctness of the operations. The fv algorithm provides more concurrency at a much higher price. The gv# is deemed as one of the best tradeoffs for STM implementations.

Figure 4 presents the single-threaded overhead of these algorithms over sequential runs, illustrating again the substantial slowdowns that the algorithms induce. Figure 5 breaks down these overheads into the various STM components. For both algorithms, the overhead of transactional reads dominates because of the frequency of read operations relative to all other operations. The effectiveness of the global version number in reducing overheads is shown in the lower read overhead of gv#.

Figure 3 provides another baseline: the overhead of compiler instrumentation. The performance is measured on a 16-way POWER5 running AIX 5. 3. For the STMXLC curve, we use the uninstrumented versions of the codes and annotate transactional regions and functions using the language extensions provided by the compiler. ³⁸

Compiler over-instrumentation is more pronounced in traditional, unmanaged languages such as C and C++, where a typical compiler instrumentation without interprocedural analysis may end up instrumenting every memory reference in the transactional region (except for stack accesses). For example, our compiler instrumentation more than doubled the number of dynamic read barriers in delaunay, genome, and kmeans. Interprocedural analysis can help improve the tightness of compiler _{118.1 43. 8} instrumentation for some ⁸ cases but is generally ^fv _{7 gv#} limited by the accuracy of global analysis. ₆

runtime (norm. to sequential)

STM operations performance. Given this baseline, 5 we now analyze in detail which operations in the ⁴ STM cause the overhead.

3

For this purpose, we use a cycle-accurate simulator of ₂ the PowerPC architecture that provides hooks for 1 instrumentation. The STM operations and subop- ⁰ _b+tree erations are instrumented with these simulator hooks. The reason for this

FIGURE

4Single-Threaded Overhead of the STM Algorithms

49. 2

delaunay

kmeans

genome