The Fallacy of Independent Ceilings: Characterizing Coupled Load-Branch Stall Interaction

Abstract

Branch mispredictions and data-cache misses are usually evaluated as separate bottlenecks: studies report perfect-branch or perfect-cache speedups as isolated upper bounds and often treat their product as the joint ceiling. In irregular workloads, however, hard-to-predict branches and cache-missing loads often occur in the same hot loops. Removing one penalty can expose the other: faster memory reaches mispredicted branches sooner, while better branch prediction leaves more long-latency loads in the out-of-order window. We call this interaction symbiotic stall latency (SSL). This paper quantifies when isolated ceilings fail using joint speedup synergy (JSS), the observed joint perfect-branch/perfect-cache speedup divided by the product of the isolated speedups. Values above one mean independent-ceiling analysis understates attainable gain. Across 53 simulated workloads, 70% show measurable coupling (JSS > 1), though many are near unity, especially in lower-pressure cases. With a conservative threshold, 40% exceed the independence product by more than 6%, and kernels with SSO > 20 show JSS from 1.23 to 3.29. We introduce symbiotic stall opportunity (SSO), a lightweight MPKI-based screen for workloads that merit full joint simulation. We map high-SSO workloads to four recurring software patterns: neighbor access, hash lookup, linked-structure traversal, and data-dependent modification. We connect SSL to reorder-buffer occupancy, squash rate, and commit starvation under isolated perfect modes. The resulting methodology is simple: use SSO to screen, JSS to validate, and report conditional branch-after-cache and cache-after-branch gains when evaluating branch predictors, prefetchers, caches, or coupled branch/memory mechanisms. Our contribution is a measurement framework showing when isolated perfect modes are adequate and when they understate joint performance headroom.