Abstract
This paper presents the notion of obstruction degree, a new metric for reasoning about the scalability of concurrent algorithms. Essentially, this simple metric gives an indication as to which of two concurrent algorithms is expected to scale better, as well as approximate the maximum number of processors up to which a concurrent algorithm is expected to scale. The scope of the metric is the arguably large class of concurrent algorithms obtained by augmenting sequential algorithms with locks (pessimistic), invalidation primitives (optimistic) or transactional memory. We illustrate the metric through various algorithms and we convey the accuracy of our scalability predictions through extensive experimental measures.
Introduction
In the era of multicore computing, the primary challenge for software developers is ensuring that applications scale effectively as the number of processor cores increases. Traditionally, determining the scalability of a concurrent algorithm required full implementation and rigorous benchmarking on specific hardware. This "trial and error" approach is both time-consuming and expensive.
Predicting scalability a priori—before implementation—is difficult because it usually requires modeling complex thread interleavings and hardware-specific contention. This paper introduces the obstruction degree, a hardware-independent metric that simplifies this complexity into a single-process analysis, allowing developers to estimate the "saturation point" where adding more cores no longer improves performance.
The Obstruction Degree Metric
The core innovation is the Obstruction Degree ($C(H)$). Instead of analyzing how multiple threads interact, the metric focuses on a single process's "history" ($H$) of acquiring and releasing protection elements, such as locks or transactional memory locations.
The calculation is governed by three fundamental rules:
- OD1: An empty operation has an obstruction degree of 0.
- OD2: Each time a process acquires a new protection element, the number of elements it already holds is added to the total degree.
- OD3: Releasing an element does not change the current degree.
This metric effectively measures the "area of obstruction" an operation creates. By drawing a parallel to the Birthday Paradox—where the probability of conflict increases non-linearly as more participants are added—the authors derive a formula for the Scalability Limit ($k_{max}$). This limit represents the point where the probability of two threads conflicting becomes high enough to stall performance.
Key Insights: Quadratic vs. Linear Scaling
The obstruction degree allows for a high-level classification of algorithms:
- Quadratic Algorithms: In protocols like two-phase locking or coarse-grained locking, the obstruction degree grows with the square of the number of objects accessed ($O(m^2)$). These typically hit a scalability wall very early.
- Linear Algorithms: Protocols like hand-over-hand (fine-grained) locking exhibit an obstruction degree that grows linearly ($O(m)$), making them significantly more scalable.
The power of this metric lies in its Single-Process Simplicity. By observing how one thread behaves in isolation, we can infer its "footprint" and predict how it will collide with others in a multi-threaded environment.
Experimental Validation
The authors validated the metric across several benchmarks:
- Concurrent Linked Lists: The metric correctly predicted that "Lazy" and "Lock-free" implementations would outperform "Coarse-grained" locking, which failed to scale beyond a single processor.
- Synthetic Benchmarks: For specific algorithmic patterns, the metric accurately predicted saturation points (e.g., predicting a limit of 32 processors for a specific "Algorithm C" where experimental data showed diminishing returns after that point).
- STAMP Benchmark Suite: In the complex labyrinth benchmark, the metric predicted a ceiling of approximately 30 processors, which aligned with the speedup trajectories observed on 16-core systems.
Limitations and Future Work
While powerful, the basic obstruction degree assumes Uniform Access, meaning every shared object is equally likely to be accessed. In practice, "hotspots" can lead to earlier-than-predicted contention. Furthermore, the metric assumes Disjoint-Access Parallelism, where operations on different objects do not interfere at the hardware level (e.g., avoiding false sharing).
Future refinements may involve weighting protection elements based on access frequency to better model non-uniform workloads and specific hardware bottlenecks.
- Summary based on "Obstruction degree: measuring concurrency in shared memory systems" by Guerraoui et al.
Summary updated