PASCAL: A Phase-Aware Shared-Cache Model for Parallel Scans Zhongchun Zhou
Chengtao Lai
Songtao Mao
[email protected] The Hong Kong University of Science and Technology Kowloon, Hong Kong
[email protected] The Hong Kong University of Science and Technology Kowloon, Hong Kong
[email protected] Johns Hopkins University Baltimore, MD, USA
arXiv:2609.10515v1 [cs.PF] 9 Sep 2026
Abstract In modern AI Accelerators and GPGPUs, many concurrent cores repeatedly access the same shared data. This pattern occurs in attention, where different query tiles share the same K/V block, GEMM, where every tile in a row reads the same panel, and many other operators. We name this pattern parallel scan. Due to a significant amount of data reuse in this pattern, the cache is expected to capture as much data reuse as possible and largely reduce requests sent to the main memory for both performance and energy consumption concerns. However, in reality, because of the intrinsic asynchrony of multi-cores, the actual cache miss rate and DRAM traffic can be much higher compared to ideal cases. In this paper, we propose PASCAL, a shared-cache model for parallel scans. It is aware of the dynamic feature of progress divergence across multicores, correlate the divergence with the combination of different factors such as occupancy, and predicts the cache miss rate before execution. Because prediction needs no target trace, timing, or counters, PASCAL supports design-space exploration at scales where cycle-accurate simulation is impractical, and its policy-independent bound states how much traffic no replacement policy can avoid. A MAPE of 13.84% is achieved in a 60-configuration dataset with various software pipeline depths, occupancies, and memory access data paths on an NVIDIA GB10 GPU, against 44.79% for physical-wave TileSight and 54.16% for exact symbolic SDCM.
CCS Concepts • Computer systems organization → Architectures; • Computing methodologies → Machine learning; Modeling and simulation.
Keywords cache, GPGPU, miss-rate prediction, reuse distance, analytical model
1
Introduction
Accurate performance prediction for deep learning applications can benefit both operator developers and hardware architects. While many components inside an AI chip are deterministic—both the latency and throughput are fixed, the prediction of cache miss rate is still a hard problem because of the cache’s dynamic behavior and the complexity of the replacement policy. Although some designs replace the cache with SPM, a shared cache remains a common choice in NVIDIA’s GPU and HUAWEI’s Ascend 910 series [20]. Excessive cache-DRAM traffic caused by a multi-core processor’s intrinsic asynchrony compared to theoretical computation is also observed in attention kernels [28]. However, current analytical models for deep learning, such as TileSight [22] and LCM [19], calculate the reuse-distance profile with a static assumption. This can underestimate the cache miss rate significantly.
We make the following contributions: • For the TTL cache, we specialize the working set theory for parallel scan—a typical memory access pattern in AI workloads. We derive a closed-form formula to calculate exact miss counts. • We extend the theory beyond the TTL cache. For the LRU cache, a bound on its miss-rate deviation from the TTL cache is given. Additionally, a fractional residency-budget bound applies to every demand-paging policy, including offline Belady. • Progress divergence across multiple processor cores is observed in our experiments, which can lead to an increase of cache miss rate and DRAM traffic by multiple times. We find that prefetch depth, compute work, occupancy, and duration all influence the phenomenon in different degrees; neither an occupancy-only explanation nor a universal pressure cutoff is supported. • We propose a pipeline for cache miss rate prediction. By considering the dynamic features of progress divergence, it achieves a MAPE of 13.84% and outperforms mainstream baselines.
2 Background and Motivation 2.1 Existing Cache Models Existing cache predictors obtain locality information in three main ways. First, frequency-based stochastic models such as Che–IRM infer a steady-state miss rate from request laws and cache capacity [9, 15, 17]. They cannot distinguish our progress-aligned and divergent executions: every worker has the same marginal address frequency, while the number of fills per round can range from one to 𝑀 because requests from different workers may share a fill. Second, working-set, footprint, and stack-distance methods characterize an observed access order [11, 12, 21, 27]; SDCM further maps reuse distance to hit probability under an associativity and random-mapping model [8]. Statistical sampling can reduce the measurement cost [5, 14], but some source must still provide the target execution’s interleaving or reuse profile. Third, static program analyses show that reuse profiles can sometimes be inferred before execution [13, 25]. For freely progressing GPU workers, however, the logical per-worker order does not determine the cross-worker order: occupancy, generated memory instructions, prefetch depth, and intervening computation change relative progress during execution. Tay and Zou developed a parameterized page-fault equation that relates memory size to page faults through a conjectured invariant capturing the interaction between reference behavior and replacement policy [26]. PASCAL addresses a complementary question: how relative progress among concurrent scans affects shared-cache traffic at a given capacity.
Zhou et al.
2.2
Motivation
This leaves the prediction problem studied here. We know what each worker scans, but neither frequency nor program order determines how much cross-worker sharing survives over a finite run. We therefore first solve the fixed-phase geometry exactly, then use one reusable machine calibration and static target-code features to predict the accumulated traffic of an unseen dynamic configuration, without profiling that target.
3 Static Geometry and Policy Bounds 3.1 Model Let Z𝑁 = {0, . . . , 𝑁 − 1} index the data blocks (e.g. tiles) of one memory access stream. The cache capacity 𝐶 is therefore measured in blocks. There are 𝑀 concurrent streams (e.g. GPU thread blocks), and stream 𝑚 carries a phase 𝑠𝑚 ∈ Z𝑁 . Time advances in rounds; in round 𝑘 stream 𝑚 accesses block: 𝑎𝑚 (𝑘) = (𝑘 + 𝑠𝑚 ) mod 𝑁 .
(1)
A stream with a larger phase is ahead: if 𝑔 = (𝑠 𝑗 − 𝑠𝑚 ) mod 𝑁 is small and positive, stream 𝑗 touched stream 𝑚’s current block 𝑔 rounds ago, so 𝑗 is a leader of 𝑚 at lag 𝑔. The global trace is the round-by-round interleaving of the 𝑀 streams; within a round we fix an arbitrary but consistent order and index streams accordingly. Let 𝑦1 < · · · < 𝑦𝐷 be the distinct phase values, where multiple streams may share a phase. Set 𝑦𝐷+1 = 𝑦1 + 𝑁 , and define the cyclic gap vector 𝒈 = (𝑔1, . . . , 𝑔𝐷 ) by 𝑔𝑖 = 𝑦𝑖+1 − 𝑦𝑖 ,
1 ≤ 𝑖 ≤ 𝐷. Í𝐷 These gaps are positive and satisfy 𝑖=1 𝑔𝑖 = 𝑁 . The definition includes the single-phase case, for which 𝑔1 = 𝑁 .
3.2
An exact round-window TTL law
The footprint 𝑈 (𝑡) is the number of distinct blocks in any 𝑡 consecutive complete rounds. It is independent of the starting round, because advancing all phases merely rotates the address ring. Lemma 1 (Cyclic-gap footprint). For every integer 𝑡 ≥ 0, 𝑈 (𝑡) =
𝐷 ∑︁
min(𝑔𝑖 , 𝑡),
Here 0 ≤ 𝑗 < 𝐷, 𝑔 (0) = 0, and an empty sum is zero. Equivalently, 𝑇 ∗ is the largest integer round window whose footprint fits within the boundary capacity: 𝑈 (𝑇 ∗ ) ≤ 𝐶 < 𝑈 (𝑇 ∗ + 1). Sorting and a prefix scan cost 𝑂 (𝑀 log 𝑀), independent of trace length. We use a precisely slotted TTL abstraction, the object Denning called the working-set policy [11] and the caching literature calls a TTL cache [6]: at the start of a round, the cache remembers the preceding 𝑇 complete rounds; current-round duplicates share one lookup/fill. At the next boundary it retains the latest 𝑇 complete rounds. Thus boundary occupancy is 𝑈 (𝑇 ). Temporary currentround fills are not part of this boundary capacity contract. A requestlevel TTL may need additional within-round storage; it is not identified with a strict capacity-𝐶 hardware cache. Theorem 2 (Exact slotted miss count). In steady state, the 𝑇 ∗ -window cache has boundary occupancy at most 𝐶 and exactly 𝐹𝐶 (𝒈) = 𝐾 (𝑇 ∗ ) = #{𝑖 : 𝑔𝑖 > 𝑇 ∗ },
𝜌 TTL = 𝐹𝐶 (𝒈)/𝑀
misses per round and misses per request, respectively. Proof. At each distinct phase, only the first current-round request can miss. Its previous occurrence was requested by the next phase 𝑔𝑖 rounds earlier (or 𝑁 rounds earlier for a single phase). It is remembered exactly when 𝑔𝑖 ≤ 𝑇 ∗ . Feasibility follows from 𝑈 (𝑇 ∗ ) ≤ 𝐶. □ Equation (4) is a specialization of the classical working-set/miss relation, not a new general footprint identity. Since 𝐶 < 𝑁 , at least one gap exceeds 𝑇 ∗ . Hence the best TTL count is 𝐾 = 1, attained by coincident phases and also by sufficiently tight noncoincident groups. If all gaps exceed 𝐶/𝐷, then 𝜃 = 𝐶/𝐷 and 𝐾 = 𝐷.
3.3
LRU and symbolic reuse distance
Theorem 3 (A one-round LRU certificate). Assume 𝐷 ≤ 𝐶, for fully associative LRU in steady state, 𝐾 (𝑇 ∗ + 1) ≤ 𝐾LRU ≤ 𝐾 (𝑇 ∗ − 1).
𝐾 (𝑡) := 𝑈 (𝑡 + 1) − 𝑈 (𝑡) = #{𝑖 : 𝑔𝑖 > 𝑡 }.
𝑖=1
(4)
Only phases with preceding reuse lag 𝑔𝑖 with the TTL classification.
(5)
∈ {𝑇 ∗,𝑇 ∗ + 1} can disagree
(2) Proof. For 0 ≤ 𝑡 < 𝑁 , partition the address ring into the territories [𝑦𝑖 , 𝑦𝑖+1 ). Within territory 𝑖, the nearest preceding phase in the scan direction is 𝑦𝑖 . Hence a block is covered by a length-𝑡 scan segment exactly when it lies among the first min(𝑔𝑖 , 𝑡) blocks of that territory. For 𝑡 ≥ 𝑁 , every block is covered and the same formula equals 𝑁 . Summing over the territories gives 𝑈 (𝑡); taking the finite difference gives 𝐾 (𝑡). □
Proof. Let RD count distinct blocks strictly between two successive references to the same block, separated by 𝑔 > 0 rounds. The intervening sequence contains 𝑔 − 1 complete rounds and is contained in 𝑔 + 1 rounds including the referenced block. Therefore 𝑈 (𝑔 − 1) ≤ RD ≤ 𝑈 (𝑔 + 1) − 1. LRU hits iff RD < 𝐶. A lag at most 𝑇 ∗ − 1 forces a hit, and a lag at least 𝑇 ∗ + 2 forces a miss. Current-round duplicates hit because at most 𝐷 − 1 < 𝐶 distinct blocks intervene. □
Í Extend 𝑈 to real 𝑡 ≥ 0 by 𝑈 (𝑡) = 𝑖 min(𝑔𝑖 , 𝑡). Since 𝐶 < 𝑁 , the equation 𝑈 (𝜃 ) = 𝐶 has a unique solution. Sorting the gaps 𝑔 (1) ≤ · · · ≤ 𝑔 (𝐷 ) gives Í𝑗 𝐶 − 𝑖=1 𝑔 (𝑖 ) 𝜃= , 𝑔 ( 𝑗 ) ≤ 𝜃 < 𝑔 ( 𝑗+1) , 𝑇 ∗ = ⌊𝜃 ⌋. (3) 𝐷−𝑗
When its interval collapses, the inexpensive TTL formula also gives exact fully associative LRU. Otherwise one can compute each worker’s exact RD by merging the at-most-𝑀 cyclic address intervals between its previous and current request, in 𝑂 (𝑀 2 log 𝑀) total time. This symbolic alternative needs no generated or measured address trace.
PASCAL: A Phase-Aware Shared-Cache Model for Parallel Scans
(b) Water-Filling Root 𝑇 ∗ (Theorems 2 & 3)
(a) Address Ring Z𝑁 (Lemma 1) ≤ 𝑦𝑖 + 𝑡 − 1
𝐾 (𝑇 ∗ ) = 2 Misses
𝑦𝑖 𝑔𝑖
𝑈 (𝑇 ∗ ) ≤ 𝐶
Arc 𝐴 𝑦𝑖 −1 ,𝑡
Scan (+1)
min(𝑔𝑖 , 𝑡 )
𝑦𝑖+1 𝑦𝑖 −1 Z𝑁
Blocks / Window 𝑡
𝑔𝑖 −1
Uncached gap > 𝑇 ∗ LRU ambiguity band
Miss Miss
𝑇 ∗ + 1 (Miss)
𝜃 = 𝑇 ∗ = ⌊𝜃 ⌋ 𝑇 ∗ − 1 (Hit)
𝑔𝑖+1
Sorted Gaps 𝑔 (𝑖 ) 𝑦𝑖+2
𝑔 (1)
𝑔 (2)
𝑔 (3)
𝑔 (4)
𝑔 (5)
Figure 1: Geometric address ring and discrete water-filling model for parallel shared scans. (a) Circular territory decomposition (Lemma 1): The address ring Z𝑁 is partitioned into 𝐷 half-open intervals [𝑦𝑖 , 𝑦𝑖+1 ) of length 𝑔𝑖 . Worker 𝑦𝑖 sweeps min(𝑔𝑖 , 𝑡) blocks (hatched). A preceding worker 𝑦𝑖 −1 sweeping 𝑡 blocks reaches at most 𝑦𝑖 −1 + 𝑡 ≤ 𝑦𝑖 + 𝑡 − 1, strictly shadowed by 𝑦𝑖 ’s arc, proving Í𝐷 that cross-worker overlaps decouple and 𝑈 (𝑡) = 𝑖=1 min(𝑔𝑖 , 𝑡) holds without inclusion-exclusion. (b) Water-filling root and miss determination (Theorems 2 & 3): Gaps are sorted 𝑔 (1) ≤ · · · ≤ 𝑔 (𝐷 ) and filled to capacity 𝐶, yielding waterline 𝜃 and characteristic window 𝑇 ∗ = ⌊𝜃 ⌋. Hatched areas beneath 𝑇 ∗ represent resident blocks satisfying 𝑈 (𝑇 ∗ ) ≤ 𝐶. Gaps protruding above 𝑇 ∗ (shaded gray) number exactly 𝐾 (𝑇 ∗ ) = #{𝑖 : 𝑔𝑖 > 𝑇 ∗ }, each incurring one miss per round under the slotted TTL model. Shaded horizontal band [𝑇 ∗ − 1,𝑇 ∗ + 1] marks the tight boundary outside which fully associative LRU under the stated trace model exactly matches slotted TTL. For an 𝐴-way cache of 𝐵 lines, SDCM’s conditional mapping is 𝐴−1 ∑︁ 𝑅 𝑃 (hit | 𝑅) = (𝐴/𝐵)𝑎 (1 − 𝐴/𝐵) 𝑅−𝑎 . (6) 𝑎 𝑎=0 Its fully associative limit is 1{𝑅 < 𝐵}. Our static SDCM–FA baseline applies this limit to exact symbolic distances, with 𝐵 = 𝐶 in abstract block units. It is not a fitted GB10 set-associativity model or a claim about every SDCM instantiation.
3.4
A residency budget for every policy
An arbitrary policy cannot be predicted from its name alone, but its best possible traffic can be bounded. Preserve within-round order by placing worker 𝑚’s round-𝑟 request at time 𝑟 + 𝑚/𝑀. Let 𝛿𝑚 > 0 be its elapsed time since the preceding request to the same block. These 𝑀 intervals are computed from the phases: choose the latest earlier time −𝑔𝑀 + 𝑗 among workers 𝑗, where 𝑔 = (𝑠 𝑗 − 𝑠𝑚 ) mod 𝑁 and a zero lag is replaced by 𝑁 if 𝑗 ≥ 𝑚. Then Í 𝛿𝑚 = (𝑚 − max 𝑗 (−𝑔𝑀 + 𝑗))/𝑀 and 𝑚 𝛿𝑚 = 𝑁 . Theorem 4 (Policy-independent residency bound). For any capacity-𝐶 demand-paging policy without prefetching, including offline Belady [4], the long-run miss count satisfies ∑︁ 𝐾policy ≥ 𝑀 − 𝑉 (𝐶), 𝑉 (𝐶) = max 𝑥𝑚 . (7) Í 0≤𝑥𝑚 ≤1 𝑚 𝑚 𝛿𝑚 𝑥𝑚 ≤𝐶
For an 𝐻 -round finite trace with arbitrary initial cache, the lower bound has an additive correction of at most 𝑁 /𝐻 . Proof. A hit with its previous reference inside the horizon requires uninterrupted residency throughout that inter-reference interval: demand paging cannot reload an unrequested, evicted block. Intervals of the same block have disjoint interiors, and at most
𝐶 blocks are resident at a time. Thus their total length is at most 𝐶𝐻 . If 𝐻𝑥𝑚 counts such hits of worker type 𝑚, then 𝑥𝑚 ≤ 1 and Í 𝑚 𝛿𝑚 𝑥𝑚 ≤ 𝐶. At most 𝑁 additional hits can have their preceding reference outside the horizon. Divide by 𝐻 and let 𝐻 increase. □ The program is fractional knapsack: sort 𝛿𝑚 , retain all cheapest intervals that fit, and fractionally fill the next one. It is an optimistic relaxation, not a realizable policy. Unlike a bound based only on the smallest gap, it accounts for the limited number of cheap reuse events. Using exact 𝛿𝑚 , rather than integer 𝑔𝑖 , also avoids incorrectly discarding request-order boundary effects. We evaluate it against Belady in Section 5.
3.5
From fixed phases to evolving progress
The fixed-phase analysis determines traffic for given relative scan positions. We now ask how far workers can fall behind one another without losing shared cache fills. Let 𝑀 workers repeatedly read blocks 0, 1, . . . , 𝑁 − 1, all starting at block zero but advancing at their own pace. For cache analysis, arrange their requests into a single event sequence that preserves each worker’s request order. The event index 𝑢 counts requests across all workers, not elapsed time or scan rounds. Let 𝑛𝑖 (𝑢) be the number of requests made by worker 𝑖 among the first 𝑢 events, with 𝑛𝑖 (0) = 0. Its next request has cumulative index 𝑘 = 𝑛𝑖 (𝑢) and accesses block 𝑘 mod 𝑁 . These counts do not reset between scans, so a worker one full scan behind is 𝑁 requests behind, even if both workers are at the same block. Over the first 𝐸 > 0 events, define 𝜎𝐸 as the largest lead of any worker over any other worker, measured in requests: 𝜎𝐸 = max max 𝑛𝑖 (𝑢) − min 𝑛𝑖 (𝑢) . (8) 0≤𝑢 ≤𝐸
𝑖
𝑖
Zhou et al.
Theorem 5 (A sharp capacity condition for preserving sharing). Let 𝑀 ≥ 2 workers share an initially empty, fully associative LRU cache of integer capacity 1 ≤ 𝐶 < 𝑁 , with no other accesses. If 𝐶 ≥ 2𝜎𝐸 − 1, every request to an index 𝑘 after its first request by any worker hits. Consequently, the miss count 𝐴𝐸 satisfies 𝐴𝐸 ≤ max 𝑛𝑖 (𝐸), 𝑖
(𝑀 − 1)𝜎𝐸 𝑀𝐴𝐸 ≤1+ . 𝐸 𝐸
(9)
For every 𝑠 ≥ 2, a two-worker schedule with 𝜎𝐸 = 𝑠 can lose sharing at 𝐶 = 2𝑠 − 2 < 𝑁 ; the threshold is sharp. Proof. Write 𝜎 = 𝜎𝐸 ≥ 1. Immediately after the first request to index 𝑘, every worker has completed at least 𝑘 + 1 − 𝜎 requests. Until another worker requests 𝑘, that worker’s count is at most 𝑘; after every intervening event, all counts are therefore at most 𝑘 + 𝜎. Thus all intervening request indices lie in [𝑘 + 1 − 𝜎, 𝑘 + 𝜎 − 1]. Excluding 𝑘 mod 𝑁 leaves at most 2𝜎 − 2 distinct addresses. The same bound holds since its most recent reference, so Mattson’s LRU criterion [21] forces a hit. There are only max𝑖 𝑛𝑖 (𝐸) first indices. Í Also, 𝐸 = 𝑖 𝑛𝑖 (𝐸) ≥ 𝑀 max𝑖 𝑛𝑖 (𝐸) − (𝑀 − 1)𝜎, proving the bounds. For sharpness, choose 𝑁 = 2𝑠. Worker 1 first requests 0, . . . , 𝑠 − 1; worker 2 requests 0, . . . , 𝑠 −2; worker 1 requests 𝑠, . . . , 2𝑠 −2; worker 2 then requests 𝑠 − 1. The largest count difference is 𝑠. Between the two references to 𝑠 − 1 there are exactly 2𝑠 − 2 distinct other addresses, so the latter reference misses at capacity 2𝑠 − 2. □ Informally, this says that if no worker ever falls more than one request behind the leader, the cache preserves the sharing entirely, and that this tolerance breaks down sharply once capacity drops below twice the lead. Bounded progress differences thus preserve near-𝐾 = 1 traffic over long runs. The bound concerns the entire history: final phase alignment can hide earlier separation or a whole-scan lag. It establishes when sharing survives, but does not ensure that workers remain close.
3.6
How the instruction path limits cache-mediated slow core catch-up
Sharing a fill and recovering a progress deficit are different benefits. Our TMA kernel primes 𝑑 − 1 copies into 𝑑 ≥ 2 buffers, then repeatedly waits for tile 𝑘, consumes it, and issues tile 𝑘 + 𝑑 − 1. With two buffers, the next copy is issued only after the issuing warp’s current-tile consumer instructions. Furthermore, the transaction barrier requires both the data and all participating threads to arrive [23]: a faster copy need not release a barrier held by a late warp. For an indefinitely continued interior loop, put 𝑟 = 𝑑 − 1 and let 𝐼𝑘 be copy 𝑘’s issue time. Use fixed costs 𝛼 ≥ 0 from the previous issue to the next wait, and 𝛽 > 0 from that wait’s release through consumption to the refill issue. Assume thread arrivals add no later gate, and let 𝜆𝑘 be copy latency including queuing. The resulting earliest-event recurrence [2] is 𝐼𝑘+𝑟 = max{𝐼𝑘+𝑟 −1 + 𝛼, 𝐼𝑘 + 𝜆𝑘 } + 𝛽, with finite initial issue times 𝐼 0, . . . , 𝐼𝑟 −1 .
𝑘 ≥ 0,
Theorem 6 (A limit on cache-mediated catch-up). For constant latency 𝜆, Equation (10) gives 𝜆+𝛽 𝐼𝑛 𝑃𝑑 (𝜆) := lim = max 𝛼 + 𝛽, . (11) 𝑛→∞ 𝑛 𝑑 −1 More generally, allow arbitrary latency sequences between bounds 0 ≤ 𝜆ℎ ≤ 𝜆𝑘 ≤ 𝜆𝑚 . For two workers, let 𝑃𝑖 denote Equation (11) with worker 𝑖’s costs and depth, and give their latency bounds subscript 𝑖. If 𝜀 = 𝑃 2 (𝜆ℎ,2 ) − 𝑃 1 (𝜆𝑚,1 ) > 0, then 𝐼 2,𝑛 − 𝐼 1,𝑛 ≥ 𝑛𝜀 − 𝑂 (1).
(12)
Even the fastest permitted responses for worker 2 and the slowest for worker 1 cannot repair this growing timing deficit. Proof. Write 𝑐 = 𝛼 + 𝛽 and 𝑃 = max{𝑐, (𝜆 + 𝛽)/𝑟 }. The recurrence has a one-index edge of weight 𝑐 and an 𝑟 -index edge of weight 𝜆 + 𝛽. Iterating each edge gives 𝐼𝑛 ≥ 𝑛𝑃 − 𝑂 (1). For 𝐵 = max0≤ 𝑗 <𝑟 (𝐼 𝑗 − 𝑗𝑃), induction gives 𝐼𝑛 ≤ 𝑛𝑃 + 𝐵, since both edge weights are at most their index lengths times 𝑃. Hence 𝐼𝑛 = 𝑛𝑃 + 𝑂 (1). Monotonicity sandwiches every variable-latency clock between its constant-bound clocks, proving Equation (12). □ Theorem 6 gives a sufficient condition under which cache hits cannot compensate for a persistent rate disadvantage. Specifically, if 𝑃2 (𝜆ℎ,2 ) > 𝑃1 (𝜆𝑚,1 ), worker 2 falls increasingly behind even under its best permitted memory responses and worker 1’s worst. The result does not rule out recovery from a transient progress deficit when this strict separation fails. Taking 𝜆ℎ , 𝜆𝑚 as hit/miss latencies, define the available overlap 𝜃 = (𝑑 −1)(𝛼 +𝛽)−𝛽 and [𝑥] + = max(𝑥, 0). The greatest asymptotic time saving per request from replacing every miss by a hit is [𝜆𝑚 − 𝜃 ] + − [𝜆ℎ − 𝜃 ] + 𝐺𝑑 = 𝑃𝑑 (𝜆𝑚 ) − 𝑃𝑑 (𝜆ℎ ) = . (13) 𝑑 −1 It is zero when even misses fit within 𝜃 : arbitrarily many hits then buy only a bounded startup advantage, not sustained catch-up. Losing this correction alone does not create divergence; Equation (12) also requires a sustained service imbalance. For 𝑑 = 2, 𝜃 = 𝛼, so prerefill consumer work provides no overlap; every additional buffer adds one 𝛼 + 𝛽 interval. Increasing only miss latency cannot decrease 𝐺𝑑 . Therefore, explaining weaker correction under pressure requires more than “misses get slower”; non-memory service and inter-warp arrival delays must also be examined. The reference depth sweep makes this distinction concrete. At (𝑁 , 𝑀, 𝐶) = (4096, 48, 1280), 16 KiB tiles and no added matrix work, 𝑑 = 2, 3, 4 give first-wave times of 841, 465, and 424 ns per normalized round, all with 𝐾 ≃ 1. At 𝑑 = 4, extending to 32 waves raises 𝐾 from 1.00 to 5.58 while time remains 425 ns per round (Figure 4). Traffic and timing were measured separately; this contrast supports their decoupling, not an estimate of 𝐺𝑑 . The theorem isolates a source-derived dependency mechanism, not the full GPU schedule: late arrivals, changing service costs and CTA turnover still require modeling. In particular it neither identifies the pressure threshold nor explains the synchronous-path compiler discontinuities.
4
Dynamic Miss-Rate Prediction
(10) Section 3 answers the conditional question: given fixed relative phases, what traffic follows? We now remove the assumption that those phases are supplied. The output remains misses per unit work,
PASCAL: A Phase-Aware Shared-Cache Model for Parallel Scans
but the predictor receives only a new configuration and reusable reference measurements, not its realized progress. Three elements carry over from the static analysis: the normalization 𝜌 = 𝐾/𝑀, the aligned shared-stream baseline 𝐾 = 1, and the sensitivity of reuse to gaps near the eviction window. What does not carry over is a closed law for how those gaps evolve on a GPU. We therefore learn finite-horizon excess traffic rather than claim to solve phase dynamics. The pipeline summarizes reference measurements as traffic curves, transfers them using static program structure, and decodes a miss rate. The following observation rule explains both the connection to cyclic geometry and the additional missing state. Scope and status. The static gap law and Equation (15) are exact for their stated abstract traces; Propositions 7 and 9 retain their explicit conditions. The traffic-curve fit, work pooling, aligned floor, sparse-horizon completion and boundary rules are modeling choices validated only in Table 1’s scope. Target timestamps, traces, timing and counters are never predictor inputs. Accordingly, the pipeline forecasts finite-horizon traffic; it does not identify a general GPU phase-evolution law or supply a distribution-free error guarantee under configuration shift.
4.1
The prediction object and the missing state
Each worker is a GPU thread block (CTA) scanning 𝑁 data blocks; 𝑀 workers can be resident concurrently. Let 𝑊 be the total number of CTA scans divided by 𝑀, so 𝐻 = 𝑊 𝑁 is work per resident-worker equivalent. It does not assume synchronized rounds or equal CTA speeds. If 𝑉 (𝐻 ) bytes are fetched into L2 from off-chip memory during the run, define 𝐴(𝐻 ) = 𝑉 (𝐻 )/𝑏,
𝐾 𝐻 = 𝐴(𝐻 )/𝐻,
𝜌 𝐻 = 𝐾 𝐻 /𝑀,
(14)
where 𝑏 is bytes per data block. Thus 𝐴 counts fill-equivalent blocks, and 𝐾 𝐻 generalizes the static 𝐾 to a whole-run average. The target includes startup and tail traffic; it is neither latency nor the fraction of L2 lookups that miss when requests merge or prefetch. Below, 𝐾 abbreviates 𝐾 𝐻 when the configuration and horizon are understood. Why current phases are insufficient. For static scans, a round window is determined by the current cyclic gaps. With variable progress, the cache instead depends on intervening requests. This is precisely the distinction captured by working sets and reuse distance [11, 21, 27]. For an ideal, initially empty, fully associative Table 1: Prospective prediction contract. A configuration key is 𝑧 = (𝑜, 𝜋, 𝑑, 𝑚); 𝐻 = 𝑊 𝑁 is the requested horizon. Category
Content
Calibration input
Reference configurations and horizons with measured whole-run fill traffic (𝑜, 𝜋, 𝑑, 𝑚, 𝑁 ,𝑊 ) and the known binary’s static execution class b𝐻 and miss rate 𝜌b𝐻 = Fill-equivalent count 𝐾 b𝐻 /𝑀 𝐾 One binary and GB10 machine, 16 KiB logical blocks, 𝐶 = 1280, and the tested configuration envelope
Target input Prediction output Validated scope
LRU cache, consider 𝑀 cyclic streams whose 𝑗th request is (𝜙𝑖 + 𝑗) mod 𝑁 , where 𝑖 indexes the stream, 𝜙𝑖 ∈ {0, . . . , 𝑁 − 1} is its initial phase, and 𝑗 starts at zero. Fix a total order of request events, including ties. Let 𝑃𝑖 (𝑢) count stream 𝑖’s requests through event 𝑢, with 𝑃𝑖 (0) = 0. For an event 𝑡 accessing a previously requested address, let 𝑠 < 𝑡 be the most recent event accessing that address. Then 𝑅𝑖 (𝑠, 𝑡) = {(𝜙𝑖 + 𝑗) mod 𝑁 : 𝑃𝑖 (𝑠) ≤ 𝑗 < 𝑃𝑖 (𝑡 − 1)}, RD(𝑡) =
𝑀 Ø
(15) 𝑅𝑖 (𝑠, 𝑡) ,
hit ⇐⇒ RD(𝑡) < 𝐶.
𝑖=1
Indeed, 𝑅𝑖 is exactly the set requested by stream 𝑖 strictly between the two accesses. Their union counts distinct intervening blocks, the LRU stack criterion of Mattson et al. [21]. If 𝑠 does not exist, the access is cold. Each 𝑅𝑖 is a cyclic interval, so merging at most 2𝑀 ordinary intervals evaluates the union in 𝑂 (𝑀 log 𝑀) time once 𝑠 and the progress counts are supplied. The cost of obtaining those quantities is separate. The connection to Section 3 is the union of cyclic intervals: fixed, equal progress gives the equal-length windows used by the static footprint; variable progress requires each stream’s intervening interval separately. Within-round ordering still matters for LRU. Equation (15) is thus an exact observation rule for a specified history, not an evolution law for it. Linear progress between CTA start/end markers specifies one possible history, not the hardware history: our markers are written by thread 0, and the synchronous kernel has no per-iteration CTA barrier. Other warps, pending fills, and insertion order remain unobserved. Such reference-only reconstructions diagnose observation error; they are not inputs to the prospective predictor. Static geometry still identifies a relevant sensitivity statistic. Under Section 3’s assumptions, let 𝐹𝐶 (𝒈) = #{𝑖 : 𝑔𝑖 > 𝜃 }, where Í 𝑖 min(𝑔𝑖 , 𝜃 ) = 𝐶. This is the static gap law, not a substitute for Equation (15). Proposition 7 (Gap-margin stability). Consider two configurations with the same cyclic ordering and 𝐷 positive gaps, ∥𝒈−𝒈 ′ ∥ ∞ ≤ 𝜖, and continuous windows 𝜃, 𝜃 ′ solving 𝑈 = 𝐶. Then |𝜃 −𝜃 ′ | ≤ 𝐷𝜖, and |𝐹𝐶 (𝒈) − 𝐹𝐶 (𝒈 ′ )| ≤ #{𝑖 : |𝑔𝑖 − 𝜃 | ≤ (𝐷 + 1)𝜖}.
(16)
Proof. Each summand min(𝑔𝑖 , 𝑡) changes by at most 𝜖. Before either footprint reaches 𝐶 < 𝑁 , its slope is at least one. Comparing the two inverse roots gives the window bound. A classification can flip only if the gap-to-window distance is no larger than the sum of its gap and window perturbations. □ Thus a wider phase distribution need not yet increase traffic: what matters in the static law is crossing the eviction margin, not spread alone. This explains why our dynamic target is traffic rather than the number or variance of phase groups. The proposition bounds sensitivity to phase errors, not errors from omitting history. Why forecast a finite-horizon integral. Congestion is a useful diagnostic, but not a sufficient prediction coordinate. The logical read pressure plotted in Figure 4 is 𝑞1 =
𝑀𝑏/𝜏1 , 𝐵 ref
𝐵 ref = 2.10 TB/s,
(17)
Zhou et al.
where 𝜏1 is mean time per work-normalized round in a 𝑊 = 1 reference run and 𝐵 ref is an empirical read-rate reference. This ratio counts logical reads, including hits and merged requests; it is not an L2-to-SM bandwidth-utilization counter. Neither target 𝜏1 nor a pressure threshold is used in our pipeline. Inferring a terminal state introduces a separate ambiguity. For example, assume an instantaneous fill count 𝑘 (𝑢) = 1 + 𝛽 [1 − exp(−(𝑢/ℓ) 𝜈 )] at work coordinate 𝑢, with amplitude 𝛽 ≥ 0, scale ℓ > 0, and exponent 𝜈 > 0. Then averaging 𝑘 over 0 ≤ 𝑢 ≤ 𝐻 gives, as 𝐻 /ℓ → 0,
4.3
Choice 2: encode traffic above static alignment
For coincident static phases, 𝐷 = 1 and 𝑔1 = 𝑁 ; the gap law gives 𝐾 = 1 when 1 ≤ 𝐶 < 𝑁 . This is one fill shared by all 𝑀 workers, not one miss per worker. We use that exact static limit as the anchor for dynamic prediction, transferring the additional traffic rather than the entire rate. Define (𝑣)+ = max(𝑣, 0) and encode each curve as 𝑎𝑧 (𝑥) = log((exp 𝐿𝑧 (𝑥) − 1)+ + 𝜀) ,
𝜀 = 0.01.
(20)
b 𝜌b = 𝐾/𝑀.
(21)
For a transferred value 𝑎b, the final prediction is 𝛽 (𝐻 /ℓ) 𝜈 + 𝑂 𝛽 (𝐻 /ℓ) 2𝜈 . 𝐾𝐻 − 1 = 𝜈 +1
b = min{𝑀, 1 + (exp 𝑎b − 𝜀)+ }, 𝐾
(18)
Short profiles primarily identify 𝛽/ℓ 𝜈 , not the plateau and growth scale separately. We therefore fit the observed integral directly, without assuming this saturation law or solving for an unobserved equilibrium.
The floor at one is a static-motivated approximation, not a universal lower bound on warm-cache or noisy whole-run counters. The coordinate has a useful error interpretation. Suppose the true count is 𝐾 = 1 + 𝑒 ∈ [1, 𝑀], let 𝑎 = log(𝑒 + 𝜀), and assume |b 𝑎 − 𝑎| ≤ 𝛿. For 0 < 𝜀 ≤ 1,
Choice 1: fit cumulative traffic over the horizon
b − 𝐾| 𝑒 + 𝜀 |𝐾 ≤ (exp(𝛿) − 1). 𝐾 1+𝑒
Write 𝑚 = 𝑚 comp for compute work per block and 𝑧 = (𝑜, 𝜋, 𝑑, 𝑚) for a configuration key, where 𝑜 is resident CTAs per streaming multiprocessor, 𝜋 selects synchronous loads or the Tensor Memory Accelerator (TMA) path, and 𝑑 is prefetch depth (𝑑 = 0 for synchronous loads). A family 𝑓 = (𝑜, 𝜋, 𝑑) varies only 𝑚. In our calibrated scope, 𝑏 = 16 KiB, 𝐶 = 1280, and 𝑀 = 48𝑜. Use 𝑥 = 𝐻 /𝑁 0 = 𝑊 𝑁 /𝑁 0 , 𝑁 0 = 4096, as a work coordinate, not elapsed time. Pooling equal 𝑥 across 𝑁 is approximate: a scalar deviation with bulk growth 𝑔 ∈ R per work unit and restart multiplier 𝑟 > 0 is multiplied by 𝑒 𝑔𝐻 𝑟 𝑊 over 𝑊 complete scan/restart cycles. Equal work therefore need not preserve restart effects; work pooling is an approximation tested empirically below.
Positive-part projection is 1-Lipschitz, and clipping to 𝑀 cannot increase error for 𝐾 ≤ 𝑀. Before clipping, the excess error is at most (𝑒 +𝜀)| exp(b 𝑎 −𝑎) −1|, proving the bound. Near alignment, the prefactor attenuates a given coordinate error; it does not establish how small that error is.
4.2
Cumulative-traffic interpolation. At each distinct reference horizon 𝑥 𝑗 , aggregate positive measured counts into their geomete𝑧 (𝑥 𝑗 ). Project 𝑌 𝑗 = log[𝑥 𝑗 𝐾 e𝑧 (𝑥 𝑗 )] onto nondecreasing ric mean 𝐾 values by least squares with equal knot weights (isotonic regression). Interpolate the projected values at 𝑡 𝑗 = log 𝑥 𝑗 with a shapepreserving piecewise cubic Hermite interpolant (PCHIP) [16], denoted 𝑆𝑧 . The untransferred curve is 𝐿𝑧0 (𝑥) = 𝑆𝑧 (log 𝑥) − log 𝑥 .
(19)
It estimates log 𝐾, not instantaneous traffic. For a common-prefix execution, 𝐴(𝐻 ) is nondecreasing, even if 𝐴(𝐻 )/𝐻 decreases. This motivates monotonicity of the fitted cumulative quantity. Different measured horizons are separate launches, so monotonic cumulative traffic acts as a shape regularizer. For 𝐿𝑧0 outside its observed range, hold the average 𝐾 at the corresponding endpoint. Sparse keys receive a reference-only initial anchor and, when only endpoint horizons are available, a normalized shape borrowed from a better-observed reference curve. Let 𝐿𝑧 denote the reference log-count curve after the initial-anchor and sparse-horizon completion rules have been applied. For a key requiring no completion, 𝐿𝑧 = 𝐿𝑧0 .
4.4
(22)
Choice 3: interpolate by execution class
Compute count alone hides changes in generated control flow. Disassembly of our binary’s warp-level matrix multiply loop gives 𝑚 = 16𝑞 + 8𝑏 8 + 4𝑏 4 + 𝑟 . Here 𝑞 ≥ 0 is an integer counting full unrolled groups, 𝑏 8, 𝑏 4 ∈ {0, 1} select residual groups, and 𝑟 ∈ {0, 1, 2, 3}. The remainder is 𝑟 = 𝑚 mod 4. Remainder zero skips the tail; one exits early; two and three traverse the same tail basic blocks, with the third matrix instruction predicated. Define the execution class 𝑠 (𝑚) = min(𝑟, 2). This tail-control-flow classification is the static structure used by the interpolator. Smoothness within a class is the modeling hypothesis. Both the compute argument and disassembly are available before execution; no target timing or trace is needed. Proposition 8 (An unsampled-class obstruction). Fix a family and horizon, and assume smoothness only within each execution class. If a target class has no references, two response laws can agree on all references yet give target counts 1 and 𝐿, where 1 < 𝐿 ≤ 𝑀. Every point predictor then has worst-case relative error at least (𝐿−1)/(𝐿+1) over these laws. Proof. Choose the laws constant within the unmeasured class and identical elsewhere. Both satisfy any within-class smoothness bound. For a prediction 𝑣, the minimum of max{|𝑣 − 1|, |𝑣 − 𝐿|/𝐿} is attained at 𝑣 = 2𝐿/(𝐿 + 1), giving the bound. □ Thus more horizons on one class cannot replace coverage of another.
PASCAL: A Phase-Aware Shared-Cache Model for Parallel Scans
Anchored interpolation within a class. Fix a family 𝑓 and horizon 𝑥. First interpolate 𝑎𝑧 (𝑥) across all reference compute values, irrespective of class, using the compute rule above; denote the pooled estimate at the query 𝑚 by 𝑝. Suppose the nearest sameclass references bracket 𝑚 at 𝑚𝐿 , 𝑚𝑅 . Let 𝑎𝐿 , 𝑎𝑅 be their encoded values and 𝑑𝐿 = 𝑚 − 𝑚𝐿 > 0, 𝑑𝑅 = 𝑚𝑅 − 𝑚 > 0 their distances. Let 𝑚 − < 𝑚 < 𝑚 + be the adjacent reference computes without class restriction, and set 𝑐 0 = (𝑚 − 𝑚 − ) −1 + (𝑚 + − 𝑚) −1 . For a trial coordinate 𝑣, minimize (𝑣 − 𝑎𝐿 ) 2 (𝑣 − 𝑎𝑅 ) 2 2 E (𝑣) = 𝑐 0 (𝑣 − 𝑝) + 𝜂𝑔 + . (23) 𝑑𝐿 𝑑𝑅
Table 2: Static hardware miss-rate MAE (percentage points). SDCM–FA uses exact symbolic distances, not a hardware trace; Che–IRM assumes uniform independent requests. Cases (# of configurations) Clusters: all sizes (33) Phase/size sweep (62)
PASCAL
SDCM–FA
Che–IRM
0.456 1.897
0.456 1.897
42.911 44.909
The positive weight 𝜂𝑔 controls agreement within a class. Each edge penalty is the integral of squared slope along a linear segment. Strict convexity yields the unique minimizer
linear within-class estimate and desired relative error 𝜁 > 0, the conservative condition √︄ 8[log(1 + 𝜁 ) − 𝜉] ℎ≤ 𝐽
𝑐 0 𝑝 + 𝜂𝑔 𝑎𝐿 /𝑑𝐿 + 𝜂𝑔 𝑎𝑅 /𝑑𝑅 𝑐 0 + 𝜂𝑔 /𝑑𝐿 + 𝜂𝑔 /𝑑𝑅 = (1 − 𝜆)𝑝 + 𝜆𝑎 lin,
suffices when 𝐽 > 0 and log(1 + 𝜁 ) > 𝜉, since the prefactor in Equation (22) is at most one. Finite differences alone do not certify 𝐽 or 𝛿 0 ; this is a conditional design bound, not a guaranteed error bar for every query.
𝑎b =
(24)
Here 𝑎 lin = (𝑑𝑅 𝑎𝐿 + 𝑑𝐿 𝑎𝑅 )/(𝑑𝐿 + 𝑑𝑅 ) is linear interpolation within the class, with weight 𝜆=
𝜂𝑔 (1/𝑑𝐿 + 1/𝑑𝑅 ) . 𝑐 0 + 𝜂𝑔 (1/𝑑𝐿 + 1/𝑑𝑅 )
All weights are nonnegative, so the result lies in the convex hull of 𝑝, 𝑎𝐿 , 𝑎𝑅 . This is anchored harmonic interpolation [29]. Our modeling choice is to connect configurations through statically known execution classes. Development validation selects the single global weight 𝜂𝑔 = 4. Queries without a same-class bracket use deterministic, endpointclamped fallbacks across compute and then prefetch depth. Unsupported occupancy/path families are rejected rather than extrapolated.
4.5
Error control and a leakage-free calibration contract
Proposition 9 (Conditional interpolation certificate). Fix a family, execution class, and horizon. Assume its true encoded response has a twice-differentiable extension 𝑎 ∗ (𝑚) on the reference bracket of width ℎ = 𝑑𝐿 +𝑑𝑅 , with |𝑎 ∗′′ | ≤ 𝐽 . Suppose |𝑝 −𝑎 ∗ (𝑚)| ≤ 𝛿 0 at the query and each endpoint estimate has error at most 𝜉. Then |b 𝑎 − 𝑎 ∗ (𝑚)| ≤ (1 − 𝜆)𝛿 0 + 𝜆(𝜉 + 𝐽ℎ 2 /8) =: Δ.
(25)
For a target count in [1, 𝑀], Equation (22) applies with 𝛿 = Δ. Proof. The linear-interpolation remainder is at most 𝐽ℎ 2 /8. Its nonnegative weights preserve the endpoint error bound 𝜉. Apply the triangle inequality to Equation (24); no independence between the estimates is required. □ Here 𝐽, 𝛿 0, 𝜉 bound within-class curvature, pooled prediction error, and reference-curve error, respectively. The latter includes measurement noise and horizon-transfer approximation. The result separates calibration spacing from reference uncertainty: halving ℎ quarters the curvature term but does not reduce 𝜉. For a purely
Select on references; evaluate on unseen keys. Calibration uses one fixed, reusable collection of configurations and horizons. In each development fold, remove a complete key 𝑧 = (𝑜, 𝜋, 𝑑, 𝑚) at every 𝑁 ,𝑊 , including its short-run measurements. Refit all curve construction, initial-value interpolation, and template selection using only the remaining references. For validation keys Z, let b𝑧 𝑗 their 𝑛𝑧 be the number of scored runs for key 𝑧, and 𝐾𝑧 𝑗 > 0, 𝐾 observed and out-of-fold predicted counts. Select by configurationbalanced MAPE: 𝑛𝑧 b 𝐾𝑧 𝑗 100 ∑︁ 1 ∑︁ −1 . |Z| 𝑛𝑧 𝑗=1 𝐾𝑧 𝑗
(26)
𝑧∈Z
This is miss-rate MAPE because the same 𝑀 divides both counts; it is not latency MAPE. The primary model uses 84 development keys and 642 scored long-run observations (𝑊 > 1), then fits once to all 1096 reference labels. Baseline learners receive the same reference budget and static workload/program features. Before either independent test panel is executed, freeze the fitted model, all forecasts, and an empirical multiplicative band. Its log b radius 𝑟 band is the development 90th percentile of | log(𝐾/𝐾)|; the −𝑟 𝑟 b b band band rate band is [𝐾𝑒 , min{𝑀, 𝐾𝑒 }]/𝑀. It is not a distributionfree coverage guarantee under configuration shift. No refit occurs between panels. Inference reads only the frozen calibration, known configuration, and requested work horizon: no target timestamps, counters, phase reconstruction, or tracing.
5 Experimental Evaluation 5.1 Experimental Setup and Methodology The experiments are conducted on an NVIDIA GB10 GPU platform (CUDA 13 and driver 580.95.05) with 48 SMs and a 24MiB L2 cache. Referring to the capacity scan experiments shown in Figure 2, we choose 20MiB as the effective cache capacity because significant off-chip traffic is observed when the scanned data size exceeds 20MiB. The data block size is 16KiB in dynamic experiments, so the effective capacity is 𝐶 = 1280.
Off-chip fills / scanned bytes, R
Zhou et al.
4.0
Algorithm 1 Static phase-controlled scan (one CTA 𝑚)
Eight sweeps Mean Threshold: R=1.5 Model: 20 MiB Nominal: 24 MiB
3.5 3.0
Require: array of 𝑁 logical blocks, phase 𝑠𝑚 , rounds 𝐻 1: 𝑎 ← 0; each of 𝑝 threads owns one 16-byte lane 2: for 𝑟 = 0, . . . , 𝐻 − 1 do 3: 𝑗 ← (𝑟 + 𝑠𝑚 ) mod 𝑁 4: all threads load their lanes of block 𝑗 with __ldcg 5: consume the loaded values into 𝑎 6: grid-wide barrier across all 𝑀 CTAs 7: end for 8: write 𝑎 to prevent dead-code elimination
2.5 2.0 1.5 1.0 4
8
12 16 20 24 Scanned data size (MiB)
28
32
Figure 2: Fixed-allocation capacity scan: all eight repetitions and their mean. The model uses 20 MiB rather than the nominal 24 MiB; the observed transition is gradual and varies between repetitions.
5.2
Static accuracy and replacement bounds
Static experiments mean that the phase distribution among different workers does not change during the experiments. In actual kernels, it can happen in many cases, e.g., the kernel latency is short, or the pressure on the memory subsystem is low. In our microbenchmarks, we use a grid-level barrier (cg::grid_group.sync()) to ensure static conditions so that we can compare PASCAL with SDCM-FA and Che-IRM fairly, while more actual dynamic experiments are conducted in Section 5.4. Algorithm 1 presents the structure of the micro-benchmark kernel. The first cluster sweep uses 𝑀 = 48, 𝑁 = 8192, 4000 rounds, 4/8/16 KiB blocks, and 11 cluster counts from 1 through 48 (33 cases). A second sweep varies phase patterns (e.g. Wrapped Gaussian, Uniform Random, and Equally Spaced), 𝑁 /𝐶, and 𝑀 with 2 KiB blocks. The results of all 95 cases are presented in Table 2. PASCAL and SDCM–FA produce identical predictions with the same 4.09% MAPE. Across these 95 static configurations, the slotted-TTL formula and exact symbolic LRU evaluation produce identical predictions. This agreement is specific to the evaluated configurations; Theorem 3 permits disagreement near the eviction boundary. Exhaustive enumeration of 𝑁 = 2, . . . , 6, 𝑀 = 1, . . . , 3, phase vectors and 1 ≤ 𝐶 < 𝑁 gives 2254 cases; 500 seeded larger cases bring the total to 2754. Symbolic distances agree with warmed tracederived distances, and SDCM–FA agrees with exact LRU replay in every case. Theorem 3 has no violation where 𝐷 ≤ 𝐶. Belady on empty-cache traces of 6𝑁 rounds respects the residency bound (Figure 3b). These checks supplement the proofs.
5.3
Why dynamic prediction is necessary
Actual kernels do not usually use grid-level barriers as we do in the static experiments, and progress divergence among multi-cores can happen in such cases. To understand the cause of progress divergence, we consider different techniques frequently used in kernel optimization in our benchmark kernel (Algorithm 2). The kernel can either use Tensor Memory Accelerator (TMA) to fetch
Algorithm 2 Dynamic open scan (one CTA; grid has 𝑇 = 𝑊 𝑀 CTAs) Require: 𝑁 , path 𝜋, TMA depth 𝑑, compute count 𝑚 comp 1: 𝑎 ← 0; this CTA starts at logical block zero 2: if 𝜋 = TMA then 3: prefetch up to 𝑑 − 1 consecutive 16 KiB blocks into stages 4: end if 5: for 𝑗 = 0, . . . , 𝑁 − 1 do 6: if 𝜋 = TMA then 7: if 𝑑 = 1 then 8: issue block 𝑗 into the sole stage 9: end if 10: wait for stage 𝑗 mod 𝑑; consume its 16 KiB block 11: if 𝑑 > 1 then issue block 𝑗 + 𝑑 − 1 into the recycled stage, if it 12: exists 13: end if 14: else 15: cooperatively load and consume block 𝑗 with __ldcg 16: end if 17: execute 𝑚 comp synthetic WMMA operations 18: end for 19: record optional start/end markers; exit
data, which is similar to DMA in NPUs, or the traditional data path (through __ldcg()). The depth of software pipelines, the FLOPs per block, and occupancy are also variables in our controlled experiments. We define a configuration key as the vector of these four variables: (𝑜, data path, 𝑑, 𝑚 comp ). We define a phase cluster by merging workers whose rounded positions are connected through cyclic gaps of at most 32 blocks. Progress divergence can be measured by the number of phase clusters. When progress divergence occurs, the phases of different workers form an increasing number of clusters. Figure 4(a) shows the complexity of the problem; occupancy alone cannot determine whether progress divergence will occur, since the TMA kernel suffers from progress divergence when occupancy is 1, while the traditional data path kernel does not. Figure 4(b) measures the progress divergence versus initial memory pressure evaluated by Equation 17. It is clear that progress divergence is highly relevant to memory subsystem contention; there is no progress divergence when the memory pressure is low. However, we cannot quantitatively calculate the divergence according to the memory pressure
(a) Controlled static clusters (33 cases)
50
4 KiB 8 KiB 16 KiB TTL = SDCM-FA
measured K
40 30 20 10 0 0
10 20 30 40 predicted misses per round, K
50
finite-trace Belady miss rate
PASCAL: A Phase-Aware Shared-Cache Model for Parallel Scans
(b) Residency bound (2,754 cases) 1.0 0.8 0.6 0.4 0.2 0.0 0.0
0.2 0.4 0.6 0.8 any-policy miss-rate lower bound
1.0
Figure 3: Static hardware accuracy and abstract-model validation. (a) Programmed clusters versus L2 lookup traffic; phase-aware predictions coincide. (b) Finite-trace Belady respects the residency lower bound; slack includes relaxation and cold-start effects.
(a) Alignment, slots, and fragmentation
40
20 10 4 sync, occ=4, no compute
2
TMA, occ=1, depth=4
1
sync, occ=1, no compute
sync, occ=4, high compute
0
50 100 150 200 elapsed rounds (thousands)
250
late phase groups, c
phase groups, c
40
20
(b) Exploratory cutoff: 53/56 correct sync TMA, no compute TMA, compute
10 4 2 1 0.2 0.4 0.6 0.8 first-revolution logical pressure, q1
1.0
Figure 4: Exploratory dynamic evidence, not the held-out prediction test. (a) Reconstructed phase groups can remain aligned, separate into slots, or fragment broadly; synchronous traces cover 𝑊 = 64, orange TMA 𝑊 = 32. (b) It sweeps occupancy, depth, and compute; only 56 initially aligned cases (𝐾1 ≤ 1.05) enter this panel. The horizontal coordinate is Equation (17), not a utilization counter. Colors denote individual trajectories in (a), but families of different occupancy/depth/compute configurations in (b). because kernels at the same pressure can present different degrees of divergence.
5.4
Dynamic prediction: comparisons
To evaluate the model’s capability of predicting unseen kernels, the 60 configuration keys in the test set are never used for model selection or calibration. The test sets cover synchronous kernels (i.e., __ldcg() data path) with occupancies 1, 2, and 4, and TMA kernels with occupancies 1 and 2 and depths 2, 3, 5, and 6. The 60 held-out configurations are partitioned into two disjoint 30-configuration panels. The panels differ only in the problem-size and horizon pairs at which their configurations are evaluated: panel A emphasizes moderate horizons, whereas panel B includes a longer-horizon stress test at (W=80).
Predictor / component PASCAL TileSight cache: physical wave TileSight cache: resident wave PPT mapping: symbolic profile Exact SDCM: same profile
A
B
All
13.87 45.81 56.03 97.97 55.98
13.80 43.78 52.35 98.39 52.34
13.84 44.79 54.19 98.18 54.16
Table 3: Published cache components with explicit scan adapters: key-balanced miss-rate MAPE (%) on the same 60 configurations. All declared adapters are shown; none receive target measurements.
Table 3 compares our model with the cache components in TileSight [22] and PPT-GPU [1]. Our combined MAPE is 13.84%, versus
Zhou et al.
Panel A: 30 unseen keys
Panel B: 30 unseen keys
Same calibration budget
Forecast miss rate (%)
Forecast miss rate (%)
PASCAL 101
10
0
Random forest
101
Extra Trees Gradient boosting Relative-loss boosting 10
0
Ridge Weighted k-NN
101
100
101
100
Observed miss rate (%)
0
Observed miss rate (%)
50 100 Key-balanced MAPE (%)
Within horizon range W=80
Panel A
Panel B
Figure 5: Frozen predictions for 60 unseen configurations and 420 outcomes. Red triangles retain panel B’s horizon extrapolations. Both panels use the same fit; repetitions share a prediction. Errors are averaged within configurations before averaging across them. Original binary
Fill-equivalent count K
12
Default rebuild
Table 4: Predeclared ablations on the unchanged test panels: whole-key miss-rate MAPE (%). Only the reduced-budget row changes the number of reference labels.
Unrolling disabled
10 8 6
Predictor
Labels Panel A Panel B
4 2 0
36
40
41 42 43 44 Compute iterations per round (m)
48
56
PASCAL Reduced calibration Four execution classes No size pooling
1096 772 1096 1096
13.87 15.07 13.46 14.31
13.80 17.61 13.91 14.95
Figure 6: Compiler intervention at fixed work and occupancy. Means and full three-repeat ranges are shown. These reference-only diagnostics supply no fitted labels or target prediction inputs.
44.79% for physical-wave TileSight and 54.16% for exact symbolic SDCM. Absolute error is 0.76 pp versus 2.80 pp for physical-wave TileSight. These SDCM-based cache models prescribe waves or alignment, whereas our model predicts how traffic varies with configuration and duration. We also compared PASCAL’s prediction pipeline with other machine learning-based methods in Figure 5 under the same 1096-label training set and the same 60-key testing set. PASCAL outperforms all other learning-based methods, especially for panel B, where the average duration of workloads is long.
5.5
Ablations and architectural interpretation
Table 4 isolates three predeclared choices on the same held-out panels. Reducing the reference budget to 772 labels raises MAPE to
15.07/17.61%, showing that coverage contributes alongside representation. Removing size pooling gives 14.31/14.95%; accounting for 𝑁 improves transfer across the tested sizes. Separating all four compute remainders gives 13.46/13.91%, slightly better in aggregate than pooling the shared tail-control-flow class. The pooled class is therefore a compact architectural hypothesis, not an empirically optimal partition. We retain the primary selected before testing rather than substitute this favorable ablation. A reference-only compiler intervention fixes 𝑁 = 4096, 𝑀 = 192, 𝐶 = 1280 and 𝑊 = 32. Eight reference compute settings, three binary variants, and three randomized repetitions give 72 measurements. The original executable and a default rebuild retain a low-traffic region; disabling only the WMMA-loop unrolling directive removes it (Figure 6). At compute 42/43, mean 𝐾 changes from 1.011/1.022 in the default rebuild to 5.897/5.741 without unrolling. Both rebuilds use 44 registers, a 64-byte stack and no spills, with measured occupancy four.
PASCAL: A Phase-Aware Shared-Cache Model for Parallel Scans
6 Related Work 6.1 Footprints, distances, and statistical caching Denning’s working set theory [11, 12], Mattson’s stack analysis [21], and HOTL [27] are the conceptual foundations of our static geometry analysis. We reinterpret the working set theory in our terms and specialize it as the gap formula for AI workloads. Such a simplification drives our research into more complex dynamic analysis. Che–IRM and its temporal-locality extensions [9, 15, 17] differ mainly in the request laws supplied to characteristic-time analysis. StatCache [5] and StatStack [14] reduce profiling cost through statistical locality measurements. Similarly, whole-program reuse prediction [13] and static array-profile estimation [25] show that pre-execution reuse distance prediction is possible.
6.2
Multicore and GPU models
Cycle-accurate simulators, such as gpgpu-sim [3], accel-sim [18, 24], and Sim-FA [28] model the memory subsystem pipeline in detail. Therefore, while high accuracy is possible through these methodologies, the simulation speed tends to be extremely low. This challenge is even more severe in the Large Language Models (LLM) era due to the large problem size and large-scale design space exploration (DSE) with these tools is not practical in such a context.
6.3
Parallel locality
Blelloch and Gibbons [7] prove shared-cache scheduling guarantees relative to sequential cache performance, using additive cache augmentation tied to parallelism and computation depth. Chen et al. [10] demonstrate constructive sharing with parallel depth-first scheduling and study task granularity on CMPs. These papers establish why scheduling is a locality resource. Our contribution is to quantify the rate of missed scans in parallel and predict their deterioration without choosing a new schedule.
7
Conclusion
Lemma 1 and Theorem 2 give a closed-form formula for TTL cache miss rate calculation in parallel scan scenarios. Theorem 3 provides bounds for the LRU cache, and Theorem 4 provides bounds for any page-demanding policy. Theorem 5 explains when excessive cache misses may not happen and the minimum requirements for cache size. Theorem 6 explains why cache hits alone cannot repair a progress divergence, and identifies the factors that do influence it: software pipeline depth and compute work per block. Those factors become the inputs to the dynamic prediction pipeline, which achieves a MAPE of 13.84% on the held-out test set.
References [1] Yehia Arafa, Abdel-Hameed A. Badawy, Gopinath Chennupati, Nandakishore Santhi, and Stephan Eidenbenz. 2019. PPT-GPU: Scalable GPU Performance Modeling. IEEE Computer Architecture Letters 18, 1 (2019), 55–58. doi:10.1109/ LCA.2019.2904497 [2] François Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. 1994. Synchronization and Linearity: An Algebra for Discrete Event Systems. Journal of the Operational Research Society 45 (1994), 118–119. https://api.semanticscholar. org/CorpusID:24896688 [3] Ali Bakhoda, George L. Yuan, Wilson W. L. Fung, Henry Wong, and Tor M. Aamodt. 2009. Analyzing CUDA Workloads Using a Detailed GPU Simulator. In ISPASS. doi:10.1109/ISPASS.2009.4919648 [4] L. A. Belady. 1966. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal 5, 2 (1966), 78–101. doi:10.1147/sj.52.0078
[5] Erik Berg and Erik Hagersten. 2004. StatCache: A probabilistic approach to efficient and accurate data locality analysis. In IEEE International Symposium on-ISPASS Performance Analysis of Systems and Software, 2004. IEEE, 20–27. [6] Daniel S. Berger, Philipp Gland, Sahil Singla, and Florin Ciucu. 2014. Exact Analysis of TTL Cache Networks: The Case of Caching Policies driven by Stopping Times. arXiv:1402.5987 [cs.PF] https://arxiv.org/abs/1402.5987 [7] Guy E. Blelloch and Phillip B. Gibbons. 2004. Effectively sharing a cache among threads. In Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Barcelona, Spain) (SPAA ’04). Association for Computing Machinery, New York, NY, USA, 235–244. doi:10.1145/1007912.1007948 [8] Mark Brehob and Richard Enbody. 1999. An Analytical Model of Locality and Caching. Technical Report MSU-CSE-99-31. [9] Hao Che, Ye Tung, and Zhijun Wang. 2006. Hierarchical Web caching systems: modeling, design and experimental results. IEEE J.Sel. A. Commun. 20, 7 (Sept. 2006), 1305–1314. doi:10.1109/JSAC.2002.801752 [10] Shimin Chen, Phillip B. Gibbons, Michael Kozuch, Vasileios Liaskovitis, Anastassia Ailamaki, Guy E. Blelloch, Babak Falsafi, Limor Fix, Nikos Hardavellas, Todd C. Mowry, and Chris Wilkerson. 2007. Scheduling threads for constructive cache sharing on CMPs. In Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures (San Diego, California, USA) (SPAA ’07). Association for Computing Machinery, New York, NY, USA, 105–115. doi:10.1145/1248377.1248396 [11] Peter J. Denning. 1968. The working set model for program behavior. Commun. ACM 11, 5 (May 1968), 323–333. doi:10.1145/363095.363141 [12] Peter J. Denning and Stuart C. Schwartz. 1972. Properties of the working-set model. Commun. ACM 15, 3 (March 1972), 191–198. doi:10.1145/361268.361281 [13] Chen Ding and Yutao Zhong. 2003. Predicting whole-program locality through reuse distance analysis. In Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation. 245–257. [14] David Eklov and Erik Hagersten. 2010. StatStack: Efficient modeling of LRU caches. In 2010 IEEE International Symposium on Performance Analysis of Systems & Software (ISPASS). IEEE, 55–65. [15] Christine Fricker, Philippe Robert, and James Roberts. 2012. A versatile and accurate approximation for LRU cache performance. In Proceedings of the 24th International Teletraffic Congress (Krakow, Poland) (ITC ’12). International Teletraffic Congress, Article 8, 8 pages. [16] F. N. Fritsch and J. Butland. 1984. A Method for Constructing Local Monotone Piecewise Cubic Interpolants. SIAM J. Sci. Statist. Comput. 5, 2 (1984), 300–304. arXiv:https://doi.org/10.1137/0905021 doi:10.1137/0905021 [17] Michele Garetto, Emilio Leonardi, and Valentina Martina. 2016. A Unified Approach to the Performance Analysis of Caching Systems. ACM Trans. Model. Perform. Eval. Comput. Syst. 1, 3, Article 12 (May 2016), 28 pages. doi:10.1145/2896380 [18] Mahmoud Khairy, Zhesheng Shen, Tor M Aamodt, and Timothy G Rogers. 2020. Accel-Sim: An extensible simulation framework for validated GPU modeling. In 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA). IEEE, 473–486. [19] Chengtao Lai, Zhongchun Zhou, Akash Poptani, and Wei Zhang. 2024. LCM: LLM-focused Hybrid SPM-cache Architecture with Cache Management for MultiCore AI Accelerators. In Proceedings of the 38th ACM International Conference on Supercomputing (Kyoto, Japan) (ICS ’24). Association for Computing Machinery, New York, NY, USA, 62–73. doi:10.1145/3650200.3656592 [20] Heng Liao, Jiajin Tu, Jing Xia, and Xiping Zhou. 2019. DaVinci: A Scalable Architecture for Neural Network Computing.. In Hot Chips Symposium. 1–44. [21] R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. 1970. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (June 1970), 78–117. doi:10.1147/sj.92.0078 [22] Zhiwen Mo, Yu Cheng, Lei Wang, Zhengju Tang, Lei Xu, Guoyu Li, Yuqi Dong, Lingxiao Ma, Yuqing Xia, Jilong Xue, Fan Yang, Luo Mai, Zhi Yang, Wayne Luk, and Hongxiang Fan. 2026. TileSight: A First-Principles Tile-Centric Analytical GPU Performance Model from Cores to Clusters. arXiv:2607.22432 [cs.DC] https://arxiv.org/abs/2607.22432 [23] NVIDIA. [n. d.]. CUDA Programming Guide: Asynchronous Data Copies. Section 4.11. https://docs.nvidia.com/cuda/cuda-programming-guide/04-special-topics/ async-copies.html Accessed September 7, 2026. [24] Junrui Pan, Weili An, Cesar Avalos Baddouh, Christin David Bose, Ni Kang, Aaron Barnes, Ahmad Alawneh, Fangjia Shen, Yechen Liu, Anusuya Nallathambi, Atthin Chandrashekar, and Timothy G. Rogers. 2026. Architecting the Next Generation of Asynchronous, Distributed GPUs for the AI Era. arXiv:2608.22602 [cs.AR] doi:10.48550/arXiv.2608.22602 [25] Abdur Razzak, Atanu Barai, Nandakishore Santhi, and Abdel Hameed Badawy. 2024. Static Reuse Profile Estimation for Array Applications. In Proceedings of the International Symposium on Memory Systems (MEMSYS ’24). Association for Computing Machinery, New York, NY, USA, 235–244. doi:10.1145/3695794. 3695817 [26] Y.C. Tay and Min Zou. 2006. A page fault equation for modeling the effect of memory size. Performance Evaluation 63, 2 (2006), 99–130. doi:10.1016/j.peva. 2005.01.007
Zhou et al.
[27] Xiaoya Xiang, Chen Ding, Hao Luo, and Bin Bao. 2013. HOTL: a higher order theory of locality. In Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems (Houston, Texas, USA) (ASPLOS ’13). Association for Computing Machinery, New York, NY, USA, 343–356. doi:10.1145/2451116.2451153 [28] Zhongchun Zhou, Yuhang Gu, Chengtao Lai, Ya Wang, Zeyu Han, Wei Zhang, and Jun Liu. 2026. Sim-FA: A GPGPU Simulator Framework for Fine-Grained
Asynchronous Pipeline Analysis. arXiv:2605.00555 [cs.AR] https://arxiv.org/ abs/2605.00555 [29] Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. 2003. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning (Washington, DC, USA) (ICML’03). AAAI Press, 912–919.