1 0.8 0.6 0.4 0.2

0

1

2

— STM manual

— STMXLC

34 5

of threads

6

7

8

Vacation

Speedup

1 0.8 0.6 0.4 0.2

0

1

2

3

456

of threads

7

8

 

ally cannot support transactions calling legacy codes that are not instrumented (for example, third-party libraries) without seriously limiting concurrency, such as by serializing transactions.

figure 4: single-threaded overhead of the stm algorithms.

fv

gv#

8

118.1

43.8

49. 2

7

evaluation

Here we use the following set of benchmarks:

˲ b+tree is an implementation of database indexing operations on a b-tree data structure for which the data is stored only on the tree leaves. This implementation uses coarse-grain transactions for every tree operation. Each b+ tree operation starts from the tree root and descends down to the leaves. A leaf update may trigger a structural modification to rebalance the tree. A rebalancing operation often involves recursive ascent over the child-parent edges. In the worst case, the rebalancing operation modifies the entire tree. Our workload inserts 2,048 items in a b+tree of order 20. For this code we have only a transactional version that is not manually instrumented, therefore experimental results are presented only in configurations where we can use our compiler to provide instrumentation;

˲ delaunay implements the Delaunay Mesh Refinement algorithm described in Kulkarni et al. ¹⁵ The code produces a guaranteed quality Delaunay mesh. This is a Delaunay triangulation with the additional constraint that no angle in the mesh be less than 30 degrees. The benchmark takes as input an unrefined Delaunay triangulation and produces a new triangulation that satisfies this constraint. In the TM implementation of the algorithm, multiple threads choose their elements from a work-queue and refine the cavities as separate transactions.

˲ genome, kmeans, and vacation are part of the STAMP benchmark suite¹⁹

runtime (norm. to sequential)

6

5

4

3

2

1

0

b+tree

delaunay

 

version 0.9.4. For a detailed description of these benchmarks see STAMP. ³⁰

Baseline Performance. In Figure 2 we present a performance comparison of three STMs: the IBM, ^{31, 34} Intel, ¹⁴ and Sun’s TL2⁷ STMs. The runs are on a quad-core, two-way hyperthreaded Intel Xeon 2.3GHz box running Linux Fedora Core 6. In these runs, we used the manually instrumented versions of the codes that aggressively minimize the number of barriers for the IBM and TL2 STMs. Since we do not have access to low-level APIs for the Intel STM, the curves for the Intel STM are from codes instrumented by its compiler, which incur additional barrier overheads due to compiler instrumentation. ³⁶ The graphs are scalability curves with respect to the serial, non-transactionalized version. Therefore a value of 1 on the y-axis represents performance equal to the serial version. The performance of these STMs is mostly on par, with the IBM STM showing better scalability on delaunay and TL2 obtaining better scalability on genome. However, the overall performance obtained is very low: on kmeans the IBM

kmeans

genome

vacation

 

STM barely attains single thread performance at 4 threads, while on vacation none of the STMs actually overcome the overhead of transactional memory even with 8 threads.

Compiler Instrumentation. The compiler is a necessary component of an STM-based programming environment that is to be adopted by mass programmers. Its basic role is to eliminate the need for programmers to manually instrument memory references to STM read- and write-barriers. While offering convenience, compiler instrumentation does add another layer of overheads to the STM system by introducing redundant barriers, often due to conservativeness of compiler analysis, as also observed in Yoo. ³⁶

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 un-instrumented versions of the codes and annotate transactional regions and functions using the language extensions provided by the compiler. ³¹