Source-linked AI summary
Quantifying performance bottlenecks of stencil computations using the Execution-Cache-Memory model
Holger Stengel, Jan Treibig, Georg Hager, Gerhard Wellein
TL;DR
Stencil performance depends on cache-dependent data traffic, including whether successive rows fit in a cache. The paper refines the ECM model and applies it to stencil algorithms, finding that in-cache transfers constrain long-range stencil bandwidth saturation; its predictions assume transfers are not latency-bound.
Problem
Predicting stencil performance requires accounting for cache-dependent traffic, including whether three successive array rows fit in a cache.
Source: §4.1 · p. 5Method
The paper refines ECM’s overlap rules and applies the model to three stencil algorithms on an Intel SandyBridge processor.
Source: §7 · p. 9Results
In-cache contributions prevent the 3D long-range stencil from saturating memory bandwidth at minimum in-memory code balance, while temporal blocking boosts full-chip performance.
Source: §7 · p. 10Takeaways & Limitations
Layer-condition analysis quantifies when spatial blocking establishes cache conditions, while temporal blocking’s benefit differs between single-core and full-chip performance.
Source: §7 · pp. 9–10ECM can overpredict latency-bound transfers when prefetching cannot hide latency, and the authors do not know how to incorporate non-temporal-store costs.
Source: §7 · p. 10
Abstract
from arXiv · showhide
Stencil algorithms on regular lattices appear in many fields of computational science, and much effort has been put into optimized implementations. Such activities are usually not guided by performance models that provide estimates of expected speedup. Understanding the performance properties and bottlenecks by performance modeling enables a clear view on promising optimization opportunities. In this work we refine the recently developed Execution-Cache-Memory (ECM) model and use it to quantify the performance bottlenecks of stencil algorithms on a contemporary Intel processor. This includes applying the model to arrive at single-core performance and scalability predictions for typical corner case stencil loop kernels. Guided by the ECM model we accurately quantify the significance of "layer conditions," which are required to estimate the data traffic through the memory hierarchy, and study the impact of typical optimization approaches such as spatial blocking, strength reduction, and temporal blocking for their expected benefits. We also compare the ECM model to the widely known Roofline model.
1. INTRODUCTION AND RELATED WORK
Stencil codes are iterative, low-intensity workloads that attract loop optimization, while performance models help estimate performance and identify bottlenecks. The paper refines ECM and applies it to stencil patterns, distinguishing its broader hierarchy view from Roofline’s bandwidth-and-peak focus.
1. INTRODUCTION AND RELATED WORK
- Stencil computations on regular lattices are low-intensity, iterative workloads targeted by cache blocking, SIMD, and shared-memory parallelization.The review by Datta et al. surveys stencil optimizations.Source: §1 · p. 1
- Performance modeling includes black-box statistical approaches and white-box first-principles models; Roofline estimates loop limits but omits bottlenecks beyond bandwidth and peak performance.The paper notes that long-range stencils can have significant in-cache transfer costs and no single dominant bottleneck.Source: §1 · p. 1
- ECM extends Roofline by accounting for contributions across the memory hierarchy and predicts single-core performance and scaling.The paper refines ECM’s overlap rules and introduces a notation for describing the model.Source: §1 · p. 1
- The paper moves from test-machine description and streaming-kernel model refinement to increasingly complex stencil applications and optimization analysis.It concludes with a summary in Sect. 7.Source: §1 · p. 1
2. EXPERIMENTAL TESTBED
Measurements primarily use a two-socket, eight-core SandyBridge-EP server, with an Ivy Bridge CPU used for comparison in Sect. 5. The testbed description reports core, cache, and memory capabilities alongside the code-compilation setup.
2. EXPERIMENTAL TESTBED
- The standard test machine is a two-socket server with eight-core SandyBridge-EP CPUs; Sect. 5 also uses a 3.0 GHz Intel Ivy Bridge CPU for comparison.Table 1 presents specifications for one socket.Source: §2 · pp. 1–2, Table 1 · p. 2
- Each SNB core supports SSE and AVX, and the four DDR3-1600 memory channels per socket connect the processor to memory.The core sustains one fullwidth AVX load and one half-width AVX store per cycle; the L2 and L3 interfaces each sustain 256 bits per cycle, half-duplex.Source: §2 · p. 2
- Stencil codes were compiled with Intel C Compiler 13.1.3, and the clock frequency was fixed at 2.7 GHz.Vector-summation measurements used LIKWID-bench.Source: §2 · p. 2
3. THE ECM PERFORMANCE MODEL
The ECM model combines processor-core execution costs with data-transfer costs through the memory hierarchy to predict single-core performance and chip-level scaling. Its predictions depend on explicit assumptions about instruction execution and overlap, and can differ from Roofline estimates when execution and transfer costs are comparable.
3.1 Model input, construction, and assumptions
- The ECM model estimates cycles for a cache-line-sized unit of work by combining core execution time with transfers from the data's initial location to L1.For a streaming kernel with double-precision data and stride-one accesses, one 64-B cache line corresponds to eight iterations.Source: §3 · p. 2, §3.1 · p. 2, §3.1.3 · p. 3
3.1.1 In-core execution time
- In-core time is determined by the execution unit taking the most cycles, subject to the processor's maximum instruction throughput.For AVX DAXPY, load and store throughput is the bottleneck, with four cycles predicted for eight iterations when the loop is sufficiently unrolled.Source: §3.1.1 · p. 2
3.1.2 Data transfers through the memory hierarchy
- Transfer-time estimates assume perfect streaming, and DAXPY requires three cache-line transfers between each pair of adjacent levels because the cache hierarchy is inclusive.The resulting estimates are six cycles between cache levels and 13 cycles between memory and L3 at 40 GB/s and 2.7 GHz.Source: §3.1.2 · pp. 2–3
3.1.3 Single-core prediction and examples
- The model assumes independent out-of-order instruction scheduling, no overlap between loads and transfers, and serialized transfers through the hierarchy.Other instructions and pipeline bubbles overlap with transfers; store-bound kernels can therefore show substantial overlap.Source: §3.1.3 · p. 3
- 4, 10, 16, and 29 cycles/CL are predicted for DAXPY data in L1, L2, L3, and memory, respectively, using AVX.The model attributes this example's execution time primarily to data transfers, even when data comes from L1.Source: Figure 2 · p. 3, §3.1.3 · p. 3
3.1.4 Conclusions from the ECM model
- For single-thread execution, theoretical bandwidth limits are unreachable at every memory-hierarchy level except L1; multiple threads can make bandwidth saturation possible.At nominal clock speed, the scalar summation prediction is 2.7 Gflop/s for cache-resident data and 1.8 Gflop/s for memory data.Source: §3.1.4 · p. 4
3.1.5 Chip-level scaling and comparison with Roofline
- Chip-level scaling assumes single-core performance grows linearly with core count until memory bandwidth becomes the bottleneck; the ECM example predicts saturation at three cores for 2.1 Gflop/s, versus six for naive code at 0.9 Gflop/s.At 1.6 GHz, the naive code would need ten cores to saturate, but the CPU has only eight.Source: §3.1.5 · p. 4
- Roofline and ECM predictions coincide when core execution dominates transfers or when the kernel's single-core behavior matches the streaming benchmark; Roofline is inaccurate when both costs are comparable and exceed benchmark costs.The paper gives the divide triad, dominated by divides or square roots, as an example of the first case.Source: §3.1.5 · p. 4
4. CASE STUDY: 5-POINT STENCIL
The 2D Jacobi case study uses the ECM model to connect layer conditions with data traffic and performance, then evaluates spatial blocking and multicore scaling. Its results show that cache-level effects and prefetch behavior qualify the benefits of blocking.
4.1 Basic analysis
- The 8-LUP AVX work unit is core-limited by the load pipeline, while three rows fitting in cache determine whether traffic is 24B/LUP or 40B/LUP.The layer condition assumes half the cache is available for layers; when it is met, only one of the stencil’s five data streams misses at that cache level.Source: §4.1 · p. 5
4.2 Single-core performance vs. problem size
- ECM predictions agree with measurements within 10% in all three layer-condition phases (L2, L3, and none), while measured memory code balance remains within 5% of its predicted value despite performance fluctuations.Source: §4.2 · p. 5
4.3 Spatial blocking optimization
- Spatial blocking can satisfy a layer condition at a higher cache level and lower code balance, but Roofline does not distinguish blocking strategies.With 24B/LUP already the minimum balance across cache levels, further spatial blocking cannot improve single-core performance.Source: §4.3 · pp. 5–6
- Small inner blocks trigger excess prefetch traffic because fetched lines are evicted before reuse; an outer block size near 300 alleviates the problem.The reported prefetch distance is about 33 cache lines, but the authors caution that it may not generalize because the prefetch mechanism is unknown.Source: §4.3 · p. 6, Figure 5 · p. 6
4.4 Multi-core scaling
- Well below 10% deviation, ECM captures multicore saturation behavior, while adapting L3 block size restores the expected 24B/LUP saturation after fixed-size blocking degrades beyond four cores.The adaptive block keeps three layers per thread in the shared cache; earlier saturation can also free cores for low-power mode or asynchronous communication.Source: Figure 6 · p. 7, §4.4 · p. 7
- At the minimum 24B/LUP balance, L1, L2, and L3 blocking show similar saturation, while earlier saturation can free cores for low-power operation or communication.The model predicts saturation at three cores for L1/L2 blocking and four for L3 blocking, though measured behavior is similar.Source: §4.4 · p. 7
- Non-temporal stores could reduce in-memory balance from 24B/LUP to 16B/LUP, but their throughput is not yet captured by the ECM model.The authors state that Intel implementations do not fit a simple throughput assumption.Source: §4.4 · p. 7
5. CASE STUDY: UXX STENCIL
The uxx case study uses the ECM model to analyze a stencil with an inner-loop divide, cache-layer requirements, and spatial and temporal blocking. It shows that transfer costs can outweigh the divide and that temporal blocking’s strongest projected benefit is at socket scale.
5. CASE STUDY: UXX STENCIL
- A divide operation in the inner loop motivates the case study because it might appear to be an obvious strength-reduction target.The paper cautions that modeling indicates that eliminating it will not necessarily yield a performance gain.Source: §5 · p. 7, §5.1 · p. 8
5.1 Analysis and ECM model
- 104cy per unit of work is predicted in main memory for SP, DP, and noDIV, implying a factor-of-two performance difference between SP and DP.The model predicts saturation at four cores for all versions.Source: Table 4 · p. 8, §5.1 · p. 8
- The layer condition depends on retaining two d1 layers and four xz layers in cache; with L3 blocking, memory code balance is 24B/LUP in SP and 48B/LUP in DP.At relevant problem sizes, the analysis ignores row conditions because they are automatically fulfilled in L1.Source: §5.1 · p. 8
- Removing the divide is not expected to improve performance, despite its low throughput; the predictions are confirmed by SNB measurements.On Ivy Bridge, the divide has no impact when data does not fit in L1.Source: §5.1 · p. 8
5.2 Optimization opportunities
- Optimal L3 temporal blocking is projected to speed up a single core by 24% in DP or 33% in SP, but its greater potential is scalable socket performance.The paper gives an upper limit above 2000MLUP/s even for DP with the divide retained.Source: §5.2 · pp. 8–9
6. CASE STUDY: 3D LONG-RANGE STENCIL
The long-range stencil’s radius-four accesses put pressure on cache capacity, so the case study examines layer conditions, blocking, and the limits of Roofline estimates. ECM analysis indicates that in-cache work remains important even when blocking improves scaling.
6. CASE STUDY: 3D LONG-RANGE STENCIL
- The case study uses a single-precision long-range stencil with radius four in each dimension, creating substantial cache-layer pressure.Only V is relevant for layer conditions; U and ROC are accessed linearly without potential for cache reuse.Source: §6 · p. 9
6.1 Analysis and ECM model
- A radius-four stencil requires nine layers in cache; when the layer condition is met only in L3, just 17/127 cycles (about 13%) are attributed to L3-to-memory transfer.In that case the model predicts 127 cycles and the code barely saturates at eight cores.Source: §6.1 · p. 9
- At two cores and above, blocking is required; the blocked code scales well almost to the full socket, as ECM predicts.At the selected problem size, the layer condition is fulfilled without blocking for one thread, so single-core performance and prediction match in both cases.Source: Figure 8 · p. 9, §6.1 · p. 9
- The Roofline model is much too optimistic because it treats the loop as core-bound until memory bandwidth saturates, while other transfer contributions remain significant.In the described case, bandwidth saturation occurs at four cores.Source: §6.1 · p. 9
6.2 Optimization opportunities
- Temporal blocking alone is predicted to have only a minor effect on single-core and full-socket performance after spatial blocking has nearly removed the memory bottleneck.If all core contributions including TnOL were reduced by 50%, the model predicts 33% single-core acceleration and saturation at six cores.Source: §6.2 · p. 9
7. SUMMARY
The paper refines the ECM model and applies it to stencil kernels to quantify runtime contributions, bottlenecks, and optimization opportunities. It also identifies conditions where its predictions are limited.
7. SUMMARY
- Applying ECM to three stencil algorithms on Sandy Bridge quantifies spatial-blocking effects and shows that divide elimination can fail to improve performance when transfer times dominate.For the long-range stencil, in-cache runtime must be reduced before advanced techniques such as temporal blocking are applied.Source: §7 · pp. 9–10
- ECM can reveal bottlenecks and optimization opportunities, while Roofline predictions can fail to match ECM when their overlapping assumption misses transfer contributions.The paper says ECM can mostly be set up with pencil and paper; a simpler high-level-description tool was still in development.Source: §7 · p. 10
- ECM is over-optimistic when memory-hierarchy transfers are latency-bound, such as pointer chasing or cases where prefetching cannot hide latency.The authors also report uncertainty about incorporating non-temporal-store costs and over-optimism for some tight loops with low Tcore on high-frequency memory interfaces.Source: §7 · p. 10