Memory Fragmentation

Fragmentation is categorized by where wasted space occurs relative to allocated blocks.

• Internal Fragmentation: Wasted space within an allocated memory block. This happens when an allocator rounds up a request to a fixed-size block or alignment boundary (e.g., requesting 33 bytes but receiving a 64-byte block). The extra 31 bytes are internal waste.
• External Fragmentation: Wasted space between allocated blocks. This is the free memory that exists as small, scattered gaps, which are individually too small to satisfy a new allocation request, despite their collective size being adequate. External fragmentation is the primary cause of allocation failures in long-running systems.

NPU execution patterns are particularly prone to fragmentation due to dynamic memory lifecycles.

• Variable Tensor Lifetimes: A computational graph executes operators with tensors of different sizes and lifespans (short-lived intermediates vs. long-lived model weights). The intermixed allocation and deallocation of these variable-sized blocks quickly scatters free space.
• Dynamic Batching: Batch sizes may change during inference, causing repeated allocation and freeing of activation memory in varying sizes.
• Kernel-Specific Scratchpad Usage: Different optimized kernels may request temporary buffers of unique sizes for intermediate results, leading to a pattern of small, unique allocations.

Fragmentation directly undermines NPU efficiency and system predictability.

• Allocation Failures (Out-of-Memory Errors): The most severe symptom. A request for a large, contiguous tensor fails despite the free memory statistic showing ample space, causing application crashes or failed inferences.
• Increased Allocation Latency: The allocator must spend more time searching through fragmented free lists to find a suitable block, or must initiate expensive compaction routines.
• Suboptimal Placement: Fragmentation can force data into slower, higher-latency memory tiers (e.g., system DRAM instead of on-chip SRAM) because contiguous space isn't available in the fast memory, degrading throughput.
• Reduced Effective Capacity: The usable memory capacity of the NPU is effectively less than its physical capacity.

Identifying fragmentation requires specific metrics beyond total free memory.

• Largest Free Block: The single largest contiguous block of free memory. This is the most critical metric—it determines the maximum tensor size that can be allocated.
• Free Block Distribution: A histogram showing the count and size of all free blocks. A system with many small blocks and a small largest free block is heavily fragmented.
• Allocation Failure Rate: Tracking failures where requested size < total free memory but > largest free block.
• Memory Pool Utilization: In pool-based allocators, fragmentation is observed as low utilization of individual pools despite high overall usage.

Strategies to combat fragmentation involve allocator design and workload management.

• Memory Pool Allocators: Pre-allocating fixed-size blocks (pools) for common tensor sizes. Requests are rounded to the nearest pool size, trading some internal fragmentation for the elimination of external fragmentation for those sizes. Common in inference engines.
• Slab Allocator: A refinement of pool allocation that manages pools (slabs) for a range of object sizes.
• Defragmentation (Compaction): Periodically moving allocated blocks in memory to coalesce free space. This is complex and costly as it requires updating all pointers/references to moved data and pausing execution.
• Arena/Region-Based Allocation: Allocating objects with similar lifetimes from a contiguous region (arena). The entire region is freed at once, avoiding fragmentation within that lifecycle. Useful for ephemeral inference request contexts.
• Buddy Allocator: An algorithm that splits and coalesces memory in power-of-two blocks, ensuring fast coalescing of free blocks but potentially causing high internal fragmentation.

Fragmentation interacts closely with other memory hierarchy concepts.

• Scratchpad Memory: Software-managed SRAM on an NPU. Without careful allocation strategies, scratchpad fragmentation can be even more detrimental than DRAM fragmentation due to its small, precious size.
• Unified Memory: Systems with a unified address space (e.g., CPU-NPU) must manage fragmentation across the entire shared space, complicating allocator design.
• Memory Pools: As a mitigation strategy, pools are explicitly configured based on the expected tensor size distribution of the target neural network.
• Working Set: Fragmentation can prevent a process's working set of active tensors from fitting into fast memory, forcing constant swapping.

A memory pool pre-allocates a large, contiguous block of memory at initialization and manages sub-allocations from this fixed block. This strategy:

• Eliminates external fragmentation by preventing the interleaving of allocated and free blocks from the system heap.
• Reduces allocation overhead by replacing general-purpose malloc/free with simple pointer arithmetic.
• Is ideal for NPU workloads with predictable, fixed-size tensor allocations (e.g., activation buffers for a specific model). Common implementations include slab allocators for fixed-size objects and buddy allocators for power-of-two sized blocks.

Memory compaction is the process of relocating allocated blocks in physical memory to consolidate free space into a single contiguous region. Key aspects:

