Working Set

The working set is defined by the principle of temporal locality, which states that memory locations accessed recently are likely to be accessed again soon. This is the foundational assumption that makes caching and paging effective. A program's working set at time t is formally the set of pages (or cache lines) referenced in the time interval (t - Δ, t), where Δ is the working set window. The size and composition of this set change as the program's execution phase changes.

A working set is not static; it evolves with program execution. It typically exhibits phase behavior, where periods of stable memory access patterns (a steady working set) are punctuated by phase transitions where the set changes rapidly. For example:

• An initialization phase loads a large dataset into memory.
• A computation phase repeatedly accesses a core subset of that data.
• A cleanup phase accesses new memory for writing results. Effective memory management, especially on NPUs with limited on-chip memory, requires algorithms to detect these phases and adapt data placement accordingly.

The relationship between the working set size (WSS) and the cache size or fast memory capacity is the primary determinant of cache/memory performance. This leads to three fundamental regimes:

• Ideal (WSS < Cache): The entire working set fits in fast memory, yielding hit rates near 100% and optimal performance.
• Thrashing (WSS >> Cache): The working set vastly exceeds cache capacity, causing constant eviction of needed data and catastrophic performance drops.
• Knee of the Curve (WSS ≈ Cache): Performance is highly sensitive to small changes in WSS or cache size; this is the critical design point for systems engineers optimizing NPU memory hierarchies.

In virtual memory systems, the working set model directly informs page replacement policies. The Working Set Model for process scheduling, formalized by Peter Denning, states a process should only be allowed to run if its working set is resident in physical memory to prevent thrashing. Practical algorithms like the WSClock approximate the working set to decide which pages to keep in RAM and which to page out to disk. For NPU scratchpad memory, similar explicit management is performed by the compiler, which must analyze the program's expected working set to allocate data structures.

The working set is not directly programmable but is observed through hardware performance counters and memory trace analysis. Key metrics include:

• Last-Level Cache (LLC) Misses: A sharp increase indicates the working set exceeds LLC size.
• Page Fault Rate: In virtual memory, a high rate indicates the working set exceeds allocated physical frames.
• Access Pattern Stride: Analyzed to distinguish between sequential, random, or strided working sets, which impacts prefetching effectiveness. Tools like perf (Linux) or VTune profile these events to guide optimization, such as adjusting data layout or tile sizes for NPU kernels.

On NPUs and GPUs, managing the working set is a core compiler and programmer responsibility due to explicit memory hierarchies (e.g., global, shared, local memory). Key optimization techniques include:

• Tiling/Loop Blocking: Restructuring computations to break large data sets into tiles that fit the accelerator's fast scratchpad memory or cache, ensuring the tile becomes the kernel's working set.
• Data Layout Transformation: Rearranging data structures (e.g., Array of Structs to Struct of Arrays) to improve spatial locality and create a more compact, cache-friendly working set.
• Kernel Fusion: Combining operations to keep intermediate data in registers or shared memory, preventing it from spilling to slower memory and bloating the working set.

A principle of program behavior where if a particular memory location is accessed, nearby memory locations are also likely to be accessed in the near future. This principle directly influences the design of cache lines and prefetching algorithms, as it is efficient to move contiguous blocks of data. Optimizing for spatial locality is key to maximizing the utility of data transferred into a cache or scratchpad, thereby improving the effective bandwidth of the memory system.

A principle of program behavior where if a particular memory location is accessed, it is likely to be accessed again in the near future. This is the foundational concept that justifies the existence of caches. A program's working set is essentially the manifestation of its temporal locality over a given time window. High temporal locality means data can be retained in fast memory (like an L1 cache or NPU SRAM), minimizing costly accesses to slower, higher-level memory.

An event that occurs when a processor requests data and that data is not present in the current level of cache. This forces a access to a slower, lower level of the memory hierarchy (e.g., L2 cache, HBM, or DRAM). Cache misses are a primary source of performance degradation. The frequency of cache misses is inversely related to how well a program's working set fits within the available cache capacity and aligns with locality principles.

A hardware or software technique that predicts future memory accesses and proactively loads data into a cache or buffer before it is explicitly requested by the processor. The goal is to hide memory latency by having data ready when needed. Effective prefetching relies on recognizing predictable memory access patterns (often stemming from spatial locality) and is critical for keeping computational units fed with data, especially when dealing with large working sets.

A small, high-speed, software-managed on-chip memory (SRAM) used in accelerators like NPUs and GPUs. Unlike a hardware-managed cache, the programmer or compiler must explicitly move data into and out of the scratchpad. Managing the scratchpad effectively requires a precise understanding of the kernel's working set—knowing exactly what data blocks are needed for a computation phase and scheduling their movement to minimize stalls.

Describes the sequence and stride with which a program reads from or writes to memory locations. Patterns can be:

• Sequential/Strided: Regular, predictable strides (optimal).
• Random: Irregular, hard-to-predict addresses (suboptimal). The pattern heavily influences cache performance, prefetcher effectiveness, and bandwidth utilization. Optimizing kernels to have coalesced and regular access patterns is essential for efficient working set management on parallel architectures.