Existing software transactional memory (STM) implementations
often exhibit poor scalability, usually because of nonscalable mechanisms
for read sharing, transactional consistency, and privatization;
some STMs also have nonscalable centralized commit mechanisms.
We describe novel techniques to eliminate bottlenecks from
all of these mechanisms, and present SkySTM, which employs
these techniques. SkySTM is the first STM that supports privatization
and scales on modern multicore multiprocessors with hundreds
of hardware threads on multiple chips.
A central theme in this work is avoiding frequent updates to
centralized metadata, especially for multi-chip systems, in which
the cost of accessing centralized metadata increases dramatically.
A key mechanism we use to do so is a scalable nonzero indicator
(SNZI), which was designed for this purpose. A secondary contribution
of the paper is a new and simplified SNZI algorithm.
Our scalable privatization mechanism imposes only about 4%
overhead in low-contention experiments; when contention is higher,
the overhead still reaches only 35% with over 250 threads. In
contrast, prior approaches have been reported as imposing over
100% overhead in some cases, even with only 8 threads.