• Requires update of all pointers/references to moved objects, which is complex in systems with direct memory addresses.
• Often implemented in garbage-collected languages (e.g., Java, C#) or managed runtimes where the runtime controls object references.
• In NPU contexts, this may involve pausing kernel execution to migrate tensor data, making it costly for real-time inference. Copy-on-write techniques can mitigate the pause time.

This technique maintains separate free lists for different allocation size classes (e.g., 64B, 256B, 1KB, 4KB+). When an allocation request arrives:

• The allocator checks the list for the smallest size class that can satisfy the request.
• Reduces search time and internal fragmentation by matching requests to appropriately sized blocks.
• If the chosen list is empty, it splits a block from a larger size class. This is a core component of many high-performance allocators (e.g., jemalloc, tcmalloc) and is effective for the mixed-size allocations common in computational graphs.

A slab allocator dedicates contiguous memory pages (a 'slab') to objects of a single, fixed size. Each slab maintains a bitmap or free list to track unused objects.

• Virtually eliminates fragmentation for that object type, as freed objects create a hole of the exact size needed for a future allocation.
• Provides excellent cache locality as all objects are the same size and often accessed in sequences.
• Heavily used in operating system kernels (e.g., Linux) for kernel objects and is ideal for NPU runtime systems managing many identical kernel argument structures or descriptor objects.

The buddy system manages memory in blocks where each block is a power-of-two size. When a request arrives, it finds the smallest suitable block. If none is free, it recursively splits a larger block into two 'buddies'.

• Efficient coalescing: When both buddy blocks are freed, they can be merged back into the larger parent block, combating external fragmentation.
• Fast allocation/deallocation due to simple bitmask operations to track free blocks.
• The trade-off is internal fragmentation, as requests are rounded up to the nearest power of two. This is often acceptable in NPU memory managers for large tensor buffers.

Arena allocation (or region-based allocation) groups allocations related to a specific task or phase (e.g., processing a single inference request) into a shared region, or 'arena'.

• Allocations are fast (often just a pointer increment).
• Deallocation is instantaneous for the entire region, freeing all objects within it at once, completely avoiding fragmentation within the arena.
• This pattern is highly effective for NPU inference pipelines, where all temporary tensors for a batch can be allocated from a per-batch arena and freed collectively when the batch completes.

A memory pool is a software design pattern where a large, contiguous block of memory is allocated once and then managed internally to satisfy smaller, subsequent allocation requests. This pattern is a primary anti-fragmentation technique because it:

• Eliminates external fragmentation by satisfying all requests from within a single, pre-allocated block.
• Reduces allocation overhead by bypassing the general-purpose allocator for frequent, small allocations.
• Is commonly used in high-performance computing and embedded systems (e.g., for tensor buffers in an NPU runtime) to guarantee deterministic performance.

Scratchpad memory (SPM) is a small, software-managed, on-chip SRAM in accelerators like NPUs. Unlike a hardware-managed cache, the programmer or compiler explicitly controls data movement in and out of the SPM. Its use directly combats fragmentation by:

• Providing a contiguous, guaranteed-latency memory region for critical data tiles or kernels.
• Eliminating cache conflict misses and unpredictable evictions that can create inefficient access patterns resembling fragmentation.
• Enabling precise, static scheduling of data flows, which prevents the dynamic, variable-sized allocations that lead to heap fragmentation in general-purpose memory.

A memory allocator is the subsystem (e.g., malloc/free in C, or a custom arena allocator) responsible for managing the dynamic allocation and deallocation of memory regions. The allocator's strategy is the defining factor in fragmentation:

• First-fit, best-fit, and worst-fit algorithms have different fragmentation characteristics over time.
• Buddy allocators reduce external fragmentation by only allocating blocks in power-of-two sizes, but can suffer from internal fragmentation.
• Slab allocators are designed for kernel objects or fixed-size requests, virtually eliminating fragmentation for those specific sizes.
• For NPUs, stream-aware allocators that tie allocations to a computation stream's lifecycle can aggressively reuse memory and minimize fragmentation.

Garbage collection (GC) is an automatic memory management process that reclaims memory occupied by objects that are no longer in use by the program. In managed runtime environments (e.g., for ML frameworks), GC algorithms directly address fragmentation:

• Mark-and-compact collectors move live objects together to eliminate external fragmentation, creating large contiguous free spaces.
• Generational collectors (like in Java/JVM) segregate objects by age, keeping frequently accessed young objects in a densely packed space to improve locality and reduce fragmentation pressure.
• The pause times and overhead of compaction can be a significant concern for real-time inference workloads on NPUs, leading to designs with manual memory management or region-based allocation.

The working set is the collection of memory pages or data blocks that a process or kernel actively uses within a specific time interval. Its relationship to fragmentation is indirect but critical:

• If the working set size exceeds the available contiguous physical memory due to fragmentation, it can trigger severe performance penalties like constant paging (in virtual memory systems) or allocation failures (in constrained NPU memory).
• Memory compaction (a defragmentation technique) aims to shrink the physical footprint of the working set by coalescing free space, allowing the active data to reside in fewer, contiguous pages.
• Understanding the working set is essential for sizing NPU memory pools and scratchpad allocations to avoid operating near capacity where fragmentation effects are most severe.

These are the two fundamental categories of memory fragmentation:

• External Fragmentation: Occurs when free memory is scattered as small, non-contiguous blocks between allocated blocks. Total free memory may be sufficient for a request, but no single free block is large enough. This is the classic problem addressed by memory pools and compactors.
• Internal Fragmentation: Occurs when an allocated block of memory is larger than the requested size. The unused memory inside the allocated block is wasted. This is common with fixed-size allocators (like a buddy system) or due to memory alignment requirements. The trade-off between internal and external fragmentation is a key design consideration for NPU memory managers.