Why we abandoned phase detection for cumulative memory envelopes?

The question

E-WarP's profiler produces a dense stream of memory-bandwidth samples for every run of an application by sampling approximately every 1.5 μs. The runtime predictor built on top of it needs a single answer out of that stream: how long will this application take if MemGuard limits it to a given bandwidth budget? The first real question wasn't about MemGuard at all — it was about what to do with the raw trace before trying to predict anything from it. Handing a predictor a million noisy samples directly didn't seem workable, so the first attempt treated it as a signal-processing problem: turn the trace into a small number of meaningful segments first.

The initial intuition

The first idea was surprisingly intuitive: if an application’s memory behavior changes over time, perhaps we could simplify prediction by identifying those changes explicitly. Instead of treating the execution as one long stream of memory accesses, we could divide it into distinct stages and summarize each stage with a representative bandwidth. If runtime could be modeled as a sequence of “low-bandwidth” and “high-bandwidth” phases, predicting performance under different DRAM budgets seemed like it should become much easier.

staging.py and step_detect.py are what that attempt looked like. step_detect.py implements three different statistical step-detectors — a windowed t-test statistic, a Gaussian derivative, and a Mallat-Zhong wavelet multiscale product — any of which can flag where a time series changes behavior significantly:

sigma = 20
dg = gaussian_filter1d(data, sigma, order=1)

mz = step_detect.mz_fwt(data, n=3)
tt = step_detect.t_scan(data, window=500)

model = tt
threshold = 0.5
steps = step_detect.find_steps(np.abs(model), threshold)

Whichever detector's output crosses that threshold gets treated as a phase boundary. Once the boundaries are fixed, each resulting stage collapses to a single average bandwidth number:

for s in steps:
    end = s
    stage_len = x[end] - x[start]
    stage_bytes = sum(trace['reads'][start:end])
    stage_bw = (stage_bytes / float(stage_len)) * 1000 / (1024 * 1024)
    staging = np.concatenate((staging, [stage_bw] * (end-start)))
    start = end

Run that over a trace and you get something that reads beautifully in a paper: Stage 1, 200 MB/s. Stage 2, 900 MB/s. Stage 3, 350 MB/s. Clean, presentable, and — for what we actually needed — wrong.

Why it failed

MemGuard doesn't regulate an average rate at all. It regulates a cumulative transaction count inside a fixed one-millisecond regulation period — the budget itself is denominated directly in transactions per period, not megabytes per second. Two stages can carry an identical average bandwidth and still behave completely differently under that rule if one packs its traffic into an early burst and the other spreads it evenly across the same window; the average is blind to exactly the timing MemGuard cares about.

The boundaries made things worse, not better. A statistically meaningful change point has no reason to land on a millisecond regulation-period boundary, so the two almost never lined up — predicting a stall meant reasoning about a MemGuard period that straddled two different "phases," which the model had no clean way to represent. The boundaries were fragile on top of that: which detector you picked, the window size, the Gaussian sigma, the threshold — change any one of those knobs and the phases shift, split, or disappear. A prediction that depends on an arbitrary signal-processing parameter isn't a prediction anyone should trust, and running the same benchmark twice shifted the boundaries again anyway, so even lining up stages across repeated executions of one program became its own research problem.

Worst of all, averaging is exactly the operation that hides what a real-time predictor needs to see. A stage's average bandwidth smooths away the burst that determines whether MemGuard throttles the application, which means the model can predict a completion time faster than what actually happens. For a real-time system, an optimistic prediction isn't a rounding error. It's a wrong answer.

The insight

The fix wasn't a better detector. It was dropping the question the whole approach was built on. Instead of asking what stage is the application in right now, the better question turned out to be: how many memory transactions could the application have issued by this point in time? That's not a stage label, it's a running count — and a running count only ever goes up, so it never needs a boundary drawn anywhere.

Because the same application doesn't behave identically run to run, no single cumulative curve is trustworthy on its own either. So the envelope tracks two curves built across dozens of runs of the same benchmark: at every instant, the highest cumulative transaction count observed at that instant across all runs, and the lowest.

loc_cumul = 0
for s in range(len(trans)):
    loc_cumul += trans[s]

    if loc_cumul > cumul_up[s]:
        cumul_up[s] = loc_cumul

    if loc_cumul < cumul_low[s]:
        cumul_low[s] = loc_cumul

Side by side, the difference is the whole point. The stage model compresses the trace into a handful of average bandwidths separated by detected boundaries. The cumulative envelope asks a different question entirely: how much memory demand could have accumulated by this point in execution? Across repeated runs, it records the highest and lowest cumulative transaction count observed at each sampled position, representing run-to-run variation as a bounded region instead of averaging it away.

Connecting it to prediction

A cumulative envelope is useful because it represents the same quantity that MemGuard regulates: cumulative memory transactions over time. Predicting runtime under a hypothetical budget becomes a replay of cumulative demand against MemGuard’s periodic replenishment behavior. Rather than reasoning about average bandwidth over arbitrary phases, the predictor determines when cumulative demand can exhaust the available budget within each regulation period and accounts for the resulting stall.

if (cumul[s] - per_trans) >= (budget - bm_tovh):
    mg_periods += 1

    # stall until the period replenishes
    addl_time += 1.0 - (time[s] - per_time)

    per_time = time[s]
    per_trans = cumul[s]

Whenever that count reaches the budget before the period ends, the model doesn't need to know what "phase" the application is in. It just knows execution has to wait for the next period to replenish before it can issue another transaction, and adds the resulting stall to the predicted runtime.

Takeaway

Averaging is seductive precisely because it’s simple—a handful of stage labels is easier to reason about, present, and tune than two curves built from dozens of runs. But an abstraction only helps if it matches the mechanism you’re trying to predict, and MemGuard’s mechanism is defined by cumulative demand within fixed regulation periods. The moment I stopped asking a signal-processing question and started asking the same question the regulator itself asks, the representation stopped fighting the problem. Using this envelope-based model, E-WarP overpredicted execution time by approximately 6% on average across the evaluated workloads. The important insight wasn’t finding a more sophisticated phase detector—it was choosing a representation that matched the behavior of the system being modeled.