Software Trace Cache: Rethinking Fetch Performance via Compiler Logic

TL;DR

The Software Trace Cache (STC) is a sophisticated code layout optimization that transforms how processors "see" instructions. By automating basic block chaining, routine splitting, and cache mapping, it significantly boosts instruction cache hit rates and fetch width. In real-world tests on commercial databases, it slashed execution time by 25% and allowed a 16KB cache to outperform a standard 64KB cache.

Context: While hardware engineers were busy building complex Trace Caches with millions of transistors, Ramirez et al. proved that the compiler could achieve similar results by simply "reorganizing the bookshelf."

The "Fetch" Wall: Why Hardware Isn't Enough

Modern superscalar processors are hungry. If a processor can execute 5 instructions per cycle, it must fetch at least 5 every cycle. However, the fetch engine faces three enemies:

1. Memory Latency: Instruction cache misses stall the whole pipeline.
2. Fetch Width: Taken branches break the sequence, often limiting fetch to just one basic block.
3. Branch Accuracy: Speculating down the wrong path wastes cycles.

Prior work (like Pettis & Hansen) attempted to reorder code, but required manual threshold settings and often focused on individual routines rather than the global execution flow.

Methodology: The Three Pillars of STC

The STC algorithm acts as a master architect for the binary, rebuild the instruction stream through three distinct phases:

1. Automated Seed Selection and Trace Construction

Instead of manual entry points, STC uses profile data to identify all subroutine entry points as seeds. It follows the most likely execution path, crossing subroutine boundaries (inlining at the layout level).

• Insight: Loops are handled by recognizing "back-edges," ensuring the most frequent fall-through paths remain sequential.

2. Routine Splitting (The Hot/Cold Divide)

By separating "hot" (frequently executed) basic blocks from "cold" (error handling, rare conditions) blocks, STC packs the useful code tightly. This compaction ensures that when a cache line is loaded, 80% of its content is used, compared to less than 50% in unoptimized binaries.

3. The Conflict Free Area (CFA) Mapping

This is the "special sauce." STC reserves a portion of the cache and maps the most popular traces there, ensuring no other code can evict them.

• Heuristic: STC automatically balances CFA size; if the code takes 30% of the cache but provides 30% of execution frequency, it’s a candidate for the CFA.

Experimental Performance: Winning on All Fronts

The authors tested STC across SPECint95 and massive commercial databases (TPC-B on Oracle).

Instruction Cache Breakthrough

STC doesn't just reduce conflict misses; it fundamentally improves spatial and temporal locality.

• Spatial: Optimized code uses the entire cache line 60% of the time.
• Temporal: Cache line "lifetime" (the time before eviction) doubles (moving from $2^{19}$ to $2^{20}$ cycles).

The Branch Predictor Paradox

A fascinating finding is the impact on branch prediction. STC makes code extremely "Not-Taken" biased (roughly 80% of branches become not-taken).

• Simple Predictors (gshare): Accuracy increases because positive interference (multiple branches both being not-taken) dominates.
• Advanced Predictors (Agree/Gskew): Accuracy actually dipped slightly. Why? Because the Branch History Register (BHR) becomes "saturated with zeros," reducing the entropy and information available for complex dealiasing. However, the gains in cache hits far outweighed this minor accuracy loss.

Deep Insight: Beyond Instruction Fetch

The value of STC extends to the L2 Shared Cache. By compacting instructions into fewer pages and fewer L1 lines, STC reduces "Instruction-Data interference" in the L2 cache. Fewer instruction evictions mean more room for data, leading to a surprise reduction in L2 Data Misses.

Critical Analysis & Conclusion

Takeaway

The Software Trace Cache is a masterclass in exploiting Inductive Bias in software execution. By aligning the software layout with the hardware's preference for sequentiality, it achieves "hardware-level" gains for free.

Limitations

• Profile Dependency: STC relies on high-quality training profiles. If the real-world workload differs significantly from the profile (cross-optimization), performance gains can diminish.
• Binary Bloat: Depending on the splitting strategy, total binary size might increase, though the "hot" working set remains small.

Future Outlook

As we move toward even wider superscalar designs and more complex memory hierarchies, software-level layout remains one of the most cost-effective ways to fight the "Memory Wall."