A Hybrid Method for Semantic Cache Analysis of Computational Kernels in C Programs
TL;DR
CATS (C Annotated Trace-based Cache Simulator), a novel hybrid method and toolset for detailed cache efficiency analysis, designed to overcome fundamental limitations of existing analysis tools, is introduced.
Abstract
The performance of modern high-performance computing systems is increasingly constrained not by computational power, but by the efficiency of memory subsystem interaction. Cache behavior optimization thus becomes a critical requirement for developers of computationally intensive applications, including numerical simulations, scientific computing, and machine learning kernels. However, existing analysis tools face fundamental limitations; they either provide only aggregated statistics, or exhibit a “semantic gap” by presenting data in machine addresses rather than source code constructs, which impedes targeted optimization of complex data-intensive programs. This paper introduces CATS (C Annotated Trace-based Cache Simulator), a novel hybrid method and toolset for detailed cache efficiency analysis, designed to overcome these limitations. CATS combines source-level static analysis with dynamic tracing at the intermediate representation (IR) level to generate semantically annotated memory traces, enabling precise identification of which source code data structures (arrays, structs, dynamically allocated objects) cause cache misses. The paper describes the methodology and architecture of CATS and presents a foundational validation of the approach through comparative accuracy analysis against reference simulators (gem5, Valgrind) on regular computational kernels (General Matrix Multiplication, GEMM). Systematic error analysis quantifies CATS’s accuracy bounds across different input sizes for the evaluated cache configuration (L1: 32 KB, L2: 256 KB). The current work explicitly focuses on single-threaded CPU-based C programs; extension to irregular kernels, multi-threaded workloads, hardware accelerators (GPU, FPGA), and specific AI applications are identified as future research. Early CATS application at the design stage enables identification of algorithmic cache bottlenecks before final implementation, complementing traditional compiler-level optimizations.