Loading page…
Master the fundamental concepts of pipelining & out-of-order execution through this focused micro-challenge.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksModern CPUs fetch ahead of resolved branches. A misprediction flushes the pipeline, wasting 10 to 20 cycles on typical cores. Tight loops with unpredictable conditions show the penalty clearly in benchmarks.
cLoading…
bashLoading…
A loop with 50/50 random branches might show ~50% miss rate and run several times slower than a biased or branchless version.
For this exercise, you will craft predictable vs unpredictable branch patterns and compare retired instructions per cycle. This task asks you to tie measured branch-misses events to the 2-bit predictor you implement next.
Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.
For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.
Show why an unpredictable branch is expensive. Run a loop of comparisons against a simulated branch predictor with a misprediction penalty, and compare three versions of the same computation: a branch over sorted data (easy to predict), the same branch over shuffled data (a coin flip), and a branchless version that has no branch to mispredict.
cLoading…
For each element v: the branchy version runs if (v >= THRESHOLD) sum += v;, and the branchless version runs mask = -(v >= THRESHOLD); sum += v & mask;. Both compute the same sum.
Values are v_i = (i · 2654435761) mod 1000 for i = 0 … N−1.
x = SEED; for i from N−1 down to 1, advance x = (x · 1103515245 + 12345) mod 2^31 and swap v[i] with v[x mod (i + 1)].A single 2-bit saturating counter, starting at 1 (weakly not-taken). It predicts taken for states 2 and 3. After each branch, a taken outcome increments the state (up to 3) and a not-taken outcome decrements it (down to 0). The "taken" outcome is v >= THRESHOLD.
Cost model: every element costs C cycles, plus P for each mispredicted branch. The branchless version has no branches.
Per experiment:
cLoading…
Rates have one decimal, ratios two. Print a blank line between experiments.
Input:
cLoading…
Output:
cLoading…
Hidden tests cover thresholds that almost every element passes or fails (predictable even when shuffled), a threshold of 0 (the branch is always taken), and arrays of 1, 8 and 32 elements.